# DESIGN AND ANALYSIS OF ALGORITHM

 Course Code : PCCS4204 Author : uLektz University : Biju Patnaik University of Technology (BPUT) Regulation : 2010 Categories : Computer Science Format : ePUB3 (DRM Protected) Type : eBook

FREE

Description :DESIGN AND ANALYSIS OF ALGORITHM of PCCS4204 covers the latest syllabus prescribed by Biju Patnaik University of Technology (BPUT) for regulation 2010. 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)