**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.

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