Scribd
Upload
615 views

Design and Analysis of Algorithms - CS8452

This book “Design and Analysis of Algorithms”, covering various algorithm and analyzing the real word problems. It delivers various types of algorithm and its problem solving techniques. It stretches an outline on analyzing the algorithm and identifying the efficiency based on the time and space complexity. It contributes an idea over analyzing the real world problems to representing the data of the problem and applying the next level algorithm to achieve the goal of the problem.

Uploaded by

Pa Krishna Sankar
Copyright
© © All Rights Reserved
Available Formats
Download as PDF, TXT or read online on Scribd
615 views

Design and Analysis of Algorithms - CS8452

This book “Design and Analysis of Algorithms”, covering various algorithm and analyzing the real word problems. It delivers various types of algorithm and its problem solving techniques. It stretches an outline on analyzing the algorithm and identifying the efficiency based on the time and space complexity. It contributes an idea over analyzing the real world problems to representing the data of the problem and applying the next level algorithm to achieve the goal of the problem.

Uploaded by

Pa Krishna Sankar
Copyright
© © All Rights Reserved
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 6

Contents

UNIT I

INTRODUCTION
1.1. Notion of an Algorithm

1.2. Fundamentals of Algorithmic Problem Solving

1.2.1. Understanding the problem

1.2.2. Choose the Exact and Approximate Problem Solving

1.2.3. Designing an Algorithm and Data Structures

1.2.4. Proving an Algorithm’s Correctness

1.2.5. Analyzing an Algorithm

1.2.6. Coding an Algorithm

1.3. Important Problem Types

1.3.1. Sorting

1.3.2. Searching

1.3.3. String processing

1.3.4. Graph problems

1.3.5. Combinatorial problems

1.3.6. Geometric problems

1.3.7. Numerical problems

1.4. Fundamentals of the Analysis of Algorithmic Efficiency

1.4.1. Analysis Framework

1.4.2. Asymptotic Notations and their properties

1.5. Mathematical analysis

1.5.1. Non-recursive algorithms

1.5.2. Recursive algorithms

1.6. Empirical analysis

1.7. Visualization

UNIT II

BRUTE FORCE AND DIVIDE-AND-CONQUER


2.1 Brute Force

2.1.1 Introduction to Brute force

2.1.2 Computing an
2.1.3 String Matching

2.2 Closest-Pair and Convex-Hull Problems

2.2.1 Closest-Pair Problem

2.2.2 Convex-Hull Problem

2.3 Exhaustive Search

2.3.1 Travelling Salesman Problem

2.3.2 Knapsack Problem

2.3.3 Assignment problem

2.4 Divide and Conquer Methodology

2.4.1 Binary Search

2.4.2 Merge sort

2.4.3 Quick sort

2.4.4 Heap Sort

2.5 Multiplication of Large Integers

2.6 Closest-Pair and Convex - Hull Problems

2.6.1 The Closest-Pair Problem

2.6.2 Convex-Hull Problem

UNIT III

DYNAMIC PROGRAMMING AND GREEDY TECHNIQUE


3.1. Dynamic programming

3.1.1. Principle of optimality

3.1.2. Coin changing problem

3.1.3. Computing a Binomial Coefficient

3.2. Floyd‘s algorithm

3.3. Multi stage graph

3.4.1. Backward approach

3.4.2. Forward approach

3.4. Optimal Binary Search Trees

3.5. Knapsack Problem and Memory functions

3.5.1. Memory Functions

3.6. Greedy Technique

3.6.1. Prim‘s algorithm

3.6.2. Kruskal's Algorithm


3.7. Container loading problem

3.8. 0/1 Knapsack problem

3.9. Optimal Merge pattern

3.10. Huffman Trees

UNIT IV

ITERATIVE IMPROVEMENT
4.1 Simplex Method

4.2 Maximum-Flow Problem

4.3 Maximum Matching in Bipartite Graphs

4.4 Stable marriage Problem

UNIT V

COPING WITH THE LIMITATIONS OF ALGORITHM POWER


5.1. Lower - Bound Arguments

5.1.1. Trivial Lower Bounds

5.1.2. Information-Theoretic Arguments

5.1.3. Adversary Arguments

5.1.4. Problem Reduction

5.2. P, NP NP- Complete and NP Hard Problems

5.2.1. P Problems

5.2.2. NP Problems

5.2.3. NP-Complete Problems

5.2.4. NP-Hard Problems

5.3. Backtracking

5.3.1. n-Queen problem

5.3.2. Hamiltonian Circuit Problem

5.3.3. Subset Sum Problem

5.4. Branch and Bound

5.4.1. LIFO Search and FIFO search

5.4.2. Assignment problem

5.4.3. Knapsack Problem

5.4.4. Travelling Salesman Problem


5.5. Approximation Algorithms for NP-Hard Problems

5.5.1. Travelling Salesman problem

5.5.2. Knapsack problem

You might also like