Concordia University
Department of Computer Science and Software Engineering
COMP 6651: Algorithm Design Techniques
Winter 2012
Office hours: Mondays 1:30-2:30 p.m. or by appointment
Lecture Schedule
:
Important Dates
Course Outline
Announcements
April 25, 2012
Please check your marks . I should be submitting grades tomorrow.
April 12, 2012
The final exam is tomorrow night between 19:00 and 22:00 in Room FG-C070. See you there, and good luck! I will be in my office tomorrow morning if you have last minute questions.
April 11, 2012
Please bring a laptop for your presentation, as well as a printout of your slides.
April 9, 2012
The Tuesday morning and Weds morning presentations will be in EV 3.101 and Weds evening presentations will be in EV 3.123. See you there!
April 8, 2012
I have been asked to mention the book sections that will be covered in the final. They are:
Chapters 1-9, 15, and 16 (except sections 16.4 and 16.5), 17, 22, 23, 24 (except 24.4), 25, 26 (except 26.4, 26.5), 34, 35 (except 35.4, 35.5).
March 30, 2012
1. For the project, please (a) bring me a printout of your three papers if you haven't done so already. Make sure they are labeled with your group number and names.
(b) Please book a time slot for your presentation. Check that your slot has been reserved.
2. For your presentation slot, please prepare a presentation for about 10-12 minutes summarizing your report. Bring your report to the presentation.
3. The classroom problems for this week will be done in my office on Weds April 4 from 5-6. Please contact me if the time does not suit. The problems are:
Group 20: 35.1-1, 35.2-3
Group 21: 34.5-7, 35.1-4, 35.2-2
March 28, 2012
HW 4 was handed out in class last Friday; please pay attention to the due date.
March 26, 2012
The demo time slots are available, I will keep updating as I get more requests. If your group does not appear in the list and you sent me email, please resend.
March 23, 2012
1. The groups who have not yet chosen their papers for the project need to send me email with their choices before Monday March 26 at 10 a.m.
2. I would like to schedule 20 minute meetings to discuss the project on April 10 and 11. The available times are
Tuesday April 10: 8 a.m. to 11:20
Wednesday April 11: 8 a.m to 9:20 a.m. and 4 p.m. to 6 p.m.
Send me your preferred time and group number and I will reserve the slot. First come first served!
Be aware that there may be small delays if other groups take more than their allotted time.
3. The classroom problems for next week are as follows:
Group 18: 34.2-2, 34.4-6, 34.5-5
Group 19: 34.2-7, 34.4-5, 34.5-6
March 19, 2012
1. The errors in the test input have been fixed.
March 16, 2012
1. The final examination schedule has been announced. Our class will have its final exam on April 13, between 7 pm and 10 pm.
2. The classroom problems for today's lecture are as follows:
Group 17: 25.2-6, 25.3-4, 26.1-6
Group 16: 25.1-10, 25.3-6, 26.1-7
3. The POD has provided some test inputs and outputs and notes
for the third programming exercise.
March 9, 2012
1. I will be handing out HW 3 (to be done individually) in class today.
Please also find Programming Exercise 3 (to be done in groups).
2. The classroom problems for next week are as follows:
Group 13: 22.3-8, 23.2-1, 24.3-2
Group 14: 22.3-12, 23.2-8, 24.3-5
March 6, 2012
The classroom problems for this Friday are
17.1-1, 17.2-2, 17.3-4 (Group 11)
17.1-3, 17.2-1, 17.3-2 (Group 12)
March 4, 2012
For those who want to see me about their midterm, I will be available Tuesday afternoon from 2-4.
March 2, 2012
The midterm was handed back today. Some students asked for some questions to be looked at again, and I have done so. The updated marks as well as marks for HW 1 and 2 can be found here . Please check carefully and let me know of any discrepancies. I believe the marks for HW1 are also updated by the marker. Please be aware that the drop date is Sunday midnight. I was given back some exams, but the students did not speak to me or ask me to look at any specific questions. I have not looked at those exams; please pick them up from me next week.
February 17, 2012
1. Midterm today at 17:45h. Students with id < 6300000 sit in the usual classroom MB 5.245. Students with id >= 6300000 should go to MB 3.445. Please be sure to come early enough to find the new classroom.
February 10, 2012
1. The midterm is next Friday during class hours - it will start at 5:45 and will last an hour and a half. It wil cover topics we have done so far: O, Omega, and Theta notations, recurrence relations and methods to solve them, divide and conquer algorithms including for sorting and selection, randomized algorithms, greedy algorithms, and dynamic programming. In terms of the book, I expect you to have covered Chapters 1-9, 15, and 16 (except sections 16.4 and 16.5).
2. In today's class, we will do more examples of greedy algorithms, and dynamic programming as well as talk about Assignment 1.
February 3, 2012
1. In class today, I will hand out Homework 2 (to be done individually). Please also find Programming Exercise 2 (to be done in groups).
2. The classroom problems for this week are as follows:
Group 9: 15.1-2, 15.3-3. 15.4-4
Group 10: 15.1-3, 15.3-5, 15.4-5
January 30, 2012
1. As announced in class last week, there is a programmer on duty (Mohsen Eftekhari) for this course who is available for questions regarding your programming assignments on Mondays between 14:00 and 17:00 in H-847.
2. The classroom problems for this week are 16.3-2, 16.1-4, 16.2-4, 16.3-8, 16.1-5, and 16.2-5.
3. Unfortunately I have another meeting today clashing with my 1:30 office hours. I will be available from 11-12 this morning as well as from 3-4. Sorry about the inconvenience.
January 20, 2012
1. In class today, I will hand out Homework 1 (to be done individually) and Programming Exercise 1 (to be done in groups).
2. The classroom exercises for next Friday are : Q 16.1-3 (page 422), 16.2-3 (page 427), 16.3-3 (page 436), Q 16.3-8 (page 436), ane also two questions not from the book. Given a set of points on the plane (i.e a set of (x_i, y_i) pairs, n of them), find (1) an algorithm that finds the two points that are closest among all pairs (2) an algorithm that finds the smallest convex polygon P such that all points are either on P or in the interior of P.
3. All students need to be in groups by the end of today's class. Check the list of groups to be sure your name is there.
January 16, 2012
The classroom problems for this Friday are Q 7.1-2 (page 174), 7.2.2 (p. 178), 9.3-1 (pg. 223), 9.3-5 (pg. 223). Also two questions not from the book. Take insertion sort, merge sort, heapsort, and quicksort. (1) Analyze their runnig time when the input is sorted, reverse sorted, almost sorted (every element is at most k away from its sorted position where k is a constant). (2) Which of these sorts is "stable" and why?
January 11, 2012
1. The classroom has been changed. The new classroom is MB 5.245.
2. Kinda pointed out a typo in Question 4.3-8. The recurrence should be:
T(n) = 4T(n/2) + n
Thanks Kinda!
January 8, 2012
1. The course outline has some minor updates. In particular, the collaboration policy for programming assignments also holds for the project. Also, the chapter references for the textbook have been provided. Please review the material covered in the first lecture, and read in advance the material for the second lecture.
2. The classroom exercises for next week are Question 1.1, 1.2-2 on page 14, Question 2.3-4 on page 39, Question 3.2 on page 61, Question 4.3-8 on page 87 and 4.3-9 on page 88. Everyone is expected to try these problems, though only Groups 1 and 2 will be asked to present their solutions.
Submission:
EV-3.249
7:00 am - 11:00 pm
Webpage maintained by lata at cs at concordia at ca. Last updated Jan 5, 2012.