CS 201: Data Structures (Winter 2017)

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) [code]
2. 01/06 F	From Python to Java	Java classes (Appendix C), javadoc (Appendix A) [code]	hw00: Getting started
Week 2: lists; more Java
3. 01/09 M	Defining Classes	Inheritance (Appendix D, Java Interlude 7) [code] - 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) [code]
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) [code]
7. 01/18 W	5.0–5; 10.0–4 optional fairy tale	Stacks and Queues (Chapters 5 and 10) [code]	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) [code]	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) - Algorithmic complexity attacks and libc qsort()
14. 02/03 F	7.8–18,45–47	Recursion (Chapter 7) [code]	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) [code]	hw07: Sorting
16. 02/10 F	6.1–12	Stacks (Chapter 6) [code] - 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 [code]
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