CSE 373: Data Structures and Algorithms
Winter 2000
Syllabus
In this class we’ll cover a fairly broad sampling of fundamental data structures and algorithms used in everyday computer programming. We’ll examine the strengths, weaknesses, and practical uses of each new concept. The intent of the class is to equip each of you with a solid set of tools and skills necessary for choosing or designing appropriate data structures and algorithms used in programming.
Gary Kimura (GaryKi@cs.washington.edu)
Sieg Hall 419, 206-543-9298
Office Hours: MWF 1:00 to 2:00 or by appointment
Teaching Assistants
Sun Liang (SunLiang@cs.washington.edu)
Office Hours and Location: Tue 12:30 to 1:30 MSCC and Wed 4:30 to
5:30 Sieg 226a
Kenneth Ka-Wai Tam (KTam@cs.washington.edu)
Office Hours and Location: Mon 10:30 to 11:30 MSCC and Tue 2:30
to 3:30 Sieg 226a
MWF 11:30 – 12:20 in PAA A114
The textbook for the class is “Data Structures and Algorithm Analysis” by Mark Allen Weiss. There are various versions of the book. I will be using the one in “C”, however you should be able to follow along in the class using the “C++” version.
Data Structures and Algorithm
Analysis in C (2nd edition)
Mark Allen Weiss
Addison Wesley, 1997
· Errata
Data Structures and Algorithm
Analysis in C++ (2nd edition)
Mark Allen Weiss
Addison Wesley, 1999
· Errata
There will be approximately 7 homework assignments and 3 programming assignments throughout the quarter, each due on a Friday at the start of class.
Late homework assignments will not be accepted; however, your lowest homework assignment score will be ignored. Also, late programming assignments will not be accepted; however, we will try and give you two weeks to complete each programming assignment.
When submitting your homework assignments please be sure to stable all the pages together, and include your name and student ID # on all the pages. This is just cheap insurance on your part that the homework you turn in will be graded and credited to you accordingly. Also clarity and neatness does count, because if we have trouble understanding your homework it is difficult for us to assign it a grade.
Your programming assignments can be done in either C or C++. It is your choosing. And you can either use the Math Science Computing Center or your own machine. Note that we will be providing sample test data for some of the programs, so please plan accordingly if you use your own machine and coordinate this with either the TA’s or myself. Because we are not requiring a specific programming platform we will not be using electronic turn-in. Instead please submit the following items:
· A stapled printout of the program code
· Sample output on the provided test data
We reserve the right to request a demonstration of any program.
Clarity and neatness still counts, probably more so on the programming assignments than the homework assignments.
This is all tentative but the general goal is to have the final grade computed from the homework assignments, programming assignments, mid-term exams, and final exam according to the following percentages.
20% of grade 7 homework assignments (6 highest count)
20% of grade 3 programming assignments
30% of grade 2 mid-term exams
30% of grade 1 final exam
As the quarter progresses these percentages might change.
Helping one another to understand the course material and the assignments is permitted and encouraged because it can help each of you learn the material in a way that working in isolation cannot. However, the homework that you turn in must be your own.
Please note that this is a tentative class schedule and with the exception of holidays will probably change slightly as the quarter progresses.
Monday Lecture |
Wednesday Lecture |
Friday Lecture |
Jan 3 Class introduction & overview |
Jan 5 (Chapter 2) Algorithm Analysis |
Jan 7 (Chapter 3) Linked Lists Homework #1 |
Jan 10 (Chapter 3) Stacks |
Jan 12 (Chapter 3) Queues |
Jan 14 (Chapter 4) Trees (Introduction) Homework #2 |
Jan 17 MLK Day |
Jan 19 (Chapter 4) Trees (Binary) |
Jan 21 (Chapter 4) Trees (Balanced) Program #1 |
Jan 24 Midterm review and Catch-up |
Jan 26 Midterm exam #1 |
Jan 28 (Chapter 5) Hashing (Introduction) Homework #3 |
Jan 31 (Chapter 5) Hashing (Collision handling) |
Feb 2 (Chapter 5) Hashing (Applications) |
Feb 4 (Chapter 6) Heaps (Introduction) Homework #4 |
Feb 7 (Chapter 6) Heaps (Applications & leftist) |
Feb 9 (Chapter 7) Sorting (Insertion & bubble) |
Feb 11 (Chapter 7) Sorting (Shell & heap) Program #2 |
Feb 14 (Chapter 7) Sorting (Merge & quick) |
Feb 16 (Chapter 7) Sorting (External & radix again) |
Feb 18 Midterm review and Catch-up Homework #5 |
Feb 21 Presidents Day |
Feb 23 Midterm exam #2 |
Feb 25 (Chapter 9) Graphs (Introduction) Homework #6 |
Feb 28 (Chapter 9) Graphs (Traversal & paths) |
Mar 1 (Chapter 9) Graphs (Minimum spanning tree, acyclic/cyclic) |
Mar 3 (Chapter 9) Graphs (Sparse matrix) Homework #7 |
Mar 6 (Chapter 10) Algorithm classifications |
Mar 8 Review |
Mar 10 Wrap-up and evaluations Program #3 |
|
Mar 15 Final Exam 2:30 – 4:20 |
|
Please do not hesitate to ask questions either in class or during office hours. I want each of you to learn the material and enjoy the class. To do this I really need your feedback in the form of questions and opinions.