Fundamental Algorithms

CSc I0600–Fall 2022

The City College of CUNY
Department of Computer Science

Instructor: 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 ]

Course Description

From the course catalog: An intensive study of advanced non-numerical programming techniques. Data representation; list, tree and string manipulation algorithms. Recursive programming. Introduction to searching and sorting. Storage management algorithms. Comparative efficiency of algorithms.

Prerequisites: CSc 220.

Textbook

Required:

Introduction to Algorithms. 3rd Edition
T. Cormen, C. Leiserson, R. Rivest, C. Stein, 2009.
ISBN-10: 0262033844
ISBN-13: 978-0262033848

Work Load & Grading

Work load
2.5 hrs/week: Class attendance
2.5 hrs/week: Readings
5.0 hrs/week: Assignments
Grading
10%: Class participation
20%: Quizzes
30%: Midterm (Oct 26) (tentative)
40%: Final (Dec 14) (tentative)

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	Aug 31	Overview. Growth of functions. Asymptotic notation. InsertionSort. Divide-and-Conquer. Examples. MergeSort.	CLRS 1–3 Review CLRS 10, 11, 12
2	Sep 7	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	Sep 14	Solving recurrences: Substitution method. Examples. Solving recurrences: Master method. Examples.	CLRS 4.3, 4.5
4	Sep 21	Sorting Algorithms: Heapsort.	CLRS 6
5	Sep 28	Sorting Algorithms: Quicksort.	CLRS 7
6	Oct 12	More on sorting: Lower bound and beyond.	CLRS 8
7	Oct 19	Balanced Search Trees: B-Trees.	CLRS 18
8	Oct 26	Midterm Exam.
9	Nov 2	Dynamic Programming (I). Example: Rod Cutting.	CLRS 15
9	Nov 9	Dynamic Programming (II). Example: Longest Common Subsequence.	CLRS 15
11	Nov 16	Greedy Algorithms. Huffman Codes.	CLRS 16
12	Nov 23	Graphs. BFS and DFS. Topological Sort. SCC.	CLRS 22
13	Nov 30	Minimum Spanning Trees.	CLRS 23
14	Dec 7	Shortest Paths: Bellman-Ford algorithm. Single-Source Shortest Paths for DAGs + Dijkstra. All-Pairs Shortest Paths: Floyd-Warshall.	CLRS 24, 25
	Dec 14	Final Exam, Dec 14, 2022, 2:00-4:30pm (tentative)

Copyright © Nelly Fazio