Book Details

DESIGN AND ANALYSIS OF ALGORITHM

DESIGN AND ANALYSIS OF ALGORITHM

Published by uLektz

Course Code:PCCS4204

Author:uLektz

University: Biju Patnaik University of Technology (BPUT)

Regulation:2010

Categories:Computer Science

Format : ico_bookePUB3 (DRM Protected)

Type :eBook

FREE

Buy Now

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)

loading