Data Structures

Table of Contents
Session 1: Basic Concepts
1.1: How do we solve a problem on a computer?
1.2: What is a data structure?
1.3: What is an algorithm?
1.4: Implementing ADT's
1.4.1: The contiguous or sequential design
1.4.2: The linked design
1.5: Putting it all together: formulating a solution to the ESP
Summary
Exercises
Session 2: Mathematical Preliminaries
2.1: Mathematical notations and elementary functions
2.1.1: Floor, ceiling and mod functions
2.1.2: Polynomials
2.1.3: Exponentials
2.1.4: Logarithms
2.1.5: Factorials
2.1.6: Fibonacci numbers
2.2: Sets
2.3: Relations
2.4: Permutations and Combinations
2.4.1: Rule of sum and rule of product
2.4.2: Permutations
2.4.3: Combinations
2.5: Summations
2.5.1: Arithmetic series
2.5.2: Geometric series
2.5.3: Harmonic series
2.5.4: Miscellaneous sums
2.6: Recurrences
2.7: Methods of proof
2.7.1: Proof by mathematical induction
2.7.2: Proof by contradiction (reductio ad absurdum)
2.7.3: Proof by counterexample
Summary
Exercises
Session 3: Algorithms
3.1: Communicating an algorithm
3.1.1: The EASY assignment statement
3.1.2: The EASY unconditional transfer statements
3.1.3: The EASY conditional transfer statements
3.1.4: The EASY iteration statements
3.1.5: The EASY input/output statements
3.1.6: The EASY declaration statements
3.1.7: The EASY control statements
3.1.8: EASY program structure
3.1.9: Sample EASY procedures
3.2: Analyzing an algorithm
3.2.1: Analysis of insertion sort
3.2.2: Asymptotic notations
3.2.3: The O-notation
3.2.4: The Ω-notation
3.2.5: The Θ-notation
3.2.6: The preponderance of the O-notation
3.2.7: Comparative growth of functions
3.2.8: Complexity classes
Summary
Exercises
Session 4: Stacks
4.1: Sequential implementation of a stack
4.1.1: Implementing the auxiliary operations
4.1.2: Implementing the insert operation
4.1.3: Implementing the delete operation
4.1.4: A Pascal implementation of the array representation of a stack
4.1.5: A C implementation of the array representation of a stack
4.2: Linked list inplementation of a stack
4.2.1: Implementing the auxiliary stack operations
4.2.2: Implementing the insert operation
4.2.3: Implementing the delete operation
4.2.4: A Pascal implementation of the linked list representation of a stack
4.2.5: A C implementation of the linked list representation of a stack
4.3: Application of stacks
4.3.1: A simple pattern recognition problem
4.3.2: Conversion of arithmetic expressions from infix to postfix form
4.4: Sequential implementation of multiple stacks
4.4.1: The coexistence of two stacks in a single array
4.4.2: The coexistence of three or more stacks in a single array
4.4.3: Reallocating memory at stack overflow
Summary
Exercises
Session 5: Queues and Deques
5.1: Sequential implementation of a straight queue
5.1.1: Implementing the insert operation
5.1.2: Implementing the delete operation
5.2: Sequential implementation of a circular queue
5.2.1: Implementing the insert and delete operations for a circular queue
5.2.2: A C implementation of the array representation of a circular queue
5.3: Linked list implementation of a queue
5.3.1: Implementing the insert operation
5.3.2: Implementing the delete operation
5.3.3: A C implementation of the linked list representation of a queue
5.4: Application of queues: topological sorting
5.5: The deque as an abstract data type
5.6: Sequential implementation of a straight deque
5.6.1: Implementing the insert operation
5.6.2: Implementing the delete operation
5.7: Sequential implementation of a circular deque
5.7.1: Implementing the insert and delete operations for a circular deque
5.8: Linked list implementation of a deque
5.8.1: Implementing the insert and delete operations
Summary
Exercises
Session 6: Binary trees
6.1: Definitions and related concepts
6.2: Binary tree traversals
6.3: Binary tree representation in computer memory
6.4: Implementing the traversal algorithms
6.4.1: Recursive implementation of preorder and postorder traversal
6.4.2: Iterative implementation of preorder and postorder traversal
6.4.3: Applications of the traversal algorithms to other operations on binary trees
6.5: Threaded binary trees
6.5.1: Finding successors and predecessors in a threaded binary tree
6.5.2: Traversing inorder threaded binary trees
6.5.3: Growing threaded binary trees
6.5.4: Similarity and equivalence of binary trees
6.6: Traversal by link inversion
6.7: Siklossy traversal
Summary
Exercises
Session 7: Applications of binary trees
7.1: Calculating conveyance losses in an irrigation network
7.2: Heaps and the heapsort algorithm
7.2.1: Sift-up: converting a complete binary tree into a heap
7.2.2: The heapsort algorithm of Floyd and Williams
7.3: Priority queues
7.3.1: Unsorted array implementation of a priority queue
7.3.2: Sorted array implementation of a priority queue
7.3.3: Heap implementation of a priority queue
Summary
Exercises
Session 8: Trees and forests
8.1: Definition and related concepts
8.2: Natural correspondence
8.3: Forest traversal
8.4: Linked representation for trees and forests
8.5: Sequential representation for trees and forests
8.5.1: Representing trees and forests using links and tags
8.5.2: Arithmetic tree representations
8.6: Trees and the equivalence problem
8.6.1: The equivalence problem
8.6.2: Degeneracy and the weighting rule for union
8.6.3: Path compression: the collapsing rule for find
8.6.4: Analysis of the union and find operations
8.6.5: Final solution to the equivalence problem
Summary
Exercises
Session 9: Graphs
9.1: Some pertinent definitions and related concepts
9.2: Representation of graphs
9.2.1: Adjacency matrix representation of a graph
9.2.2: Adjacency lists representation of a graph
9.3: Graph traversals
9.3.1: Depth first search
9.3.2: Breadth first search
9.4: Some classical applications of DFS and BFS
9.4.1: Identifying directed acyclic graphs
9.4.2: Topological sorting
9.4.3: Finding the strongly connected components of a digraph
9.4.4: Finding articulation points and biconnected components of a connected undirected graph
9.4.5: Determining whether an undirected graph is acyclic
Summary
Exercises
Session 10: Applications of graphs
10.1: Minimum-cost spanning trees for undirected graphs
10.1.1: Prim's algorithm
10.1.2: Kruskal's algorithm
10.2: Shortest path problems for directed graphs
10.2.1: Dijkstra's algorithm for the SSSP problem
10.2.2: Floyd's algorithm for the APSP problem
10.2.3: Warshall's algorithm and transitive closure
Summary
Exercises
Session 11: Linear lists
11.1: Linear Lists
11.2: Sequential representation of linear lists
11.3: Linked representation of linear lists
11.3.1: Straight singly-linked linear list
11.3.2: Straight singly-linked linear list with a list head
11.3.3: Circular singly-linked linear list
11.3.4: Circular singly-linked linear list with a list head
11.3.5: Doubly-linked linear lists
11.4: Linear lists and polynomial arithmetic
11.5: Linear lists and multiple-precision integer arithmetic
11.5.1: Integer addition and subtraction
11.5.2: Integer multiplication
11.5.3: Representing long integers in computer memory
11.5.4: EASY procedures for multiple-presicion integer arithmetic
11.6: Linear lists and dynamic storage management
11.6.1: The memory pool
11.6.2: Sequential-fit methods: reservation
11.6.3: Sequential-fit methods: liberation
11.6.4: Buddy-system methods: reservation and liberation
11.7: Linear lists and UPCAT processing
11.7.1: Determining degree program qualifiers within a campus
11.7.2: Implementation issues
11.7.3: Sample EASY procedures
Summary
Exercises
Session 12: Generalized lists
12.1: Definitions and related concepts
12.2: Representing lists in computer memory
12.3: Implementing some basic operations on generalized lists
12.4: Traversing pure lists
12.5: Automatic storage reclamation
12.5.1: Algorithms for marking and gathering
Summary
Exercises
Session 13: Sequential tables
13.1: The table ADT
13.2: Direct-address table
13.3: Static sequential tables
13.3.1: Linear serach in a static sequential table
13.3.2: Binary search in an ordered static sequential table
13.3.3: Multiplicative binary search
13.3.4: Fibonaccian search in an ordered sequential table
Summary
Exercises
Session 14: Binary search trees
14.1: Binary search trees
14.1.1: Implementing some basic operations for dynamic tables
14.1.2: Analysis of BST search
14.2: Height-balanced binary search trees
14.3: Rotations on AVL trees
14.4: Optimum binary search trees
Summary
Exercises
Session 15: Hash tables
15.1: Converting keys to numbers
15.2: Choosing a hash function
15.2.1: The division method
15.2.2: The multiplicative method
15.3: Collision resolution by chaining
15.3.1: EASY procedures for chained hash tables
15.3.2: Analysis of hashing with collision resolution by chaining
15.4: Collision resolution by open addressing
15.4.1: Linear probing
15.4.2: Quadratic probing
15.4.3: Double hashing
15.4.4: EASY procedures for open-address hash tables
15.4.5: Ordered open-address hash tables
15.4.6: Analysis of hashing with collision resolution by open addressing
Summary
Exercises
Bibliography
Index