CSc I0600–Spring 2022
The City College of CUNY
Department of Computer Science
Prof. Nelly Fazio
Lectures: Wednesday, 2:00–4:30pm, Online
Office hours: Mondays, 11:00am–12:00pm (and by appointment), Online
Email: fazio AT cs DOT ccny DOT cuny DOT edu [Put CScI0600 in Subject line]
[ Course Description | List of Topics | Textbook | Work Load & Grading | CUNY Academic Integrity Policy | Assignments | Weekly Schedule ]
Prerequisites: CSc 220.
|1||Feb 2||Overview. Growth of functions. Asymptotic
Divide-and-Conquer. Examples. MergeSort.
Review CLRS 10, 11, 12
|2||Feb 9|| Solving recurrence: Recursion-tree method. Examples.
More on Divide-and-Conquer: Maximum Subarray. Matrix multiplication.
|CLRS 4.1–4.2, 4.4.
Review Appendix A
|3||Feb 16|| Solving recurrences: Substitution method. Examples.
Solving recurrences: Master method. Examples.
|CLRS 4.3, 4.5|
|4||Feb 23||Sorting Algorithms: Heapsort.||CLRS 6|
|5||Mar 2||Sorting Algorithms: Quicksort.||CLRS 7|
|6||Mar 9||More on sorting: Lower bound and beyond.
|7||Mar 16||Balanced Search Trees: B-Trees.||CLRS 18|
|8||Mar 23||Dynamic Programming (I). Example: Rod Cutting.||CLRS 15|
|9||Mar 30||Midterm Exam.|
|9||Apr 6||Dynamic Programming (II). Example: Longest Common Subsequence.||CLRS 15|
|11||Apr 13||Greedy Algorithms. Huffman Codes.||CLRS 16|
|12||Apr 27||Graphs. BFS and DFS. Topological Sort. SCC.||CLRS 22|
|13||May 4||Minimum Spanning Trees.||CLRS 23|
|14||May 11||Shortest Paths: Bellman-Ford algorithm.
Single-Source Shortest Paths for DAGs + Dijkstra.
All-Pairs Shortest Paths: Floyd-Warshall.
|CLRS 24, 25|
|May 18||Final Exam, May 18, 2022, 2:00-4:30pm|
Copyright © Nelly Fazio