NCSC-8011 Advanced Data
Structures (AD
711)
Course Description: The course develops efficient data
structures used to obtain more efficient solutions to classical problems,
such as those based on graph theoretical models, as well as problems that
arise in application areas of contemporary interest.
Course Prerequisites: NCSC 8011 is an advanced graduate course. Students should ensure
they meet the following prerequisites before registering for NCSC
8011:
- An upper division undergraduate data structures and algorithms course
equivalent to NCSC- 3011. Such a course should cover sequential and linked
representation, stacks, queues, trees, and graphs. Fundamnetal sorting
algorithms such as insert, bubble, selection, heap, quick, and merge sort.
Fundamental tree traversal methods such as inorder, preorder, and
postorder. Fundamental graph algorithms such as deph- and breadth-first
traversal and shortest past algorithms.
- An undergraduate discrete math course equivalent to NCSC-2201. Such a
course should cover proof methods (induction, contradiction, etc.),
asymptotic analysis (big Oh, Omega, and Theta), simple counting results
such as the sum of first n integers, etc.
- Students should be proficient in the prerequisite material at a
performance level of B or better.
Course Objectives: To cover those data structures that
are important in the development of efficient algorithms for a variety of
applications.
Course Outline by Topical Areas:
- Amortized complexity
- External sorting
- Tournament trees and k-way merging
- Run generation
- Optimal merging of runs
- Buffering
- Double-ended priority queues
- Leftist trees
- Binomial heaps
- Fibonacci heaps
- Pairing heaps
- Binary search trees
- Optimal binary search trees
- AVL-trees
- 2-3 and 2-3-4 trees
- Red-black trees
- B-trees
- Splay trees
- Binary trees
- Higher order trees
- Suffix trees
- Differential files
- Segment trees
- Priority search trees
- Multidimensional search trees
- Quad trees
|
