# Design and Analysis of Algorithm (Heap sort, Data structure for disjoint sets, Graph Algorithms And Fast Fourier Transform)

 Course Code : ULZ0084 Author : uLektz University : General for All University Regulation : 2017 Categories : Computer Science Format : ePUB3 (DRM Protected) Type : eBook

FREE

Description :Design and Analysis of Algorithm (Heap sort, Data structure for disjoint sets, Graph Algorithms And Fast Fourier Transform) of ULZ0084 covers the latest syllabus prescribed by General for All University for regulation 2017. Author: uLektz, Published by uLektz Learning Solutions Private Limited.

Note : No printed book. Only ebook. Access eBook using uLektz apps for Android, iOS and Windows Desktop PC.

##### Topics
###### UNIT I INTRODUCTION TO DESIGN AND ANALYSIS OF ALGORITHMS AND HEAPSORT

1.1 Introduction to design and analysis of algorithms-Growth of Functions (Asymptotic notations, standard notations and common functions)

1.2 Recurrences-solution of recurrences by substitution-recursion tree and Master methods-worst case analysis of Merge sort-Quick sort and Binary search

1.3 Design & Analysis of Divide and conquer algorithms

1.4 Heap sort : Heaps-Building a heap-The heap sort algorithm

1.5 Priority Queue-Lower bounds for sorting

###### UNIT II DYNAMIC PROGRAMMING ALGORITHMS, GREEDY ALGORITHMS AND DATA STRUCTURE FOR DISJOINT SETS

2.1 Dynamic programming algorithms (Matrix-chain multiplication, Elements of dynamic programming, Longest common subsequence)

2.2 Greedy Algorithms (Assembly-line scheduling, Achivity- selection Problem, Elements of Greedy strategy, Fractional knapsac problem, Huffman codes)

2.3 Data structure for disjoint sets: Disjoint set operations-Linked list representation-Disjoint set forests

###### UNIT III GRAPH ALGORITHMS AND FAST FOURIER TRANSFORM

3.1 Graph Algorithms: Breadth first and depth-first search

3.2 Minimum Spanning Trees-Kruskal and Prim's algorithms-single- source shortest paths (Bellman-ford and Dijkstra's algorithms)-All-pairs shortest paths (Floyd – Warshall Algorithm)

3.3 Back tracking-Branch and Bound

3.4 Fast Fourier Transform-string matching (Rabin-Karp algorithm)

3.5 NP - Completeness (Polynomial time, Polynomial time verification-NP - Completeness and reducibility-NP-Complete problems (without Proofs)-Approximation algorithms (Vertex-Cover Problem, Traveling Salesman Problem)