back to cs312-syllabus

CS312 - Teaching Material - Spring 2006

Lectures

1. 3/27/06: Generalities on computational problems, models of computation and algorithms. The sorting problem. Decision Trees. Lower bound to the number of comparisons in the comparisons-based sorting problem.



2. 3/29/06: Loop invariants. SelectionSort. Proof of correctness and analysis of the number of comparisons as a function of the length of the array.



3. 4/3/06: Asymptotic notation.



4. 4/5/06: Summation formulae. Binary representation of integers. Logarithms. Length of the binary representation of an integer.



5. 4/10/06: Geometric sums. Approximating sums with integrals. The Divide-and-Conquer design technique. MegeSort. Analysis of MergeSort.



6. 4/12/06: Approximating functions through the Least Squares (LS) method. Divide-and-Conquer recurrence relations. The Master Theorem.



7. 4/17/06: Review of the master method. Integer powers and modular exponentiation.



8. 4/19/06: lab work.



9. 4/24/06: Graphs: basic definitions, adjacency matrix, adjacency list. Paths and circuits. Eulerian and Hamiltonian graphs. Bipartite graphs and colorings.



10. 4/26/06: DFS. Backtracking algorithms. Basic combinatorics. Generation of r-permutations and r-sequences. Combinations and combinations with repetitions. A backtracking algorithm for HC.



11. 5/1/06: Adts. Specification and implementation. Stacks, Queues, DEqueues. Array and Linked list implementation of the Stack Adt. Use of interfaces in Java. BFS.



12. 5/3/06: MT1.



13. 5/8/06: Review of MT1. Modular Exponentiation. The repeated squaring method. Applications: the RSA cryptosystem.



14. 5/10/06: Priority Queues. Heap-based implementation and its analysis. Heapsort.



15. 5/15/06: Analysis of makeheap. The Dictionary Adt. The Java Collections Framework. Classes HashSet, HashMap. Hash Tables. Overriding methods hashCode and equals. Ordered Dictionaries. Binary Search Trees. Classes TreeSet and TreeMap. Implementing interface Comparable.



16. 5/17/06: Union-Find. Path Compression.



17. 5/22/06: Trees. Greedy Programming: the Kruskal Algorithm for the determinantion of Minimal Spanning Trees (MST).



18. 5/24/06: MT2.



19. 5/31/06: Review of MT2. The principle of suboptimality. Dynamic Programming. The Matrix-chain multiplication problem. Memoization.

Announcements

• Wednesday, April 19, there will be a lab lecture under the supervision of a substitute. No office hours will be held next Tuesday and Wednesday.

Important Deadlines

1. Wednesday 5/3/2006: MT1. Sample MT
2. Wednesday 5/24/2006: MT2.
3. Monday 6/5/2006, 1:30-4:00: Final.

Packages

1. sorting.
2. backtracking.
3. priorityq.
4. balancedtrees.
5. disjointsets.

Assignments

1. hw1. Due Thursday, April 27, 2006, before class.

CSNS - Computer Science Network Services

Assignments and exams should be uploaded by the due date through the CSNS - Computer Science Network Services website. If you have never used this system before then follow the instructions for students.