


CMSC 420 Data Structures, Syllabus  Draft 2019 Version

Tentative Syllabus 
 by the end of the semester, we will have covered nearly all of the (required) shaffer text. we will also work our way through dave mount's notes on topics either not in shaffer or not well covered in shaffer. and, finally, we will draw from samet resources to discuss the dreaded quadtrees and other methods for dealing with spatial data.

Expected Order of Coverage (this may be changed without notice) 
 Review content of Shaffer 1, 2, and 3.
 Note: we do chapter 3 a bit differently than they do it in (351)
 We slip a little definition of graph G=(V,E) in hereV is set of vertices, E is set of edges, both of which are finite in this course.
 Review issues raised in Shaffer 4
 linked lists vs static lists vs java array lists(?)
 lists: queues/stacks/dequeues
 Joint coverage of Shaffer 5/6 Chapter on nonbinary trees
 kary trees
 extended kary trees
 Finish Shaffer 5: Applications of binary/extended binary trees
 Finish Shaffer 6: General Trees, equivalence classes, unionfind, and leftchild/right sibling representations
 Other topics in Shaffer include: randomized skip list; kd trees; PR and PM quadtrees; AVL trees; splay trees; sorting/searching; closed and open hashing; spiral hashing; B tree family (23/redblack/B+tree/B* tree)
 This will be updated based on project choiceslecture order is subject to the needs of the project, meaning that we will visit Shaffer 13 regularly, as well as Samet and Dave Mount as needed.
 Another possible topic is Fibonacci Heaps, constructed from Binomial heaps.

Return to main page.

