THE TEXTBOOK

Algorithm Design,
Michael T. Goodrich and Roberto Tamassia
John Wiley & Sons, 2002 (0-471-38365-1)

This course provides an introduction to algorithm analysis, abstract data types, and data structures. Topics include lists, queues, priority queues, trees, and graphs. The impact of these structures on algorithm design is explored. External memory management is discussed.

See "Course policies" below for details on testing and grading.

Upon completion of this course, students will:

1. Understand how to analyze algorithms.
2. Be able to apply the following basic data structures (among others) to solve problems:
   1. Stacks
   2. Queues
   3. Lists
   4. Trees
3. Understand how merge, quick, bucket, and radix sorts work.
4. Be able to apply the greedy method, divide-and-conquer, and dynamic programming to algorithm design.
5. Understand the nature and uses of graph structures.

Assessment will be by means of quizzes and exams, as specified below.

Students should always read their assignments and come to class prepared to discuss and/or work on the material. Each student may be absent twice without penalty. Each additional two absences without a medical excuse (no others are acceptable) will cost the student three points on the course grade.

Grades will be based upon 3 quizzes (worth 10% each) and 2 exams (worth 20% each) and a final (worth 30%).

See the Course Schedule for details.



Students who plagiarize tests and projects will receive zeros for the work in question, with no makeup opportunities.

COURSE SCHEDULE

CAUTION: COURSE SCHEDULE SUBJECT TO CHANGE WITHOUT WARNING!

---

DATE	TOPIC	ASSIGNMENT
Tues Aug 31	Methodologies	Read Ch. 1.1
Thurs Sept 2	Asymptotic Notation	Read Ch. 1.2
	Homework due Sept 7:	R-1.2, 1.3, 1.7, 1.10, 1.11, 1.12, 1.27
Tues Sept 7	Math Review	Read Ch. 1.3
Thurs Sept 9	Two Prefix Averages Algorithms	Read Ch. 1.4
Tues Sept 14	Amortization and Experimentation	Read Ch. 1.5, 1.6
Thurs Thurs 16	Review and Quiz #1
Tues Sept 21	Stacks & Queues; Vectors	Read Ch. 2.1, 2.2.1
Thurs Sept 23	Lists & Sequences	Read Ch. 2.2.2, 2.2.3
	Homework due Oct 7:	R-2.1, 2.2, 2.5, 2.8, 2.10, 2.11, 2-19
Tues Sept 28	Trees	Read Ch. 2.3
Thurs Sept 30	Priority Queues & Heaps	Read Ch. 2.4
Tues Oct 5	Dictionaries & Hash Tables	Read Ch. 2.5
Thurs Oct 7	Review for Exam
Tues Oct 12	COLUMBUS DAY -- NO CLASS
Thurs Oct 14	Exam #1
Tues Oct 19	Ordered Dictionaries & Binary Search Trees	Read Ch. 3.1
Thurs Oct 21	AVL & Bounded-Depth Trees	Read Ch. 3.2, 3.3
	Homework due Oct 28:	R-3.1, 3.2, 3.3, 3.5, 3.7, 3.11, 3.15
Tues Oct 26	Splay Trees & Skip Lists	Read Ch. 3.4, 3.5
Thurs Oct 28	Review and Quiz #2
	Drop Date:  After Nov 3 you cannot drop the course without getting a grade.  No W or L!
Tues Nov 2	Merge-Sort & The Set ADT	Read Ch. 4.1, 4.2
	Homework due Nov 11:	R-4.1, 4.2, 4.5, 4.9, 4.11, 4.17
Thurs Nov 4	Quick-Sort & Lower Bounds	Read Ch. 4.3, 4.4
Tues Nov 9	Buckets, Radices, & Selection	Read Ch. 4.5, 4.6, 4.7
Thurs Nov 11	Review for Exam
Tues Nov 16	Exam #2
Thurs Nov 18	The Greedy Method	Read Ch. 5.1
Tues Nov 23	Divide and Conquer	Read Ch. 5.2
	Homework due Dec 2:	R-5.1, 5.3, 5.5, 5.7
Wed Nov 24 -- Fri Nov 26	Thanksgiving Vacation
Tues Nov 30	Dynamic Programming	Read Ch. 5.3
Thurs Dec 2	Review & Quiz #3
Tues Dec 7	Graphs	Read Ch. 6.1, 6.2
	Homework due Dec 9:	R-6.1, 6.2, 6.3
Thurs Dec 9	Graph Traversal	Read Ch. 6.3
Mon Dec 13	FINAL EXAMS BEGIN
EXAM DAY	FINAL EXAM

Syllabus last modified April 29, 2010.