DESIGN AND ANALYSIS OF ALGORITHM

 DESIGN AND ANALYSIS OF ALGORITHM

UNIT-1

Introduction: Algorithm definition, Specifications, Performance Analysis- Time Complexity, Space Complexity. Asymptotic Notations-Big-Oh, Omega, Theta. 

Divide and Conquer: General Method, Binary Search, Finding Maximum and Minimum, Merge Sort, Quick sort, closest pair of points. 

UNIT – II 

The Greedy Method – General Method, Knapsack Problem, Job sequencing with deadlines, Minimum-cost spanning trees, Optimal storage on tapes, Single source shortest paths, Huffman coding. 

UNIT – III 

Dynamic Programming - General method, Multistage graph, All pairs shortest path, Single Source Shortest path, Optimal Binary search trees, 0/1 Knapsack, Reliability design, the travelling salesman problem. 

UNIT - IV 

Back tracking - The General Method, The 8-Queens Problem, Sum of subsets, Graph Coloring, Hamiltonian cycles.

UNIT-V 

Branch and Bound – General method, Job sequencing with deadlines –LC Branch and Bound, FIFO Branch and Bound and LIFO Branch and Bound, 0/1 Knapsack problem - LC Branch and Bound solution, FIFO Branch and Bound solution, Travelling salesperson Problem – LC Branch and Bound solution 

TEXTBOOK(S): 

1. Ellis Horowitz, SartajSahni,S Rajasekaran , “Fundamentals of Computer Algorithms”, University press, 2nd edition, 2012.


All Units PPTS: (LINK)

https://drive.google.com/drive/folders/1ediUlr9-Id1qkgCkVQJKwm7iADu2EvJF?usp=sharing

Comments

Popular posts from this blog

DATA SCIENCE

DEEP LEARNING