|| fully asynchronous -- enrolled students recieve the details for the course via Canvas.
||CS 112 Data Structures, CS 206 Introduction to Discrete Structures II
||The full course syllabus is available on here.
This webpage contains the highlights of course syllabus that are potentially updated as the semester progresses.
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.
- Instructor: Sepehr Assadi
- Instructor Email: firstname.lastname@example.org
- Lecture Schedule: fully asynchronous on a week-by-week basis
- Office hours: Thursdays 8:00 PM to 9:00 PM and Fridays 9:00 AM to 10:00 AM (on Zoom)
(the two office hours of each week
cover the same topics and are intended to cover different time zones)
This course has three teaching assistants.
Teaching Assistant 1:
Teaching Assistant 2:
- Teaching Assistant: Shuchang Liu
- Teaching Assistant Email: email@example.com
- Office Hours: Mondays 11:00am to 12:00noon and Wednesdays 11:00am to 12:00noon (on Zoom)
Teaching Assistant 3:
- Teaching Assistant: Vihan Shah
- Teaching Assistant Email: firstname.lastname@example.org
- Office Hours: Tuesdays 5:00pm to 6:00pm and Fridays 3:00pm to 4:00pm (on Zoom)
- Teaching Assistant: Janani Sundaresan
- Teaching Assistant Email: email@example.com
- Office Hours: Tuesdays 8:00pm to 9:00pm and Wednesdays 3:00pm to 4:00pm (on Zoom)
- Mid-term exam 1: Monday 03/01 (24-hour take-home exam)
- Mid-term exam 2: Monday 04/12 (24-hour take-home exam)
- Final exam: TBA (according to the University schedule)
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.
- Jeff Erickson: Algorithms, © Copyright 2019 Jeff Erickson. The electronic version is freely available on this webpage.
The final grade for the course will be based on the following weights:
- 25% Quizzes (weekly for ~2% each)
- 25% Homeworks (5 for 5% each + a "homework 0" with 2% bonus credit)
- 20% Mid-term exams (2 for 10% each)
- 30% Final exam
- +10% Bonus credit (at the discretion of the Instructor/TAs)
See the syllabus
for more details.
The students are expected to follow Rutgers academic integrity policy
CS Department academic integrity policy
for all their work in this course.
See the syllabus
for more details.
The schedule below the red line
and subject to change.
All the reading references are to Erickson's book and its supplementary materials unless stated otherwise.
||Readings and Remarks
|| Jan 18
|| Introduction and Course Policy, Intro to Algorithm Design and Asymptotic Analysis
|| [Chap 0] -- HW0 release
|| Jan 25
|| Proof by Induction, Recursion, Divide and Conquer, Merge Sort
-- HW0 due , HW1 release
|| Feb 1
|| Solving Recurrences, Quick Sort, Randomized Quick Sort
[Nuts and Bolts]
|| Feb 8
|| Hashing, Hash Functions, Hash Tables
-- HW1 due , HW2 release
|| Feb 15
|| Dynamic Programming: Fibonacci Numbers, Knapsack, Longest Increasing Subsequence
|| [Chap 3] (see also [Chap 2])
|| Feb 22
|| Greedy Algorithms: Unit-weight Knapsack, Job Scheduling, Maximum Disjoint Intervals
-- HW2 due
|| Mid-term Exam 1
|| Monday, March 01
|| Mar 1
|| Intro to Graph Algorithms, Graph Reductions
|| Mar 8
|| Graph Search: DFS & BFS, Topological Sort, Longest Path in DAGs
-- HW3 release
|| Mar 15
|| No Class: Spring Recess
|| Mar 22
|| Minimum Spanning Tree: The Generic Algorithm, Kruskal's and Prim's Algorithms
-- HW3 due , HW4 release
|| Mar 29
|| Single-Source Shortest Path: Bellman-Ford Algorithm, Dijkstra's Algorithm
|| [Chap 8]
|| Apr 05
|| Network Flow: Introduction and Applications
-- HW4 due
|| Mid-term Exam 2
|| Monday, April 12
|| Apr 12
|| Bipartite Matching: The Auction Algorithm (optional lecture)
|| Apr 19
|| Intro to P vs NP: NP-Completeness and Reductions
-- HW5 released
|| Apr 26
|| Intro to P vs NP: NP-Hardness Reductions
|| [Chap 12]
|| May 03
|| Last day of classes
|| Final Exam
|| According to the University Schedule.
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.
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
the Wikibook on LaTeX for Mathematics
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.