CS 201: Data Structures (Spring 2018)
[ 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: 6a (MW 15:10–16:20, F 15:30–16:30) in Center for Math & Computing 301
- Course website: http://cs.carleton.edu/faculty/jyang/cs201.18s/
Course Information
Think back to your favorite assignment from Introduction to Computer Science. Did you ever get the feeling that "there has to be a better/smarter way to do this problem"? The Data Structures course is all about how to store information intelligently and access it efficiently. How can Google take your query, compare it to billions of web pages, and return the answer in less than one second? How can one store information so as to balance the competing needs for fast data retrieval and fast data modification? To help us answer questions like these, we will analyze and implement stacks, queues, trees, linked lists, graphs, and hash tables.- Textbook: Data Structures and Abstraction with Java, 4th edition, Frank Carrano and Timothy Henry, 2015.
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
Daily/weekly schedule to be updated throughout the term; topics, readings, and exam dates are 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. 03/26 M | Introduction; Java basics (Appendix B) | |||
| 2. 03/28 W | From Python to Java | Java classes (Appendix C), javadoc (Appendix A) | hw00: Getting started | |
| 3. 03/30 F | Defining Classes | Java tutorial
- lab1: Python to Java | hw01: Java basics | |
| Week 2: ADT and interface; lists | ||||
| 4. 04/02 M | D.0–9 | Inheritance (Appendix D, Java Interlude 7) | ||
| Unit 1: Abstract Data Types | ||||
| 5. 04/04 W | P.0–18 | Interfaces (Prelude), Lists (Chapter 12), generics (Java Interlude 1) | hw02: Lunar lander | |
| 6. 04/06 F | JI-1; JI-2 | Exceptions (Java Interlude 2) | ||
| Week 3: stacks, queues, graphs | ||||
| 7. 04/09 M | 12.1–2,9–10,14; 13.1–4
[note]
The textbook uses 1-based indexing for Lists and 0-based indexing for arrays. This is silly and unimportant. Do not dwell on this point.
| List implementation with an array (Chapter 13) | hw03: Zoo displayer | |
| 8. 04/11 W | 5.0–5; 10.0–4
fairy tale | Stacks and Queues (Chapters 5 and 10) | ||
| 9. 04/13 F | 28.0–11
fairy tale | Graphs (Chapter 28) | ||
| Week 4: maps and sets; intro to complexity analysis | ||||
| 10. 04/16 M | 19.0–4; JI-5.0–7 | Maps (Chapter 19), Sets, Iterators (Java Interlude 5) | hw04: Maze solver | |
| Unit 2: Efficiency and Algorithms | ||||
| 11. 04/18 W | 4.0–10; 8.8,14
fairy tale | Efficiency and Sorting (Chapters 4 and 8)
- VisuAlgo step-by-step visualizations of sorting - toptal side-by-side comparisons of sorting | ||
| 12. 04/20 F | (none) | Exam 1 | ||
| Week 5: recursion and sorting | ||||
| 13. 04/23 M | 7.0–7; 9.10–14,23
fairy tale | Recursive Sorting (Chapters 7 and 9)
- (This fairy tale is especially good!) - Algorithmic complexity attacks and libc qsort() - optional math: lower bound analysis for comparison-based sorting | hw05: Path finder | |
| 14. 04/25 W | 7.8–18,45–47
fairy tale | Recursion (Chapter 7) | ||
| Unit 3: Implementation | ||||
| 15. 04/27 F | 3.1–8; 14.0–6 | Links, nested classes, linked list (Chapters 3 and 14)
- optional math: amortized analysis for adding to the end of an ArrayList | hw06: Complexity | |
| Week 6: stacks and queues | ||||
| 16. 05/02 W | 6.1–12 | Stacks (Chapter 6)
- lab2: Implement a Generic Linked Stack | ||
| 17. 05/04 F | 11.1–8 | Queues (Chapter 11) | hw07: Zoo displayer reprise | |
| Week 7: trees | ||||
| 18. 05/07 M | 23.1–9,22–24 | Trees (Chapters 23 and 24)
- lab3: Construct Expression Trees | ||
| 19. 05/09 W | 23.10–11,29–32; 25.2–4,7–8
fairy tale | Binary search trees (Chapter 25) | hw08: Queue recursor | |
| 20. 05/11 F | 25.19–28,40–43 | Map and Set based on trees | ||
| Week 8: heaps | ||||
| 21. 05/14 M | 10.19; 23.9,33–35; 26.2–3,5–7,9–10
fairy tale | Priority Queues; Heaps (Chapter 26) | hw09: Code interpreter | |
| 22. 05/16 W | (none) | Exam 2 | ||
| 23. 05/18 F | 26.13–18; 27.0,13–14 | Heap sort; Balanced search trees (Chapter 27) |
[note]
Department webserver is down for maintenance 5:30pm to 6:30pm on Friday 5/18.
| |
| Week 9: hashing | ||||
| 24. 05/21 M | 21.0–12
[note]
Don't worry too much about 21.9.
| Balanced search trees; Hashing (Chapter 21) | hw10: Heap builder | |
| 25. 05/23 W | 21.13–24 | Map and Set based on hashing (Chapter 22) | ||
| 26. 05/25 F | 22.1–8 | Hash code functions
- lab4: Compare Hash Code Functions | hw11: Cloud dreamer | |
| Week 10: graphs | ||||
| 27. 05/28 M | 29.0–10 | Graphs (Chapter 29)
- lab5: Graph Implementations | ||
| 28. 05/30 W | (none) | Graphs; course wrap up | hw12: Hashing | |
| Final Exam: 06/02 Saturday 12:00–14:30 | ||||