Efnisyfirlit

• Preface
• Chapter 1 Introduction
• 1.1 Algorithm
• 1.2 Another definition
• 1.3 Analyzing the performance of algorithms
• 1.4 Growth of the functions
• 1.5 Asymptotic notations
• 1.5.1 The O (big oh) notation
• 1.5.2 The Ω notation
• 1.5.3 The θ notation
• 1.6 Recurrence relation
• 1.6.1 Linear recurrence relation
• 1.6.2 Solution of homogeneous recurrence relation
• 1.6.3 Solution to nonhomogeneous linear recurrence relation
• 1.7 Divide and conquer relations
• 1.7.1 Solution to DAC recurrence relation
• 1.7.2 The recursion tree method
• 1.7.3 The substitution method
• 1.7.4 Change of variable method
• 1.8 Master’s theorem
• Problem set
• Chapter 2 Sorting techniques
• 2.1 Sorting
• 2.2 Insertion sort
• 2.2.1 Analysis of insertion sort
• 2.3 Quick sort
• 2.3.1 DAC approach
• 2.3.2 Analysis of quick sort
• 2.4 Merge sort
• 2.4.1 Analysis of merge sort
• 2.5 Heap sort
• 2.5.1 Analysis of Heapify
• 2.5.2 Heap sort
• 2.5.3 Analysis of heap sort
• 2.6 Sorting in linear time
• 2.7 Counting sort
• 2.7.1 Analysis of counting sort
• 2.8 Radix sort
• 2.8.1 Analysis of radix sort
• 2.9 Bucket sort
• 2.9.1 Analysis of bucket sort
• 2.9.2 Binomial distribution
• Problem set
• Chapter 3 Algorithm design techniques
• 3.1 Greedy approach
• 3.1.1 Traveling salesman problem
• 3.1.2 Fractional knapsack problem
• 3.2 Backtracking
• 3.2.1 Hamiltonian cycle
• 3.2.2 8-queen problem
• 3.3 Dynamic programming
• 3.3.1 0/1 knapsack problem
• 3.3.2 The traveling salesman problem
• 3.3.3 Chain matrix multiplication
• 3.3.4 Optimal binary search tree
• 3.4 Branch-and-bound technique
• 3.4.1 Assignment problem
• 3.4.2 Knapsack problem
• 3.5 Amortized analysis
• 3.5.1 Aggregate method
• 3.5.2 The potential method
• 3.6 Order statistics
• Problem set
• Chapter 4 Advanced graph algorithm
• 4.1 Introduction
• 4.1.1 Terminology
• 4.2 The graph search techniques
• 4.2.1 Breadth first search
• 4.2.2 Depth first search
• 4.3 Spanning tree
• 4.3.1 Kruskal’s algorithm
• 4.3.2 Prim’s algorithm
• 4.4 Shortest path algorithm
• 4.4.1 Warhsall’s algorithm
• 4.4.2 Floyd Warshall’s algorithm
• 4.4.3 Dijkstra algorithm
• 4.4.4 Bellman–Ford algorithm
• 4.5 Maximum flow
• 4.5.1 Maximum flow and minimum cut
• 4.5.2 Ford Fulkerson method
• Problem set
• Chapter 5 Number theory, classification of problems, and random algorithms
• 5.1 Division theorem
• 5.1.1 Common divisor and greatest common divisor
• 5.2 Chinese remainder theorem
• 5.3 Matrix operations
• 5.3.1 Strassen’s matrix multiplication
• 5.3.2 Divide and conquer for matrix multiplication
• 5.3.3 Strassen’s multiplication
• 5.4 Pattern matching
• 5.4.1 The Naive algorithm
• 5.4.2 The Rabin–Karp algorithm
• 5.5 P and NP class problem
• 5.5.1 Reducibility
• 5.5.2 NP complete problem
• 5.6 Approximation algorithms
• 5.6.1 Relative error
• 5.6.2 Approximation algorithm for TSP
• 5.6.3 The vertex cover problem
• 5.7 Deterministic and randomized algorithm
• 5.7.1 The nut and bolt problem
• 5.8 Computational geometry
• 5.9 The convex hull
• 5.9.1 Counterclockwise and clockwise
• 5.9.2 Finding whether two line segments intersect
• 5.10 Class P problems
• 5.10.1 NP (nondeterministic Polynomial Time) Problems
• 5.10.2 Any problem in P is also in NP
• 5.10.3 NP Hard Problems
• 5.10.4 NP Complete
• 5.10.5 Halting Problem for Deterministic Algorithms
• 5.10.6 The satisfiability problem
• 5.11 Clique
• 5.11.1 Clique Decision Problem
• 5.11.2 Non-Deterministic Algorithm for Clique Decision Algorithm
• Problem set
• Chapter 6 Tree and heaps
• 6.1 Red–Black Tree
• 6.2 Operations on RBT
• 6.2.1 Rotation
• 6.2.2 Insertion
• 6.2.3 Deletion
• 6.3 B-tree
• 6.3.1 Searching key k in B-tree
• 6.4 Binomial heap
• 6.4.1 Binomial heap
• 6.5 Fibonacci heap
• 6.5.1 Operation on Fibonacci heap
• Chapter 7 Lab session
• Appendices
• Further reading
• Index