Contributing Scholar - Sartaj Sahni, University of Florida

3 Semester Credit Hours

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.

Prerequisites

• One year of college-level calculus (NMTH 1111 and NMTH 1112)
• A course in linear algebra and differential equations (NMTH 2301)

• An undergraduate course in Discrete Mathematics (like NCSC 2201) covering sets, sequences, functions and relations, undirected and directed graphs, asymptotic notation for the running time of algorithms, (concept of proof, and techniques for constructing proofs (by contradiction, by induction)

• An undergraduate upper division or graduate course in algorithms and data structures (NCSC 3011) covering, at a minimum, topics such as: stacks, queues, heaps, trees, and graphs; sorting (insert, bubble, selection, heap, quick, and merge sort), searching, and hashing; elementary algorithm performance analysis; fundamental tree traversal methods such as inorder, preorder, and postorder; fundamental graph algorithms such as depth and breadth first traversal and shortest path algorithms; elementary algorithm performance analysis.

• Experience with programming in C++ or Java

• General prerequisite: Students must have the knowledge resulting from completing all coursework in the curriculum for a BS degree in Computer Science from a regionally-accredited institution in the United States or the equivalent from a foreign institution; performance level in this coursework should be equivalent to a cumulative undergraduate GPA of 2.9 or better on 4.0 scale
  

Course Objectives

To cover those data structures that are important in the development of efficient algorithms for a variety of applications.

Course Topics

The following topics will be covered in the order given.

• Amortized complexity
• External sorting
• Tournament trees
• Run generation
• Optimal merging of runs
• Buffering
• Double-ended priority queues
• Leftist trees
• Binomial heaps
• Fibonacci heaps
• Pairing heaps
• Dictionaries
• Optimal binary search trees
• AVL-trees
• AVL trees
• 2-3 and 2-3-4 trees
• Red-black trees: rank, join & split 
• B-trees
• Splay trees
• Binary tries
• Patricia
• Higher order tries
• Suffix trees
• Differential files
• Segment trees
• Priority search trees
• Multidimensional search trees
• Quad trees