CSc 22000–Spring 2016

The City College of CUNY
Department of Computer Science

Instructor: Prof. Nelly Fazio
Lectures: T/Th, 11:00am–12:15pm, NAC-5126
Office hours: Thursdays, 1:30–2:30pm (and by appointment), SH-279
Email: fazio AT cs DOT ccny DOT cuny DOT edu [Put CSc220 in Subject line]

Course Assistant: Robin Nag
Office hours: Wednesdays, 4:00–5:00pm, SH-278
Email: csc22000 AT gmail DOT com [Put LastName_Assignment#_ProblemDescription in Subject line]

[ Course Description | List of Topics | Textbook | Work Load & Grading | CUNY Academic Integrity Policy | Assignments | Labs | 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). Familiarity with C++ programming is also assumed.

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.



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.



Weekly Schedule (tentative)

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

Copyright © Nelly Fazio