Analysis of Algorithm
Free

Index
 How to Pass AOA
 Introduction to AOA (Analysis of Algorithm )
 Time Complexity
 All Pair Shortest Path (FloydWarshall) with solved Example
 Multistage Graphs Problem with Solved Example
 Space Complexity
 Knapsack Problem part 1
 Knapsack Problem Part 2
 Knapsack Problem Part 3
 Divide and Conquer Algorithm with Example
 Binary Search Method with Example
 Max Min Problem with Solved Example
 Merge Sort Algorithm with Solved Example
 Multiplying Long Integers Using Divide and Conquer Technique
 Prim’s algorithm for Minimum Spanning Tree
 Flowshop Scheduling Explained
 Travelling Salesperson Problem with Solved Example
 Optimal Binary Search Trees with Example #1
 N Queen Problem using Backtracking with Example
 Quick Sort Algorithm web
 Optimal Binary Search Trees with Example #2
 15 Puzzle Problem Explained with Example
 Sum of Subsets Problem Explained #1 Backtracking
 Sum of Subsets Problem Explained #2 Backtracking
 Dijkstra’s Algorithm with Solved Example
 Graph Coloring Problem Explained Backtracking
 Kruskal algorithm for Minimum Spanning Tree With Example
 Quick Sort Algorithm Explained with Example
Analysis of Algorithms
Analysis of Algorithms is semester 4 subject of final year of computer engineering in Mumbai University. Prerequisite for studying this subject are Data structure concepts, Discrete structures.
Course Objectives for subject Analysis of Algorithms is to provide mathematical approaches for Analysis of Algorithms. To understand and solve problems using various algorithmic approaches. To analyze algorithms using various methods Course Outcomes for subject Analysis of Algorithms At the end of the course learner will be able to Analyze the running time and space complexity of algorithms. Describe, apply and analyze the complexity of divide and conquer strategy. Describe, apply and analyze the complexity of greedy strategy. Describe, apply and analyze the complexity of dynamic programming strategy. Explain and apply backtracking, branch and bound. 6 Explain and apply string matching techniques.
The concept of algorithm has existed since antiquity. Arithmetic algorithms, such as a division algorithm, was used by ancient Babylonian mathematicians c. 2500 BC and Egyptian mathematicians c. 1550 BC. Greek mathematicians later used algorithms in 240 BC in the sieve of Eratosthenes for finding prime numbers, and the Euclidean algorithm for finding the greatest common divisor of two numbers. Arabic mathematicians such as alKindi in the 9th century used cryptographic algorithms for codebreaking, based on frequency analysis.
In mathematics and computer science, an algorithm is a finite sequence of welldefined, computerimplementable instructions, typically to solve a class of problems or to perform a computation. Algorithms are always unambiguous and are used as specifications for performing calculations, data processing, automated reasoning, and other tasks. As an effective method, an algorithm can be expressed within a finite amount of space and time, and in a welldefined formal language for calculating a function. Starting from an initial state and initial input (perhaps empty), the instructions describe a computation that, when executed, proceeds through a finite number of welldefined successive states, eventually producing output and terminating at a final ending state. The transition from one state to the next is not necessarily deterministic; some algorithms, known as randomized algorithms, incorporate random input.
In computer science, the analysis of algorithms is the process of finding the computational complexity of algorithms the amount of time, storage, or other resources needed to execute them. Usually, this involves determining a function that relates the length of an algorithm’s input to the number of steps it takes (its time complexity) or the number of storage locations it uses (its space complexity). An algorithm is said to be efficient when this function’s values are small, or grow slowly compared to a growth in the size of the input. Different inputs of the same length may cause the algorithm to have different behavior, so best, worst and average case descriptions might all be of practical interest. When not otherwise specified, the function describing the performance of an algorithm is usually an upper bound, determined from the worst case inputs to the algorithm. The term “analysis of algorithms” was coined by Donald Knuth. Algorithm analysis is an important part of a broader computational complexity theory, which provides theoretical estimates for the resources needed by any algorithm which solves a given computational problem. These estimates provide an insight into reasonable directions of search for efficient algorithms.
Module Introduction consists of the following subtopics Performance analysis, space, and time complexity Growth of function, BigOh, Omega Theta notation Mathematical background for algorithm analysis. Complexity class: Definition of P, NP, NPHard, NPComplete Analysis of selection sort, insertion sort. Recurrences: The substitution method, Recursion tree method, Master method. Module Divide and Conquer Approach consists of the following subtopics General method, Merge sort, Quick sort, Finding minimum and maximum algorithms and their Analysis, Analysis of Binary search. Module Greedy Method Approach consists of the following subtopics General Method, Single source shortest path: Dijkstra Algorithm Fractional Knapsack problem, Job sequencing with deadlines, Minimum cost spanning trees: Kruskal and Prim‟s algorithms. Module Dynamic Programming Approach consists of the following subtopics General Method, Multistage graphs, Single source shortest path: Bellman Ford Algorithm All pair shortest path: Floyd Warshall Algorithm, Assemblyline scheduling Problem 0/1 knapsack Problem, Travelling Salesperson problem, Longest common subsequence. Module Backtracking and Branch and bound ,General Method, Backtracking: Nqueen problem, Sum of subsets, Graph coloring ,Branch and Bound: Travelling Salesperson Problem, 15 Puzzle problem. Module String Matching Algorithms consists of the following subtopics The Naïve stringmatching algorithm, The Rabin Karp algorithm, The KnuthMorrisPratt algorithm.
Suggested Reference books for subject Analysis of Algorithms from Mumbai university are as follows T. H. Cormen, C.E. Leiserson, R. L. Rivest, and C. Stein, “Introduction to algorithms”, 2nd Edition, PHI Publication 2005. Ellis Horowitz, Sartaj Sahni, S. Rajsekaran. “Fundamentals of computer algorithms” University Press. Suggested Reference books for subject Analysis of Algorithms from Mumbai university are as follows Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, “Algorithms”, Tata McGrawHill Edition. S. K. Basu, “Design Methods and Analysis of Algorithm”, PHI.
Prepare For Your Placements: https://lastmomenttuitions.com/courses/placementpreparation/
/ Youtube Channel: https://www.youtube.com/channel/UCGFNZxMqKLsqWERX_N2f08Q
Follow For Latest Updates, Study Tips & More Content!
Course Features
 Lectures 28
 Quizzes 0
 Duration 10 hours
 Skill level All levels
 Language Hindi
 Students 1260
 Certificate No
 Assessments Yes

Surajkm
Very nice teaching skills
Short videos but very descriptive videos. Nice one thank you so much sir