A systematic study of algorithms and their complexity, including searching and sorting algorithms, mathematical algorithms, scheduling algorithms, tree and graph traversal algorithms, P, NP, NP-complete and intractable problems. This course satisfies both the critical thinking and the quantitative reasoning requirements.

Essential Information:

Instructor:	Erik Steinmetz
E-mail:	steinmee@augsburg.edu
Office:	Sverdrup 203A
Phone:	(612) 330-1062
Class:	8:30 a.m. to 12 noon in Sverdrup 202
Dates:	9 September, 23 September, 7 October, 21 October, 4 November, 18 November, 2 December, 9 December
Text:	Introduction to Algorithms (2nd Edition); Cormen, Leiserson, Rivest & Stein
Office Hours:	6 p.m. to 8 p.m. Tuesday nights before a Weekend college session.  9 a.m. to 11 a.m. Saturday, October 28

Grading

There will be a mid-term and a final exam during the course, each counting for 30 percent of the grade. Graded homeworks will make up the remainder of the grade. All homeworks must be completed individually.

Schedule

Date	Topics	Chapter
9 September	Algorithm Analysis, Growth of Functions	Algorithms 1, 2, 3, 4
23 September	Sorting	Algorithms 6, 7, 8
7 October	Lists, Stacks, Queues and Hash Tables	Algorithms 10, 11
21 October	Review, Mid-term, Binary Search Trees	Algorithms 12
4 November	Dynamic Programming, Greedy Algorithms	Algorithms 15, 16
18 November	Graph Algorithms	Algorithms 22, 23, 24
2 December	NP-Completeness, Approximation Algorithms	Algorithms 34, 35
9 December	Review, Final	Algorithms

Assignments

Assignment	Date Due
Problems 2.1-3, 2.2-2, 2.2-3, 2-2, 3.1-2, 4.3-1, and 4.3-2	23 September
Problems 6.1-1, 6.1-5, 7.1-3, 7.1-4, 7.4-2, 8.2-1, 8.3-1, 8.4-1, 8.4-2   Implement a Heapsort using an array of int.	7 October
Problems 10-1, 11.3-4, 11.4-2, 12.1-3, 12.2-3, 12.3-1 Implement a Queue of ints using an array, checking for overflow or underflow on the enqueue and dequeue methods. Your examples in main must show that these methods work.	4 November
Problems 15.3-2, 16.1-1, 16.2-2 (implement in Java), and 16-1 Implement the fastest way and print stations algorithms from the Assembly Line problem in chapter 15, except using three assembly lines. You can start with this code.	18 November
Problems 22.1-2, 22.2-1, 22.2-2, 22.2-3, 22.3-1, 22.3-2, 24.3-2, and 24.3-4	2 December

Exam Schedule

The mid-term will be held during the middle 90 minutes of class on 21 October.

The final will be held during the final 120 minutes of class on 9 December.

Class Links

A zipped copy of the contents of the CD that comes with the book.

A copy of some sample code which prints out the contents of a heap.