CS 201: Data Structures (Winter 2017)
[ Current Week ]
Basic Information
- Instructor: Jed Yang, Center for Math & Computing 324,
- Office hours: Monday 16:20–17:20 (in CMC 306), Thursday 14:35–15:35, Friday 13:00–14:00; or by appointment
- Lectures: 3a (MW 11:10–12:20, F 12:00–13:00) in Center for Math & Computing 301
- Course website: http://cs.carleton.edu/faculty/jyang/cs201.17w/
Resources
- Syllabus [PDF]
- Student Resources of the textbook, including electronic versions of appendices B, C, and E
- Java API
- Java style, which I expect you to follow
- Transition from Python to Java: by Lambert, by Miller
- Run Java on your computer, via a virtual machine, or from a USB drive
- Pair programming guidelines
Calendar
Weekly schedule below to be updated throughout the term; tentative and subject to change.Instructions regarding reading.
Date | Read before class | Topics and textbook reference | Due 10pm after class | |
---|---|---|---|---|
Unit 0: Introduction | ||||
Week 1: getting started with Java | ||||
1. 01/04 W | Introduction; Java basics (Appendix B) | |||
2. 01/06 F | From Python to Java | Java classes (Appendix C), javadoc (Appendix A) | hw00: Getting started | |
Week 2: lists; more Java | ||||
3. 01/09 M | Defining Classes | Inheritance (Appendix D, Java Interlude 7)
- lab01: Python to Java | hw01: Java lab | |
Unit 1: Primary ADTs | ||||
4. 01/11 W | P.1–18 | Interfaces (Prelude), Lists (Chapter 12), generics (Java Interlude 1) | ||
5. 01/13 F | JI-1; JI-2 | Implementing interface and using lists
- lab02: Plant a Garden | hw02: Lunar lander | |
Week 3: stacks, queues, and graphs | ||||
6. 01/16 M | 12.1–2,9–10,14; 13.1–4 | List implementation with an array (Chapter 13) | ||
7. 01/18 W | 5.0–5; 10.0–4
optional fairy tale | Stacks and Queues (Chapters 5 and 10) | hw03: Zoo displayer | |
8. 01/20 F | 28.0–11 | Graphs (Chapter 28) | ||
Week 4: intro to complexity analysis; midterm exam 1 | ||||
9. 01/23 M | 19.0–4; JI-5.0–7 | Maps (Chapter 19), Sets, Iterators (Java Interlude 5) | hw04: Maze solver | |
Unit 2: Efficiency and Algorithms | ||||
10. 01/25 W | 4.0–10
optional fairy tale | Efficiency (Chapter 4) | ||
11. 01/27 F | (none) | Midterm 1 | ||
Week 5: recursion and sorting | ||||
12. 01/30 M | 8.8,14,20–24; 9.20–23
optional fairy tale | Sorting (Chapters 8 and 9) (This optional fairy tale is especially good!) - VisuAlgo step-by-step visualizations of sorting - toptal side-by-side comparisons of sorting | hw05: Path finder | |
13. 02/01 W | 7.0–7; 9.10–14 | Recursive Sorting (Chapters 7 and 9) | ||
14. 02/03 F | 7.8–18,45–47 | Recursion (Chapter 7) | hw06: Complexity | |
Unit 3: Implementation | ||||
Week 6: links and stacks | ||||
15. 02/08 W | 3.1–8; 14.0–6 | Links, nested classes, linked list (Chapters 3 and 14) | hw07: Sorting | |
16. 02/10 F | 6.1–12 | Stacks (Chapter 6)
- lab03: Implement a Generic Linked Stack | ||
Week 7: queues and trees | ||||
17. 02/13 M | 11.1–8 | Queues (Chapter 11) | hw08: Zoo displayer reprise | |
18. 02/15 W | 23.1–11,22–24 | Trees (Chapters 23 and 24)
- lab04: Construct Expression Trees | ||
19. 02/17 F | 23.29–32; 25.2–4,7–8
optional fairy tale | Binary search trees (Chapter 25) | hw09: Queue recursor | |
Week 8: priority queues; midterm exam 2 | ||||
20. 02/20 M | 25.19–28,40–43 | Map and Set based on trees | ||
21. 02/22 W | 10.19; 23.33–35; 26.2–3,5–7,9–10
optional fairy tale | Priority Queues; Heaps (Chapter 26) | hw10: Code interpreter | |
22. 02/24 F | (none) | Midterm 2 | ||
Week 9: hashing | ||||
23. 02/27 M | 26.13–18; 27.0,13–14 | Heap sort; Balanced search trees (Chapter 27) | ||
24. 03/01 W | 21.0–12 (don't worry too much about 21.9) | Balanced search trees; Hashing (Chapter 21) | hw11: Heap builder | |
25. 03/03 F | 21.13–24 | Hash code functions, collisions
- lab05: Compare Hash Code Functions | ||
Week 10: graphs | ||||
26. 03/06 M | 22.1–8 | Map and Set based on hashing (Chapter 22) | hw12: Cloud dreamer | |
27. 03/08 W | 29.0–10 | Graphs (Chapter 29)
- lab06: Graph Implementations | ||
28. 03/10 F | (none) | Graphs; course wrap up | hw13: Hashing | |
Final Exam: 03/13 Monday 15:30–18:00 |