COMP 3804:  Design and Analysis of Algorithms
(Teaching this course after 7-years!)


Instructor: Anil Maheshwari

OFFICE HOURS: Wednesday 10:15 to 11:45 AM in Room 5125b HP

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


Term: Fall 2018 Class Hours: 13:05 to 14:25  Mondays and Wednesdays in TB 360

Course-TA: 

 
Starting from the Week of Sept 10th (except the Study Break Week), please go to HP  5336
  1. Arash: Mondays 9 - 10:30 AM
  2. Fedor: Thursdays 10 - 11AM
  3. Kerry: Thursdays 2:30 - 4 PM
  4. Yunkai: Fridays 1 - 2PM

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 - pseod-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, ...
Linear Programming: What it is, how to express several problems as LP problems (Flow, Shortest Paths, Matching), review of simplex algorithm.
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 Websitepublisher's web-site)

There are numerous other textbooks on Algorithms and  Reference Materials

The following is the schedule for assignments and exams.


Posted On
Due Date
Marked By?

% of Total Marks

BACKGROUND QUIZ1(WINTER 2010)

Background Quiz 2 (Summer 2010)
Sept 05
Never
You

Make sure you know this material - this is minimum background required to understand the material in this course
(Warning: Less than 32% had reasonable background in previous  terms). DFW of this course is pretty close  to 50% for last several terms!

A1
PDF-File
LaTeX-File
Sep 05
Sep 24



6.25%

A2
PDF-File
LaTeX File
Sep 26
Oct 15


6.25%
A3
Oct 26
Nov 12


6.25%
A4
Nov 14
Dec 03


6.25%
Mid-Term
Oct 29



25%

Final Exam
Please check exam schedule



50%


To pass this course:
  1. You must secure at least  50% Marks in the FINAL EXAM.
  2. You must secure at least a total of 50% marks in the whole course.



Fall 2018 Class-Wise Schedule:

Sep 05: Introduction to Algorithmic Thinking (Design &  Analysis of Algorithm) Illustrated via finding a subarray of an array that has the largest sum (Also see my rough draft)

Sep 10: Algorithmic Technique: Divide-and-Conquer: Vrahanka/Fibonacci numbers; How to multiply two n-bit numbers. Solving recurrences of type T(n)=aT(n/b)+f(n).
Sep 12: More on solutions of some of the standard recurrences including Multiplication, Matrix Multiplication, Merge Sort, Binary Search, etc.. Substitution method for solving recurrences of the form T(n)=T(n/3)+T(2n/3)+n=O(n log n).

Sep 17:Algorithm for finding the median element.
Sep 19: Finishing Analysis for finding the k-th order/median element. My Notes on Median. Introduction to Graphs and how to store them in
computer.

Sep 24: Intro to Graphs and Graph Traversal using depth first search
(See Chapter 3 of the textbook for details.)
Sep 26:
A1 Due. Graph traversal of undirected and directed graphs using depth first search - concept of pre and post number and its applications. 
 
Oct 01: Strongly-Connected Components - DAGs of SCC Components - G^R and G  (Section 3.4 of the textbook)
Oct 03: SCC Analysis. MST (Section 5.1)

Oct 10:
MST - Kruskal + Prim's Algorithm for MST + Associated Data Structures.
 
Oct 15:
A2 Due; Finishing Kruskal's algorithm; Heap Data Structure with Extract-Min and Decrease Key; Prim's Algorithm
Oct 17: MST-Pseudocodes. Continue with Prim's Algorithm; Some selected exercises from Assignment 2.  SSSP - Introduction.

Oct 29:
MID-TERM [All the material covered in the course up to the Oct 17th class]
Oct 31:


Nov 05:
Nov 07:

Nov 12:
A3 Due
Nov 14:

Nov 19:
Nov 21:

Nov 26: 

Nov 28:

Dec 03: A4 Due
Dec 05: Review and some remarks on Final Exam.





This is just a guideline for me - we may not follow the same path this term!

What was done in Fall 2011 version

