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