1. Introduction to Algorithms, Specification of Algorithm, Complexity.pdf

Course Name: Design and Analysis of Algorithm Topic: Introduction to Algorithms, Specification of Algorithm Course code : CS3102 Credits : 4 Mode of delivery : Hybrid (PowerPoint presentation) Faculty : Dr. Ajit Noonia Email-id : ajit.noonia@jaipur.manipal.edu B.TECH V SEM CSE ACADEMIC YEAR: 2024-2025 1

Assessment criteria’s 9/4/2024 2

Course Information • Course Handout • Communicate through eMail • Office hours • To be communicated • Grading policy • Will be communicated as per university guidelines 9/4/2024 CS3102 (DAA), Dept. of CSE 3

Syllabus Introduction: Algorithm Definition and Criteria of Algorithms, Iterative and Recursive Algorithms. Performance Analysis: Priori and Posteriori Analysis, Asymptotic Notations, Space Complexity, Time Complexity, Performance measurement of iterative and recursive algorithms. Solving Recurrence Relations: Substitution Method, Iterative Method, Recursive Tree Method, Master Method. Divide and Conquer: Introduction, Binary Search, Finding Maximum and Minimum, Merge Sort, Quick Sort, Randomized Quick Sort, Integer Multiplication. Graph Search Algorithm: Graph representation, Breadth First Search, and Depth First Search. Greedy Strategy: Introduction, Knapsack Problem, Job Sequencing with Deadlines, Huffman Coding, Union and Find Operation (Set and Disjoint Set), Minimum Cost Spanning Tree Algorithms (Prim’s and Kruskal’s), Optimal Merge Patterns, Single Source Shortest Path (Dijkstra’s Algorithm). Dynamic Programming: Introduction, Single Source Shortest Path (Bellman and Ford Algorithm), All Pair Shortest Path (Floyd Wrashal’s Algorithm), Optimal Binary Search Trees, 0/1 Knapsack Problem, Travelling Salesperson Problem, Longest Common Subsequence, Matrix Chain Multiplication, Edit distance. Backtracking: Introduction, N-Queens Problem, Graph Colouring, and Hamiltonian Cycles. Branch and Bound: Introduction, FIFO and LC Branch and Bound, 0/1 Knapsack Problem, Travelling Salesman Problem. String Matching: Naïve String Matching, Rabin Karp Algorithm, Knuth-Morris-Pratt Algorithm. Complexity Classes: NP, NP-Complete and NP-Hard Problems, Cook’s Theorem, Polynomial-time reductions, Satisfiability, Reduction from Satisfiability to Vertex Cover. 9/4/2024 CS3102 (DAA), Dept. of CSE 4

More Information • Textbook •Introduction to Algorithms 3rd, Cormen, Leiserson, Rivest and Stein, The MIT Press, • Fundamentals of Computer Algorithms, 2nd, Sartaj Sahni, Ellis Horowitz, Sanguthevar Rajasekaran • Others • Introduction to Design & Analysis Computer Algorithm 3rd, Sara Baase, Allen Van Gelder, Adison-Wesley, 2000. • Algorithms, Richard Johnsonbaugh, Marcus Schaefer, Prentice Hall, 2004. • Introduction to The Design and Analysis of Algorithms 2nd Edition, Anany Levitin, Adison-Wesley, 2007. 9/4/2024 CS3102 (DAA), Dept. of CSE 5

Course Outcomes: 9/4/2024 CS3102 (DAA), Dept. of CSE 6 [CS3102.1] Analyze the running times of algorithms using asymptotic analysis. (Bloom’s Level: 4 Analyze). [CS3102.2] Contrast and design algorithms using the divide-and-conquer and graph-searching algorithms to solve business problems, hence enhancing analytical skills. (Bloom’s Level: 4 Analyze) [CS3102.3] Apply the concept of greedy and dynamic programming approaches to solving real-life problems to enhance entrepreneurship capabilities. (Bloom’s Level: 3 Apply) [CS3102.4] Utilize the principles of backtracking and branch and bound algorithms to showcase their functioning and problem-solving capabilities. (Bloom’s Level: 3 Apply) [CS3102.5] Evaluate various advanced algorithm concepts such as string matching, approximation algorithms, and complexity classes to enhance employability. (Bloom’s Level: 5 Evaluate)

Goal of the Course 9/4/2024 CS3102 (DAA), Dept. of CSE 7 Learning Learning to solve real problems that arise frequently in computer applications. Learning Learning the basic principles and techniques used for answering the question: “How good, or, how bad is the algorithm” Getting Getting to know a group of “very difficult problems” categorized as “NP-Complete”

