CS 201: Data Structures (Winter 2018)

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.18w/

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. 01/03 W Introduction; Java basics (Appendix B)
[code]

2. 01/05 F From Python to Java Java classes (Appendix C), javadoc (Appendix A)
[code]
hw00: Getting started
Week 2: ADT and interface; lists

3. 01/08 M Defining Classes Java tutorial
- lab1: Python to Java
hw01: Java basics
4. 01/10 W D.0–9 Inheritance (Appendix D, Java Interlude 7)
[code]

Unit 1: Abstract Data Types

5. 01/12 F P.0–18 Interfaces (Prelude), Lists (Chapter 12), generics (Java Interlude 1)
[code]
hw02: Lunar lander
Week 3: stacks and queues

6. 01/15 M JI-1; JI-2 Exceptions (Java Interlude 2)
[code]

7. 01/17 W 12.1–2,9–10,14; 13.1–4 List implementation with an array (Chapter 13)
[code]
hw03: Zoo displayer
8. 01/19 F 5.0–5; 10.0–4
fairy tale Stacks and Queues (Chapters 5 and 10)
[code]

Week 4: graphs, maps, and sets; intro to complexity analysis

9. 01/22 M 28.0–11
fairy tale Graphs (Chapter 28)
[code]

10. 01/24 W 19.0–4; JI-5.0–7 Maps (Chapter 19), Sets, Iterators (Java Interlude 5)
[code]
hw04: Maze solver
Unit 2: Efficiency and Algorithms

11. 01/26 F 4.0–10; 8.8,14
fairy tale Efficiency and Sorting (Chapters 4 and 8)
Week 5: sorting and links

12. 01/29 M (none) Exam 1
13. 01/31 W 7.0–7; 9.10–14,23
fairy tale Recursive Sorting (Chapters 7 and 9)
- (This fairy tale is especially good!)

- optional math: lower bound analysis for comparison-based sorting

- optional math: average analysis for quick sort
hw05: Path finder
Unit 3: Implementation

14. 02/02 F 3.1–8; 14.0–6 Links, nested classes, linked list (Chapters 3 and 14)
[code]

- optional math: amortized analysis for adding to the end of an ArrayList

Week 6: recursion

15. 02/07 W 7.8–18,45–47
fairy tale Recursion (Chapter 7)
[code]

- VisuAlgo step-by-step visualizations of sorting

- toptal side-by-side comparisons of sorting

- Algorithmic complexity attacks and libc qsort()
hw06: Complexity
16. 02/09 F 6.1–12 Stacks (Chapter 6)
[code]

- lab2: Implement a Generic Linked Stack

Week 7: trees

17. 02/12 M 11.1–8 Queues (Chapter 11) hw07: Zoo displayer reprise
18. 02/14 W 23.1–11,22–24 Trees (Chapters 23 and 24)
- lab3: Construct Expression Trees

19. 02/16 F 23.29–32; 25.2–4,7–8
fairy tale Binary search trees (Chapter 25)
- optional math: average analysis for quick sort via BSTs
hw08: Queue recursor
Week 8: heaps

20. 02/19 M 25.19–28,40–43 Map and Set based on trees
[code]

21. 02/21 W 10.19; 23.33–35; 26.2–3,5–7,9–10
fairy tale Priority Queues; Heaps (Chapter 26) hw09: Code interpreter
22. 02/23 F (none) Exam 2
Week 9: hashing

23. 02/26 M 26.13–18; 27.0,13–14 Heap sort; Balanced search trees (Chapter 27)
- optional math: bulk adding to a heap

