COMP 3804 Introduction to Algorithms

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

Instructor: Anil Maheshwari

Course Delivery: The video lectures and notes are posted from the Winter 2021 offering of this course from Professor Michiel Smid (see https://cglab.ca/~michiel/3804.html). He has graciously agreed to share the contents with us. (Note: Except for a couple of initial videos, the rest are professionally recorded in a classroom setting at Carleton.) In addition to these, my office hours will be during the class time slot on Tuesday and Thursdays from 14:35 to 15:55. You are welcome to join live during the office hour. During the office hour(s), in addition to answering your questions, we may solve a few problems related to that weeks topic from the weekly practice problem set and/or assignments. Some relevant parts of the office hours will be recorded and posted in the Brightspace system. Ample resources and relevant pointers will be provided during the course.

OFFICE HOURS: Tuesday and Thursday 14:35-15:55 Online over zoom (link provided in Brightspace).

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

Course-TA:

TAs will be mainly marking assignments, tests and exam.

Course Objectives: An introduction to the design and analysis of algorithms. Topics include: divide-and-conquer, dynamic programming, linear programming, greedy algorithms, graph algorithms, NP-completeness.
(Also listed as MATH 3804.) Prerequisites: COMP 2002 or COMP 2402, COMP 2804, MATH 2007 and MATH 2108, or equivalents. Lectures three hours a week.

A bit of detailed Objectives and Contents are as follows:
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 - pseodo-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.

Text-Book
DPV: Das, Papadimitriou and Vazirani, "Introduction to Algorithms", Mc Graw Hill 2008.
(See Papadimitriou's Website; publisher's web-site)

There are numerous other textbooks on Algorithms and Reference Materials

CLRS: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. Introduction to Algorithms. (2nd/3rd) edition, McGraw-Hill, 2001.
See Books web-site
Jeff Erickson's Algorithms book
Kleinberg and Tardos, "Algorithm Design", Addison-Wesley
Mehlhorn and Sanders, "Algorithms and Data Structures", Springer
(Knuth) D.E. Knuth, "The art of computer programming", Vol. 1,2,3,4,... Addison-Weseley.
Aho, Hopcroft and Ullman, "The design and analysis of algorithms", Addison-Weseley in 1980s.
My Notes on Algorithm Design
Master Theorem Solver from Project Nayuki

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 PDF-File LaTeX-File	Sep 9	Sep 24	10%
A2 PDF-File LaTeX File (Figures: dfs-undirected, grid-graph and tree)	Sep 23	Oct 8	10%
A3 PDF-File LaTeX-File	Oct 22	Nov 12	10%
A4 PDF-File LaTeX-File	Nov 17	Dec 6	10%
Test - 1	Oct 14	Oct 14	15% (14:35-15:55 PM on Thursday October 14th)
Test -2	Nov 25	Nov 25	15% (14:35-15:55 PM on Thursday November 25th)
Final Exam	Please check exam schedule		30%

To pass this course:

You must secure at least a total of 50% marks in the whole course.

Weekly Outline:
(Video Recordings for the relevant part of the office hours are posted in Brightspace)

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(Merge-Sort Analysis) Part 2(Multiplying Integers) Part 3(Faster Multiplication) Part 4 (Recursion Tree)	Divide-and-Conquer Recursion Tree	Set - I Set-II	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	Set-III	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	Set-III continued + Assignment 1 Solutions	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	Set-IV	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 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)	Shortest-paths in directed graphs Correctness of Dijkstra's algorithm	shortest-paths correctness	Test-1 Solutions SSSP Examples BFS+ Set-V	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	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)	Prim's MST Analysis & Introduction to Dynamic Programming I	Dynamic Programming	Practice problems from problem set V + Answering questions on Assignment 3.	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		Problem Set VI Solutions to Problems in Assignment 3.	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) Nov. 25	Decision Problems Decision Problems using languages TEST-2	Introduction to P and NP Complexity Classes Formal definitions of decision problems, P and NP.	Solutions to Problems in Assignment 3 + Problems Set VI.	Complexity classes P and NP Decision problems - SAT, Clique, Hamiltonian Cycle, TSP, Subset Sum P subset NP, Polynomial-time reductions. Test takes place during the class time slot of 14:35-15:55 via Brightspace system on Thursday, November 25th. The syllabus consists of all the material covered in Weeks 6-9 that includes Shortest Paths, Minimum Spanning Trees and Dynamic Programming. This includes all the lectures from Oct 19-Nov 18 (inclusive).
11 (Nov 30, Dec 2)	Polynomial-time reductions NP-Completeness	Polynomial-time reductions NP-Complete Problems	Problem Set VII	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	NO Office Hour on Thursday December 9th.	3SAT, Clique, 0-1 Integer Linear Programs are NP-Complete. Sketch of the proof of Circuit-SAT is NP-Complete.
December 13	FINAL EXAM			It takes place online over the brightspace system on December 13th from 7PM to 10PM. Course contents for the final exam includes all the lectures, notes, assignments, and the tests. You need to upload your answers before 10:10 PM. No e-mail submissions will be accepted.

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:

Students are encouraged to collaborate on assignments, but at the level of discussion only. When writing down the solutions, they must do so in their own words. Just a word of caution - in theoretically oriented courses, it is important to come up with your own ideas for the proof/an algorithm/a contradiction/etc. Sometimes these are like logical puzzles - if somebody tells you a solution then they are trivial and hard part is to come up with a solution. What we want to learn is how to solve them ourselves.
Past experience has shown conclusively that those who do not put adequate effort into the assignments do not learn the material and have a probability near 1 of doing poorly on the exams.

We will 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/

Announcements

Final Exam is scheduled for December 13th starting at 7 PM.
No Office Hours on Thursday November 4th.
We won't have any office hours during the Fall Break. But if you have questions etc., please send me an e-mail.
Test 1 takes place on Thursday October 14th during the class time slot on Brightspace system.
Assignment 1 has been marked. If you want any of the questions to be remarked, please send me an e-mail with some reasoning.
Assignment 2 is posted. My recommendation will be to start early.
Video Recordings for the relevant part of the office hours are posted in Brightspace
Assignment 1 is posted
We will likely send e-mail via Brightspace for important information. You may also check here.

For NP-Completeness you may like to visit some of the following references:

A List of NP-Complete Problems

Some reductions illustrated nicely 1 2 3

NP-Completeness Column

Graph of NP-Complete Problems

Puzzles are NP-Complete

The Girl who proved P=NP

Here are the lists of proofs that P=NP as well as proofs that P<>NP

Here is the description from Clay Mathematical Institute
Richard Karp Video

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