COMP 3804: Design and Analysis of
Algorithms (Fall 2021)
OFFICE HOURS: Tuesday and Thursday
14:35-15:55 Online over zoom (link provided in
The following is the schedule for 4
Assignments, 2 Tests, and the Final Exam:
||% of Total Marks
||Make sure you know this
material - this is minimum background required to understand
the material in this course.
(Figures: dfs-undirected, grid-graph and tree)
|Test - 1
||Oct 14||15% (14:35-15:55 PM on
Thursday October 14th)
||Nov 25||15% (14:35-15:55 PM on Thursday November 25th)|
||Please check exam schedule
||Practice Problem Set/ Assignment Solutions
during office hour.
|0 (Sep 9)
||Naive and faster methods for
computing Fibonacci numbers,
O, Omega, Theta Notation
See Chapter 1 (Section 1.3) for more details
|1 (Sep 14, 16)
Part 2(Multiplying Integers)
Part 3(Faster Multiplication)
Part 4 (Recursion Tree)
Analyzing merge-sort, multiplication of
two n-bit numbers, matrix multiplication.
Additional notes on analyzing recurrences including
See Chapter 1 (Section 1.4 and 1.5) for more details
Also, see the following link for Master Method simulator:
|2 (Sept 21, 23)
Randomized Selection+ Heaps
||Group of 5 deterministic selection algorithm.
Randomized selection algorithm.
What are Heaps?
|3 (Sept 28, 30)
More on Heaps + Graphs
|Introduction to Graphs and
|Set-III continued +
Assignment 1 Solutions
|Heap operations, heap sort.
Introduction to Graphs.
|4 (Oct 5, 7)
DAGs, Topological Sort, and DFS
||Graph representation, Graph exploration,
tree and back edges,
depth-first search traversal,
finding connected components using explore and
Is G bipartite?
Acyclic directed graphs (DAGs)
|5 (Oct 12, 14)
in directed graphs
TEST-1 (October 14th)
|DFS in directed graphs
||Assignment- 2 Solutions
||DFS in directed graphs - forward, backward,
cross and back edges in the traversal.
Test takes place during the class time slot of 14:35-15:55 via Brightspace system on October 14th. The syllabus consists of all the material covered in Weeks 1-5 (inclusive), Assignments and the Problem Sets. This includes all the lectures from Sept 9 - Oct 12th (inclusive).
|6 (Oct 19, 22)
in directed graphs
Correctness of Dijkstra's algorithm
|Shortest paths in DAGs
Dijsktra's single-source shortest path
algorithm for general directed graphs
||NO OFFICE HOURS|
|7 (Nov 2, 4)
DS + Kruskal's MST algorithm
Kruskal and Prim's MST algorithms
|union-find data structure + MST
Prim's MST algorithms
Additional Notes on MSTs
NO OFFICE HOURS on November 4th
|Union-find data structure
Minimum spanning tree algorithms - Kruskal and Prim's Algorithm.
Analysis of Kruskal's algorithm using union-find DS
|8 (Nov 9, 11)
MST Analysis &
Introduction to Dynamic Programming I
||Analysis of Prim's using priority queues
Revisiting shortest paths in DAGs, dynamic programming framework - structure of optimal solution, set-up recurrence relation, solve recurrence bottom-up.
Longest paths in DAGs
|9 (Nov 16, 18)
Dynamic Programming III
|Longest increasing sequence,
matrix-chain multiplication, longest-common sequence,
all-pairs shortest paths - Floyd-Warshall algorithm. Longest
paths in graphs - optimal substructure property?
|10 (Nov 23, 25)
Decision Problems using languages
|Introduction to P and NP Complexity
Formal definitions of decision problems, P and NP.
|Complexity classes P and NP
Decision problems - SAT, Clique, Hamiltonian Cycle, TSP, Subset Sum
P subset NP,
|11 (Nov 30, Dec 2)
|Definition, Clique to Independent set, Clique
to Vertex cover, 3SAT to Independent set.
NP-Hard and NP-Complete Problems. How to show a problem is NP-Complete?
|12 (Dec 7, 9)
Circuit-SAT is NP-Complete
|More Hardness Reductions
|3SAT, Clique, 0-1 Integer Linear Programs are
Sketch of the proof of Circuit-SAT is NP-Complete.