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:

Steve Wolfman		Mon 11:30-12:30, Fri 3:30-4:30	Sieg 226d
Zasha Weinberg		Mon 2:30-3:30 Sieg 226d, Tues 2:30-3:30 226d
Nic Bone		Thu 11:30-12:20 Sieg 226b, Fri 12:30-1:20 226a

Lecture: MWF 1:30-2:20

Week at-a-glance:

		Monday	Tuesday	Wednesday	Thursday	Friday
9:30					Section AA AND 008
10:00
10:30
11:00
11:30		Steve office hours SIG 226d			Nic office hours SIG 226b
12:00
12:30						Nic office hours SIG 226a
1:00
1:30		Lecture EE1 037		Lecture EE1 037		Lecture EE1 037
2:00
2:30		Zasha office hours SIG 226d	Zasha office hours SIG 226d		Section AB LOW 117
3:00
3:30						Steve office hours SIG 226d
4:00

Computing Resouces:

Sieg PC Labs

Math Sciences PC Lab

Evaluation:

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

Important Dates:

Midterm		Friday, February 4
Martin Luther King Day		Monday, January 17
Presidents Day		Monday, February 21
Final Exam		Monday, March 13, 2:30-4:20 pm

Approximate Course Schedule:

week of ...		topic	reading
Jan 3		introduction, review (stacks, queues, lists, trees)	(Chapters 1 & 3)
Jan 10		asymptotic analysis	(Chapter 2)
Jan 17 (19)		priority queues	(Chapter 6)
Jan 24		binary search trees, self-balancing trees	(Chapter 4)
Jan 31		catch-up, midterm
Feb 7		B-Trees, Multi-D trees	(Chapter 4)
Feb 14		hashing	(Chapter 5)
Feb 21 (23)		sorting	(Chapter 7)
Feb 28		disjoint set union-find	(Chapter 8)
Mar 6		graphs, wrap-up	(Chapter 9)

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).

• 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!