Sept 8: Course Mechanics; Required Background (f1 f2) ; Changes from previous Years;
Sept 13: Stable Marriages!!
Sep 15: DPV 0; 2.1; 2.2: Fibonacci Recurrence; O-notation;
Sep 20: Divide-and-Conquer  - Multiplying two n-bit numbers + Recurrences (DPV 2.5 and 2.1) - Masters Theorem+Substitution (My notes on Evaluating Recurrences).
Sep 22: Words on Sorting - Merge Sort - Divide and Conquer - Matrix Multiplication - Finding Min/Max
Sep 27: Randomized and Deterministic Algorithms for Finding Medians.
Sep 29: Partial Solutions to Assignment 1 + Introduction to Graphs.
Oct 04: Graph Representation + DFS in undirected graphs (DPV 3.1 + 3.2)
Oct 06: Solutions of Assignment 2 + DFS continued + DFS in directed Graphs + DAGs (DPV 3.2+ 3.3)
Oct 11: Linearization of DAGs; Greedy Algorithms via MST (DPV 5.1) ; Partitioning Lemma for MSTs.
Oct 13: MST (DPV 5.1) [Kruskal's Algorithm + Review of PQs and Binary Heaps] My Notes on Heaps
Oct 18: PRIMs Algorithm +
Oct 20: BFS (DPV 4.1+ 4.2) + SSSP (DPV 4.3+4.4)  + SSSP (DPV 4.4)
Oct 25: MID-TERM
Oct 27:  Correctness of Dijkstra's Algorithm
Nov 01: Dynamic Programming [DPV Whole of Chapter 6]
Nov 03: Dynamic Programming
Nov 08: Dynamic/Linear Programming [DPV 7.1 + 7.7] (Note that for LP the focus is on the formulation of a problem as a LP, what does it mean when we solve an LP, what is a significance of a LP. We do not need details on how to solve an LP and how the Simplex Algorithm works - interested students can please read the relevant sections in the  book - this will require a great deal of linear algebra/geometric intution to appreciate the steps in the algorithm.)
Nov 10: Solutions of Assignment 5, Linear Programming (Bandwidth Allocation Problem,  SSSP as an LP, Why a problem in P has always a LP formulation (via the circuit satisfiability))
Nov 15: NP-Completeness - Introduction to NP-Completeness via Richard Karp's Video.
Nov 17: Solutions of Assignment 6, NP-Completeness -  Definitions of P, NP, Hard Problems, Polynomial Time Verification, and the Question Is P=NP?.
Nov 22: NP-Completeness - Proof of equivalence of  Clique - Vertex Cover - Independent Sets. Polynomial Time Redicibility among Combinatorial Problems. How to show a problem is NP-Complete - (3CNF SAT --> CLIQUE<G,k>)
Nov 24: Solutions of Assignmnet 7, NP-Completeness- (Here are my Partial Notes on proving a few NP-Completeness Results)
             
More examples of  Reductions (Polynomial Time Reducibility: Vertex Cover,  Independent Set,  0-1 Integer Linear Programming)
Nov 29: More examples of Reductions  (Subset Sum, Directed Hamiltonial Cycle)
Dec 01: Solutions of Assignment 8,  (Hamiltonian Cycle, Cooks Proof: How to show that Circuit-SAT is NP-Complete),
             Conclude
            Steps in Solving a Problem Algorithmically -
               - Is the Problem Easy: Divide-and-Conquer; Greedy, Dynamic Programming and Designing a LP Forumation.
              -  Is the Problem Hard: An Integer Linear Programming Forumation,  Hardness-Reductions.
              - Coping with Hardness: Approximation Algorithms, Heuristics, Probablistic Algorithms, Surrendor!
              - Some remarks about Final Exam
                FINAL EXAM is During The Examination Period - Look for the exam for COMP 3804/MATH 3804 in the exam schedule.
                It consists of several questions.
                Question 1 has 20 parts, each worth 3 marks - where you will be asked to provide a 1-2 line answer for a problem.
                Correct Answer is worth 3 Marks, Wrong answer is worth 0 Marks, and No Answer (i.e. the blank box) is worth 0.6 Marks.
               This question covers essentially all the topics that we have covered during the course.

                Other questions do have parts, but not that many.
                GOOD LUCK.

     


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 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
  1. All announcements will be posted here or mentioned in the class - its up to you to ensure that you are up-to-date in terms of whats going on
  2. For NP-Completeness you may like to visit some of the following references:
    1. A List of NP-Complete Problems
    2. Some reductions illustrated nicely 1 2 3
    3. NP-Completeness Column
    4. Graph of NP-Complete Problems
    5. Puzzles are NP-Complete
    6. The Girl who proved P=NP
    7. Here are the lists of proofs that P=NP as well as proofs that P<>NP
    8. Here is the description from Clay Mathematical Institute
  3. Assignment 1 is posted
  4. You can upload a scanned copy of your Assignment on cuLearn. It doesn't have to be typed as such. Use a good image capturing device and upload the pdf files.
  5. Assignment 2 is posted

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