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 6 | intro | course intro, Java basics | 1 | SA-0 | |
| Jan 8 | encapsulation | classes, instance variables, contructors, overloading | 2 | SA-1 | SA-0 |
| Jan 10 | inheritance | base classes, subclasses, overriding | SA-2 | SA-1 | |
| Jan 13 | graphics | buffered images, video | SA-3 | SA-2 | |
| Jan 15 | abstraction | abstract data types, asymptotic notation | 7.1 | PS-1 | SA-3 |
| Jan 17 | lists | linked list implementation | 3.2 | SA-4 | |
| Jan 20 | no class | MLK day | |||
| x-hour | lists 2 | growing array implementation | 7.2, 3.1.1, 4-4.3, 7.4 | SA-4 | |
| Jan 22 | hierarchies | trees and recursion | 8 | PS-2 | PS-1 |
| Jan 24 | hierarchies 2 | binary search trees | 11.1 | ||
| Jan 27 | midterm review | ask questions about midterm 1 | |||
| Jan 28 | midterm 1 | 6:00pm - 8:00pm Cummings 100 | |||
| Jan 29 | hierarchies 3 | balance, 2-3-4 trees, red/black trees (no recitation) | 11.2, 11.5, 11.6 | SA-5 | PS-2 |
| Jan 31 | info retrieval | maps, sets | 10.1 | SA-6 | SA-5 |
| Feb 3 | hashing | hash functions, tables | 10.2 | SA-7 | SA-6 |
| Feb 5 | keeping order | stacks, queues | 6 | SA-8 | SA-7 |
| Feb 7 | prioritizing | priority queues, heaps | 9.1 - 9.4 | PS-3 | SA-8 |
| Feb 10 | relationships | graphs | 14.1, 14.2 | SA-9 | |
| Feb 12 | graph traversal | breadth- and depth-first search | 14.3 | SA-9 | |
| Feb 14 | shortest paths | Dijkstra's algorithm, A* search | 14.6 | PS-4 | PS-3 |
| Feb 17 | midterm review | ask questions about midterm 2 | |||
| Feb 18 | midterm 2 | 6:00pm - 8:00pm Cummings 100 | |||
| Feb 19 | pattern matching | finite automata, finite state machines | |||
| Feb 21 | pattern recognition | hidden Markov models | PS-5 | PS-4 | |
| Feb 24 | web services | acronym soup (URL, REST, XML, GUI) | Java tutorials | ||
| Feb 26 | client/server | sockets, threads | Java tutorials | ||
| Feb 28 | synchronization | synchronized blocks, monitors, semaphores | Java tutorials | PS-6 | PS-5 |
| Mar 3 | producer/consumer | streams | Java tutorials | ||
| Mar 5 | string finding | Boyer-Moore, tries, suffix trees | 13.2, 13.3 | ||
| Mar 7 | final exam review | ask questions about the final exam | PS-6 | ||
| tbd | final exam | 12-hour section location tbd | |||
| tbd | final exam | 2-hour section location tbd |