CS2984 Data Structures and Algorithms
Calendar and Coursenotes: Spring 2009

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, January 20: Course introduction
    Coursenotes: Slides 1-10
    Reading Assignment: Chapter 1
  • Thursday, January 22: Mathematical Background
    Coursenotes: Slides 11-27
    Reading Assignment: Chapter 2
• Week 2: Algorithm Analysis (Chapter 3)
  • Tuesday, January 27: Growth rates and Big-Oh notation
    Coursenotes: Slides 28-41
    Assignment Due: Initial schedule sheet for Project 1
  • Thursday, January 29: Analyzing programs; analyzing problems
    Coursenotes: Slides 42-61
    Reading Assignment: Chapter 3
• Week 3: Lists, Stacks, Queues (Chapter 4)
  • Tuesday, February 3: List implementations
    Coursenotes: Slides 62-87
    Assignment Due: Intermediate schedule sheet for Project 1
  • Thursday, February 5: Freelists, doubly linked lists, stacks, queues
    Coursenotes: Slides 88-105
    Reading Assignment: Chapter 4
• Week 4: Dictionary, Binary Trees
  • Tuesday, February 10: Dictionary, Binary Trees
    Coursenotes: Slides 106-121
    Assignment Due: Project 1 final submission
  • Thursday, February 12: Binary Tree Representations
    Coursenotes: Slides 122-139
    
• Week 5: Binary Trees: BST, Heap, Huffman Tree
  • Tuesday, February 17: Binary Search Trees, Heaps
    Coursenotes: Slides 140-155
    Assignment Due: Homework 1; Project 2 initial schedule sheet
  • Thursday, February 19: Huffman Trees
    Coursenotes: Slides 156-160
    Reading Assignment: Chapter 5
• Week 6: Midterm; General Trees
  • Tuesday, February 24: Midterm
    
  • Thursday, February 26: Discuss Midterm; General Trees, Union/Find
    Coursenotes: Slides 161-166
    Algorithm Visualization for Union/Find
    Reading Assignment: Sections 6.1 and 6.2
• Week 7: File Processing
  • Tuesday, March 3: Union/Find, Disks
    Assignment Due: Project 2 intermediate schedule sheet
    Coursenotes: Slides 167-169; 212-220
  • Thursday, March 5: Buffer Pools
    Coursenotes: Slides 221-235
    Reading Assignment: Sections 8.1 through 8.4
• Spring Break: 3/7-3/15
• Week 8: Hashing
  • Monday, March 16
    Project 2 early due date
  • Tuesday, March 17: Hash functions
    In-class lab: Hashing tutorial Sections 1-4 ( http://research.cs.vt.edu/algoviz/hashing/index.php)
    Assignment Due: Project 2
    
  • Thursday, March 19: Project 3, Memory managers, review buffer pools
    The in-class lab on hashing was postponed until next Tuesday
    
• Week 9: Hashing; Hashing Quiz; Self-organizing lists
  • Tuesday, March 24: Hashing: collision resolution
    Assignment Due: Project 3 initial schedule sheet
    
  • Thursday, March 26: Hashing Quiz; File processing in Java
    Class notes
• Week 10: Sorting
  • Tuesday, March 31: n² sorting algorithms, Shellsort
    Assignment Due: Project 3 intermediate schedule sheet
    Coursenotes: Slides 178-189
  • Thursday, April 2: n log n sorting algorithms: Quicksort and Mergesort
    Assignment Due: Homework 2
    Coursenotes: Slides 190-198
• Week 11: Sorting; Midterm 2
  • Monday, April 6: Early due date for Project 3
  • Tuesday, April 7: Heapsort, Radix Sort, Lower bounds on sorting problem
    Assignment Due: Project 3
    Coursenotes: Slides 199-211
    Algorithm Visualization for Radix Sort
    Reading Assignment: Chapter 7
  • Thursday, April 9: Midterm
• Week 12: Indexing
  • Tuesday, April 14: Indexing, 2-3 Trees, introduction to B-trees
    Assignment Due: Project 4 initial schedule sheet
    Coursenotes: Slides 279-295
    
  • Thursday, April 16: Classes cancelled
• Week 13: B-trees, Graphs
  • Tuesday, April 21: B+ Trees
    Coursenotes: Slides 296-302
    Reading Assignment: Chapter 10
  • Thursday, April 23: Graphs Representations, searches
    Coursenotes: Slides 303-317
    
• Week 14: Graphs
  • Tuesday, April 28: Graphs -- Topological Sort, Shortest Paths problems
    Coursenotes: Slides 318-330
    Assignment Due: Project 4 intermediate schedule sheet
    
  • Thursday, April 30: Graphs -- Minimal Cost Spanning Trees
    Coursenotes: Slides 331-337
    Reading Assignment: Chapter 11
• Week 15: Wrap up
  • Monday, May 4:
    Assignment Due: Project 4 Early due date
    
  • Tuesday, May 5: Wrap up, evaluations
    Assignment Due: Project 4
    
  • Thursday, May 7:
    Assignment Due: Homework 3
    
  • Friday, May 8: Final at 10:05-12:05 in the regular classroom.

Go to the CS2984 Homepage.