CISC-365 Algorithms I, Fall 2010

         Dorothea Blostein; 720 Goodwin; 613 533-6537;; home page
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. 

         Marie Matheson;; home page
         Sami Torbey;
        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

         Tuesday 9:30, Thursday 8:30, Friday 10:30 in Jeffery 101.

Dates for Tests:
         The five tests are during lecture on Fridays: Oct. 8, Oct. 22, Nov. 5, Nov. 19, and Dec. 3.

Course Information

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.

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.

Course Schedule

Here is information on topics, readings, assignments, and labs. Small adjustments may be made during the term. The dates and topics for the class tests will not be changed.
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)
page 11: 1.1‑1, 1.1‑2, 1.1‑4, 1.1‑5
page 29: 2.2‑1, 2.2‑2, 2.2‑4
page 39: 2.3‑3 to 2.3‑7
pages 41‑42: 2‑3a,b; 2‑4a,b,c,d

(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
Pages 9-10 of the textbook present a good short introduction. Chapter 34 presents NP-completeness formally, in more detail than we need for this course. Focus on pages 1048‑1054 for an overview, and page 1067 for an introduction to reducibility.

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
pages 52‑53: 3.1‑1, 3.1‑2, 3.1‑3
page 60: 3.2‑1
pages 61‑62: 3‑2; 3‑4a,b,d,e

Lab on Permutations
Lab 1.pdf

Lab 1 Solution

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

Study problems for NP completeness

Lab on enumerating possibilities
Lab 2.pdf
Lab 2 Data

Lab 2 Solution

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

Lab 3 Solution

Test 1 October 8:
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

Solution, Part 1
Solution, Part 2

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
Solution Part 2

(There is no lab 6; the next one is lab 7)

Test 2 October 22:
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

Solution Part 1
Solution Part 2

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:
Prim's algorithm for minimum spanning tree, pages 634-635
Dijkstra's algorithm for single-source shortest-path, Section 24.3
Both of these algorithms use tree vertices and fringe vertices, with a greedy rule for choosing which fringe vertex to add to the tree next.

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

Solution Part 1
Solution Part 2
Solution Part 3

Test 3 November 5:
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

Solution Part 1
Solution Part 2
Solution Part 3

Test 4 November 19:
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:
Introduction to approximation algorithms, pages 1106-1108.
Section 35.1 Vertex cover example

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

Solution Part 1
Solution Part 2
Solution Part 3

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)
Test 5 December 3:
Branch and bound, Approximation Algorithms, NP-Completeness

Solutions to tests given in Fall 2010
Test 1 solution
Test 2 solution
Test 3 solution
Test 4 solution

Sample Tests (written by Prof. Robin Dawes)

Test 1 from 2008 (PDF)               Solutions

Test 2 from 2008 (PDF)               Solutions

Test 3 from 2008 (PDF)

Test 4 from 2008 (PDF)

Sample questions for Test 5 (PDF)