CS 344: Design and Analysis of Computer Algorithms -- Fall 2019

Instructor Sepehr Assadi
Credits 4 units
Schedule Mondays and Thursdays 12:00 PM - 1:20 PM in TIL-232 (Livingston campus)
Prerequisites CS 112 Data Structures, CS 206 Introduction to Discrete Structures II
Syllabus The full course syllabus is available on Canvas. 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 recitation sections.

Section 1: Section 2: Section 3:

Important Dates

Reading

The official textbook for the course is: For further reading: 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: The students are expected to follow Rutgers academic integrity policy for all their work in this course. See the course syllabus on Canvas for more information.

Homeworks: There will be five homeworks in the course and a tentative schedule of release and due dates are available on the course calendar. Homeworks should be done individually and students have one week to work on each homework unless stated otherwise. Homeworks must be typeset in LaTeX and submitted via Canvas by 11:59pm EST on the due date. A LaTeX template will be released with each homework (for introduction to LaTeX, see the Resources on LaTeX section). The students are allowed to submit up to two homeworks late, each with a delay of at most two days. A zero credit will be given to any homework submitted after two days past the deadline or homeworks that are submitted late even after the two allowed extensions. More information on homeworks is available in the course syllabus on Canvas.

Mid-term exams: There will be two mid-term exams during this course. The first mid-term will cover lectures 1 to 10 and the second mid-term will cover lectures 11 to 19. The mid-term exams will be will be held during scheduled class hours. The two mid-term exams will be closed-book: no textbooks, electronic devices, or cheat sheets are allowed. A missed exam draws zero credit. However, emergencies will be considered upon submitting a University-issued written verification to the Instructor.

Final exam: The final exam will be from the material covered in the entire course. This exam will be 3 hours long and will be held at the end of the semester according to the Rutgers undergraduate schedule of classes. The final exam will also be closed-book: no textbooks, electronic devices, or cheat sheets are allowed.

Participation: There is up to 5% extra credit for participation. By default your participation grade is zero. If you typically come to the lectures/recitations but you never answer questions during the lectures or the recitations, your participation grade will remain zero. Positive participation grades will be given to students that actively participate in lectures and recitations. There is however no such thing as “negative participation” which can hurt your grade — participation can only help (by giving you a small bump to your final grade). There is no formula for participation bumps and this grade will be at the discretion of the Instructor and TAs. More information is available in the course syllabus on Canvas.

Course Calendar

The schedule below the red line is tentative and subject to change. The references are all to the CLRS book unless stated otherwise.

# Date Topics Readings and Remarks
1 Thu 09/05 Introduction, Course Policy, Intro to Algorithm Design Chapter 1
2 Mon 09/09 Intro to Algorithm Design and Asymptotic Analysis Chapters 2.1, 2.2, 3
3 Thu 09/12 Proof by Induction, Intro to Sorting, Binary Search Chapters 2.1, 4.3, intro of part II -- HW1 release
4 Mon 09/16 Sorting via Divide and Conquer: Merge Sort Chapters 2.3, 4.4
5 Thu 09/19 Solving Recurrences, Quick Sort Chapters 4.5, 7.1, 7.2 -- HW1 due
6 Mon 09/23 Randomized Quick Sort, Basics of Probabilistic Analysis Chapters 5, 7.3 -- HW2 release
7 Thu 09/26 More on Randomized Quick Sort, Counting Sort, Concluding Remarks on Sorting Chapters 8.2
8 Mon 09/30 Dynamic Programming: Fibonacci Numbers, Knapsack Problem [Chap3] of Erickson's book, Chapter 15.1
9 Thu 10/03 Dynamic Programming: Longest Increasing Subsequence [Chap3] of Erickson's book, Chapters 15.2, 15.4 -- HW2 due
10 Mon 10/07 Dynamic Programming: Review [Chap3] of Erickson's book, Chapter 15.3
Thu 10/10 Mid-term Exam 1 --
11 Mon 10/14 Greedy Algorithms vs Dynamic Programming [Chap4] of Erickson's book, Chapters 16.1, 16.2 -- HW3 release
12 Thu 10/17 Greedy Algorithms: Job Scheduling, Maximum Disjoint Intervals [Chap4] of Erickson's book, Chapter 16.3
13 Mon 10/21 Intro to Graph Algorithms: Graph Reductions, Graph Search [Chap5] of Erickson's book, Part VI intro, Chapter 22.1
14 Thu 10/24 Graph Representation, Algorithms for Graph Search: DFS Chapter 22.3 -- HW3 due
15 Thu 10/28 Algorithms for Graph Search: BFS, Topological Sort Chapters 22.2 and intro of 24
16 Thu 10/31 Algorithms for Topological Sorting and Longest Path in DAGs Chapter 22.4
17 Mon 11/04 Minimum Spanning Tree: The Generic Algorithm Chapters 23.intro, 23.1, 21 (for union-find data structure)
18 Thu 11/07 Minimum Spanning Tree: Kruskal's Algorithm Chapters 23.2 -- HW4 due
19 Thu 11/11 Minimum Spanning Tree: Prim's Algorithm Chapters 23.2
Thu 11/14 Mid-term Exam 2 --
20 Mon 11/18 Practice Session --
21 Thu 11/21 Single-Source Shortest Path: Bellman-Ford Algorithm Chapters 24.intro, 24.1 -- HW5 release
22 Mon 11/25 Single-Source Shortest Path: Dijkstra's Algorithm, Network Flow: Introduction Chapter 24.3, 26.1
23 Tue 11/26 Network Flow: Applications to Bipartite Matching and Exam Scheduling Problem Chapters 26.3, and [Chap 11] of Erickson's book -- unusual time
Thu 11/28 No Class: Thanksgiving Recess --
24 Mon 12/02 Intro to P vs NP: NP-Completeness and Reductions Chapters 34.3, 34.4
25 Thu 12/05 Intro to P vs NP: NP-Hard Problems Chapter 34.5, [Chap 12] of Erickson's book -- HW5 due
26 Mon 12/09 Intro tto P vs NP: NP-Hardness Reductions Chapter 34.3
Tue 12/17 Final Exam According to the University Schedule.

Questions?

The course has a Piazza page accessible through Canvas.

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.