CS2984 Data Structures and Algorithms
Calendar and Coursenotes: Fall 2008
This page will show what we cover each day, including the course notes covered in class. The full course notes covered so far during the semester can always be found here.
Reading assignments are also posted for each week. The intention is that you will have finished the reading for that week by the end of the week (that is, typically you would be expected to read material after the associated lecture). However, some folks like to read it before the lecture, so I will try to get it up by the beginning of the week if I can.
- Week 1: Course Introduction, Mathematical Background
-
Tuesday, August 26: Course introduction.
Coursenotes: Slides 1-10
Reading Assignment: Chapter 1 -
Thursday, August 28: Mathematical Background, Project 1
Coursenotes: Slides 11-25
Reading Assignment: Chapter 2
-
Tuesday, August 26: Course introduction.
- Week 2: Algorithm Analysis (Chapter 3)
-
Tuesday, September 2: Growth rates and Big-Oh notation
Coursenotes: Slides 26-44
Assignment Due: Initial schedule sheet for P1 -
Thursday, September 4: Analyzing programs; analyzing problems
Coursenotes: Slides 45-59
Reading Assignment: Chapter 3
-
Tuesday, September 2: Growth rates and Big-Oh notation
- Week 3: Lists, Stacks, Queues (Chapter 4)
- Monday, September 8/Tuesday, September 9: P1 meetings with Dr. Shaffer
-
Tuesday, September 9: Array-based and linked lists
Coursenotes: Slides 60-84
Reading Assignment: Section 4.1 -
Thursday, September 11: Doubly linked lists; Stacks and Queues
Coursenotes: Slides 85-103
Reading Assignment: Chapter 4
- Week 4:
- Monday, September 15:
Project 1 early due date @ 11pm - Tuesday, September 16: Binary Trees
Coursenotes: Slides 104-119
Project 1 due @ 11pm - Thursday, September 18: Discuss Project 2; Binary Trees
Coursenotes: Slides 120-131
Reading Assignment: Chapter 5 through Section 5.3
- Monday, September 15:
- Week 5:
- Tuesday, September 23: Discuss Project 2; Binary Search Trees,
Heaps
Coursenotes: Slides 132-153
Homework 1 due @ 11pm
Project 2 initial schedule due @ 11pm
Reading Assignment: Sections 5.4, 5.5 - Thursday, September 25: Huffman Coding Trees
Course Notes: 154-158 Reading Assignment: Complete reading Chapter 5
- Tuesday, September 23: Discuss Project 2; Binary Search Trees,
Heaps
- Week 6: Midterm; P2 meetings; General Trees
- Tuesday, September 30: Midterm on Chapters 1-5
- Wednesday, October 1 -- Friday, October 10: P1 meetings with Dr. Shaffer
- Thursday, October 2: Midterms returned; Chapter 6: General trees
and Union/find
Course Notes: 159-167
- Tuesday, September 30: Midterm on Chapters 1-5
- Week 7: General trees; Sorting
- Tuesday, October 7: General tree representations; Insertion sort
Course Notes: 168-178
Union/Find applet
Reading Assignment: Chapter 6
- Thursday, October 9: n2 sorts, Shellsort
Course Notes: 179-187
- Tuesday, October 7: General tree representations; Insertion sort
- Week 8: Sorting
- Tuesday, October 14: Quicksort, Mergesort, Heapsort
Course Notes: 188-199
Project 2 due @ 11:00pm - Thursday, October 16: Binsort, Radix sort, empirical comparison;
Project 3 introduction
Course Notes: 200-206
Radix Sort Applet
- Tuesday, October 14: Quicksort, Mergesort, Heapsort
- Week 9: File Processing
- Tuesday, October 21: Lower bounds proof for sorting; Buffer
pools
Course Notes: 207-209; 223-233
Reading Assignment: Sections 8.3 and 8.4 - Thursday, October 23: Disk Drives
Course Notes: 210-222
Reading Assignment: Sections 8.1 and 8.2
- Tuesday, October 21: Lower bounds proof for sorting; Buffer
pools
- Week 10: External Sorting; Searching
- Tuesday, October 28: External Sorting
Course Notes: 234-252
Reading Assignment: Chapter 8 - Thursday, October 30: Searching
Course Notes: 253-272
Reading Assignment: Section 9.1
- Tuesday, October 28: External Sorting
- Week 11: Hashing
- Tuesday, November 4: Hash functions
Hashing Tutorial Sections 1-4 - Thursday, November 6: Collision resolution and deletion
Hashing Tutorial Sections 5-8:
- Tuesday, November 4: Hash functions
- Week 12: Searching, Indexing
- Tuesday, November 11: Hashing quiz; Self-organizing search
Courses Notes: 273-276
Reading Assignment: Chapter 9 through Section 9.3
Homework 2 due @ 11:00pm - Thursday, November 13: Indexing, Linear Indexing, 2-3 Trees, B-Trees
Course Notes: 277-292
Reading Assignment: Chapter 10 through Section 10.4
2-3 Tree Visualization: Data Structures Visualization
- Tuesday, November 11: Hashing quiz; Self-organizing search
- Week 13: B-trees, Graphs
- Tuesday, November 18: B-trees
Course Notes: 293-300
Reading Assignment: Chapter 10 - Thursday, November 20: Graph Representations
Course Notes: 301-315
Reading Assignment: Chapter 11 through Section 11.3.2
- Tuesday, November 18: B-trees
- Week 14: Graphs
- Tuesday, December 2: Topological Sort, shortest paths
Course Notes: 316-328
Reading Assignment: Chapter 11 through Section 11.4
- Thursday, December 4: Minimal Cost Spanning Trees; Discuss final; Course Evaluations
Course Notes: 329-335
Reading Assignment: Chapter 11
- Tuesday, December 2: Topological Sort, shortest paths
- Week 15: No Class
- Monday, December 8: Early due date for Project 4.
- Tuesday, December 9: NO CLASS. Project 4 regular due date.
- Thursday, December 11: Homework 3 due.
- Final: Wednesday, December 17 at 2:05-4:05 in the regular classroom. 230 points total.
Go to the CS2984 Homepage.