MET CS 566 Analysis of Algorithms

Course Calendar Summer 2003

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