This is a tentative syllabus for the course. Links will be added regularly with topics and assignments. Notes will be provided for each class, linked from the date. Unless otherwise indicated, references are to the textbook Data Structures & Algorithms in Java by Goodrich and Tamassia. Feedback is appreciated — typos, suggestions for more detailed explanations, additional examples, etc.
| Date | Problems | Techniques | References | Out | Due |
|---|---|---|---|---|---|
| Jan 5 | intro | course intro, Java basics | 1 | SA-0 | |
| Jan 7 | encapsulation | classes, instance variables, contructors, overloading | 2 | SA-1 | SA-0 |
| Jan 9 | inheritance | base classes, subclasses, overriding | SA-2 | SA-1 | |
| Jan 12 | graphics | buffered images, video | SA-3 | SA-2 | |
| Jan 14 | abstraction | abstract data types, asymptotic notation | 7.1 | PS-1 | SA-3 |
| Jan 16 | lists | linked list implementation | 3.2 | SA-4 | |
| Jan 19 | no class | MLK Day | |||
| Jan 21 | lists 2 | growing array implementation (no recitation) | 7.2, 3.1.1, 4-4.3, 7.4 | SA-4 | |
| Jan 23 | hierarchies | trees and recursion | 8 | PS-2 | PS-1 |
| Jan 27 | midterm 1 | 6:00pm - 8:00pm Cummings 100 | |||
| Jan 28 | hierarchies 2 | binary search trees | 11.1 | ||
| Jan 30 | hierarchies 3 | balance, 2-3-4 trees, red/black trees | 11.2, 11.5, 11.6 | SA-5 | PS-2 |
| Feb 2 | info retrieval | maps, sets | 10.1 | SA-6 | SA-5 |
| Feb 4 | hashing | hash functions, tables | 10.2 | SA-7 | SA-6 |
| Feb 6 | keeping order | stacks, queues | 6 | SA-8 | SA-7 |
| Feb 9 | prioritizing | priority queues, heaps | 9.1 - 9.4 | PS-3 | SA-8 |
| Feb 11 | relationships | graphs | 14.1, 14.2 | SA-9 | |
| Feb 13 | graph traversal | breadth- and depth-first search | 14.3 | PS-4 | SA-9 |
| Feb 16 | midterm 2 | 6:00pm - 8:00pm Cummings 100 | PS-3 | ||
| Feb 18 | shortest paths | Dijkstra's algorithm, A* search | 14.6 | ||
| Feb 20 | pattern matching | finite automata, finite state machines | |||
| Feb 23 | pattern recognition | hidden Markov models | PS-5 | PS-4 | |
| Feb 25 | web services | acronym soup (URL, REST, JSON, GUI) | Java tutorials | ||
| Feb 27 | client/server | sockets, threads | Java tutorials | ||
| Mar 2 | synchronization | synchronized blocks, monitors, semaphores | Java tutorials | PS-6 | PS-5 |
| Mar 4 | producer/consumer | streams | Java tutorials | ||
| Mar 6 | string finding | Boyer-Moore, tries, suffix trees | 13.2, 13.3 | ||
| Mar 9 | review | ask questions about the final exam | PS-6 | ||
| Mar 14 | final exam | 12-hour section 8:00am - 11:00am Cummings 100 | |||
| Mar 15 | final exam | 2-hour section 8:00am - 11:00am Cummings 100 |