# Design And Analysis Of Algorithms

 Course Code : 10CS43 Author : uLektz University : Visvesvaraya Technological University, Karnataka (VTU) Regulation : 2010 Categories : Computer Science Format : ePUB3 (DRM Protected) Type : eBook

FREE

Description :Design And Analysis Of Algorithms of 10CS43 covers the latest syllabus prescribed by Visvesvaraya Technological University, Karnataka (VTU) 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

1.1 Notion of Algorithm, Review of Asymptotic Notations, Mathematical Analysis of Non-Recursive and Recursive Algorithms

1.2 Brute Force Approaches: Introduction, Selection Sort and Bubble Sort, Sequential Search and Brute Force String Matching

###### UNIT II DIVIDE AND CONQUER

2.1 Divide and Conquer: General Method, Defective Chess Board, Binary Search, Merge Sort, Quick Sort and its performance

###### UNIT III THE GREEDY METHOD

3.1 THE GREEDY METHOD: The General Method, Knapsack Problem, Job Sequencing with Deadlines

3.2 Minimum-Cost Spanning Trees: Prim’s Algorithm, Kruskal’s Algorithm; Single Source Shortest Paths

###### UNIT IV DYNAMIC PROGRAMMING

4.1 DYNAMIC PROGRAMMING: The General Method, Warshall’s Algorithm, Floyd’s Algorithm for the All-Pairs Shortest Paths Problem

4.2 Single-Source Shortest Paths: General Weights, 0/1 Knapsack, The Traveling Salesperson problem

###### UNIT V DECREASE-AND-CONQUER APPROACHES, SPACE-TIME TRADEOFFS

5.1 Decrease-and-Conquer Approaches: Introduction, Insertion Sort, Depth First Search and Breadth First Search, Topological Sorting

5.2 Space-Time Tradeoffs: Introduction, Sorting by Counting, Input Enhancement in String Matching

###### UNIT VI LIMITATIONS OF ALGORITHMIC POWER AND COPING WITH THEM

6.1 LIMITATIONS OF ALGORITHMIC POWER AND COPING WITH THEM: Lower-Bound Arguments

6.2 Decision Trees, P, NP, and NP-Complete Problems

6.3 Challenges of Numerical Algorithms

###### UNIT VII COPING WITH LIMITATIONS OF ALGORITHMIC POWER

7.1 Backtracking: n - Queens problem, Hamiltonian Circuit Problem, Subset – Sum Problem

7.2 Branch-and-Bound: Assignment Problem, Knapsack Problem, Traveling Salesperson Problem

7.3 Approximation Algorithms for NP-Hard Problems, Traveling Salesperson Problem, Knapsack Problem

###### UNIT VIII PRAM ALGORITHMS

8.1 PRAM ALGORITHMS: Introduction, Computational Model, Parallel Algorithms for Prefix Computation, List Ranking, and Graph Problems