CS 344: Design and Analysis of Computer Algorithms -- Spring 2023

Instructor Sepehr Assadi
Credits 4 units
Schedule Tuesdays and Thursdays, 2:00 PM - 3:20PM in PHY-LH (Busch campus).
Prerequisites CS 112 Data Structures, CS 206 Introduction to Discrete Structures II
Syllabus The full course syllabus is available on here. This webpage contains the highlights of course syllabus that are potentially updated as the semester progresses.

Overview

The goal of this course is to familiarize students with basic concepts and techniques in algorithm design. The course covers mathematical induction, techniques for analyzing algorithms, sorting and searching, divide and conquer, greedy algorithms, dynamic programming, graph algorithms, and elements of the theory of NP-completeness.

Logistics

Lecture: This course has four teaching assistants.

Teaching Assistant 1: Teaching Assistant 2: Teaching Assistant 3: Teaching Assistant 4:

Important Dates

Reading

The official textbook for the course is: Homeworks and exams will be solely based on the materials presented in the class -- this includes the parts that may not necessarily be covered in the textbook.

Grading

The final grade for the course will be based on the following weights: See the syllabus for more details.

The students are expected to follow Rutgers academic integrity policy and CS Department academic integrity policy for all their work in this course. See the syllabus for more details.

Course Calendar

The schedule below the red line is tentative and subject to change. All the reading references are to Erickson's book and its supplementary materials unless stated otherwise.

# Date Topics Readings and Remarks
1 Tue 01/17 Introduction and Course Policy, Intro to Algorithm Design [Chap 0] -- HW0 release
2 Thu 01/19 Algorithm Design and Asymptotic Analysis [Chap 0]
3 Tue 01/24 Proof of Correctness and Induction [Appendix I], [Chap 1] -- HW0 due , HW1 release
4 Thu 01/26 Recursions and Recurrences [Appendix I], [Chap 1]
5 Tue 01/31 Divide and Conquer: Merge Sort, Solving Recurrences [Chap 1]
6 Thu 02/02 Divide and Conquer: Quick Sort, Randomized Quick Sort [Chap 1] [Nuts and Bolts]
7 Tue 02/07 Randomized Quick Sort, Counting Sort, Searching [Discrete Probability] -- HW1 due , HW2 release
8 Thu 02/09 Hashing, Hash Functions, Hash Tables [Hashing]
9 Tue 02/14 Dynamic Programming: Fibonacci Numbers [Chap 3] (see also [Chap 2])
10 Thu 02/16 Dynamic Programming: Knapsack [Chap 3] (see also [Chap 2])
11 Tue 02/21 Dynamic Programming: Longest Increasing Subsequence [Chap 3] (see also [Chap 2]) -- HW2 due
* Thu 02/23 Mid-term Exam 1
12 Tue 02/28 Greedy Algorithms: Unit-Weight Knapsack, Job Scheduling [Chap 4]
13 Thu 03/02 Greedy Algorithms: Maximum Disjoint Intervals [Chap 4]
14 Tue 03/07 Intro to Graph Algorithms, Graph Reductions [Chap5] -- HW3 release
15 Thu 03/09 Graph Search: Depth-First-Search and Breadth-First-Search [Chap5]
* Tue 03/14 No Class: Spring Recess
* Thu 03/16 No Class: Spring Recess
16 Tue 03/21 Graph Search: Depth-First-Search and Breadth-First-Search [Chap5] -- HW4 release
17 Thu 03/23 Minimum Spanning Tree: The Generic Algorithm [Chap 7] -- HW3 due* (the deadline is on Thursday instead)
18 Tue 03/28 Minimum Spanning Tree: Kruskal's and Prim's Algorithms [Chap 7]
19 Thu 03/30 Shortest Path: Bellman-Ford Algorithm [Chap 8]
20 Tue 04/04 Shortest Path: Dijkstra's Algorithm [Chap 8] -- HW4 due
* Thu 04/06 Mid-term Exam 2
21 Tue 04/11 Introduction to Network Flow [Chap 10.1]
22 Thu 04/13 Network Flow Applications: Bipartite Matching [Chap 11]
23 Tue 04/18 Intro to P vs NP [Chap 12] -- HW5 released
24 Thu 04/20 NP-Completeness and Reductions [Chap 12]
25 Tue 04/25 NP-Hardness Reductions [Chap 12]
27 Thu 04/27 NP-Hardness Reductions [Chap 12]
* Tue 05/02 Reading Day HW5 due
* Final Exam According to the University Schedule.

Questions?

The course has a Piazza page accessible through Canvas. If you have something to discuss directly with the Instructor (e.g., a concern, a question, or a comment) outside regular office hours, send an email with the subject “[CS344S23] ?” (replace ? with what you like to discuss) to the Instructor.

Resources on LaTeX

You can download LaTeX for free here. For the purpose of this course, you do not even need to install LaTeX and can instead use an online LaTeX editor such as Overleaf.

Two great introductory resources for LaTeX are Getting started with TeX, LaTeX, and friends by Allin Cottrell (for general purpose LaTeX) and LaTeX for Undergraduates by Jim Hefferson (for undergraduates mathematics) accompanied by the following cheatsheet (note that this document use "\( MATH \)" notation compared to the perhaps more widely used "$ MATH $" -- both are completely fine in LaTeX). You can also use this wonderful tool Detexify by Daniel Kirsch for finding the LaTeX commands of a symbol (just draw the symbol!).

If you are interested in learning more about LaTeX (beyond what is needed for this course), check the Wikibook on LaTeX and the Wikibook on LaTeX for Mathematics.

Rutgers CS Diversity and Inclusion Statement

Rutgers Computer Science Department is committed to creating a consciously anti-racist, inclusive community that welcomes diversity in various dimensions (e.g., race, national origin, gender, sexuality, disability status, class, or religious beliefs). We will not tolerate micro-aggressions and discrimination that creates a hostile atmosphere in the class and/or threatens the well-being of our students. We will continuously strive to create a safe learning environment that allows for the open exchange of ideas and cherished freedom of speech, while also ensuring equitable opportunities and respect for all of us. Our goal is to maintain an environment where students, staff, and faculty can contribute without the fear of ridicule or intolerant or offensive language.

If you witness or experience racism, discrimination micro-aggressions, or other offensive behavior, you are encouraged to bring it to the attention to the undergraduate program director and/or the department chair. You can also report it to the Bias Incident Reporting System.

COVID-19 Protocols

We will follow university guidelines when it comes to COVID-19 protocols. If you are feeling sick, or suspect you may have been exposed to COVID-19, do not come to the class. Arrangements will be made for students who are not able to attend class because of an illness or quarantine.

Open and Affordable Textbooks Program

A previous iteration of this course has received an Open and Affordable Textbooks Program Award from the Rutgers University Libraries. The OAT Program supports textbook affordability at Rutgers by encouraging courses to adopt educational materials that are freely available, available at a low cost (compared to similar courses), or part of the Rutgers University Libraries' electronic collections, and thereby free of charge to Rutgers University students. OAT program