COSC 160: Data Structures
Instructor
Jeremy Bolton: Teaching and Research
Course Calendar
Syllabus
Books
Recommended Texts:
- [Dz] Drozdek, Data Structures and Algorithms in C++, 4th, Cengage, 2013
- [Cm] Cormen et al, Introduction to Algorithms, 3rd, MIT Press, 2009
Math Methods Review
- [Hk] Hammack, Book of Proof, MOOT, 2013
Topic Schedule
Please feel free to use and modify any of my slides. Please acknowledge when appropriate.
The following schedule is sequentially organized by topics and subject to change.
We will cover approximately 1 topic per week, but this will vary.
SEE CANVAS FOR SUBMISSION AND DUE DATES
| Topic | Topic/notes | Readings | Assignments, etc. |
|---|---|---|---|
| 0 | Introduction and Overview [ppt | pdf ] |
||
| 1 | What is Data and How is it encoded [ppt | pdf ] |
[Dz] 2.1 - 2.9, 9.1 | |
| 2 | Complexity Analysis: Examples with Sort and Search[ppt | pdf ] |
[Dz] 1.1 - 1.9, 5.1 - 5.8 [Cm] 2.1, 2.2, 2.3 , 3.1, 3.2 [Cm] 4.3, 4.4 [Hk] 4: Direct Proofs [Hk] 9: Disproving [Hk] 10: Induction |
Assignment #1 [sol] |
| 3 | Structure for Efficiency [ppt | pdf ] Ex: Lists  |
[Dz] 3.1-3.3 | Assignment #2 [sol] |
| 4 | Dynamic and Circular Arrays [ppt | pdf ] and Queues [ppt | pdf ]  |
[Dz] 4.1 - 4.2 [Cm] 10.1, 10.2 |
|
| 5 | Ordering for Efficiency and Self-Organizing Structures [ppt | pdf ] |
[Dz] 3.5, 9.3.4 (MergeSort) | Project #1 poisson_huge uniform_huge poisson_rand uniform_rand |
| Review Quiz | |||
| 5.5 | Matrices and Sparse Matrices [ppt | pdf ]  |
[Dz] 3.6 Sahni |
Assignment #3 [sol] Project #2 Polynomials PDF |
| 6 | General Trees and Traversals [ppt | pdf ]  |
[Dz] 6.1-6.6 [Cm] 10.4 |
Assignment #4 [sol] |
| 7 | Binary Trees and BSTs [ppt | pdf ]  |
[Dz] 6.1-6.6 [Cm] 12.1-12.3 |
|
| 8 | Heaps and Heap Sort [ppt | pdf ] 
| [Dz] 6.9, 9.3.2 [Cm] 6.1 - 6.5 |
Project #3 |
| Exam #1 | Previous Exam | Assignment #5 [exemplar sol] |
|
| 9 | AVL Trees [ppt | pdf ]  |
[Dz] 6.7 | |
| 10 | B-Trees [ppt | pdf ]  |
[Dz] 7.1 [Cm] 18.1 - 18.3 |
Assignment #6 [exemplar sol] Project #4 |
| 11 | Hash Tables[ppt | pdf ]  |
[Dz] 10.1 - 10.6 [Cm] 11.1 - 11.4 |
|
| 12 | Radix Sort[ vid ] |
Assignment #7 [exemplar sol] Project #5 (extra credit) |
|
| 13 | Graphs Part 1 [ppt | vid ] Part 2[pdf ]  |
[Dz] 8.1 - 8.4 [Cm] 22.1 - 23.3, 24.1 - 24.3 |
|
| 13 | TBA |
TBA | |
| Exam #2 | Previous Exam |