CSE 373: Data Structures and Algorithms

Winter 2000

Syllabus

 

Course Description

 

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.

 

Instructor

 

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

 

Lecture

 

MWF 11:30 – 12:20 in PAA A114

 

Textbook

 

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

 

·        Publisher’s Page

·        Author’s Page

·        Errata

·        On-line code

 

Data Structures and Algorithm Analysis in C++ (2nd edition)
Mark Allen Weiss
Addison Wesley, 1999

 

·        Publisher’s Page

·        Author’s Page

·        Errata

·        On-line code

 

Homework/programming assignments schedule and policy

 

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.

 

Grading policy

 

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.

 

Collaboration

 

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.

 

Tentative Schedule

 

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

 

 

Ask questions

 

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.