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:
Weekly Lecture Topics - Reading Assignments - Project Assignments and Deadlines
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.
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.
Review of Data Structures, Databases, RAM vs. Disk Memory, Persistant Data
Structures, Speed vs. Space
Review of Hash Tables, Hash tables on disk, The bucket approach, Index
file approach (2 files required)
Review of Binary Trees, Trees vs. Binary Trees, Binary Search Trees, Storing
Binary Trees as Disk files (two approaches)
Red-Black Trees, RAM based, Balanced vs. unbalanced trees, Rotations, Insertions,
2-3-4 Trees and external storage (disk files), Search, Insertion, Node
Heaps, Heap Sort, Trickle down
Graphs, Edges and vertices, Searching, Breadth-First, Depth-First, Minimum
Weighted Graphs, Shortest path, Dijkstra's algorithm, Shortest path
When to use what - Review of data structure choices