24. 02/28 W 21.0–12 (don't worry too much about 21.9) Balanced search trees; Hashing (Chapter 21) hw10: Heap builder
25. 03/02 F 21.13–24 Map and Set based on hashing (Chapter 22)
Week 10: graphs

26. 03/05 M 22.1–8 Hash code functions
- lab4: Compare Hash Code Functions
hw11: Cloud dreamer
27. 03/07 W 29.0–10 Graphs (Chapter 29)
- lab5: Graph Implementations

28. 03/09 F (none) Graphs; course wrap up hw12: Hashing
Final Exam: 03/14 Wednesday 12:00–14:30

Date	Read before class	Topics and textbook reference	Due 10pm after class
Unit 0: Introduction
Week 1: getting started with Java
1. 01/03 W		Introduction; Java basics (Appendix B) [code]
2. 01/05 F	From Python to Java	Java classes (Appendix C), javadoc (Appendix A) [code]	`hw00`: Getting started
Week 2: ADT and interface; lists
3. 01/08 M	Defining Classes	Java tutorial - `lab1`: Python to Java	`hw01`: Java basics
4. 01/10 W	D.0–9	Inheritance (Appendix D, Java Interlude 7) [code]
Unit 1: Abstract Data Types
5. 01/12 F	P.0–18	Interfaces (Prelude), Lists (Chapter 12), generics (Java Interlude 1) [code]	`hw02`: Lunar lander
Week 3: stacks and queues
6. 01/15 M	JI-1; JI-2	Exceptions (Java Interlude 2) [code]
7. 01/17 W	12.1–2,9–10,14; 13.1–4	List implementation with an array (Chapter 13) [code]	`hw03`: Zoo displayer
8. 01/19 F	5.0–5; 10.0–4 fairy tale	Stacks and Queues (Chapters 5 and 10) [code]
Week 4: graphs, maps, and sets; intro to complexity analysis
9. 01/22 M	28.0–11 fairy tale	Graphs (Chapter 28) [code]
10. 01/24 W	19.0–4; JI-5.0–7	Maps (Chapter 19), Sets, Iterators (Java Interlude 5) [code]	`hw04`: Maze solver
Unit 2: Efficiency and Algorithms
11. 01/26 F	4.0–10; 8.8,14 fairy tale	Efficiency and Sorting (Chapters 4 and 8)
Week 5: sorting and links
12. 01/29 M	(none)	Exam 1
13. 01/31 W	7.0–7; 9.10–14,23 fairy tale	Recursive Sorting (Chapters 7 and 9) - (This fairy tale is especially good!) - optional math: lower bound analysis for comparison-based sorting - optional math: average analysis for quick sort	`hw05`: Path finder
Unit 3: Implementation
14. 02/02 F	3.1–8; 14.0–6	Links, nested classes, linked list (Chapters 3 and 14) [code] - optional math: amortized analysis for adding to the end of an ArrayList
Week 6: recursion
15. 02/07 W	7.8–18,45–47 fairy tale	Recursion (Chapter 7) [code] - VisuAlgo step-by-step visualizations of sorting - toptal side-by-side comparisons of sorting - Algorithmic complexity attacks and libc qsort()	`hw06`: Complexity
16. 02/09 F	6.1–12	Stacks (Chapter 6) [code] - `lab2`: Implement a Generic Linked Stack
Week 7: trees
17. 02/12 M	11.1–8	Queues (Chapter 11)	`hw07`: Zoo displayer reprise
18. 02/14 W	23.1–11,22–24	Trees (Chapters 23 and 24) - `lab3`: Construct Expression Trees
19. 02/16 F	23.29–32; 25.2–4,7–8 fairy tale	Binary search trees (Chapter 25) - optional math: average analysis for quick sort via BSTs	`hw08`: Queue recursor
Week 8: heaps
20. 02/19 M	25.19–28,40–43	Map and Set based on trees [code]
21. 02/21 W	10.19; 23.33–35; 26.2–3,5–7,9–10 fairy tale	Priority Queues; Heaps (Chapter 26)	`hw09`: Code interpreter
22. 02/23 F	(none)	Exam 2
Week 9: hashing
23. 02/26 M	26.13–18; 27.0,13–14	Heap sort; Balanced search trees (Chapter 27) - optional math: bulk adding to a heap
24. 02/28 W	21.0–12 (don't worry too much about 21.9)	Balanced search trees; Hashing (Chapter 21)	`hw10`: Heap builder
25. 03/02 F	21.13–24	Map and Set based on hashing (Chapter 22)
Week 10: graphs
26. 03/05 M	22.1–8	Hash code functions - `lab4`: Compare Hash Code Functions	`hw11`: Cloud dreamer
27. 03/07 W	29.0–10	Graphs (Chapter 29) - `lab5`: Graph Implementations
28. 03/09 F	(none)	Graphs; course wrap up	`hw12`: Hashing
Final Exam: 03/14 Wednesday 12:00–14:30