back to cs312-syllabus

CS312 - Teaching Material - Fall 2003

Lectures

• Lecture 1, 9/25/2003.

  Basic informal definitions: Algorithms, Computational Problems, Data Structures, Computational Complexity, Problem Instances and Problem Solutions. Example: formulation of the Sorting Problem. InsertionSort.




• Lecture 2, 9/30/2003.

  Mathematical preliminaries: the Gauss formula. Analysis of InsertionSort. Discussion on the order of growth.




• Lecture 3, 10/2/2003.

  Mathematical preliminaries: generalizations of the Gauss formula. The asymptotic notation. Observations and properties. Presentation of a Java implementation of InsertionSort.




• Lecture 4, 10/7/2003.

  Finite geometric series. Asymptotic approximations. MergeSort. The MergeSort equation. The Divide and Conquer technique. Java implementation of MergeSort (the package includes also javadoc documentation).




• Lecture 5, 10/9/2003.

  Comparisons-based sorting. Decision Trees. Lower bound on the number of comparisons.




• Lecture 6, 10/14/2003.

  Approximation of sums with the method of the integral. Examples. Sorting in linear time: CountingSort.




• Lecture 7, 10/16/2003.

  SelectionSort. Exercises. Preparation to the Midterm examination.




• Midterm 1, 10/16/2003.



• Lecture 8, 10/28/2003.

  Midterm Review. Divide-and-conquer recurrence relations. The master method.




• Lecture 9, 10/30/2003.

  Recurrence relations. Master Theorem. Higher order linear recurrence relations with constant coefficients.




• Lecture 10, 11/4/2003.

  Randomized QuickSort. Average running time. The QuickSort equation. Worst-case analysis.




• Lecture 11, 11/6/2003 (reviewed).

  Heaps. HeapSort. Analysis.




• Lecture 12, 11/11/2003.

  Data Structures: specification and implementation. Notion of formal specification of Abstract Data Types (Adt's). Examples: the Stack Adt. Use of Java interfaces to define the signature of a formal specification of an Adt. Types of implementations. The Stack data structure: Java interface and an array based Java class implementation.




• Lecture 13, 11/13/2003.

  Elementary Data Structures: Stacks, Queues, Deques. Implementation techniques: arrays, circular buffers, linked lists, doubly linked lists. Priority Queues.




• Lecture 14, 11/18/2003.

  Computation of the gcd using the Euclidean Algorithm. Modular Exponentiation using the (recursive) Repeated Squaring Method. Applications: the RSA cryptosystem and the Diffie-Hellman protocol.




• Lecture 15, 11/20/2003.

  Priority Queues. Heap based implementation. Numerical Algorithms. Analysis of the performance of the Euclidean Method. Algorithms to perform arithmetic operations. Application of Newton's method to compute the inverse of a real number with additions, subtractions and multiplications.




• Lecture 16, 11/25/2003.

  A subquadratic algorithm to multiply large integers. Binary Search Trees. The BinarySearchTree data structure and a linked-node based implementation. Basic traversal algorithms: inorder, preorder and postorder.




• Lecture 17, 12/02/2003.

  Insertion and deletion in Binary Search Trees (see package online).

Important Deadlines

• Midterm 1: Tuesday, October 21, 2003.
• Midterm 2: Thursday, November 13, 2003 (takehome).


• Final Exam. Tuesday, December 9, 2003. Time: 7:30-10:00pm.