back to cs312-syllabus

CS312 - Teaching Materials - Fall 2010

Lectures

1. 9/27/10: Presentation of the course. Basic concepts and definitions.

   [ slides | printable slides ]




2. 9/29/10: Asymptotic Notation.



3. 10/4/10: Summation formulas. Loop invariants. SelectionSort revisited. Proof of correctness and analysis of the computational complexity. Logarithms.



4. 10/6/10: Length of the representation of integer numbers. Approximation of summations: the method of the integral. The factorial of arbitrary integers: importance of the cost criterion in the model of computation.

   [ slides (revised 10/6/10) | printable slides (revised 10/6/10)]




5. 10/11/10: Loop Invariants: exercises 19, 20, page 40. Horner's algorithm to evaluate a polynomial on a point. Design Techniques: the Divide-and-Conquer method. MergeSort. Direct solution to the MergeSort equation.

   [ slides | printable slides ]




6. 10/13/10: Recurrence relations of the Divide-and-Conquer type. Linear Recurrence relations of the first order. Master Method.

   Recommended Exercises:

   • Study all class notes including the last part: exponentiation, the repeated squaring method and the discussion over cost criteria.
   • From the textbook: 21, page 20, 13-20, page 52, 13-29, page 65.



7. 10/18/10: Integral powers of a number. The Repeated Squaring Method. Discussion over the cost criteria. Exercises on the master method and on linear recurrence relations of the first order.



8. 10/20/10: Exercises on the analysis of nested for-loop statements.



9. 10/25/10: MT1.



10. 10/27/10: Review of MT1.



11. 11/1/10: Preparation to MT1 Makeup. Fibonacci numbers. Recursive memoized solution. Solving second-order homogeneous recurrence relations with constant coefficients.



12. 11/3/10: MT1 Makeup.



13. 11/8/10: Review of MT1 Makeup (statistics of the results). Introduction to Data Structures (chapter 3). Stacks: Adt specification and array implementation.

    Assignment: Study the Linked List implementation of a Stack.




14. 11/10/10: Queues and Priority Queues. Heaps.

    Assignment: study package priorityq.




15. 11/15/10: Priority Queues. Introduction to graphs. The single source multiple destination shortest path problem. Sketch of the Dijkstra Algorithm. Second midterm announced.



16. 11/17/10: Indirect Heaps. Graph representations: adjacency matrices and adjacency lists. Implementation of the Dijkstra algorithm using indirect heaps.



17. 11/22/10: Partitions and Union-Find Data Structures. Minimal Spanning Trees and the Kruskal Algorithm.



18. 11/24/10: MT2.

    Recommended Exercises: page 148-149, all; page 161-162, 10, 11; page 163-164: 3.12, 3.15; page 282-283: all; page 301-302: 5, 6, 7, 8, 10, 11.




19. 11/29/10: Review of MT2 (see MT2 results). Introduction to Dynamic Programming: the "matrix chain multiplication" problem.

    [ slides | printable slides ]




20. 12/1/10: The "matrix chain multiplication" problem and the Floyd and Warshall algorithm. Binary Search Trees. Preparation to the final exam.

Announcements

1. 10/12/2010: MT1 will take place on Wednesday, 10/20/10. Postponed to Monday 10/25/10. Topics (notes from the instructor + the first two chapters of the textbook, except Section 2.5):
   • The asymptotic notation.
   • Loop invariants and summation formulas: the analysis of iterative (for-loop, while-loop) statements.
   • Divide-and-Conquer. First-order linear recurrence relations and divide-and-conquer recurrence relations. The master method. Analysis of divide-and-conquer recursive algorithms.

   10/16/10: Recommended Exercises:

   • Study all class notes including the last part: exponentiation, the repeated squaring method and the discussion over cost criteria.
   • From the textbook: 21, page 20, 13-20, page 52, 13-29, page 65.
   
   
2. 10/28/2010: MT1 Makeup will take place on Wednesday, 11/3/2010.


3. 11/15/2010: MT2 will take place on Wednesday, 11/24/2010.

   Topics (chapters 2, 3, 7.2, 7.4):

   • MT1 topics.
   • Data Structures: Stacks, Queues, Linked Lists, Priority Queues, Binary Heaps and Indirect Heaps, Heapsort, Binary Search Trees, Disjoint Sets.
   • Shortest Paths on digraphs and the Dijkstra Algorithm.
   • Minimal Spanning Trees and the Kruskal Algorithm.

Downloads

1. Sample MT1.
2. priorityq.
3. Trees.
4. Graphs Algorithms (updated Nov 23, 2010) (Dijkstra and Kruskal algorithms).

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.