>>>>>>>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<<<<<<<<<<<< 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:301:30 Jeffery 157 (Lab A time) Sami Tuesday 2:304:30 Jeffery 157 (Lab B time) Sami Thursday 12:302:30 Goodwin 544 Marie Friday 12:302:30 Jeffery 157 (Lab C time) MarieLectures:
Textbook: Introduction to Algorithms, Third Edition, by Cormen, Leiserson, Rivest, and Stein
Marking Scheme: Five 50minute 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. Worstcase, averagecase, and bestcase 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.
NPcompleteness readings for weeks 2, 3, and 4 Introduction to NPCompleteness This is a clear, concise introduction. List of NPcomplete 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)  NPcompleteness  NPCompleteness readings, same as in week 2. 
Hand in Assignment 2 Oct. 1. Sample NPcompleteness proof: The Set Intersection Problem is NPComplete 
Lab on enumerating possibilities Lab 2.pdf Lab 2 Data 
Week 4 (Oct. 5, 7)  NPcompleteness  NPCompleteness readings, same as in week 2. 
NPcompleteness 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, NPCompleteness 

Week 5 (Oct. 12, 14, 15)  Divide and conquer. Recurrences. 
Parts of Chapter 4: Introduction, pages 6567. 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: Recursiontree 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 359360 Section 15.1 Rod cutting example Section 15.2 Matrixchain multiplication Section 15.3 Elements of dynamic programming Section 15.4 Longest common subsequence example Prof. Blostein's examples: Matrixchain multiply and CYK parsing Description of CYK parsing Twopage 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 414415. Section 16.1 Activityselection 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, coinchanging) and be somewhat familiar with the supplemental examples for weighted graphs: Prim's MST algorithm and Dijkstra's shortestpath 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. Pseudocode is provided for Naive Exhaustive Search (page 2), Naive Branch and Bound (page 3) , and better Branch and Bound (pages 46). 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 NPcompleteness readings from week 2. Prof. Blostein's notes on proving that vertex cover is NPcomplete (reduction from 3SAT to Vertex Cover).  Practice translating 3SAT expressions to a vertexcover problem, according to the reduction described in lecture and in Prof. Blostein notes.  (no lab this week) 
Branch and bound, Approximation Algorithms, NPCompleteness 