**COMP 3804: Design and Analysis of
Algorithms
**

**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**

Course-TA:

Starting from the Week of Sept 10th (except the Study Break Week), please go to HP 5336

**Arash: Mondays 9 - 10:30 AM****Fedor: Thursdays 10 - 11AM**

**Kerry: Fridays 12:45 - 2:15 PM**

**Yunkai: Fridays 1 - 2PM**

Course Objectives:

(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, ...

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.

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**

(I use material from here to teach!)

- Kleinberg and Tardos, "Algorithm Design"

- Mehlhorn and Sanders, "Algorithms and Data Structures"
- (Knuth) D.E. Knuth, "The art of computer programming", Vol. 1,2,3, Addison-Weseley.
- Aho, Hopcroft and Ullman, "The design and analysis of algorithms", Addison-Weseley in 1980s.

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 PDF-File LaTeX-File |
Oct 31 |
Nov 19 |
6.25% | |||

A4 PDF-File LaTeX-File |
Nov 14 |
Dec 05 |
6.25% | |||

Mid-Term |
Oct 29 |
25% |
||||

Final Exam |
Please check exam schedule |
50% |

To pass this course:

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

Sep 05:

Sep 10:

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.

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

Oct 31: SSSP -

Nov 05: Dijkstra's Algorithm- Correctness. My Notes

Nov 07: Shortest Paths in DAGs, Increasing Sequence and Introduction to Dynamic Programming - Short and Long Paths in DAGs, Longest Increasing SubSequence [See Chapter 6 of Text Book]

Nov 12: DP - Matrix Multiplication, Longest Common Sequence,

Nov 14: DP - LCS, Knapsack, All Pairs SP.

Nov 19: A3 Due, DP, and Intro to NP-Hardness [Richard Karp Video]

Decision Problems, P & NP, P \subset NP.

Nov 21: NP-Hardness [Chapter 8] Classes P & NP-Complete, Polynomial Time Reducibility, 3CNF-SAT to CLIQUE

Nov 26: NP-Completeness Proofs: Circuit-SAT to SAT, SAT to 3CNF-SAT, 3CNF-SAT to 0-1 ILP

Nov 28: NP-Hardness: 3CNF-SAT to 0-1 ILP contd., 3CNF-SAT to SUBSET-SUM,

Dec 03: NP-Completeness Proofs: Equivalence of Vertex-cover, Clique, Independent-Set Problems, SUBSET-SUM to Knapsack.

Dec 05: A4 Due. NP-Hardness

Review, Solutions to selected Exercises from Assignment 3+4, and some remarks on Final Exam.

Dec 10: If you want, you may bring a non-programmable calculator for the final exam.

Final Exam at 2PM most likely in the Field House - Please find this out through the Carleton Exam Website.

The exam is based on the material covered in the class from Sept 5-Dec 5 (inclusive), relevant sections of the textbook, and all the assignments. Please review Assignments & exercises (solved and unsolved) in the textbook as part of preparation for the exam. The format of the exam is

- 20 Short Answer Questions worth a total of 70 = 3.5 x 20 Marks

- 2 Long Answer Questions worth a total of 30= 15 x 2 Marks.

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.

- 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.

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

- 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
- 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

- Assignment 1 is posted
- 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.

- Assignment 2 is posted
- Assignment 3 is posted
- Assignment 4 is posted
- Please try to complete the online teaching
evaluation.