# DESIGN AND ANALYSIS OF ALGORITHM (DAA)

Neeraj Yadav | 06-Nov-2015 |

#### Hi friends, here Neeraj Yadav uploaded notes for DAA with title DESIGN AND ANALYSIS OF ALGORITHM (DAA). You can download this lecture notes, ebook by clicking on the below file name or icon.

UNIT-I
Introduction, Sorting in polynomial Time & Sorting in Linear Time
1.1 Algorithms
1.1.1 Algorithm has five important features
1.2 Design of Algorithms
1.3. Analysis of Algorithm
1.3.1 Abstract/mathematical comparison of algorithms
1.3.2 Running time of an Algorithm
1.4 Complexity of Algorithm
1.4.1 Asymptotic Analysis
1.4.2 Asymptotic Complexity
1.4.3 Order of growth of Function
1.5 Asymptotic Notations
1.6 Recurrences and their solutions method:
1.6.1 The substitution method
1.6.2 The Recursion-Tree Method:
1.6.3 Master Method/Theorem
1.7 Sorting in Polynomial time
1.7.1 Insertion Sort
1.7.2 Merge Sort
1.7.3 Quick Sort:
1.7.4 Heap procedures and Heap-Sort
1.8 Sorting in Linear Time: Non-comparison sorts.
1.8.1Counting sort
1.8.3 Bucket Sort
1.9 Median and Order Statistics
UNIT- II
2.1 Red Black Tree
2.1.1 Height bound lemma
2.1.2 Red Black Tree insertion
2.1.3 Red Black Tree Deletion
2.2 Augmenting data structure
2.2.1 Augmenting Data Structures: Methodology
2.2.2 Order statistic tree
2.2.2.1 Determine ith order statistics
2.2.2.2 Determine the rank of an element
2.2.3 Interval Trees
2.3 Binomial Heap
2.3.1 Binomial Tree
WWW.GUPSHUPSTUDY.COM
2.3.2. Operation on Binomial Heap
2.4 B-trees
2.4.1 Operations on B-Tree
2.4.2 The height of a B-Tree
2.5 Fibonacci Heaps
2.5.1 Algorithms for various Fibonacci Heaps operations
2.6 Data structure for Disjoint Sets
2.6.1 Operations
2.6.2 Analysis of disjoint-set data structures
2.6.3 Application
2.6.5 Weighted-Union Heuristic:
2.7 Disjoint-set Implementation: Forests
2.8 Dictionaries and priority Queues
2.9 Mergable Heaps
2.10 Concatenable queue
UNIT-III
Advanced Design and Analysis Techniques
3.1 Dynamic Programming
3.1.1 Matrix Chain Multiplication
3.1.2 Longest common subsequence
3.2 Greedy Algorithms
3.2.1 Activity Selection Problem
3.2.2 Knapsack Problem
3.2.3 Huffman codes
3.2.4 Task Scheduling Problem
3.3 Branch & Bound
3.4 Amortized Analysis
UNIT-IV
Graph Algorithms
4.1 Graph Algorithms
4.1.1 Elementary Graph properties
4.2 Representation of Graph
4.3 Graph-searching Algorithms
4.3.2 Depth-first Search (DFS).
4.4 Minimum Spanning Tree
4.4.1 Kruskal’s Algorithm
4.4.2 Prims Method
4.5 Single-Source Shortest Paths
4.5.1 Dijkstra’s Algorithm
4.5.2 The Bellman-Ford algorithm
WWW.GUPSHUPSTUDY.COM
4.5.3 Single-source shortest paths in directed acyclic graphs
4.6 All-Pairs Shortest Paths
4.6.1 The Floyd-Warshall algorithm
4.7 Transitive closure of a directed graph
4.8 Maximum Flow
4.8.1 Ford Fulkerson Method
4.8.2 Cut of Flow Network
UNIT-V
5.1 Randomized Algorithms
5.1.1Randomized Quick Sort
5.2 String Matching
5.2.1String Matching Algorithms
5.3NP-Hard and NP-Completeness
5.4 Approximation Algorithms
5.4.1 Vertex cover problem
5.5 Sorting Network
5.6 Matrix Operations
5.6.1 Matrix Multiplication : It is the product of two matrices.
5.6.1.1 Strassen’s algorithm for matrix multiplication
5.6.2 Solving systems of Linear equations
5.6.2.1 Overview of LUP decomposition
5.7 Polynomials and FFT
5.8 Number Theoretic Algorithms
5.8.1 GCD
5.8.2 Multiplicative Inverse
5.8.3 Chinese Remainder Theorem
5.8.4 RSA Public-Key Cryptosystem

#### Attachment Lists

• DESIGN AND ANALYSIS OF ALGORITHM(DAA).pdf (Size: 4665.79KB)
Share With Friends :
29-Mar-2017

#### Egi Febian

mrs neeraj, is this note have a cover? because it's a good note..

29-Mar-2017

i need this book