Algorithm and Design Complexity

by Anli Sherine, Geno Peter, Mary Jasmine, S. Albert Alexander

Length: 182 pages
Edition: 1
Language: English
Publisher: CRC Press
Publication Date: 2023-05-04
ISBN-10: 1032409320
ISBN-13: 9781032409320
Sales Rank: #0 (See Top 100 Books)

Computational complexity is critical in analysis of algorithms and is important to be able to select algorithms for efficiency and solvability. Algorithm and Design Complexity initiates with discussion of algorithm analysis, time space trade-off, symptotic notations and so forth. It further includes algorithms that are definite and effective, known as computational procedures. Further topics explored include divide and conquer, dynamic programming, and backtracking.

Features:

Includes complete coverage of basics and design of algorithms.
Discusses algorithm analysis techniques like divide-and-conquer, dynamic programming, and greedy heuristics.
Provides time and space complexity tutorials.
Reviews combinatorial optimization of Knapsack problem.
Simplifies recurrence relation for time complexity. This book is aimed at graduate students and researchers in computers science, information technology, and electrical engineering.

Cover
Half Title
Title
Copyright
Contents
Preface
Acknowledgments
About the Authors
Introduction
Chapter 1 Algorithm Analysis
	1.1 Algorithm Analysis
	1.2 Time–Space Trade-Off
	1.3 Asymptotic Notations
	1.4 Properties of Big-Oh Notations
	1.5 Conditional Asymptotic Notations
	1.6 Recurrence Equations
	1.7 Solving Recurrence Equations
	1.8 Analysis of Linear Search
Chapter 2 Divide and Conquer
	2.1 Divide and Conquer: General Method
	2.2 Binary Search
	2.3 Finding the Maximum and Minimum
	2.4 Merge Sort
	2.5 Greedy Algorithms: General Method
	2.6 Container Loading
	2.7 Knapsack Problem
Chapter 3 Dynamic Programming
	3.1 Introduction: Dynamic Programming
	3.2 Multistage Graphs
	3.3 All-Pairs Shortest Paths
	3.4 Optimal Binary Search Trees
	3.5 0/1 Knapsack
	3.6 The Traveling Salesperson Problem
Chapter 4 Backtracking
	4.1 Backtracking: The General Method
	4.2 The 8-Queens Problem
	4.3 Sum of Subsets
	4.4 Graph Coloring
	4.5 Hamiltonian Cycles
	4.6 0/1 Knapsack (Using Backtracking)
Chapter 5 Graph
	5.1 Introduction
	5.2 Graph Traversals
	5.3 Connected Components and Spanning Trees
	5.4 Spanning Trees
	5.5 Biconnected Components and DFS
	5.6 Branch and Bound
	5.7 0/1 Knapsack Problem
	5.8 NP-Hard and NP-Complete Problems
Index