CS 102: Data Structures
Spring, 2007
Schedule
Class MWF 1:20-2:35 , Lab Wednesday, 4:00-6:00
Jan 22 Introduction
24 Java review Weiss, Ch 1, MBS narrative Ch 1-4
24 - Lab The Marine Biology Simulation MBS code and documentation (read over narrative, Ch. 1-4)
swap roles swap code
29 Java review Weiss, Ch.2 - 4 Quiz 1: Weiss, Ch 1-2
- arrays and ArrayList
31 Java review
- inheritance and composition
- template pattern Dancing example Dancing code
31 - Lab Template Pattern for Fish
Feb 5 Java review - strategy pattern Quiz 2: Weiss, Ch 3-4
7 Analysis of Algorithms Weiss, Ch. 5, 5.1-8
7 - Lab Strategy Pattern for Fish
12 Analysis of Algorithms Weiss, Ch. 5, 5.5-8
14 Sequential and Binary Search complexity Quiz 3: Weiss, Ch. 5
14 - Lab Database operations with complexity
19 Recursion Weiss, Ch. 7, 7.1-7.3 Recursion NestedRect, Recursion Broccoli, Broccoli Role-play
21 Recursion, divide-and-conquer Weiss, Ch. 7, 7.4-5, 7.7
Recursion, back-tracking
21 - Lab Lab 5 -- recursive solution to the Maze Lab 5 code and info
26 Collections, iterator pattern, Lists Weiss, Ch .6, 6.1-6.3, 6.5 (skip 6.4)
Sets Quiz 5 : Weiss, Ch. 7
28 Collections, Sets and Maps Ch. 6, 6.5, 6.7-6.8 (skip 6.6) Set example, Map example
28 - Lab Lab 6 -- an email directory code for lab 6 SetPractice, MapPractice
SetPracticeSoln, MapPracticeSoln
Mar 5 Sets and Maps Quiz 4 : Weiss, Ch. 6
7 Exam 1 oldExam1 oldExam2
7 - Lab No new lab
March 10-20 Break
19 No Class
21 Sorting, insertion, selection Ch. 8, 8.1-8.3, 8.6, 8.8
Quicksort Sort demos 1 Sort demos2 Sort demos 3
21 - Lab Lab 7 -- Comparing sorts
26 Shellsort, mergesort Ch. 8, 8.4-8.5 Quiz 6 (W. Ch 8) due
lower bounds
28 Stack, Queue, Priority Queue Ch. 6, 6.6, 6.9 ParensCheckerExample
28 - Lab Design exercise CRC cards, class diagrams
Apr 2 Applications of ADTs Ch. 11, 11.1-11.2 Quiz 7 (W. 6.6, 6.9) due
infix to postfix InfixToPostfixToVal
4 Application of ADTs - Character counts and priority queues Quiz 8 (W. 11.1, 11.2) due
Application of data structures to ski hill design Maze
4 - Lab Lab 8 Ski hill, start genericStackQueuePQ
9 Implementing ADTs, stacks Ch 16, 16.1, 16.2
queues with linked lists stack example and code
11 Implementing ADTs, linked lists Ch 17 17.1 Quiz 9 (W. Ch 16, 16.1 - 16.2) due
11 - Lab Lab 8 Ski hill, complete
16 A linked list class Ch 17, 17.2, 17.3 Circular Linked List solution
18 Priority Queues and minHeaps Ch 21, 21.1, 21.2
Heapsort Ch 21, 21.3, 21.5 Heapsort demo
18 - Lab Lab 9 Implementing an ADT using linked lists Lab 9 code
23 Exam 2 solutions old exam1, old exam2, (note- no graphs this time)
25 Binary trees tree examples Ch. 18, 18.2-18.3
Binary trees Huffman code
25 - Lab Lab 10 Expression tree
30 Binary search trees, TreeSet Ch. 19, 19.1, 19.3 animation
May 2 Hash tables Quiz 10 (W. Ch 18 & 19) due
2 - Lab Finish Hash tables, review for final
May 7, 9:00 - 11:00 Final Exam