Purpose of Course: The objective of this class is to study the fundamental data structures and algorithms used in computer science. Students will study advanced programming techniques and will learn to analyze the algorithms to determine their time and space requirements. We will also look at applications to graphics, vision, AI, databases, etc.

Text: Data Structures and Algorithm Analysis in C++, Mark A. Weiss, Benjamin Cummings Publishing Co., 1999 (Second Edition).

Topics to be Covered:

• Introduction: Data Structures, Abstraction, Induction, Recursion (Ch1)

• Algorithm Analysis (Ch 2)

• Review of Lists, Stacks, and Queues (Ch 3)

• Trees, Search Trees: Binary, AVL, Splay, B-trees (Ch 4)

• Hashing (Ch 5)

• Priority Queues: Heaps (Ch 6)

• Sorting: Mergesort, Quicksort, Decision Trees (Ch 7)

• Disjoint Sets: Union-Find (Ch 8)

• Graph Algorithms (Ch 9)

Evaluation: Roughly, Exercises 15%, Programs 35%, Midterm 25%, Final 25%.

Notes:

• Late exercise sets will be accepted only until the exercises are graded and returned to the class.

• Late programs will be accepted, but will lose points, 10% per week late. (The first 10% starts the day after the program is due.)

• Incompletes are only for students with a medical excuse; unfinished assignments do not constitute a medical excuse.

• All work turned in on exercises, programs, and exams must be entirely your own. Cheating will be reported to the Department, the Dean, the University, etc. Discussion of concepts is fine; copying of code or anything else is not. If you're not sure, ask me before you do it!

• I hope you enjoy the class.