Algorithms

CSc 22000–Fall 2026

 The City College of CUNY
Department of Computer Science

Instructor: Prof. Nelly Fazio
Lectures: T/Th, 11:00am–12:15pm, Shepard 381
Office hours: Tuesdays/Thursdays, 12:30–1:30pm (and by appointment), NAC 8/201
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 ]

Course Description

From the course catalog: Measuring algorithmic complexity (O-Notation); searching and sorting algorithms and their complexity; tree and graph algorithms and their complexity; classes of algorithms, such as divide-and-conquer, backtracking, greedy, probabilistic, etc. Computational complexity; the classes P and NP.

Prerequisites: CSc 212, and (CSc 217 or EE 311).

Major Topics Covered in the Course

Growth of functions. Divide-and-Conquer algorithms. Master theorem. Sorting algorithms. Advanced data structures (e.g., red-black trees, B-trees, splay trees). Dynamic programming. Greedy algorithms. Graph algorithms (e.g., BFS/DFS, shortest paths, MST, max-flow). NP-completeness. Additional topics: Amortized analysis, Fibonacci heaps, number-theoretic algorithms, and basic approximation algorithms.

Textbook

Required:

Work Load & Grading

NOTE: There will be NO make-up or substitute exams

CUNY Academic Integrity Policy

Cheating will not be tolerated. If you cheat, you risk losing your position as a student in the department and the college. CUNY policy on academic integrity can be found here. Failure to understand and follow these rules will constitute cheating, and will be dealt with as per university guidelines.

Assignments

Posted on blackboard.

Weekly Schedule (tentative)

Introduction to Dynamic Programming (I).
Lecture Date Topic Readings
1 Sep 1 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 8 Solving recurrence: Recursion-tree method. Examples. CLRS 4.4
4 Sep 10 More on Divide-and-Conquer: Maximum Subarray. CLRS 4.1
5 Sep 15 Solving recurrences: Substitution method. Examples. CLRS 4.3
6 Sep 17 Solving recurrences: Master method. Examples. CLRS 4.5
7 Sep 22 Sorting Algorithms: Heapsort. CLRS 6
8 Sep 24 Sorting Algorithms: Quicksort. CLRS 7
9 Sep 29 More on sorting: Lower bound and beyond. CLRS 8
10 Oct 1 More on sorting: Lower bound and beyond. CLRS 8
11 Oct 6 Balanced Search Trees: Red-Black Trees (I). Review CLRS 12
CLRS 13
12 Oct 8 Balanced Search Trees: Red-Black Trees (II). CLRS 13
13 Oct 15 Examples of Insert Operation in Red-Black Trees.  
14 Oct 20 Balanced Search Trees: B-Trees (I). CLRS 18
15 Oct 22 Balanced Search Trees: B-Trees (II). CLRS 18
16 Oct 27 Review  
17 Oct 29 Midterm Exam.  
18 Nov 3 Dynamic Programming (II). Example: Rod Cutting. CLRS 15
19 Nov 5 Dynamic Programming (III). Example: Longest Common Subsequence. CLRS 15
20 Nov 10 Greedy Algorithms. Huffman Codes. CLRS 16
21 Nov 12 Graphs. BFS and DFS. CLRS 22
22 Nov 17 Topological Sort. CLRS 22
23 Nov 19 Strongly Connected Components. CLRS 22
24 Nov 24 Minimum Spanning Trees. CLRS 23
25 Dec 1 Single-Source Shortest Paths: Bellman-Ford algorithm. CLRS 24
26 Dec 3 Single-Source Shortest Paths for DAGs + Dijkstra. CLRS 24
27 Dec 8 All-Pairs Shortest Paths: Floyd-Warshall.
Transitive closure of a graph. 		CLRS 25
28 Dec 10 Review
 
Dec 17 Final Exam, 11:00am—12:15pm

Copyright © Nelly Fazio