Scribd
Upload
18 views7 pages

Sharing DAA CS8452

Uploaded by

Rey Denzo
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
18 views7 pages

Sharing DAA CS8452

Uploaded by

Rey Denzo
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 7

See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/328488585

Design and Analysis of Algorithms

Book · October 2018

CITATIONS READS

64 12,027

2 authors:

Krishna Sankar P Shangaranarayanee N P


Tata Consultancy Services Limited Angel college of Engineering and Technology
58 PUBLICATIONS 174 CITATIONS 25 PUBLICATIONS 116 CITATIONS

SEE PROFILE SEE PROFILE

All content following this page was uploaded by Krishna Sankar P on 24 October 2018.

The user has requested enhancement of the downloaded file.


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


View publication stats

You might also like