Design and Analysis of Algorithms (ICT 2257) PDF

Design and Analysis of Algorithms (ICT 2257) 4 - Credits[L-3 T-1 P-0 4] B.Tech. (Computer and Communication Engineering)  Syllabus Introduction: Asymptotic Notations Space and Time Complexity Graphs: Representations of Graph and Digraphs DFS, BFS...

Design and Analysis of Algorithms (ICT 2257) 4 - Credits[L-3 T-1 P-0 4] B.Tech. (Computer and Communication Engineering)  Syllabus Introduction: Asymptotic Notations Space and Time Complexity Graphs: Representations of Graph and Digraphs DFS, BFS Finding path and connected components Spanning tree Department of I&CT, MIT, Manipal  Syllabus Contd… Greedy Method: Container Loading Problem 0/1 Knapsack Problem, Topological Sorting Single Source Shortest Path Bipartite Cover Minimum Spanning Tree Divide and Conquer: Strassen’s Matrix Multiplication Binary Search Merge Sort Quick Sort Solving Recurrence Equations Department of I&CT, MIT, Manipal  Syllabus Contd… Dynamic Programming: 0/1 Knapsack Problem, Matrix Multiplication Chain Problem All Pair Shortest Path Back Tracking and Branch & Bound Methods: 0/1 Knapsack Problem Max Clique Problem Traveling Salesperson Problem (TSP) Department of I&CT, MIT, Manipal  Syllabus Contd… Trees: Binary Search Tree AVL Tree, Red Black Tree B Tree B+ Tree etc. Hashing: Hash function Collision resolution techniques: open addressing: Separate chaining Closed addressing: Linear probing, Quadratic probing, double hashing Department of I&CT, MIT, Manipal Syllabus Contd… NP-Completeness and Approximation Algorithms: Class P Problems Class NP Problems NP – hard Problems NP - complete Problems Approximation Algorithms Vertex Cover Problem TSP Department of I&CT, MIT, Manipal Course Outcomes By the end of this Course, the students should be able to: Understand asymptotic notations to represent the complexities of algorithms. Understand the basic concepts of graph traversal methods. Apply various algorithm designing techniques for a given problem. Comprehend the basic concepts of trees and hashing techniques. Understand NP complete and NP hard problems. Department of I&CT, MIT, Manipal  References T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms (3e), Prentice-Hall India, 2009. Sartaj Sahani, Data Structures, Algorithms and Applications in C++ (2e), Silicon Press, 2005. Mark Allen Weiss, Data Structures and Algorithm Analysis in C, Pearson Education (3e), 2009. Department of I&CT, MIT, Manipal Define Set Define Graph Define Tree There are n stairs, a person standing at the bottom wants to reach the top. The person can climb either 1 stair or 2 stairs at a time. Count the number of ways, the person can reach the top. 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. Algorithm: Name of Persian mathematician Muhammad ibn Musa al-Khwarizmi - was a Persian mathematician, astronomer, geographer, and scholar in the House of Wisdom in Baghdad. Department of I&CT, MIT, Manipal Asymptotic Notations Q, O, W, o, w Theta, Big-Oh, Big-Omega/Omega, small/little oh, small/little omega. Used for comparing two functions say f(n) and g(n). Need this notation for analysis of algorithm – i.e., to analyze time complexity/space complexity of an algorithm as a function of input size n say f(n). n is positive integer and f(n) is monotonically increasing function (in the case of time and space complexity). Department of I&CT, MIT, Manipal Department of I&CT, MIT, Manipal Department of I&CT, MIT, Manipal Big-Oh (O) f(n)=O(g(n)) iff  positive constants c and n0, such that n  n0, such that f(n)  cg(n) g(n) is an asymptotic upper bound for f(n). Department of I&CT, MIT, Manipal  Examples Any linear function an + b is in O(n2). Whether an+b=O(n) ? How? Yes. an + b  |a|n + n for all n  b an + b  |a| n2 +|b| n2 for all n  1 = (|a|+1) n = (|a|+|b|) n2 = O(n2) Taking c = (|a|+1) and no=b we Another way: get an+b=O(n) an + b  n2 + n2 for all n  max{|a|, |b|} an + b 0, then f(n)= Ω (nm) Department of I&CT, MIT, Manipal Omega Ratio Theorem Theorem [Omega Ratio Theorem] Let f(n) and g(n) be such that lim n→ ∞ 𝑔(𝑛) 𝑔 𝑛 /𝑓 𝑛 exists. f(n)=Ω(g(n) iff lim n→ ∞ ≤ 𝑐 for some finite constant c. 𝑓 𝑛 Check whether 10n2 – 5n + 6 = Ω(n2) lim n→ ∞ n2/(10n2 – 5n + 6) = lim n→ ∞ n2/n2(10 – (5/n) + (6/n2)) = 1/10 Limit exists. Hence the result. Department of I&CT, MIT, Manipal Theta Notation (θ) f(n)= θ(g(n)) iff  positive constants c1 , c2 and n0, such that n  n0, such that c1.g(n) ≤ f(n) ≤ 𝒄𝟐. 𝒈 𝒏 i.e., f(n)= θ(g(n)) iff f(n) = O(g(n)) and f(n) = Ω(g(n)) g(n) is an asymptotic lower and upper bound for f(n). Department of I&CT, MIT, Manipal Theorem: If f(n)= amnm+ … +a1n+ao and am > 0, then f(n)= Θ(nm) 𝑓 𝑛 Theorem [Theta Ratio Theorem] f(n) = Θ(g(n) iff lim n→ ∞ 𝑔 𝑛 ≤ 𝑐1 and 𝑔 𝑛 lim n→ ∞ 𝑓 𝑛 ≤ 𝑐2 for some finite constants c1 and c2. Department of I&CT, MIT, Manipal Small Oh (o) f(n) = o(g(n)) iff f(n)=O(g(n)) but f(n) ≠ Ω (g(n)) 𝑓 𝑛 i.e., lim n→ ∞ 𝑔 𝑛 =0 Example 3n + 5 = o (n2) = o(n3) Department of I&CT, MIT, Manipal Small Omega (w) f(n) = w(g(n)) iff f(n)= Ω (g(n)) but f(n) ≠ O (g(n)) 𝑔 𝑛 i.e., lim n→ ∞ 𝑓 𝑛 =0 3 N2+ 5 = w(N)= w (1) Department of I&CT, MIT, Manipal Problem: n3+n2 logn = 𝛩(n3) ? Show using substitution method. Do not use any theorem. Ans: n3+n2 logn ≤ n3 + n3 = 2 n3 for all n ≥ 1 (since logn ≤ n) Therefore n3+n2 logn = O(n3) Also, n3+n2 logn ≥ n3 for all n ≥ 1 Therefore, n3+n2 logn = Ω (n3) Hence n3+n2 logn = 𝜃(n3) Department of I&CT, MIT, Manipal Find the asymptotic time complexity of the following 1. ∑ 1𝑛 𝑖 = 2. ∑ 1𝑛 𝑖2 = 3. ∑ 1𝑛 𝑖3 = 4. n! 5. Express using Big Oh notation. Department of I&CT, MIT, Manipal Find the asymptotic time complexity of the following 𝑛 𝑛+1 1. ∑ 1𝑛 𝑖 = 2 𝑛 𝑛+1 2𝑛+1 2. ∑ 1𝑛 𝑖2 = 6 𝑛 𝑖3 𝑛2 𝑛+1 2 3. ∑1 = 4 4. n! 5. O(max{mn2, m2n}) = O(m3) if m > n else O(n3). Department of I&CT, MIT, Manipal Thank You Department of I&CT, MIT, Manipal