COMP 3804: Design and Analysis of
Algorithms (Fall 2022)
Fall 2022
Weeklyoutline
Assignments
Problem Sets
OFFICE HOURS: Fridays 13:30  14:30 PM (No office hour
on Sept 16th)
Email: anil@scs.carleton.ca,
WWW:http://www.scs.carleton.ca/~anil
Grading Components
(Tentative)
 Course Logistics  Tutorials; Exam; Tests; Assignments.
 Illustrating D&C via finding a subarray of an array of integers that maximizes the sum.
 See Kadane's algorithm for the maximum subarray problem. Another link is here.
Week # 
Michiel's Video 
Michiel's Notes 
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 
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 
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 
Heap operations, heap sort. Introduction to Graphs. 
4 (Oct 5, 7) 
Graph
Representation Explore Depthfirstsearch DAGs, Topological Sort, and DFS 
Depthfirstsearch Directedgraphs 
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 
DFS in directed graphs 
DFS in directed graphs  forward, backward, cross and back edges in the traversal. 
6 (Oct 19, 22) 
Shortestpaths
in directed graphs Correctness of Dijkstra's algorithm 
shortestpaths correctness 
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 
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. 