Course Syllabus

Computer Science 282 Advanced Data Structures

Course Description: An exploration of advanced data structures (particularly persistent structures) using object-oriented design. An introduction to databases using Java. Course reviews main-memory data structures such as hash tables and trees. Disk-based structures such as persistent hash tables and indexed files. Architectural foundations for files, large scale sorting and serialization.

Please check the web page http://www.coc.cc.ca.us/departments/comp_sci/ferguson/cs282 each week for:

Required Text:

Grading: Grading will be based on the following breakdown:

Quiz 1 10% 20 points
Midterm 20% 40 points
Quiz 2 10% 20 points
Final 30% 60 points
Project 1 10% 20 points
Project 2 10% 20 points
Project 3 10% 20 points Needed Point Totals: A – 175 points, B – 150 points, C – 120 points, D – 100 points

NO, NO, NO Laptops, cell phones or Ipod/MP3 players are to be used during class lectures. Laptops may ONLY be used during lab time. Surfing the Internet during class time is reserved for class related web sites. EBay, chat rooms, sports sites and other non class related surfing is strictly prohibited. Violations of these rules may result in a penalty reduction of points.

Important Dates:

Please be sure to avoid scheduling conflicts with these dates.
Student Learning Outcomes:
 1) Evaluate advanced data structures and algorithms with an emphasis on persistence.
2) Analyze data structure impact on algorithms, program design and program performance.

Course Outline

  1. Review of Data Structures, Databases, RAM vs. Disk Memory, Persistant Data Structures, Speed vs. Space
  2. Review of Hash Tables, Hash tables on disk, The bucket approach, Index file approach (2 files required)
  3. Review of Binary Trees, Trees vs. Binary Trees, Binary Search Trees, Storing Binary Trees as Disk files (two approaches)
  4. Red-Black Trees, RAM based, Balanced vs. unbalanced trees, Rotations, Insertions, Deletions
  5. 2-3-4 Trees and external storage (disk files), Search, Insertion, Node splits
  6. Heaps, Heap Sort, Trickle down
  7. Graphs, Edges and vertices, Searching, Breadth-First, Depth-First, Minimum Spanning Trees
  8. Weighted Graphs, Shortest path, Dijkstra's algorithm, Shortest path
  9. When to use what - Review of data structure choices