Introduction: Algorithm Definition and Criteria of Algorithms, Iterative and Recursive Algorithms 9/4/2024 CS3102 (DAA), Dept. of CSE 8

What is an Algorithm? A finite set of instructions that specifies a sequence of operations to be carried out to solve a specific problem or class of problems is called an Algorithm. 9/4/2024 CS3102 (DAA), Dept. of CSE 9

Characteristics of Algorithms 9/4/2024 CS3102 (DAA), Dept. of CSE 10 • It should externally supply zero or more quantities. Input: • It results in at least one quantity. Output: • Each instruction should be clear. Definiteness: • An algorithm should terminate after executing a finite number of steps. Finiteness: • the algorithm must produce the correct output within a reasonable amount of time and using an acceptable number of resources (such as memory). Effectiveness:

Advantages of an Algorithm 9/4/2024 CS3102 (DAA), Dept. of CSE 11 Effective Communication: Since it is written in a natural language like English, it becomes easy to understand the step-by-step solution to any problem. Easy Debugging: A well-designed algorithm facilitates easy debugging to detect the logical errors that occurred inside the program. Easy and Efficient Coding: An algorithm is nothing but a blueprint of a program that helps develop a program. Independent of Programming Language: Since it is language-independent, it can be easily coded by incorporating any high-level language.

Two Distinct Choices 9/4/2024 CS3102 (DAA), Dept. of CSE 12

How to write an Algorithm Algorithm Swap(a, b) { temp = a; a = b; b = temp; } 9/4/2024 CS3102 (DAA), Dept. of CSE 13

Probably the Oldest Algorithm 9/4/2024 CS3102 (DAA), Dept. of CSE 14

Euclid Algorithm: RecursiveVersion 9/4/2024 CS3102 (DAA), Dept. of CSE 15

Analysis of Algorithm 9/4/2024 CS3102 (DAA), Dept. of CSE 16 Space Complexity: The space complexity can be understood as the amount of space required by an algorithm to run to completion. Time Complexity: Time complexity is a function of input size n that refers to the amount of time needed by an algorithm to run to completion. The analysis is a process of estimating the efficiency of an algorithm. There are two fundamental parameters based on which we can analyze the algorithm:

How to Analyse an Algorithm 9/4/2024 CS3102 (DAA), Dept. of CSE 17 Algorithm Swap(a, b) { temp = a; a = b; b = temp; }

Applications 9/4/2024 CS3102 (DAA), Dept. of CSE 18

Frequency Count Method Algorithm Sum(A, n) { s = 0; for(i=0; i<n; i++) { s = s + A[i]; } return s; }

Frequency Count Method (Example) Algorithm Add(A, B, n) { for(i=0; i<n; i++) { for(j=0; j<n; j++) { C[i,j] = A[i,j] + B[i,j] } } }

Frequency Count Method (Example) Algorithm Multiply(A, B, n) { for(i=0; i<n; i++) { for(j=0; j<n; j++) { C[i,j] = 0; for(k=0; k<n; k++) { C[i,j] = C[i,j] + A[i,k] * B[i,j]; } } } }

Example for(i=0; i<n; i++) { statement; }

Example for(i=n; i>0; i--) { statement; }

Example for(i=0; i<n; i=i+2) { statement; }

Example for(i=0; i<n; i++) { for(j=0; j<n; j++) { statement; } }

Example for(i=0; i<n; i++) { for(j=0; j<i; j++) { statement; } }

Example p=0; for(i=1; p<=n; i++) { p=p+i; }

Example for(i=1; i<n; i=i*2) { statement; }

Example for(i=n; i>=1; i=i/2) { statement; }

Example for(i=1; i<n; i++) { statement; } for(j=1; j<n; j++) { statement; }

Example for(i=0; i<n; i++) { for(j=1; j<n; j=j*2) statement; }

Observations 1. for(i=0; i<n; i++) O(n) 2. for(i=0; i<n; i+2) n/2 O (n) 3. for(i=n; i>1; i--) O (n) 4. for(i=1; i<n; i=i*2) O(log n) Base 2 5. for(i=1; i<n; i=i*3) O(log n) Base 3 6. for(i=n; i>1; i=i/2) O(log n) Base 2

Compare Class of Functions 1<log n < √n < n < n*log n < n2 < n3 < - - - - - - -< 2n < 3n < ----<nn log n n n^2 2^n 0 1 1 2 1 2 4 4 2 3 4 8 16 64 16 256

1. Introduction to Algorithms, Specification of Algorithm, Complexity.pdf

More Related Content

Similar to 1. Introduction to Algorithms, Specification of Algorithm, Complexity.pdf

Recently uploaded

1. Introduction to Algorithms, Specification of Algorithm, Complexity.pdf