Algorithm Analysis and Design

COMP 3804 / MATH 3804, School of Computer Science, Carleton University
Time: Fall 2014, Mondays and Wednesdays, 11:35 to 12:55
Instructor: Amin Gheibi
Classroom: TB 240
Course Webpage:
Assignments, Grades, and discussions in cuLearn:

Course Description

This course is an introduction to design and analysis of algorithms. Topics that we cover in this course are recurrence relations, time and memory complexity, sorting and searching, divide-and-conquer, dynamic programming, greedy algorithms, graph algorithms and NP-completeness. We will also briefly talk about some special topics such as linear programming.


COMP 2002 or COMP 2402, and either COMP 1805 or both of MATH 2007 and MATH 2108, or equivalents.


  • Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, (2009) Published by MIT Press.
  • Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, (2007) Published by McGrawHill.


Item Weight Hard Deadline
Assignment 1 10 % Sep. 29, Before the lecture
Assignment 2 10 % Oct. 15, Before the lecture
Mid-term Test 20 % Oct. 22, During the class
Assignment 3 10 % Nov. 17, Before the lecture
Assignment 4 10 % Dec. 1, Before the lecture
Final Exam 40 % Will be announced by the university
Bonus: Implementation Extra 5 % To determine the topic: before Assignment 2 due date
To release your implementation: Last day of the class

Assignment boxes can be found on the 3rd floor, in room 3115 HP. You can drop the assignments there or hand them to the instructor in the class prior to the lecture. Late assignments will not be accepted. Late means after the lecture starts on the due date as specified.

For bonus, you should implement one of the specified algorithms (it should be interactive and has a web interface). Please come to my office hours to discuss this option and determine the algorithm for your implementation. More details will be announced in the class.

Important Dates (from Calendar)

September 4, 2014 Fall and fall/winter classes begin. September 17, 2014 Last day of registration for fall term and fall/winter courses. September 30, 2014 Last day to withdraw from fall term and fall/winter courses with a full fee adjustment. October 10, 2014 December examination schedule (fall term final and fall/winter mid-terms) available online. October 13, 2014 Statutory holiday. University closed. October 27-31, 2014 Fall break, no classes. November 7, 2014 Last day to submit, to the Paul Menton Centre for Students with Disabilities, Formal Examination Accommodation Forms for December examinations. December 8, 2014 Fall term ends. Last day of fall-term classes. Last day for academic withdrawal from fall term courses.

Please refer to Carleton calendar for details

Office Hours and Contact Information



The TAs room is HP 1170 (tunnel entrance). They hold office hours based on the following table:
Name Email Office Hours
Arash Nouri arashnourisagharlou[at]cmail[dot]carleton[dot]ca Fridays, 12:00 to 13:30
Spencer Whyte spencerwhyte[at]cmail[dot]carleton[dot]ca Thursdays, 12:00 to 13:00

Collaboration Policy

Students are encouraged to collaborate on assignments, but at the level of discussion only. When writing down the solutions, students must do so in their own words.

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


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

Unauthorized Co-operation or Collaboration

Senate policy states that "to ensure fairness and equity in assessment of term work, students shall not co-operate or collaborate in the completion of an academic assignment, in whole or in part, when the instructor has indicated that the assignment is to be completed on an individual basis". Please refer to the course outline statement or the instructor concerning this issue.

Students with Disabilities Requiring Academic

Accommodations Register with the Paul Menton Centre for Students with Disabilities (PMC) for a formal evaluation of disability-related needs. Documented disabilities could include but are not limited to mobility/physical impairments, specific Learning Disabilities (LD), psychiatric/psychological disabilities, sensory disabilities, Attention Deficit Hyperactivity Disorder (ADHD), and chronic medical conditions. Registered PMC students are required to contact the PMC, 613-520-6608, every term to ensure that I receive your Letter of Accommodation, no later than two weeks before the first assignment is due or the first in-class test/midterm requiring accommodations. If you only require accommodations for your formally scheduled exam(s) in this course, please submit your request for accommodations to PMC by the deadlines published on the PMC website:

Religious Obligation

Write to me concerning 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

Pregnancy Obligation

Write to me concerning 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

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

News and Cool Stuff

Fall 2014 - Amin Gheibi