Introduction to Algorithms CS 201 PDF

Course Overview Introduction to Algorithms CS 201 Module 1.4 DATA STRUCTURES AND ALGORITHMS 1 Course Overview Algorithm An algorithm is...

Course Overview Introduction to Algorithms CS 201 Module 1.4 DATA STRUCTURES AND ALGORITHMS 1 Course Overview Algorithm An algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language. CS 201 DATA STRUCTURES AND ALGORITHMS 2 2 Course Overview of Algorithm Basic Categories Search − Algorithm to search an item in a data structure. CS Sort − Algorithm to sort items in 201 a certain order. Insert − Algorithm to insert an item in a data structure. DATA STRUCTURES AND Update − Algorithm to update ALGORITHMS an existing item in a data structure. Delete − Algorithm to delete an existing item from a data structure. 3 3 Course Overview Characteristics of an Algorithm CS 201 DATA STRUCTURES AND ALGORITHMS 4 4 Course How to Overview Write an Algorithms? To write an algorithm, the following things are needed as a pre-requisite: 1. The problem that is to be solved by this algorithm i.e. clear problem definition. CS 201 2. The constraints of the problem must be considered while solving the problem. DATA 3. The input to be taken to solve STRUCTURES AND the problem. 4. The output is to be expected when the problem is solved. ALGORITHMS 5. The solution to this problem is within the given constraints. Then the algorithm is written with the help of the above parameters such that it solves the problem. 5 5  Course Overview Example: Problem: Design an algorithm to add two numbers and display the result. Alternatively, the algorithm can be written as − CS 201 DATA STRUCTURES AND ALGORITHMS 6 6 Course Overview Hands-On Activity Implement the algorithm below using Java. Algorithm to add 3 numbers and print their sum: 1. START CS 201 2. Declare 3 integer variables num1, num2, and num3. 3. Take the three numbers, to be added, as inputs in variables num1, DATA STRUCTURES AND num2, and num3 respectively. 4. Declare an integer variable sum to store the resultant sum of the 3 numbers. ALGORITHMS 5. Add the 3 numbers and store the result in the variable sum. 6. Print the value of the variable sum 7. END 7 7  Time Factor − Time is measured by counting the number of key operations such as comparisons in the sorting Course Overview Algorithm Complexity Two Factors of Algorithm Analysis 1. CPU Time (Time Complexity) 2. Main memory space (Space Complexity) Time Complexity CS 201 The time complexity of an algorithm represents the amount of time required by the algorithm to run to completion. Time requirements can be defined as a numerical function T(n), where T(n) can be measured as the number of steps, provided each step consumes constant time. DATA STRUCTURES AND For example, the addition of two n-bit integers takes n steps. Consequently, the total computational time is T(n) = c ∗ n, where c is the time taken for the addition of two bits. Here, ALGORITHMS we observe that T(n) grows linearly as the input size increases. Space Complexity The space complexity of an algorithm represents the amount of memory space required by the algorithm in its life cycle. The space required by an algorithm is equal to the sum of the following two components − A fixed part is a space required to store certain data and variables, that are independent of the size of the problem. For example, simple variables and constants used, program size, A variable part is a space required by variables, whose size depends on the size of the, for 8 8 example, dynamic memory allocation, recursion stack space, etc. Course Overview Algorithm Analysis The efficiency of an algorithm can be analyzed at two different stages, before implementation, and after implementation. They are the following A Priori Analysis − It's used to identify the most frequently CS 201 occurring elements and meaningful associations in a dataset. As an example, products brought in by consumers to a shop may all be used as inputs in this system.. DATA STRUCTURES AND ALGORITHMS A Posterior Analysis − This is an empirical analysis of an algorithm. The selected algorithm is implemented using a programming language. This is then executed on the target computer. In this analysis, actual statistics like running time and space required, are collected. 9 9 Course Overview Asymptotic Analysis Asymptotic analysis of an algorithm refers to defining the mathematical foundation/framing of its run-time performance. Using asymptotic analysis, we can very well conclude the best case, average case, and worst-case scenario of an algorithm. CS 201 Asymptotic analysis is input bound i.e. if there's no input to the algorithm, it is concluded to work in constant time. Other than the "input" all other factors are considered constant. DATA STRUCTURES AND Asymptotic analysis refers to computing the running time of any operation in mathematical ALGORITHMS units of computation. For example, the running time of one operation is computed as f(n), and maybe for another operation, it is computed as g(n2). This means the first operation running time will increase linearly with the increase in n and the running time of the second operation will increase exponentially when n increases. Similarly, the running time of both operations will be nearly the same if n is significantly small. 10 10 Course Overview Asymptotic Notations Asymptotic Notations are programming languages that allow you to analyze an algorithm’s running time by identifying its behavior as its input size grows. This is also referred to as an algorithm’s growth rate. You can’t compare two algorithm’s head to head. You compare space and time complexity using asymptotic analysis. It compares two CS 201 algorithms based on changes in their performance as the input size is increased or decreased. The time required by an algorithm falls under three types − DATA STRUCTURES AND o Best Case − Minimum time required for program ALGORITHMS o Average Case − Average time required for program o Worst Case − Maximum time required for program There are mainly three asymptotic notations: o Big-O Notation (O-notation) o Omega Notation (Ω-notation) o Theta Notation (Θ-notation) 11 11  Course 1. Big-OOverview Notation Big-O notation represents the upper bound of the running time of an algorithm. Therefore, it gives the worst-case complexity of an algorithm. o It is the most widely used notation for Asymptotic analysis. o It specifies the upper bound of a function. o The maximum time required by an algorithm or the worst-case time complexity. CS 201 It returns the highest possible output value(big-O) for a given input. o Big-Oh(Worst Case) It is defined as the condition that allows an algorithm to complete statement execution in the longest amount of time possible. DATA STRUCTURES AND Mathematical Representation: ALGORITHMS O(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0 } 12 12  Course 2. ThetaOverview Notation (Θ-Notation) Theta notation encloses the function from above and below. Since it represents the upper and the lower bound of the running time of an algorithm, it is used for analyzing the average- case complexity of an algorithm. Theta (Average Case) You add the running times for each possible input combination and take the average in the average case. CS 201 Mathematical Representation: DATA STRUCTURES AND ALGORITHMS Θ (g(n)) = {f(n): there exist positive constants c1, c2 and n0 such that 0 ≤ c1 * g(n) ≤ f(n) ≤ c2 * g(n) for all n ≥ n0} Note: Θ(g) is a set 13 13 Course Overview 3. Omega Notation (Ω-Notation): Omega notation represents the lower bound of the running time of an algorithm. Thus, it provides the best-case complexity of an algorithm. The execution time serves as a lower bound on the algorithm’s time complexity. It is defined as the condition that allows an algorithm to complete statement execution in the shortest amount of time. CS 201 Mathematical Representation DATA STRUCTURES AND Ω(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ cg(n) ≤ f(n) for all n ≥ALGORITHMS n0 } 14 14