Next:
1. Introduction
Data Structures and Algorithms
CONTENTS
1. Introduction
1.1 Some Definitions
1.1.1 Four Fundamental Data Structures
1.2 Complexity of Algorithms
1.2.1 Big Oh Notation
1.2.2 Examples
1.2.3 An Example: Complexity of Mergesort
1.2.4 Role of the Constant
1.2.5 Worst Case, Average Case, and Amortized Complexity
1.2.6 Big Omega and Big Theta Notations
1.2.7 An Example:
1.3 To Probe Further
1.4 Problems
2. Lists
2.1 List Abstract Data Type
2.1.1 A Program with List ADT
2.2 Implementation of Lists
2.2.1 Array Implementation of Lists
2.2.2 Pointer Implementation of Lists
2.2.3 Doubly Linked List Implementation
2.3 Stacks
2.4 Queues
2.4.1 Pointer Implementation
2.4.2 Circular Array Implementation
2.4.3 Circular Linked List Implementation
2.5 To Probe Further
2.6 Problems
2.7 Programming Assignments
2.7.1 Sparse Matrix Package
2.7.2 Polynomial Arithmetic
2.7.3 Skip Lists
2.7.4 Buddy Systems of Memory Allocation
3. Dictionaries
3.1 Sets
3.2 Dictionaries
3.3 Hash Tables
3.3.1 Open Hashing
3.4 Closed Hashing
3.4.1 Rehashing Methods
3.4.2 An Example:
3.4.3 Another Example:
3.5 Hashing Functions
3.5.1 Division Method
3.5.2 Multiplication Method
3.5.3 Universal Hashing
3.6 Analysis of Closed Hashing
3.6.1 Result 1: Unsuccessful Search
3.6.2 Result 2: Insertion
3.6.3 Result 3: Successful Search
3.6.4 Result 4: Deletion
3.7 Hash Table Restructuring
3.8 Skip Lists
3.8.1 Initialization:
3.9 Analysis of Skip Lists
3.9.1 Analysis of Expected Search Cost
3.10 To Probe Further
3.11 Problems
3.12 Programming Assignments
3.12.1 Hashing: Experimental Analysis
3.12.2 Skip Lists: Experimental Analysis
4. Binary Trees
4.1 Introduction
4.1.1 Definitions
4.1.2 Preorder, Inorder, Postorder
4.1.3 The Tree ADT
4.1.4 Data Structures for Tree Representation
4.2 Binary Trees
4.3 An Application of Binary Trees: Huffman Code Construction
4.3.1 Implementation
4.3.2 Sketch of Huffman Tree Construction
4.4 Binary Search Tree
4.4.1 Average Case Analysis of BST Operations
4.5 Splay Trees
4.5.1 Search, Insert, Delete in Bottom-up Splaying
4.6 Amortized Algorithm Analysis
4.6.1 Example of Sorting
4.6.2 Example of Tree Traversal (Inorder)
4.6.3 Credit Balance
4.6.4 Example of Incrementing Binary Integers
4.6.5 Amortized Analysis of Splaying
4.7 To Probe Further
4.8 Problems
4.8.1 General Trees
4.8.2 Binary Search Trees
4.8.3 Splay Trees
4.9 Programming Assignments
4.9.1 Huffman Coding
4.9.2 Comparison of Hash Tables and Binary Search Trees
4.9.3 Comparison of Skip Lists and Splay Trees
5. Balanced Trees
5.1 AVL Trees
5.1.1 Maximum Height of an AVL Tree
5.1.2 AVL Trees: Insertions and Deletions
5.2 Red-Black Trees
5.2.1 Height of a Red-Black Tree
5.2.2 Red-Black Trees: Insertions
5.2.3 Red-Black Trees: Deletion
5.3 2-3 Trees
5.3.1 2-3 Trees: Insertion
5.3.2 2-3 Trees: Deletion
5.4 B-Trees
5.4.1 Definition of B-Trees
5.4.2 Complexity of B-tree Operations
5.4.3 B-Trees: Insertion
5.4.4 B-Trees: Deletion
5.4.5 Variants of B-Trees
5.5 To Probe Further
5.6 Problems
5.6.1 AVL Trees
5.6.2 Red-Black Trees
5.6.3 2-3 Trees and B-Trees
5.7 Programming Assignments
5.7.1 Red-Black Trees and Splay Trees
5.7.2 Skip Lists and Binary search Trees
5.7.3 Multiway Search Trees and B-Trees
6. Priority Queues
6.1 Binary Heaps
6.1.1 Implementation of Insert and Deletemin
6.1.2 Creating Heap
6.2 Binomial Queues
6.2.1 Binomial Queue Operations
6.2.2 Binomial Amortized Analysis
6.2.3 Lazy Binomial Queues
6.3 To Probe Further
6.4 Problems
6.5 Programming Assignments
6.5.1 Discrete Event Simulation
7. Directed Graphs
7.1 Directed Graphs
7.1.1 Data Structures for Graph Representation
7.2 Shortest Paths Problem
7.2.1 Single Source Shortest Paths Problem: Dijkstra's Algorithm
7.2.2 Dynamic Programming Algorithm
7.2.3 All Pairs Shortest Paths Problem: Floyd's Algorithm
7.3 Warshall's Algorithm
7.4 Depth First Search and Breadth First Search
7.4.1 Breadth First Search
7.5 Directed Acyclic Graphs
7.5.1 Test for Acyclicity
7.5.2 Topological Sort
7.5.3 Strong Components
7.6 To Probe Further
7.7 Problems
7.8 Programming Assignments
7.8.1 Implementation of Dijkstra's Algorithm Using Binary Heaps and Binomial Queues
7.8.2 Strong Components
8. Undirected Graphs
8.1 Some Definitions
8.2 Depth First and Breadth First Search
8.2.1 Breadth-first search of undirected graph
8.3 Minimum-Cost Spanning Trees
8.3.1 MST Property
8.3.2 Prim's Algorithm
8.3.3 Kruskal's Algorithm
8.4 Traveling Salesman Problem
8.4.1 A Greedy Algorithm for TSP
8.4.2 Optimal Solution for TSP using Branch and Bound
8.5 To Probe Further
8.6 Problems
8.7 Programming Assignments
8.7.1 Implementation of Some Graph Algorithms
8.7.2 Traveling Salesman Problem
9. Sorting Methods
9.1 Bubble Sort
9.2 Insertion Sort
9.3 Selection Sort
9.4 Shellsort
9.5 Heap Sort
9.6 Quick Sort
9.6.1 Algorithm:
9.6.2 Algorithm for Partitioning
9.6.3 Quicksort: Average Case Analysis
9.7 Order Statistics
9.7.1 Algorithm 1
9.7.2 Algorithm 2
9.7.3 Algorithm 3
9.8 Lower Bound on Complexity for Sorting Methods
9.8.1 Result 1: Lower Bound on Worst Case Complexity
9.8.2 Result 2: Lower Bound on Average Case Complexity
9.9 Radix Sorting
9.10 Merge Sort
9.11 To Probe Further
9.12 Problems
9.13 Programming Assignments
9.13.1 Heap Sort and Quicksort
10. Introduction to NP-Completeness
10.1 Importance of NP-Completeness
10.2 Optimization Problems and Decision Problems
10.3 Examples of some Intractable Problems
10.3.1 Traveling Salesman Problem
10.3.2 Subset Sum
10.3.3 Knapsack Problem
10.3.4 Bin Packing
10.3.5 Job Shop Scheduling
10.3.6 Satisfiability
10.4 The Classes
P
and
NP
10.5 NP-Complete Problems
10.5.1 NP-Hardness and NP-Completeness
10.6 To Probe Further
10.7 Problems
11. References and Resources
11.1 Primary Sources for this Lecture Notes
11.2 Useful Books
11.3 Original Research Papers and Survey Articles
11.4 Web Resources
About this document ...
Next:
1. Introduction
eEL,CSA_Dept,IISc,Bangalore
