CMSC 420 Data Structures, Syllabus - Draft 2019 Version

• 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.

• 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 here--V 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 non-binary trees
• k-ary trees
• extended k-ary trees
• Finish Shaffer 5: Applications of binary/extended binary trees
• Finish Shaffer 6: General Trees, equivalence classes, union-find, and left-child/right sibling representations
• Other topics in Shaffer include: randomized skip list; k-d trees; PR and PM quadtrees; AVL trees; splay trees; sorting/searching; closed and open hashing; spiral hashing; B tree family (2-3/red-black/B+tree/B* tree)
• This will be updated based on project choices---lecture 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.