back to cs312-syllabus

CS312 - Teaching Material - Spring 2004

Lectures

• Lecture 1, 3/29/2004.

  Basic informal definitions: Algorithms, Computational Problems, Data Structures, Computational Complexity, Problem Instances and Problem Solutions. Models of Computation and Cost criteria. Example: computation of the factorial of large integers.




• Lecture 2, 4/5/2004.

  Timing the execution of a method in a Java program. The Sorting Problem. InsertionSort. The Gauss formula. Analysis of InsertionSort. Discussion on the order of growth.




• Lecture 3, 4/7/2004.

  The Sieve of Eratosthenes. The factoring problem. Applications: the RSA cryptosystem. Min and Max. Linear and Binary Search.




• Lecture 4, 4/12/2004.

  Modular exponentiation.




• Lecture 5, 4/14/2004.

  Order of growth and asymptotic notation.




• Lecture 6, 4/19/2004.

  Modular Arithmetics. Computation of the GCD: the Euclidean Algorithm.




• Lecture 7, 4/21/2004.

  Mergesort. Analysis of Mergesort. Divide and Conquer algorithms.




• Lecture 8, 4/26/2004.

  Divide and Conquer recurrence relations. The master Theorem.




• Midterm 1, 4/28/2004.



• Lecture 9, 5/3/2004.

  Lower bound to the computational complexity of the (comparison-based) Sorting problem.




• Lecture 10, 5/5/2004.

  Randomized QuickSort. The QuickSort equation and its solution.




• Lecture 11, 5/10/2004.

  Heaps. Heapsort. Analysis.




• Lecture 12, 5/12/2004.

  Recursion revisited. Memoization. Introduction to Dynamic Programming. The Matrix-chain Multiplication Problem.




• Lecture 13-14 (updated 5:00pm), 5/17-19/2004.

  Data Structures. Abstract data types. Specification and Implementation. Java interfaces. Stacks, Queues: Array and Linked List implementation.




• Lecture 15, 5/24/2004.

  Priority Queues: heap-based implementation.




• Midterm 2, 5/26/2004.



• Lecture 16 (end of the course), 6/1/2004.

  Maps and Hash Tables. Binary Search Trees.

Important Deadlines

• Midterm 1: Wednesday, April 28, 2004. Material to Cover: everything in the provided lecture notes (consult also the textbook following the references in the notes). Sample of midterm 1.


• Midterm 2: Wednesday, May 26, 2004.


• Final: Monday, June 7, 2004. Time: 10:45am-1:15pm.

Packages

• largefact
• modexp
• sorting
• priorityq
• trees