Analysis of Algorithm

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 al-Kindi in the 9th century used cryptographic algorithms for code-breaking, based on frequency analysis.

In mathematics and computer science, an algorithm is a finite sequence of well-defined, computer-implementable 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 well-defined 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 well-defined 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, Big-Oh, Omega Theta notation Mathematical background for algorithm analysis. Complexity class: Definition of P, NP, NP-Hard, NP-Complete 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, Assembly-line scheduling Problem 0/1 knapsack Problem, Travelling Salesperson problem, Longest common subsequence. Module Backtracking and Branch and bound ,General Method, Backtracking: N-queen 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 string-matching algorithm, The Rabin Karp algorithm, The Knuth-Morris-Pratt 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/placement-preparation/

/ Youtube Channel: https://www.youtube.com/channel/UCGFNZxMqKLsqWERX_N2f08Q

Follow For Latest Updates, Study Tips & More Content!

/lastmomenttuition

/ Last Moment Tuitions

/ lastmomentdost