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

Instructor Sepehr Assadi
Credits 4 units
Schedule fully asynchronous -- enrolled students recieve the details for the course via 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

Lecture: This course has three teaching assistants.

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

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.

# Week of Topics Readings and Remarks
1 Jan 18 Introduction and Course Policy, Intro to Algorithm Design and Asymptotic Analysis [Chap 0] -- HW0 release
2 Jan 25 Proof by Induction, Recursion, Divide and Conquer, Merge Sort [Appendix I], [Chap 1] -- HW0 due , HW1 release
3 Feb 1 Solving Recurrences, Quick Sort, Randomized Quick Sort [Chap 1] [Discrete Probability] [Nuts and Bolts]
4 Feb 8 Hashing, Hash Functions, Hash Tables [Hashing] -- HW1 due , HW2 release
5 Feb 15 Dynamic Programming: Fibonacci Numbers, Knapsack, Longest Increasing Subsequence [Chap 3] (see also [Chap 2])
6 Feb 22 Greedy Algorithms: Unit-weight Knapsack, Job Scheduling, Maximum Disjoint Intervals [Chap 4] -- HW2 due
Mid-term Exam 1 Monday, March 01
7 Mar 1 Intro to Graph Algorithms, Graph Reductions [Chap5]
8 Mar 8 Graph Search: DFS & BFS, Topological Sort, Longest Path in DAGs [Chap5] [Chap 6.2-6.4] -- HW3 release
Mar 15 No Class: Spring Recess
9 Mar 22 Minimum Spanning Tree: The Generic Algorithm, Kruskal's and Prim's Algorithms [Chap 7] -- HW3 due , HW4 release
10 Mar 29 Single-Source Shortest Path: Bellman-Ford Algorithm, Dijkstra's Algorithm [Chap 8]
11 Apr 05 Network Flow: Introduction and Applications [Chap 10.1] [Chap 11] -- HW4 due
Mid-term Exam 2 Monday, April 12
12 Apr 12 Bipartite Matching: The Auction Algorithm (optional lecture)
13 Apr 19 Intro to P vs NP: NP-Completeness and Reductions [Chap 12] -- HW5 released
14 Apr 26 Intro to P vs NP: NP-Hardness Reductions [Chap 12]
May 03 Last day of classes 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 “[CS344S21] ?” (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 A Short Introduction to LaTeX 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.

Open and Affordable Textbooks Program

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. As a student in this course, you will be asked to provide feedback on this initiative at the end of the semester. OAT program