1: M 07/07 Administrative.
Algorithm: origins, the concept, simple examples. Correctness. Analysis. Design.
Analysis of algorithm examples: insertion sort as representative incremental design, merge sort as representative of divide and conquer.
Best, worse and average case for insertion sort; deriving and solving the recurrence relation for merge sort;
Intuitive introduction of the big-O notation in the context of finding prototypical functions for running time.
Readings: Ch.I.1-2
2: W 07/09 Asymptotic notation: lower and upper bounds.
Solving recurrences: recursion trees, substitution methods
Readings: Ch.I.3-4; handout: Mathematical Induction
3: M 07/14 Sorting: heapsort. Readings: Ch.II.6; handout: Heaps
4: W 07/16 Analysis of heapsort.
5: M 07/21 Quicksort. Readings: Ch.II.7; handout: Quicksort
6: W 07/23 Asymptotic lower bound for comparison sort.
Sorting in linear time: counting sort, radix sort, bucket sort.
Readings: Ch.II.8; handout: Lower Bound and Sorting in linear time
Medians and order statistics Readings:
Ch.II.9
7: M 07/28
Hash Tables.
Readings: Ch.III.11; handout: Hashing
Review for midterm. Overview of Sorting Algorithms
8: W 07/30 Midterm.
CHANGE!!!! Midterm will be 1 ½ hour
9: M 08/04 Binary search trees Readings: Ch.III.12
Readings: handout Search Trees
Red-Black trees. Augmenting Data
Structures. Readings: Ch.III.13,14
10: W 08/06 Dynamic programming: Assembly line scheduling.
Readings: Ch.IV.15.1, handout: Dynamic Programming, Assembly Line Example
Matrix chain multiplication. Characteristics.
Readings: Ch.IV.15.2,3
11: M 08/11 Greedy algorithms: Activity selection. Characteristics.
Huffman codes. Readings: Ch.IV.16.1-3.
Self study: Minimum spanning trees. Disjoint sets. Readings: Ch.VI.23, Ch.V.21.1
Public Key Cryptography:
Number theory fundamentals; greatest common divisor; modular arithmetic.
RSA
public key cryptosystem.
Readings: Ch.VI.23, Ch.VI.31Review for final
12: W 08/13 Final.
Return to MET CS 566 home page
Page prepared by Tanya Zlateva