COMP 3804:  Design and Analysis of Algorithms (Fall 2022)

Fall 2022 Weekly-outline     Assignments       Problem Sets

Instructor: Anil Maheshwari

Course Delivery: The course is in person. In addition to lectures, we have a tutorial this term, where a TA will solve some problems related to lecture material covered in the previous week(s) of the course. We plan to have 3 assignments, 3 tests, and a final exam.  Lectures are scheduled for Wednesdays and Fridays from 11:35 AM to 12:55 PM in ME 3275. Tutorials and 3 tests will take place on Mondays in UC182 from 14:35 to 15:55 PM.   

OFFICE HOURS: Fridays 13:30 - 14:30 PM (No office hour on Sept 16th)

E-mail: anil@scs.carleton.ca, WWW:http://www.scs.carleton.ca/~anil

Course-TA: 
 
TAs will be mainly marking assignments, tests, and conduct office hours. Tyler will hold the tutorials.

TA Office Hours are in HP 4125 and the schedule is as follows (Office hours will start in the week of September 19th):

Stephen: 14:45-15:45 Tuesdays

Ross: 10:15-11:15 Wednesdays

Tyler: 14:00-15:00 Thursdays

Course Objectives: See the undergraduate calendar listing for an official description and pre-requisites.


Objectives:
Designing algorithms, their correctness and efficiency.
How to think about abstract computation - develop algorithmic intuition - how to attack a problem algorithmically.
Algorithmic techniques - learn key techniques (greedy, divide-and-conquer, dynamic programming, LP, ..) - which technique to use for a given problem. How to compare one algorithmic solution versus another for a problem
How to express the algorithmic solution - pseudo-code - steps - analyze - argue that it is correct - essentially how will you explain your algorithmic solutions to others?

Contents (tentatively):
Introduction: Whats an Algorithm, big-O notation, recurrence relation.
Divide and Conquer: Multiplying two n-bit integers, merge-sort, Matrix Multiplication, Median, ..
Graphs: Representation, Traversals - DFS & BFS, Shortest Paths (including A* heuristic).
Greedy Algorithms: Minimum Spanning Trees, Huffman Encodings, ...
Dynamic Programming: Edit Distance, Longest Common Sequence, ...
NP-Completeness: search problems, polynomial time reductions, ideas of Cooks Theorem.
Whats Next: Brief idea on how to cope with NP-Complete problems - introduction to approximation algorithms, exhaustive search and search heuristics.

Reference Books
 
There are numerous textbooks on Algorithms and  Reference Materials

  Grading Components (Tentative)


 Posted On
 Due Date

% of Total Marks
A1
 September 19
(See Brightspace
COMP/MATH 3804 LEC)
Oct 6th

5%
A2
 October 7
(See Brightspace
COMP/MATH 3804 LEC)

Nov 10th


5% 

A3

 November 16
(see Brightspace
COMP/MATH 3804 LEC)
Dec  6th

5%

Test - 1


15% (Monday September 26, 14:35-15:55 PM in UC182)

Test - 2


15% (Monday October 31, 14:35-15:55 PM in UC 182)
Test - 3


15% (Monday November 21, 14:35-15:55 PM in UC182)
Final Exam
 Please check the exam schedule/location

40%

Final Exam is scheduled for December 20th at 9 AM.

The exam will consist of 25 Questions, where you need to provide short answers, and a Bonus problem.  These questions will cover the material for the entire term. Expect questions on Complexity Notations (O, Omega and Theta), analyzing recurrences (e.g. T(n)=3T(n/4)+O(n^2)), divide-and-conquer including finding the k-th order statistics, dfs and graph exploration of undirected and directed graphs, linearization of DAGs, single-source shortest paths - properties and Dijkstra's and Bellman-Ford algorithms, minimum spanning trees - properties and algorithms of Kruskal and Prim, Dynamic Programming Technique with its applications to numerous problems, and Complexity Theory (definitions, decision problems, polynomial-time reductions, how to show a problem is NP-Complete?, Examples of NP-Complete Problems (CIRCUIT-SAT, 3CNF-SAT, Clique, Vertex Cover, Independent Sets, Subset-Sum, Knapsack, 3 Coloring a graph, Set Cover, etc.),  the question P=NP?).

For preparation, please review the course material, assignments, tutorial problems, problems from tests, the pointers provided on the website on various topics, and problems from any of the algorithm books (DPV, CLRS, ....).
 


   
Weekly Outline for Fall 2022: 
Problem Sets for Monday Tutorials

Sep 12: Problems on complexity notation

Sep19: Problems on recurrences

Sep 26: Test 1

Oct 3: Problems from Test 1 + DFS Exercises

Oct 10: Thanksgiving

Oct 17: Solutions of Assignment 1 + Problems on SSSP 

Oct 24: Fall Break

Oct 31: Test 2

Nov 07: Cancelled

Nov 14: Problems from Test 2 + MST and Dynamic Programming Problems

Nov 21: Test - 3

Nov 28: Test 3 Problems and Dynamic programming examples

