Computer Science
0

# CSC 220 - Syllabus

The City College of New York • Grove School of Engineering • Computer Science Department • Course Syllabus

 Course number CSc 22000 Course name Algorithms Credits & hours 3 cr., 3 hr. Course coordinator Prof. Peter Brass

Textbook, title, author, and year

• No required textbook; note-taking required; recommend buy a used copy of, e.g., the Cormen-Rivest-Leiserson book; but all algorithms textbook since the 1990s are similar
• Other supplemental materials: wikipedia pages exist for all algorithms discussed in this class, and are recommended. Do not rely on code published in online; it is frequently bad

Specific course information

• Algorithms, their analysis and implementations. Asymptotic Analysis (O-Notation) and Recurrence Relations as applied to the worst-case runtime of algorithms. Implementation projects done individually, with test code provided; midterm and final exams.
• Prereq.: CSc 21200
• Required course

Specific goals for the course and Relationship to student outcomes

 1 2 3 4 5 6 a. the student acquires knowledge of how to specify and determine algorithm behavior (worst-case runtime, expected runtime of randomized algorithms; Asymptotic Analysis with O and Omega; Analysis of Recursions) R P b. the student acquires knowledge of how to compare the advantages and limitations of distinct algorithms that perform the same task (compare sorting algorithms: bubble-, insertion-, merge-, heap-, quick-, radixsort; compare minimum spanning tree algorithms: Prim's and Kruskal's Algorithm; compare BFS and DFS) R P c. the student acquires knowledge of some classes of algorithmic paradigms, e.g., divide-and-conquer, randomized, greedy, use of data structures, etc.(mergesort for divide-and-conquer, quicksort for randomized, heapsort and Prim's algorithm for use of data structures, Kruskal's algorithm for greedy) R P
 I - introductory-level; R - reinforced-level; P - program-level

Brief list of topics to be covered

 Seq. Topics 1 Algorithms and Problems: sorting; Introduction O-Notation; bubblesort; insertion sort 2 Divide-and-Conquer; Mergesort; Analysis of Recursions 3 Randomized Algorithms; Quicksort; Analysis of Expected Runtime 4 Data Structures; Heapsort 5 Lower Bound: Decision Tree Bound for Comparison-Based Sorting 6 Radix Sort: Linear Time Sorting that is not Comparison-Based 7 Search Trees: Basic Find, Insert, and Delete; Rotations 8 Height-Balanced Search Trees; Analysis and Rebalancing Algorithm 9 Midterm Preparation, Review, and Midterm Exam 10 Graph exploration, DFS and BFS 11 Shortest Paths; Dijkstra's Algorithm 12 Minimum Spanning Trees; Prim's and Kruskal's Algorithm 13 Maximum Flow; Ford-Fulkerson algorithm, Max-Flow-Min-Cut-Algorithm 14 Dynamic Programming Algorithms 15 Arithmetic on Long Integers; Karatsuba-Ofen Algorithm 16 String Matching; Knuth-Morris-Pratt Algorithm 17 Complexity Classes P, NP; NP-completeness; SAT Problem is NP-Complete 18 Final Exam Preparation; Review; Final Exam