Fall 2017 Schedule

This is the current framework. It is also the basis for changes, that will
appear as the course progresses. We follow the order of topics in the
text, with some changes!

The assigned readings are usually from the
course text.

The days of tests are marked by [T]. Version of October 28.

. .

Week |
Date |
Topics |
Readings (Textbook sections) |

1 |
Aug. 30 | Administration; Review of discrete math. | Course website; Appendices A,B,C. |

2 |
Sept. 6 | [T] Asymptotic notation. Proof methods; Binary search (as example of analysis and proof) | Chapters 3, 1, 2.1-2 |

3 |
Sept. 13 | Algorithms: Insertion sort, Randomized algorithms | 2.1--2, 5.1--3 5.4.4 |

4 |
Sept. 20 | [T] Recurrences. Sorting: lower bound; mergesort. | 4.3--5; 8.1; 2.3 |

5 |
Sept. 27 | heaps & heapsort; QuickSort. | 6, 7.1--2, 7.4 |

6 |
Oct. 4 | [T] Selection: QuickSelect; Binary Search Trees I; | 9; 10; 12.1 |

7 |
Oct. 11 | Binary search trees II --- their shapes and operations. | 10.4, 12, to page 295. |

8 |
Oct. 25 | [T] Dynamic programming | Chapter 15. |

9 |
Nov. 1 | Graph representations; Searches in Graphs (BFS,DFS). | Chapter 22.1--3 . |

10 |
Nov. 8 | [T] Depth-First-Search (DFS); Disjoint set ADT; | 22.3--5, Chapter 21. |

11 |
Nov. 15 | Minimum Spanning Trees; Shortest Paths I. | Ch. 23; Ch. 24: pp.643--650; 24.2--3. |

12 |
Nov. 29 | [T] Shortest paths in graphs II. | 24.1--3,5; 25.1--2 |

13 |
Dec. 6 | Cont: Shortest paths. Graph maximum-flow problems; | 25.1--2, 26.1--3. |

14 |
Dec. 13 | [F] Introductory complexity; NP-completeness. | 34.1--3 |