Algorithms I
Fall 2009
CISC-365*
Algorithms IFall 2009 |
|
|
|
|
|
|
|
|
|
|
| Internal Links | Personnel |
|
| Course Information |
||
| Lecture Schedule and Test Schedule |
||
| Practice Problems |
|
|
| Course Record |
|
|
| Recommended Readings |
|
|
| Challenges |
|
|
| Sample Tests |
||
| Labs |
| External Links |
Queen's School of Computing |
| Computing
Students'
Association |
|
| Class
Photo Gallery |
|
| CISC-365*
WebCT login page |
|
| Learning
- Your First Job (Paper by Dr. R. Leamnson) |
|
| Academic Integrity |
|
| Instructor |
Dr. Robin W. Dawes |
 |
| Goodwin
537 |
||
| dawes AT cs
DOT queensu
DOT ca |
||
| http://www.cs.queensu.ca/~dawes/ |
||
| 533-6061 (but
e-mail is a much
better idea) |
||
| Office Hours:
24/7, by appointment |
| TAs |
Name |
Email
(all at cs.queensu.ca) |
Office
Hours |
Picture |
| Na
Harrington |
na |
 |
||
| Lili Wang | lili |  |
||
| Calendar
Description |
Principles of design, analysis and implementation of efficient algorithms. Case studies from a variety of areas illustrate divide and conquer methods, the greedy approach, branch and bound algorithms and dynamic programming. |
| Text |
Cormen/Leiserson/Rivest/Stein, Introduction to Algorithms |
| Syllabus |
Complexity of
algorithms and
Complexity of problems: Reducibility, P, NP, NP-Completeness, etc. Divide and Conquer Paradigm: Quicksort, Median, Closest Pair of Points, etc. Principle of Optimality Dynamic Programming Paradigm: Longest Common Subsequence, Chained Matrix Multiplication, etc. Greedy Paradigm: Huffman Coding, Activity Selection, Minimum Weight Spanning Trees, etc. Branch-and-Bound Paradigm: 15-Puzzle, Travelling Salesperson Problem, etc. Class Choice (three or more topics will be proposed, the class will choose one by vote) |
| Marking
Scheme |
There will be five
50-minute
tests. The lowest of the five marks will count for
10%, and the other four will each count for 20% There will be two graded lab tests, worth 5% each |
| Class
Schedule Labs |
Monday 1:30
- 2:20 Wednesday 12:30 - 1:20 Friday 11:30 - 12:20 Tuesday 2:30 - 4:30 Wednesday 3:30 - 5:30 Friday 2:30 - 4:30 |
All
class meetings in Walter Light 210 Jeffery 157 Jeffery 155 Jeffery 157 |
||
| Test Schedule |
Date |
Location |
Material |
|
| Test 1 |
Friday October 9 |
TBA |
NP-Completeness and Divide & Conquer | |
| Test 2 |
Friday October 23 |
TBA |
Dynamic
Programming |
|
| Test 3 |
Friday November 6 |
TBA |
Greedy
Algorithms |
|
| Test 4 |
Friday November 20 |
TBA |
Branch
and Bound |
|
| Test 5 |
Friday December 4 |
TBA |
Class
Choice |
|
| Lab Test 1 |
Week of October 19 |
TBA |
Mystery |
|
| Lab Test 2 | Week of November 30 | TBA | Mystery | |
| Source |
Page | Exercise
Set |
Exercises |
Suggested Date |
| Text | 11 | 1.1 | 1, 2, 4, 5 | Sept 18 |
| 29 | 2.2 |
1, 2, 4 |
Sept 18 | |
| 37 | 2.3 |
3, 4, 5, 6, 7 |
Sept 18 | |
| 39 | Chapter 2 Problems |
2-3 a, b 2-4 a, b, c, d |
Sept 18 | |
| 52 | 3.1 | 1, 2, 3 | Sept 25 | |
| 60 | 3.2 |
1, 8 |
Sept 25 | |
| 61 | Chapter 3 Problems |
3-2 3-4 a, b, d, e |
Sept 25 | |
| 107 | Chapter 4 Problems |
4-1 a, b, g 4-2 |
Sept 25 | |
| 1101 | Chapter 34 Problems |
34-1 d 34-2 a 34-3 a |
Oct 2 | |
| 369 | 15.1 |
2, 3 |
Oct 9 | |
| 389 | 15.3 | 5 | Oct 9 | |
| 396 | 15.4 |
1, 5, 6 (hard) |
Oct 16 | |
| 404 | Chapter 15 Problems |
1, 2, 3, 4 |
Oct 16 | |
| 421 | 16.1 |
1, 2, 3, 4 |
Oct 30 | |
| 427 | 16.2 |
3, 7 |
Oct 30 | |
| 436 | 16.3 |
2, 6 |
Oct 30 | |
| 446 | Chapter 16 Problems |
1 |
Oct 30 | |
| course website |
B&B
Practice
Problems |
Nov 13 | ||
| 1111 | 35.1 | 1, 3 (hard) | ||
| 1116 | 35.2 | 1, 5 | ||
| 1127 | 35.4 |
1 | ||
| Monday, September 14 Plan: Intro and Review Intro (PDF of Powerpoint) Some Interesting Problems |
Wednesday,
September 16 Plan: NP-Completeness Easy Problems and Difficult Problems |
Friday,
September 18 Plan: NP-Completeness Reductions and CNF-SAT |
| Monday, September 21 Plan: NP-Completeness NP-Completeness |
Wednesday,
September 23 Plan: NP-Completeness NP-Completeness |
Friday,
September 25 Plan: NP-Completeness NP-Completeness |
| Monday, September
28 Plan: Divide and Conquer NP-Completeness |
Wednesday,
September 30 Plan: Divide and Conquer Divide and Conquer |
Friday, October 2 Plan: Dynamic Programming Divide and Conquer |
| Monday, October 5 Plan: Dynamic Programming Dynamic Programming |
Wednesday, October 7 Plan: Dynamic Programming Dynamic Programming |
Friday,
October 9 TEST on NP-Completeness and Divide & Conquer |
| Monday, October 12 No Class - Thanksgiving |
Wednesday, October
14 Plan: Dynamic Programming |
Friday,
October 16 Plan: Dynamic Programming |
| Monday, October 19 Plan: Greedy Algorithms Dynamic Programming Wrap-up |
Wednesday, October
21 Plan: Greedy Algorithms |
Friday,
October 23 TEST on Dynamic Programming |
| Monday, October 26 Plan: Greedy Algorithms |
Wednesday, October
28 Plan: Greedy Algorithms |
Friday,
October 30 Plan: Greedy Algorithms |
| Monday, November 2 Plan: Branch and Bound Greedy Algorithms (complete) |
Wednesday, November
4 Plan: Branch and Bound Branch and Bound |
Friday, November 6 TEST on Greedy Algorithms |
| Monday, November 9 Plan: Branch and Bound |
Wednesday, November
11 Plan: Branch and Bound |
Friday,
November 13 Plan: Branch and Bound |
| Monday, November 16 Plan: Branch and Bound |
Wednesday, November
18 Plan: Class Choice Approximation Algorithms |
Friday,
November 20 TEST on Branch and Bound |
| Monday, November 23 Plan: Class Choice Approximation Algorithms |
Wednesday, November
25 Plan: Class Choice Approximation Algorithms |
Friday,
November 27 Plan: Class Choice |
| Monday, November 30 Plan: Class Choice Completed Approximation Algorithm Notes |
Wednesday, December
2 Plan: Ask Me Anything Day |
Friday, December 4 TEST on Class Choice |
| Source | Chapter |
Details |
Target
Date |
| Text |
1 |
should be familiar ideas | Sept 18 |
| Text |
2 |
scan this |
Sept 18 |
| Text |
3 |
the essential ideas
here are the
"big O", "omega" and "theta" definitions and applications |
Sept 21 |
| Text |
4 |
- review the
substitution method
and the recursion-tree method (not covered in class) - you are not required to learn the master method, but it is a very powerful tool - study it if you have time |
Sept 21 |
| Electronic Enterprises Laboratory | http://lcm.csa.iisc.ernet.in/dsa/node216.html a brief but clear introduction to NP-Completeness, very similar to the approach we will take in class | Sept 25 | |
| Wikipedia |
http://en.wikipedia.org/wiki/List_of_NP-complete_problems Just as it says, this is a big list of NP-complete problems |
Sept 25 | |
| Wikipedia |
http://en.wikipedia.org/wiki/P_%3D_NP_problem A reasonably good summary of the problem classes P and NP and the relationship between them. Much easier to read than our text on this subject. |
Sept 25 | |
| mathreference.com |
http://mathreference.com/lan-cx-np,intro.html This collection of pages takes the same approach to the topic as we did (concentrating on problems and algorithms, rather than on formal languages) but it strays into error quite quickly. In fact, it contains some oversimplifications and some blatant errors that you should be able to spot. Good hunting! |
Sept 25 | |
| Text |
15 |
Intro, 15.1, 15.3,
15.4 |
Oct 9 |
| Text |
16 |
Intro, 16.1, 16.2,
16.3 |
Oct 30 |
| The internets |
Branch and Bound
sources: http://www.imada.sdu.dk/Courses/DM85/TSPtext.pdf http://www.lpds.sztaki.hu/pgrade/nagy_miklos/index.html http://www.cs.berkeley.edu/~demmel/cs267-1995/assignment5.html CMSC 132 Lecture |
Nov 13 | |
| Challenge |
Winning Entry |
Honourable Mention |
| 1. |
||
| 2. |
||
| 3. |
||
| 4. |
||
| 5. |
||
| 6. |
||
| 7. |
||
| 8. |
||
| 9. |
||
| 10. |
||
| 11. |
||
| 12. |
| Week | Lab Statement | My Solution |
| Lab 1 (Week of Sept
14) |
Lab 1 (PDF) | Solution |
| Lab 2 (Week of Sept
21) |
Lab 2 (PDF) Lab 2 Data |
Solution |
| Lab 3 (Week of Sept
28) |
Lab 3 (PDF) Lab 3 Data |
Solution |
| Lab 4 (Week of
October 5) |
Lab 4 Part 1 (PDF) Lab 4 Part 2 (PDF) Lab 4 Data |
Solution Part 1 Solution Part 2 |
| Lab 5 (Week of
October 12) |
Lab 5 Part 1 (PDF) Lab 5 Part 2 (PDF) Lab 5 Data |
Solution Part 1 Solution Part 2 |
| Lab 6 (Week of
October 19) - Lab Test 1 |
||
| Lab 7 (Week of
October 26) |
Lab 7 Part 1 (PDF) Lab 7 Part 2 (PDF) Lab 7 Data |
Solution Part 1 Solution Part 2 |
| Lab 8 (Week of
November 2) |
Lab 8 Part 1 (PDF) Lab 8 Part 2 (PDF) Lab 8 Data |
Solution Part 1 Solution Part 2 Solution Part 3 |
| Lab 9 (Week of
November 9) |
Lab 9 Part 1 (PDF) Lab 9 Part 2 (PDF) Lab 9 Data |
Solution |
| Lab 10 (Week of
November 16) |
Lab 10 (PDF) Lab 10 Data |
Solution Part 1 Solution Part 2 Solution Part 3 |
| Lab 11 (Week of
November 23) |
Lab 11 (PDF) Lab 11 Data - corrected |
Solution Part 1 Solution Part 2 Solution Part 3 |
| Lab 12 (Week of
November 30) - Lab Test 2 |