>>>>>>>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<<<<<<<<<<<< You can pick up Test 5 and your course mark for CISC365 from my office (Goodwin 720) at - 12:00 to 1:00 on Monday, Dec 13 or - 12:00 to 1:00 on Tuesday, Dec 14. After that I will give the remaining tests to Wendy in the main office (fifth floor, acoss from the elevator), and you can pick them up from her anytime during business hours.
TA office/lab hours start in week 2 of term.
Monday 11:30-1:30 Jeffery 157 (Lab A time) Sami
Tuesday 2:30-4:30 Jeffery 157 (Lab B time) Sami
Thursday 12:30-2:30 Goodwin 544 Marie
Friday 12:30-2:30 Jeffery 157 (Lab C time) Marie
Lectures:
Textbook: Introduction to Algorithms, Third Edition, by Cormen, Leiserson, Rivest, and Stein
Marking Scheme: Five 50-minute tests are given in class on Fridays: October 8, October 22, November 5, November 19, and December 3. The four highest test marks each count for 20% of the course mark, and the lowest test mark counts for 10% of the course mark. Assignment 1 and assignment 2 each count for 5% of the course mark.
Assignments, Textbook Problems, and Labs
The only marked assignments are assignment 1 and assignment 2, due on September 24 and October 1 respectively.
To help you learn the rest of the course material, there are weekly labs, as well as the textbook problems listed in the following course schedule. The labs and textbook problems are for study purposes; they are not handed in or marked. The TAs and the course instructor are happy to discuss any of the assignments, labs, and textbook problems with you.
Academic Integrity:
Please familiarize yourself with the material on Queen's
academic integrity website.
| Week | Topic | Readings | Assignments | Labs |
| Week 1 (Sept. 14, 16 17) | Introduction and review. Lower bounds and upper bounds for constants, algorithms and problems. Worst-case, average-case, and best-case bounds. Notation for asymptotic growth of functions. |
Textbook chapter 1. These ideas should be familiar. Skim chapter 2. Most of this should be familiar. Start reading chapter 3. Focus on the "big O", "omega" and "theta" definitions, and the applications of these definitions. |
Start Assignment 1.
Introductory problems in the textbook (not handed in) |
(no lab this week) Note: Labs were written by Prof. Robin Dawes, fall 2009. |
| Week 2 (Sept. 21, 23, 24) | More lower and upper bounds. Class NP. |
Finish chapter 3 on asymptotic growth of functions.
NP-completeness readings for weeks 2, 3, and 4 Introduction to NP-Completeness This is a clear, concise introduction. List of NP-complete problems A handy reference. Classes P and NP A summary of the problem classes P and NP and the relationship between them. This presentation is easier to read than the one in the textbook. |
Hand in Assignment 1 Sept. 24. Start Assignment 2.
Textbook problems on growth of functions |
Lab on Permutations Lab 1.pdf |
| Week 3 (Sept. 28, 30, Oct. 1) | NP-completeness | NP-Completeness readings, same as in week 2. |
Hand in Assignment 2 Oct. 1. Sample NP-completeness proof: The Set Intersection Problem is NP-Complete |
Lab on enumerating possibilities Lab 2.pdf Lab 2 Data |
| Week 4 (Oct. 5, 7) | NP-completeness | NP-Completeness readings, same as in week 2. |
NP-completeness sample proof and study problems Same as in week 3 |
Lab on heapsort Lab 3.pdf Lab 3 Data |
|
Lower and upper bounds, growth of functions, NP-Completeness |
||||
| Week 5 (Oct. 12, 14, 15) | Divide and conquer. Recurrences. |
Parts of Chapter 4: Introduction, pages 65-67. Section 4.1 Example of divide and conquer, and analysis. Section 4.2 Another example - optional. Section 4.3 Substitution method for recurrences. Read this. Section 4.4 Optional: Recursion-tree method. Section 4.5 Master method. Don't memorize this, but be able to use it. If I ask a test question about this, I will provide a statement of the Master Theorem. On a personal note, as a "master's student" I worked on recurrences, and this later became known as the "master method". Weird, eh? (Page 112 mentions the source of the master method is "Bentley, Haken and Saxe [44]"; before I got married, I was Dorothea Haken.) |
Textbook problems on divide and conquer page 107: 4‑1a,b,g; 4‑2 Labs 4 and 5 provide examples of divide and conquer algorithms. |
Lab on divide and conquer (test faulty chips) Lab 4 Part 1.pdf Lab 4 Part 2.pdf Lab 4 Data |
| Week 6 (Oct. 19, 21) | Dynamic programming |
Parts of Chapter 15: Introduction to dynamic programming, pages 359-360 Section 15.1 Rod cutting example Section 15.2 Matrix-chain multiplication Section 15.3 Elements of dynamic programming Section 15.4 Longest common subsequence example Prof. Blostein's examples: Matrix-chain multiply and CYK parsing Description of CYK parsing Two-page intro to dynamic programming and sequence alignment Prof. Blostein's Study Guide for Dynamic Programming |
Textbook problems on dynamic programming page 370: 15.1‑2, 15.1‑3 page 378: 15.1‑1 (or use Fig 15.5 as in Prof. Blostein's handout) page 390: 15.3‑5 pages 396‑397: 15.4‑1, 15.4‑5 pages 404‑406: 15‑1, 15‑2, 15‑3, 15‑4 pages 421‑422: 16.1‑1
|
Lab on divide and conquer (buy low, sell high) Lab 5 Part 1.pdf Lab 5 Part 2.pdf Lab 5 Data Solution Part 1 (There is no lab 6; the next one is lab 7) |
|
More NP completeness. Divide and conquer, recurrences |
||||
| Week 7 (Oct. 26, 28, 29) | Dynamic programming | Same readings as in week 6 (dynamic programming). |
Textbook problems on dynamic programming Same as in week 6 |
Lab on dynamic programming (tollway) Lab 7 Part 1 Lab 7 Part 2 Lab 7 Data |
| Week 8 (Nov. 2, 4) | Greedy algorithms |
These sections of Chapter 16: Introduction to greedy algorithms, pages 414-415. Section 16.1 Activity-selection example Section 16.2 Elements of the greedy strategy Section 16.3 Huffman code example (skip Lemmas 16.2 and 16.3)
Two greedy algorithms for weighted graphs:
|
Textbook problems on greedy algorithms pages 421‑422: 16.1‑2, 16.1‑3, 16.1‑4 pages 427‑428: 16.2‑3 page 436: 16.3‑2, 16.3‑6 page 446: 16‑1 (coin changing problem, as discussed in class) |
Lab on greedy algorithms (visit water cooler) Lab 8 Part 1 Lab 8 Part 2 Lab 8 Data |
|
Dynamic programming |
||||
| Week 9 (Nov. 9, 11, 12) | Greedy algorithms |
Same readings as in week 8 (greedy algorithms). For the test, you should be able to assess proposed greedy algorithms (do they provide optimal solutions?), and you should be able to write your own greedy algorithms. You should understand the examples from Chapter 16 (activity selection, Huffman code, coin-changing) and be somewhat familiar with the supplemental examples for weighted graphs: Prim's MST algorithm and Dijkstra's shortest-path algorithm. |
Textbook problems on greedy algorithms Same as in week 8 |
Lab on dynamic programming (zombie zapper) Lab 9 Part 1 Lab 9 Part 2 Lab 9 Data |
| Week 10 (Nov. 16, 18) | Branch and Bound |
Study four elements of Branch and Bound: the bounding function, the branching method, selecting a branch to investigate, and the initial solution. (Parallel computing is often used to speed up the execution of Branch and Bound algorithms; we skip this topic.)
Since Branch and Bound is not discussed in the textbook, refer to these internet sources: Principles and examples. This is a detailed presentation. The following pages present the four elements: page 13 bounding function; page 16 select a branch to investigate; page 19 branch (divide up the solution space); page 19 initial solution (to provide an initial bound). Traveling Salesman A detailed, readable presentation of B&B algorithms for the Traveling Salesman Problem. Pseudo-code is provided for Naive Exhaustive Search (page 2), Naive Branch and Bound (page 3) , and better Branch and Bound (pages 4-6). We discuss these algorithms in class. B&B Demo for Activity Assignment This demo steps through an example of activity assignment, showing the bounding and branching at each step. |
Branch and Bound problems Understand the execution of the Branch and Bound algorithm for Traveling Salesman and activity assignment (readings/demo listed in the previous column). Practice making up branching and bounding methods. You can try problems on the following list B&B Practice Problems. Text 5 will have questions about branch and bound, but will not ask about code: no questions about code for the algorithms we discussed (traveling salesman or activity assignment), and no questions asking you to write code for a new branch and bound problem. |
Lab on dynamic programming (assign cabinet posts) Lab 10 Lab 10 Data |
|
Greedy algorithms |
||||
| Week 11 (Nov. 23, 25, 26) | Branch and bound. Approximation algorithms. |
Same readings as in week 10 (branch and bound).
Beginning of Chapter 35: |
Branch and Bound problems Same as in week 10 Textbook problems on approximation algorithms page 1111: 35.1‑1, 35.1‑3 |
Lab on an NP complete problem: dominating set problem Lab 11 Lab 11 Data |
| Week 12 (Nov 30, Dec. 2) | Review; Recap of NP Completeness |
Review the NP-completeness readings from week 2. Prof. Blostein's notes on proving that vertex cover is NP-complete (reduction from 3-SAT to Vertex Cover). | Practice translating 3-SAT expressions to a vertex-cover problem, according to the reduction described in lecture and in Prof. Blostein notes. | (no lab this week) |
|
Branch and bound, Approximation Algorithms, NP-Completeness |
||||