Description:

In this class we'll be studying a number of fundamental data structures and algorithms used in computer programming. An emphasis will be placed on data structures and algorithms that are of practical value, though more esoteric ones will also be considered. Students will analyze each concept covered in the course to understand its strengths and weaknesses, and to understand applications for which it would be appropriate. By the end of the course, students should have the skills necessary for selecting between existing data structures and algorithms, and for designing their own.

Text:

Mark Allen Weiss' Data Structures and Algorithm Analysis in C++ (second edition), Addison-Wesley (1999)

Office hours:

Bart Niswonger		Whenever the door is open & Mon 11:50-12:50, Wed 1:30-2:30	Sieg 226D
Ashish Sabharwal		Tue 10:50-11:50 in Sieg 226B, or by appointment

Lecture:

MWF 10:50-11:50

Week at-a-glance:

	Monday	Tuesday	Wednesday	Thursday	Friday
9:50
10:50	Lecture EE1 037	Ashish Office Hours Sieg 226B	Lecture EE1 037	Section GUG 410	Lecture EE1 037
11:50	Bart Office Hours Sieg 226D
12:50
1:50			Bart Office Hours (1:30-2:30) Sieg 226D
2:50

Computing Resouces:

Sieg PC Labs

Campus Labs

Evaluation (Tentative):

Written Assignments		25%
Programming Assignments		25%
Midterm		20%
Final Exam		20%
Best of these, extra		10%

Important Dates:

Midterm		Wednesday, July 18
Independence Day		Wednesday, July 4
Final Exam		Friday, August 17, 10:50-11:50 am

Approximate Course Schedule:

week of ...		topic	reading
June 18		introduction, review (stacks, queues, lists), priority queues, heaps	(Chapters 3 & 6)
June 25		asymptotic analysis	(Chapters 1 & 2)
July 2		priority queues & heaps, trees	(Chapters 6 & 4)
July 9		binary search trees, self-balancing trees	(Chapter 4)
July 16		B-Trees, AVL Trees, midterm	(Chapter 4)
July 23		hashing, disjoint set union-find	(Chapters 5 & 8)
July 30		advanced ADTs, sorting	(Chapter 12 & 7)
August 6		sorting, graphs	(Chapters 7 & 9)
August 13		algorithm design, wrap-up, final	(Chapter 10)

Assignments:

• Language: GNU C++; all programming work is expected to work with g++ on the instructional UNIX machines
• Schedule: Homeworks will normally be due at the beginning of class on the due date; projects will be due at 10PM on the due date. For the purposes of late days, Friday to Monday is one day (regardless of holidays), holidays are considered normal days.
• Late Policy: Homework assignments which arrive late will receive no credit. For projects, each student has four late days to dispose of over the course of the quarter. Projects can be late without penalty as long as all students in the project group have sufficient remaining late days (so, one project could be late four days or four could be late one day each over the quarter). You must contact TAs if you will be using late days. After the late days have been used, late projects will receive no credit. We may be flexible if you contact us before the project due date. So, tell us if you're having trouble!
• Collaboration: Collaboration on assignments is permitted and encouraged provided that the following rules are followed:
• Each student has spent at least 10 minutes working on each problem independently before collaborating with others.
• Cooperation must be limited to group discussion and brainstorming. No written or electronic material may be exchanged or leave the brainstorming session.
• After collaborating, each student must take a half-hour break from the problem. Watching some brainless TV is a recommended activity.
• Each student must write up their own solution independently, using their own words to prove that they understand the problem on their own.

Any deviation from these rules will be considered cheating. If you are uncertain as to what is or is not reasonable collaboration, please contact the instructor.

Note that some projects may be explicitly assigned to teams rather than individuals.

• Cheating: Cheating will not be tolerated and will result in university disciplinary action and a failing grade in the course. If you are having problems understanding or keeping up with the material, please contact me to discuss how we can fix the problem. Don't cheat!