BITM Data Structure and Algorithm with Java

Computational and Asymptotic Complexity. Big-O Notation. Properties of Big-O Notation Ω and Q. Possible Problems. Examples of Complexities. Finding Asymptotic Complexity: Examples. The Best, Average, and Worst Cases. Amortized Complexity. NP-Completeness.

Singly Linked Lists: Insertion, Deletion, Search. Doubly Linked Lists: Circular Lists, Skip Lists, Self-Organizing Lists. Sparse Tables. Case Study: A Library.

Stacks, Queues, Priority Queues. Case Study: Existing a Maze.

Recursive Definitions. Method Calls and Recursion Implementation. Anatomy of a Recursive Call. Tail Recursion. Nontail Recursion. Indirect Recursion. Nested Recursion. Excessive Recursion. Backtracking.

Trees, Binary Trees, and Binary Search Trees. Implementing Binary Trees. Searching a Binary Search Tree. Tree Traversal. Breadth-First Traversal. Depth-First Traversal. Insertion, Deletion, Deletion by Merging, Deletion by Copying. Balancing a Tree. The DSW Algorithm. AVL Trees. Self-Adjusting Trees. Self-Restructuring Trees, Splaying. Heaps: Heaps as Priority Queues, Organizing Arrays as Heaps, Polish Notation and Expression Trees. Operations on Expression Trees. Case Study: Computing Word Frequencies.

The Family of B-Trees. B-Trees, B*-Trees, B+-Trees. Case Study: Spell Checker.

Graph Representation. Graph Traversals, Shortest Paths, All-to-All Shortest Path Problem, Cycle Detection. Spanning Trees. Connectivity. Connectivity in Undirected Graphs, Connectivity in Directed Graphs. Topological Sort, Networks.

Elementary Sorting Algorithms: Insertion Sort, Selection Sort, Bubble Sort. Efficient Sorting Algorithms: Heap Sort, Quicksort, Mergesort, Radix Sort. Case Study: Adding Polynomials.

Hash Functions: Division, Folding, Mid-Square Function, Extraction. Collision Resolution: Open Addressing, Chaining, Bucket Addressing, Deletion. Case Study: Hashing with Buckets.