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

Instructor Sepehr Assadi
Credits 4 units
Schedule Tuesdays and Thursdays, 2:00 PM - 3:20PM in RWH-105 (Richard Weeks Hall; Busch campus) -- the class will be online in January (see Canvas).
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

Important Note: Following Rutgers's response to recent surge of COVID-19 cases, all in-person instructions will temporarily convert to remote classes through Sunday, January 30, 2022. Please see Canvas for more information.

Lecture: The information on teaching assistants will be published soon.

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/18 Introduction and Course Policy, Intro to Algorithm Design [Chap 0] -- HW0 release
2 Thu 01/20 Algorithm Design and Asymptotic Analysis [Chap 0]
3 Tue 01/25 Proof by Induction, Recursions [Appendix I], [Chap 1] -- HW0 due , HW1 release
4 Thu 01/27 Divide and Conquer, Merge Sort [Appendix I], [Chap 1]
5 Tue 02/01 Solving Recurrences, Quick Sort [Chap 1]
6 Thu 02/03 Basics of Probability, Randomized Quick Sort [Discrete Probability] [Nuts and Bolts]
7 Tue 02/08 Hashing, Hash Functions [Hashing] -- HW1 due , HW2 release
8 Thu 02/10 Hash Tables [Hashing]
9 Tue 02/15 Dynamic Programming: Fibonacci Numbers [Chap 3] (see also [Chap 2])
10 Thu 02/17 Dynamic Programming: Knapsack [Chap 3] (see also [Chap 2])
11 Tue 02/22 Dynamic Programming: Longest Increasing Subsequence [Chap 3] (see also [Chap 2]) -- HW2 due
* Thu 02/24 Mid-term Exam 1 Online take-home exam
12 Tue 03/01 Greedy Algorithms: Job Scheduling [Chap 4]
13 Thu 03/03 Greedy Algorithms: Maximum Disjoint Intervals [Chap 4]
14 Tue 03/08 Intro to Graph Algorithms, Graph Reductions [Chap5] -- HW3 release
15 Thu 03/10 Graph Search: Depth-First-Search and Breadth-First-Search [Chap5]
* Tue 03/15 No Class: Spring Recess
* Thu 03/17 No Class: Spring Recess
16 Tue 03/22 Graph Search: Depth-First-Search and Breadth-First-Search [Chap5] -- HW4 release
17 Thu 03/24 Minimum Spanning Tree: The Generic Algorithm [Chap 7] -- HW3 due* (the deadline is on Thursday instead)
18 Tue 03/29 Minimum Spanning Tree: Kruskal's and Prim's Algorithms [Chap 7]
19 Thu 03/31 Shortest Path: Bellman-Ford Algorithm [Chap 7]
20 Tue 04/05 Shortest Path: Dijkstra's Algorithm [Chap 8] -- HW4 due
* Thu 04/07 Mid-term Exam 2 Online take-home exam
21 Tue 04/12 Introduction to Network Flow [Chap 10.1]
22 Thu 04/14 Network Flow Applications: Bipartite Matching [Chap 11]
23 Tue 04/19 Intro to P vs NP [Chap 12] -- HW5 released
24 Thu 04/21 NP-Completeness and Reductions [Chap 12]
25 Tue 04/26 NP-Hardness Reductions [Chap 12]
27 Thu 04/28 NP-Hardness Reductions [Chap 12]
* Tue 05/03 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 “[CS344S22] ?” (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

In order to protect the health and well-being of all members of the University community, masks must be worn by all persons on campus when in the presence of others (within six feet) and in buildings in non-private enclosed settings (e.g., common workspaces, workstations, meeting rooms, classrooms, etc.). Masks must be worn during class meetings; any student not wearing a mask will be asked to leave.

Masks should conform to CDC guidelines and should completely cover the nose and mouth.

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