CS 221: Data Structures

Regular Course for Montana State Students

Spring 2005

Date	Lecture Topic	Reading	Graded Events
01/12 01/14	Return CS 160 Finals Software Design	1.1 - 1.4
01/17 01/19 01/21	Martin Luther King Day! Software Design Software Design	1.5 - 1.6 1.7 - 1.8
01/24 01/26 01/28	Program Correctness and Efficiency Program Correctness and Efficiency Program Correctness and Efficiency	2.1 - 2.3 2.4 - 2.5 2.6 - 2.8
01/31 02/02 02/04	Streams Inheritance and Class Hierarchies Inheritance and Class Hierarchies	A.10 3.1 - 3.3 3.4 - 3.5
02/07 02/09 02/11	Inheritance and Class Hierarchies Lists and the Collection Interface Lists and the Collection Interface	3.6 - 3.8 4.1 - 4.3 4.4
02/14 02/16 02/18	Lists and the Collection Interface Lists and the Collection Interface Lists and the Collection Interface	4.5 4.6 4.7 - 4.8
02/21 02/23 02/25	President's Day! Stacks Stacks	5.1 - 5.2 5.3
02/28 03/02 03/04	Stacks Review Midterm	5.4	Midterm (15%)
03/07 03/09 03/11	Return Midterms Queues Queues	6.1 - 6.2 6.3
03/14 03/16 03/18	Spring Break! Spring Break! Spring Break!
03/21 03/23 03/25	Queues Recursion University Day!	6.4 7.1
03/28 03/30 04/01	Recursion Recursion - Searching Recursion	7.2 7.3 7.4
04/04 04/06 04/08	Recursion Recursion - Mike Thiesen Sorting	7.5 7.6 10.1 - 10.2
04/11 04/13 04/15	Sorting Sorting Sorting	10.3 - 10.5 10.6, 10.10 10.7
04/18 04/20 04/22	Sorting Sorting Java 5.0	10.8 10.9
04/25 04/27 04/29	Java 5.0 Trees Review	8.1 - 8.3
05/05	Final, 8:00 a.m. - 9:50 a.m.		Final (25%)

Grading

40% of your grade comes from exams. 60% of your grade comes from the laboratory. To pass the course, you must average at least 50% on the exams. The final will not be given early.

Meeting Times

Lecture: Monday, Wednesday and Friday 9:00 a.m. - 9:50 a.m. in EPS 103.
Laboratory: Thursday 8:00 a.m. - 9:50 a.m. (section 3), 10:00 a.m. - 11:50 a.m. (section 4), or 1:10 p.m. - 3:00 p.m. (section 5) in EPS 110.

Textbooks

Objects, Abstraction, Data Structures and Design Using Java, by Koffman & Wolfgang.

Instructor

John Paxton. EPS 363. 994-5979. Office Hours: Monday 10:00 - 11:50, Wednesday 10:00 - 10:50, Friday 10:00 - 10:50 and by appointment.

Course Outcomes

At the end of the course, students should be able to

Understand the concept of an ADT.
Understand and be able to implement the list ADT.
Understand and be able to implement the stack ADT.
Understand and be able to implement the queue ADT.
Understand and be able to implement the priority queue ADT.
Be able to determine the time complexity of simple algorithms.
Understand and be able to implement several standard sorting techniques.
Understand and be able to implement linear and binary search.

Other Information

Last modified: April 28, 2005.