back to cs312-syllabus

CS312 - Teaching Material - Fall 2004

Lectures

  1. 9/23/2004: Introduction. Basic informal definitions: Algorithms, Computational Problems, Data Structures, Computational Complexity, Problem Instances and Problem Solutions. Models of Computation and Cost criteria. Example: InsertionSort.

    Textbook: chapter 1.


  2. 9/28/2004: Mathematical Preliminaries. Polynomials, sequences, boolean expressions, binomial coefficients, logarithms, numerical conversions, length of the digital representation of an integer number in a given base.

    Textbook: 2.1.


  3. 9/30/2004: Mathematical Induction. Summations. The factorial of arbitrary integers.

    Textbook: 2.2, 2.3.


  4. 10/5/2004: Loop invariants. Analysis of algorithms. Upper bounds and least upper bounds. Asymptotic notation.

    Textbook: all 2.3 (do all relative exercises).


  5. 10/7/2004: Recurrence relations. Linear homogeneous recurrence relations. Divide and Conquer recurrence relations. Mergesort. Analysis of Mergesort.

    Textbook: 2.4.

  6. 10/12/2004: The Master Theorem. Exercises.

    Textbook: 2.4.

    10/13/2004: Midterm1

  7. 10/19/2004: Review of the midterm examination. Basic concepts and definitions about graphs and directed graphs.

    Textbook: 2.5.


  8. 10/21/2004: Trees, rooted trees and binary trees.

    Textbook: 2.6 (all).


  9. 10/26/2004: Introduction to Data Stuctures. Specification and implementation. Abstract Data Types. Use of Java interfaces. Example: array and linked list implementation of the Stack Adt in Java using generics.

    Textbook: 3.1, 3.2, 3.3.


  10. 10/28/2004: Overview of the Java Collections Framework. Queues. Circular Buffers. Priority Queues. Definition of Heap.

    Textbook: 3.5.


  11. 11/2/2004: Binary Heaps. Array representation. Building Heaps in linear time. Heapsort. Analysis of Heapsort.

    Textbook: 3.5.


  12. 11/4/2004: Representation of trees and graphs. Adjancency lists. Endogenous Trees. Tree traversals: inorder, preorder and postorder. Binary Search Trees: insertion, deletion and searches. The issue of balancing.

    Textbook: 3.4


  13. 11/9/2004: Analysis of the average height of randomly built binary search trees. AVL balanced trees. Rotations. Worst case AVL trees. Fibonacci trees.

  14. 11/16/2004: Hashing. Hash code functions and compression functions. Separate Chaining. Load factor. Hashing primitive types and Strings in Java. The Java classes HashMap and HashSet. Overriding Object methods hashCode() and equals(). Consistency issues.

    15. 11/18/2004: Midterm 2.

  15. 11/23/2004: Review of the midterm examination. Comparisons-based sorting and searching. Lower bound to the number of comparisons in the sorting problem. Graphs. DFS. Connectivity. BFS. Shortest-Path.

    Textbook: 4.1, 4.2, 4.3


  16. 11/30/2004: Overview on design techniques. Divide and Conquer. Greedy Algorithms. Minimal Spanning Trees. The Kruskal Algorithm.

    Textbook: 4.5, 5.1, 5.2, 7.1, 7.2


  17. 12/2/2004: Recursion revisited. Memoization. Dynamic Programming. The Matrix-chain multiplication problem.

    Textbook: 8.1, 8.3


Packages


Important Deadlines