Syllabus for CS 306, Computer Algorithms II

Fall 2007


The syllabus is broken up into three three-week sections and one six-week section.

  1. Introduction and Review

  2. Algorithm Analyses

  3. Algorithm Design

  4. Data Structures

The phrase "X through Y" means "from the beginning of X to the end of Y."

Pages marked with an asterisk (*) contain tclets displaying algorithm animations; the tclet browser plug-in must be installed in your browser to see the animations. Your browser should guide you through plug-in installation; if it doesn't you can get more information from the tclet plug-in page.

Section 1 – Introduction and Review, Tuesday, 4 September to Thursday, 20 September.

Readings
Nyhoff sections 2.4, 10.1 through 10.3

Class notes
Introduction
Dynamic Storage and C++
Dynamic Storage Management
Recursion Basics
Recursion in Practice

Assignment
Assignment 1 (last modified on 5 October 2007) available on Tuesday, 11 September; due on Tuesday, 25 September at 5:30 p.m.
A code review.
The grades.

Quiz - Tuesday, 25 September
The answers.
The grades.

Section 2 – Algorithm Analyses, Tuesday, 25 September to Thursday, 11 October.

Readings
Nyhoff sections 10.4, 10.6

Class notes
Program Measurement
Performance Estimation
Performance Estimation in Practice
Algorithm Correctness

Assignment
Assignment 2 (last modified on 12 October 2007) available on Tuesday, 25 September; due on Tuesday, 16 October at 5:30 p.m.
A code review.
The grades.

Quiz - Tuesday, 16 October
The answers.
The grades.

Section 3 – Algorithm Design, Tuesday, 16 October to Thursday, 1 November.

Mid-term grades due - 23 October

Class notes
Exhaustive Search
Heursitics
Greed
Divide and Conquer

Problem presentation
9 October, R. Clayton, Colinear points.
23 October, P. Rinaldi, Bowling.

Assignment
Assignment 3 (last modified on 31 October 2007) available on Tuesday, 16 October; due on Tuesday, 6 November at 5:30 p.m.
An example solution.
The grades.

Quiz - Tuesday, 6 November
The answers.
The grades.

Section 4 – Data Structures, Tuesday, 6 November to Tuesday, 11 December.

Drop day - 6 November

No class - Thanksgiving, 22 November

Readings
Nyhoff section 12.7, chapters 15 and 16

Class notes
Hashing Basics
Hashing In Practice
Trees
Balanced Trees
Graph Basics
Graph Algortihms

Problem presentations
8 November, S. Skwarek, Long Division.
13 November, D. Banks, Golf.
15 November, T. Perriello, Game.
20 November, J. Bacon, Testing the Catcher.
27 November, E. Carpouzis, Ulam.
29 November, V. Betancourth, Soccer.
4 December, A. Kaufman, Number Chains.
6 December, B. Codd, Typing.
11 December, A. Karpodinis, Floppies.
11 December, D. Alpaugh, Expanding Fractions.
11 December, B. Wallerstein, Clock Hands.

Assignment
Assignment 4a (last modified on 10 November 2007) available on Tuesday, 6 November; due on Tuesday, 27 November at 5:30 p.m.
Assignment 4b (last modified on 10 November 2007) available on Tuesday, 27 November; due on Tuesday, 11 December at 5:30 p.m.)

Quiz - Tuesday, 11 December

Open Lecture about tries at 5:30 to 7:30 p.m. on Tuesday, 18 December in HH C1.


This page last modified on 10 September 2007.