Algorithms

CSc 22000–Spring 2020

The City College of CUNY
Department of Computer Science

Instructor: Prof. Nelly Fazio
Lectures: T/Th, 11:00am–12:15pm, NAC-6113
Office hours: Tuesdays, 1:00–2:00pm (and by appointment), SH-279
Email: fazio AT cs DOT 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)

Lecture Date Topic Readings
1 Jan 28 Overview. Growth of functions. Asymptotic notation. InsertionSort. CLRS 1, 2.1, 2.2, 3
Review CLRS 10, 11
2 Jan 30 Divide-and-Conquer. Examples. MergeSort.
Solving recurrence: Recursion-tree method. Examples.
CLRS 2.3, 4.4. Appendix A
3 Feb 4 More on Divide-and-Conquer: Maximum Subarray. Matrix multiplication.
Solving recurrences: Substitution method. Examples.
CLRS 4.1–4.3
4 Feb 6 Solving recurrences: Master method. Examples. CLRS 4.5
5 Feb 11 Sorting Algorithms: Heapsort. CLRS 6
6 Feb 13 Sorting Algorithms: Quicksort. CLRS 7
7 Feb 18 More on sorting: Lower bound and beyond.
CLRS 8
8 Feb 20 Balanced Search Trees: Red-Black Trees (I). Review CLRS 12
CLRS 13
9 Feb 25 Balanced Search Trees: Red-Black Trees (II). CLRS 13
10 Feb 27 Balanced Search Trees: B-Trees (I). CLRS 18
11 Mar 3 Balanced Search Trees: B-Trees (II). CLRS 18
12 Mar 5 Dynamic Programming (I). Example: Rod Cutting. CLRS 15
13 Mar 10 Dynamic Programming (II). Example: Matrix chain multiplication. CLRS 15
14 Mar 12 Dynamic Programming (III). Example: Longest Common Subsequence. CLRS 15
15 Mar 17 Midterm Exam.  
16 Mar 19 Greedy Algorithms. CLRS 16
17 Mar 24 Greedy Algorithms. Huffman Codes. CLRS 16
18 Mar 26 Graphs. BFS and DFS. CLRS 22
19 Mar 31 Topological Sort. SCC. CLRS 22
20 Apr 2 Minimum Spanning Trees. CLRS 23
  Nov 7 No class! Wednesday schedule  
  Nov 9 No class! Spring recess  
  Nov 14 No class! Spring recess  
  Nov 16 No class! Spring recess  
21 Apr 21 Advanced Data Structures: Fibonacci Heaps. CLRS 19
22 Apr 23 Max-Flow. CLRS 26
23 Apr 28 String Matching. CLRS 32
24 Apr 30 Single-Source Shortest Paths: Bellman-Ford algorithm. CLRS 24
25 May 5 Single-Source Shortest Paths for DAGs + Dijkstra. CLRS 24
26 May 7 All-Pairs Shortest Paths: Floyd-Warshall. CLRS 25
27 May 12 NP-Completeness.
CLRS 34
28 May 14 NP-Completeness.
CLRS 34
May 21 Final Exam, 10:30am—12:45pm, Room NAC-6113

Copyright © Nelly Fazio