AlgorithmsCSc 22000–Fall 2024 |
The City College of CUNY Department of Computer Science |
Instructor:
Prof. Nelly Fazio
Lectures: T/Th, 11:00am–12:15pm, NAC 4/121B
Office hours: T/Th, 12:30–1:30pm (and by appointment), SH-279
Email: nfazio AT ccny DOT cuny DOT edu
[Put CSc220 in Subject line]
[ Course Description | List of Topics | Textbook | Work Load & Grading | CUNY Academic Integrity Policy | Assignments | Weekly Schedule ]
Prerequisites: CSc 212, and (CSc 217 or EE 311).
Lecture | Date | Topic | Readings | |
1 | Aug 29 | Overview. Growth of functions. Asymptotic notation. InsertionSort. | CLRS 1, 2.1, 2.2, 3 Review CLRS 10, 11 |
|
2 | Sep 3 | Divide-and-Conquer. Examples. MergeSort. | CLRS 2.3. Appendix A | |
3 | Sep 5 | Solving recurrence: Recursion-tree method. Examples. | CLRS 4.4 | |
4 | Spe 10 | More on Divide-and-Conquer: Maximum Subarray. | CLRS 4.1 | |
5 | Sep 12 | Solving recurrences: Substitution method. Examples. | CLRS 4.3 | |
6 | Sep 17 | Solving recurrences: Master method. Examples. | CLRS 4.5 | |
7 | Sep 19 | Sorting Algorithms: Heapsort. | CLRS 6 | |
8 | Sep 24 | Sorting Algorithms: Quicksort. | CLRS 7 | |
9 | Sep 26 | More on sorting: Lower bound and beyond. | CLRS 8 | |
10 | Oct 1 | More on sorting: Lower bound and beyond. | CLRS 8 | |
11 | Oct 8 | Balanced Search Trees: Red-Black Trees (I). | Review CLRS 12 CLRS 13 |
|
12 | Oct 10 | Balanced Search Trees: Red-Black Trees (II). | CLRS 13 | |
13 | Oct 17 | Balanced Search Trees: B-Trees (I). | CLRS 18 | |
14 | Oct 22 | Balanced Search Trees: B-Trees (II). | CLRS 18 | |
15 | Oct 24 | Review | ||
16 | Oct 29 | Midterm Exam. | ||
17 | Oct 31 | Dynamic Programming (I). Example: Rod Cutting. | CLRS 15 | |
18 | Nov 5 | Dynamic Programming (II). Example: Longest Common Subsequence. | CLRS 15 | |
19 | Nov 7 | Greedy Algorithms. | CLRS 16 | |
20 | Nov 12 | More on Greedy Algorithms. Huffman Codes. | CLRS 16 | |
21 | Nov 14 | Graphs. BFS and DFS. | CLRS 22 | |
22 | Nov 19 | Topological Sort. | CLRS 22 | |
23 | Nov 21 | Strongly Connected Components. | CLRS 22 | |
24 | Nov 26 | Minimum Spanning Trees. | CLRS 23 | |
Nov 28 | No class! Thanksgiving. | |||
25 | Dec 3 | Single-Source Shortest Paths: Bellman-Ford algorithm. | CLRS 24 | |
26 | Dec 5 | Single-Source Shortest Paths for DAGs + Dijkstra. | CLRS 24 | |
27 | Dec 10 | All-Pairs Shortest Paths: Floyd-Warshall. | CLRS 25 | |
28 | Dec 12 | Review | ||
Dec 19 | Final Exam, 11:00am—12:15pm, NAC 4/121 |
Copyright © Nelly Fazio