COMP 3804: Design and Analysis of
Algorithms (Fall 2021)
OFFICE HOURS: Tuesday and Thursday
14:3515:55 Online over zoom (link provided in
Brightspace).
Email: anil@scs.carleton.ca,
WWW:http://www.scs.carleton.ca/~anil
The following is the schedule for 4
Assignments, 2 Tests, and the Final Exam:
Posted On 
Due Date 
% of Total Marks 

BACKGROUND
Quiz 1 Quiz 2 
Sept 9 
Never 
Make sure you know this
material  this is minimum background required to understand
the material in this course. 

A1 PDFFile LaTeXFile 
Sep 9 
Sep 24 
10% 

A2 PDFFile LaTeX File (Figures: dfsundirected, gridgraph and tree) 
Sep 23 
Oct 8 
10%  
A3 PDFFile LaTeXFile 
Oct 22 
Nov 12 
10%  
A4 PDFFile LaTeXFile 
Nov 18 
Dec 2 
10%  
Test  1 
Oct 14 
Oct 14  15% (14:3515:55 PM on
Thursday October 14th) 

Test 2 
Nov 25 
Nov 25  15% (14:3515:55 PM on Thursday November 25th)  
Final Exam 
Please check exam schedule 
30% 
Week # 
Michiel's Video 
Michiel's Notes 
Practice Problem Set/ Assignment Solutions during office hour. 
Topics + Additional pointers 
0 (Sep 9) 
Introductory
Remarks 
Introduction 
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
1(MergeSort Analysis) Part 2(Multiplying Integers) Part 3(Faster Multiplication) Part 4 (Recursion Tree) 
DivideandConquer Recursion Tree 
Set
 I SetII 
DivideandConquer Technique Analyzing mergesort, multiplication of two nbit numbers, matrix multiplication. Additional notes on analyzing recurrences including substitution method. See Chapter 1 (Section 1.4 and 1.5) for more details Also, see the following link for Master Method simulator: https://www.nayuki.io/page/mastertheoremsolverjavascript 
2 (Sept 21, 23) 
Deterministic
Selection Randomized Selection+ Heaps 
Selection (deterministic) Selection (randomized) Heaps 
SetIII 
Group of 5 deterministic selection algorithm. Randomized selection algorithm. What are Heaps? 
3 (Sept 28, 30) 
Operations
on Heaps More on Heaps + Graphs 
Introduction to Graphs and Graph Exploration 
SetIII continued + Assignment 1 Solutions 
Heap operations, heap sort. Introduction to Graphs. 
4 (Oct 5, 7) 
Graph
Representation Explore Depthfirstsearch DAGs, Topological Sort, and DFS 
Depthfirstsearch Directedgraphs 
SetIV 
Graph representation, Graph exploration, tree and back edges, depthfirst search traversal, finding connected components using explore and ccnumber Is G bipartite? Directed graphs. Acyclic directed graphs (DAGs) Topological Sorting 
5 (Oct 12, 14) 
DFS
in directed graphs TEST1 (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:3515:55 via Brightspace system on October 14th. The syllabus consists of all the material covered in Weeks 15 (inclusive), Assignments and the Problem Sets. This includes all the lectures from Sept 9  Oct 12th (inclusive). 
6 (Oct 19, 22) 
Shortestpaths
in directed graphs Correctness of Dijkstra's algorithm 
shortestpaths correctness 
Test1 Solutions SSSP Examples BFS+ SetV 
Shortest paths in DAGs Dijsktra's singlesource shortest path algorithm for general directed graphs 
Oct 2529 
FALL BREAK 
NO OFFICE HOURS  
7 (Nov 2, 4) 
UnionFind
DS + Kruskal's MST algorithm Kruskal and Prim's MST algorithms 
unionfind data structure + MST Prim's MST algorithms Additional Notes on MSTs 
NO OFFICE HOURS on November 4th 
Unionfind data structure Minimum spanning tree algorithms  Kruskal and Prim's Algorithm. Analysis of Kruskal's algorithm using unionfind DS 
8 (Nov 9, 11) 
Prim's
MST Analysis & Introduction to Dynamic Programming I 
Dynamic Programming 
Analysis of Prim's using priority queues Revisiting shortest paths in DAGs, dynamic programming framework  structure of optimal solution, setup recurrence relation, solve recurrence bottomup. Longest paths in DAGs 

9 (Nov 16, 18) 
Dynamic
Programming II Dynamic Programming III 
Longest increasing sequence,
matrixchain multiplication, longestcommon sequence,
allpairs shortest paths  FloydWarshall algorithm. Longest
paths in graphs  optimal substructure property? 

10 (Nov 23, 25) 
Decision
Problems Decision Problems using languages 
Introduction to P and NP Complexity
Classes 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, Polynomialtime reductions. 

11 (Nov 30, Dec 2) 
Polynomialtime
reductions NPCompleteness 
Polynomialtime reductions NPComplete Problems 
Definition, Clique to Independent set, Clique
to Vertex cover, 3SAT to Independent set. NPHard and NPComplete Problems. How to show a problem is NPComplete? 

12 (Dec 7, 9) 
Hardness
Reductions CircuitSAT is NPComplete 
More Hardness Reductions CircuitSAT problem 
3SAT, Clique, 01 Integer Linear Programs are
NPComplete. Sketch of the proof of CircuitSAT is NPComplete. 