CSCI 151: Data Structures (Spring 2019)

Resources

Lab	Name	Assigned	Due
1	Java with Codingbat	Tue 1/15	Tue 1/22 @ 1pm
2	Prisoners’ Dilemma	Tue 1/22	Tue 1/29 @ 1pm
3	Extensible arrays	Tue 1/29	Tue 2/5 @ 1pm
4	Extensible arrays and dictionaries	Tue 2/5	Tue 2/12 @ 1pm
	Asymptotic Analysis
5	Sortimator	Tue 2/19	Tue 2/26 @ 1pm
6	Skip lists	Tue 2/26	Tue 3/5 @ 1pm
7	Two Towers	Tue 3/5	Tue 3/12 @ 1pm
	Binary trees
9	Ice cream store	Tue 3/26	Tue 4/2 @ 1pm
10	Tries and text prediction	Tue 4/9	Tue 4/16 @ 1pm
11	Hash table tic-tac-toe	Tue 4/16	Tue 4/23 @ 1pm

Project	Name	Assigned	Due
1	Java and Arrays	M 1/28	F 2/8
2	Adventure	W 3/27	F 4/19
3	Final project	F 4/19	T 5/7

T Jan 16 - W Jan 17: Intro to Java (caesar.py, Caesar.java)
F Jan 18: Classes & objects in Java
(FrequencyCounter, FrequencyMain)
W Jan 23: Extensible arrays I
(ExtensibleIntArray, ExtIntArrayTest)
F Jan 25: Extensible arrays II (ensureCapacity)
(ExtensibleIntArray2, ExtIntArray2Test)
M Jan 28: Interfaces and Inheritance
(Counter, LoudCounter, Tickish, CounterMain, ResettableCounter, InheritanceMain)
W Jan 30: Array Dictionaries
(ExtensibleArray, Association, ArrayDictionary)
F Feb 1: Generics
(GenericAssociation, GenericAsssociationDemo, GenericExtensibleArray, GenericArrayDictionary, GenericDictionaryDemo)
M Feb 4: Stacks (array-based)
(ArrayStack, StackTest)
W Feb 6: Java memory model
F Feb 8, M Feb 11: Stacks (linked)
(LinkedNode, LinkedStack)
W Feb 13: Asymptotic analysis, binary search
(BinarySearch)
F Feb 15: Binary search; sorting I (insertion sort)
M Feb 18: Comparable; sorting II (merge sort)
(ComparableDemo)
W Feb 20: Sorting III (merge sort analysis, quicksort)
F Feb 22: Queues I
M Feb 25: Linked Queues
(LinkedQueue)
W Feb 27: Iterators I
(IteratorDemo)
F Mar 1: Iterators II
(GenericExtensibleArray, ArrayIterDemo, Skiperator)
W Mar 27: Heaps
(Heap, HeapTest)
M Apr 24: Graphs
(Graph, GraphTest)

The exam will not cover iterators or binary trees.

Here are some sample exam questions:

Recall our implementation of a Dictionary using an extensible array of Associations.
- How does the get method work? In terms of big-O, how long does it take to run, and why?
- How does the put method work? How long does it take?
Suppose we use keys that are Comparable, and keep the array of Associations always sorted by key (instead of just being in the order we added them).
- How would this change the implementation and running time of get?
- How would it change the implementation and running time of put?
Explain how you would reverse a stack using only the public stack methods (push, pop, size, isEmpty).
Imagine trying to write a remove method for a linked stack implementation. See IntStack, ListIntNode, ListIntStack, RemoveTest.
- Implement the removeNext method in ListIntStack. Run RemoveTest.java to see if you have implemented it correctly.
- Now explain how the remove method works.