back to cs312-syllabus

CS312 - Teaching Material - Winter 2005

Lectures

  1. 1/3/2005: Presentation of the course. Generalities on the concepts of Algorithm, Computational Problem, Problem Instance, Problem Solution and Analysis. Example: computing the integer powers of a rational number. Programming with structures: iteration, selection and sequence.

    Textbook: chapter 1.


  2. 1/5/2005: Analysis of algorithms: models of computation and cost criteria. The Euclidean algorithm for the GCD. Basic mathematical preliminaries: polynomials, boolean expressions, logarithms, binary representation of integers, upper bound and least upper bound of a subset of real numbers.

    Textbook: chapter 2.1.


  3. 1/10/2005: Mathematical induction, geometric sums, loop invariants.

    Textbook: chapter 2.2, 2.3.


  4. 1/12/2005: Analysis of Algorithms. Asymptotic notation. Example: finding the maximum element in an array.

    Textbook: chapter 2.3


  5. 1/19/2005: More on the asymptotic notation. Analysis of special cases. Examples.

    Textbook: chapter 2.3 (all).


  6. 1/24/2005: Recurrence Relations.

    Textbook: chapter 2.4.


  7. 1/26/2005: The Sorting Problem. BubbleSort and MergeSort. Complexity analysis of the number of comparisons and data exchanges.

    Textbook: chapter 2.4.


  8. 1/31/2005: The divide-and-conquer design technique. The Master Method to solve divide-and-conquer recurrences.

    Textbook: chapter 2.4.


    9. 2/2/2005: Midterm1.

  9. 2/7/2005: Graphs.

    Textbook: chapter 2.5.


  10. 2/9/2005: Trees.

    Textbook: chapter 2.6.


  11. 2/14/2005: Data Structures. Specification and Implementation. Use of Java interfaces. The Stack Adt. Linked List implementation and Array implementation.

    Textbook: chapter 3.1, 3.2, 3.3.


  12. 2/16/2005: Queues and Priority Queues.

    Textbook: chapter 3.5.


  13. 2/21/2005: Heaps. Heap-based Priority Queues. Heapsort.

    Textbook: chapter 3.5.


  14. 2/23/2005: Binary Trees. Traversal algorithms. The "Dictionary" Adt. Binary Search Trees: insertion and deletion.

    Textbook: chapter 3.4.


  15. 2/28/2005: The Java Collections Framework. The interfaces List, Set and Map. Hash tables. The classes HashSet and HashMap. Overriding methods equals() and hashCode(). The classes TreeSet and TreeMap. Implementing interface Comparable. The classes ArrayList and LinkedList.

    16. 3/2/2005: Midterm 2.

  16. 3/7/2005: Review of the midterm examination. The Disjoint-Sets Adt.

    Textbook: chapter 3.6.


  17. 3/9/2005: Path Compression implementation of the Disjoint-Sets Adt. Course recap. Overview on design techniques: divide-and-conquer, Dynamic Programming and Greedy. An example of Greedy algorithm: Kruskal's algorithm for Minimal Spanning Trees and its implementation using the DisjointSets data structure.

    Textbook: chapter 7.2.


Packages


Important Deadlines