Dec 05: NP-Completeness Exercises

Dec 09: Problems from Assignment 3.


What was covered in Fall 2021 (i.e., Last Year)?

 (Video Recordings for the relevant part of the office hours are posted in Brightspace)
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(Merge-Sort Analysis)

Part 2(Multiplying Integers)

Part 3(Faster Multiplication)

Part 4 (Recursion Tree)
 Divide-and-Conquer

Recursion Tree
Divide-and-Conquer Technique
Analyzing merge-sort, multiplication of
two n-bit 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/master-theorem-solver-javascript
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

Depth-first-search

DAGs, Topological Sort, and DFS

 Depth-first-search



Directed-graphs
 Graph representation, Graph exploration,
tree and back edges,
depth-first search traversal,
finding connected components using explore and
cc-number

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)
 Shortest-paths in directed graphs

Correctness of Dijkstra's algorithm
 shortest-paths


correctness
 Shortest paths in DAGs

Dijsktra's single-source shortest path
algorithm for general directed graphs
Oct 25-29
 FALL BREAK
NO OFFICE HOURS
7 (Nov 2, 4)
 Union-Find DS + Kruskal's MST algorithm



Kruskal and Prim's MST algorithms
 union-find data structure + MST

Prim's MST algorithms

Additional Notes on MSTs
 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)
 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, set-up recurrence relation, solve recurrence bottom-up.
Longest paths in DAGs
9 (Nov 16, 18)
 Dynamic Programming II

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


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,
Polynomial-time reductions.
11 (Nov 30, Dec 2)
 Polynomial-time reductions

NP-Completeness
 Polynomial-time reductions

NP-Complete Problems
 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)
 Hardness Reductions

Circuit-SAT is NP-Complete


 More Hardness Reductions

Circuit-SAT problem		 3SAT, Clique, 0-1 Integer Linear Programs are NP-Complete.

Sketch of the proof of Circuit-SAT is NP-Complete.

Undergraduate Academic Advisor:

The undergraduate advisor for the School of Computer Science is available in Room 5302C HP, by telephone at 520-2600, ext. 4364 or by email at undergraduate_advisor@scs.carleton.ca. The advisor can assist with information about prerequisites and preclusions, course substitutions/equivalencies, understanding your academic audit and the remaining requirements for graduation. The undergraduate advisor will also refer students to appropriate resources such as the Science Student Success Centre, Learning Support Services and the Writing Tutorial Services.
University Policies:

Student Academic Integrity Policy: Every student should be familiar with the Carleton University student academic integrity policy. A student found in violation of academic integrity standards may be awarded penalties which range from a reprimand to receiving a grade of F in the course or even being expelled from the program or University. Some examples of offences are: plagiarism and unauthorized co-operation or collaboration. Information on this policy may be found in the Undergraduate Calendar.

Plagiarism: As defined by Senate, "plagiarism is presenting, whether intentional or not, the ideas, expression of ideas or work of others as one's own". Such reported offences will be reviewed by the office of the Dean.

Unauthorized Co-operation or Collaboration:
We follow the normal policies of Carleton University for providing academic accommodations as deemed necessary. Please contact the appropriate authorities well in advance so that you can be accommodated.

Equity Statements:
You may need special arrangements to meet your academic obligations during the term. For an accommodation request the processes are as follows:

Pregnancy obligation: write to me with any requests for academic accommodation during the first two weeks of class, or as soon as possible after the need for accommodation is known to exist. For more details visit the Equity Services website: http://www2.carleton.ca/equity/

Religious obligation: write to me with any requests for academic accommodation during the first two weeks of class, or as soon as possible after the need for accommodation is known to exist. For more details visit the Equity Services website: http://www2.carleton.ca/equity/

Academic Accommodations: The Paul Menton Centre for Students with Disabilities (PMC) provides services to students with Learning Disabilities (LD), psychiatric/mental health disabilities, Attention Deficit Hyperactivity Disorder (ADHD), Autism Spectrum Disorders (ASD), chronic medical conditions, and impairments in mobility, hearing, and vision. If you have a disability requiring academic accommodations in this course, please contact PMC at 613-520-6608 or pmc@carleton.ca for a formal evaluation. If you are already registered with the PMC, contact your PMC coordinator to send me your Letter of Accommodation at the beginning of the term, and no later than two weeks before the first in-class scheduled test or exam requiring accommodation (if applicable). Requests made within two weeks will be reviewed on a case-by-case basis. After requesting accommodation from PMC, meet with me to ensure accommodation arrangements are made. Please consult the PMC website (www.carleton.ca/pmc)  for the deadline to request accommodations for the formally-scheduled exam (if applicable).

Medical Certificate: The following is a link to the official medical certificate accepted by Carleton University for the deferral of final examinations or assignments in undergraduate courses. To access the form, please go to http://www1.carleton.ca/registrar/forms/

Important Dates: For important academic dates and deadlines, refer to https://calendar.carleton.ca/academicyear/

http://www.scs.carleton.ca/~maheshwa