DSA-Introduction-and-Arrays.pptx

Introduction to Algorithms CCS 104-Data Structures and Algorithms  What is an Algorithm? An algorithm is a well-defined, step-by-step procedure for solving a problem or accomplishing a specific task. It can be defined as a set of precise, unambiguous, and order...

Introduction to Algorithms CCS 104-Data Structures and Algorithms  What is an Algorithm? An algorithm is a well-defined, step-by-step procedure for solving a problem or accomplishing a specific task. It can be defined as a set of precise, unambiguous, and ordered steps that, when followed, leads to a solution or output for a given problem or task. It must be clear, deterministic, and have a finite number of steps. 08/30/2024 CCS 104 - Data Structures and Algorithms  Important properties of an algorithm  Correctness: The algorithm should be correct. It should be able to process all the given inputs and provide correct output.  Efficiency: The algorithm should be efficient in solving problems. 08/30/2024 CCS 104 - Data Structures and Algorithms  Examples of Algorithms in everyday life A recipe is an algorithm for preparing a specific dish, providing a series of steps that, when executed in order, result in a completed meal. The process of assembling a piece of furniture by following the instructions is another example of an algorithm. The daily routine you follow going to school. 08/30/2024 CCS 104 - Data Structures and Algorithms  Algorithms in Computer Science Algorithms are the core of software development. Used to process, manipulate, and analyze data to solve complex problems efficiently. Algorithms include sorting a list of numbers, searching for a specific item in a dataset, compressing and decompressing files, and routing data in a network. 08/30/2024 CCS 104 - Data Structures and Algorithms  Algorithm Design Techniques Algorithm design techniques are strategies used to create efficient and effective algorithms for solving problems or accomplishing tasks. Brute Force Divide and Conquer Greedy Algorithms Dynamic programming Backtracking Branch and bound 08/30/2024 CCS 104 - Data Structures and Algorithms  Algorithm Design Techniques  Brute Force - technique involves trying all possible solutions to a problem until the correct one is found.  Divide and conquer - breaks a problem down into smaller subproblems and solves each subproblem independently. Examples of divide and conquer algorithms include merge sort and quick sort.  Greedy algorithms - make locally optimal choices at each step with the hope of finding a globally optimal solution. Examples of greedy algorithms include Dijkstra's shortest path algorithm and Kruskal's minimum spanning tree algorithm. 08/30/2024 CCS 104 - Data Structures and Algorithms  Algorithm Design Techniques  Dynamic programming - used to solve problems that exhibit overlapping subproblems and optimal substructure. It typically involves breaking the problem down into smaller subproblems, solving each subproblem only once, and storing the results in a table for future reference. Examples of dynamic programming algorithms include the Fibonacci sequence, the knapsack problem, and the longest common subsequence problem. 08/30/2024 CCS 104 - Data Structures and Algorithms  Algorithm Design Techniques  Backtracking - is a technique used to solve problems that involve searching through a large solution space. It involves incrementally building candidates to the solution and, when a partial candidate cannot be extended to a complete solution, backtracking to a previous step to explore other possibilities. Examples of backtracking algorithms include the eight queens problem and the traveling salesman problem. 08/30/2024 CCS 104 - Data Structures and Algorithms  Algorithm Design Techniques  Branch and bound - is an optimization technique used for solving combinatorial problems. It involves partitioning the problem into smaller subproblems (branching) and using bounds to eliminate subproblems that cannot lead to an optimal solution (bounding). Examples of branch and bound algorithms include the integer linear programming problem and the traveling salesman problem. 08/30/2024 CCS 104 - Data Structures and Algorithms  Algorithm Analysis and Complexity Algorithm analysis and complexity are essential concepts in computer science that help determine the efficiency and performance of algorithms. Understanding these concepts allows developers to choose the most suitable algorithm for a particular task or problem, considering the available resources and requirements. 08/30/2024 CCS 104 - Data Structures and Algorithms  Algorithm Analysis and Complexity  Worst Case complexity: It is the complexity of solving the problem for the worst input of size n. It provides the upper bound for the algorithm. This is the most common analysis used.  Average Case complexity: It is the complexity of solving the problem on an average. We calculate the time for all the possible inputs and then take an average of it.  Best Case complexity: It is the complexity of solving the problem for the best input of size n. 08/30/2024 CCS 104 - Data Structures and Algorithms  Why analyze algorithms? Analyzing algorithms helps developers understand their behavior, compare different algorithms, and optimize their performance. By understanding an algorithm's time and space complexity, developers can make informed decisions about the most efficient algorithm for a given problem, considering factors such as available memory, processor speed, and problem size. 08/30/2024 CCS 104 - Data Structures and Algorithms  Factors affecting algorithm performance The performance of an algorithm can be affected by several factors:  size of the input data  hardware and software environment  implementation details. 08/30/2024 CCS 104 - Data Structures and Algorithms  Measuring algorithm efficiency Algorithm efficiency is typically measured in terms of: Time complexity refers to the number of basic operations an algorithm performs as a function of the input size. Space complexity refers to the amount of memory an algorithm uses as a function of the input size. 08/30/2024 CCS 104 - Data Structures and Algorithms  Asymptotic Notation It is a way to describe the growth of an algorithm's time or space complexity as the input size approaches infinity. It provides an abstraction that allows developers to compare algorithms and understand their behavior for large input sizes without considering implementation-specific details. 08/30/2024 CCS 104 - Data Structures and Algorithms  Algorithm Analysis Notations Big O notation (O): Big O notation describes the upper bound of an algorithm's growth rate, or in other words, the maximum number of operations an algorithm will perform as a function of the input size. It is used to express the worst-case time complexity. 08/30/2024 CCS 104 - Data Structures and Algorithms  Algorithm Analysis Notations Big Omega notation (Ω): Big Omega notation describes the lower bound of an algorithm's growth rate, or the minimum number of operations an algorithm will perform as a function of the input size. It is used to express the best-case time complexity. 08/30/2024 CCS 104 - Data Structures and Algorithms  Algorithm Analysis Notations Big Theta notation (Θ): Big Theta notation is used when both the upper and lower bounds of an algorithm's growth rate are the same, or in other words, when the best-case and worst-case time complexities are equal. It is used to express the average-case time complexity. 08/30/2024 CCS 104 - Data Structures and Algorithms  Time and Space Complexity It is a way to describe the growth of an algorithm's time or space complexity as the input size approaches infinity. It provides an abstraction that allows developers to compare algorithms and understand their behavior for large input sizes without considering implementation-specific details. 08/30/2024 CCS 104 - Data Structures and Algorithms  Time Complexity Time complexity is a measure of the amount of time an algorithm takes to execute as a function of the input size. It is usually expressed using the asymptotic notation. Time complexity analysis focuses on the number of basic operations performed by the algorithm, which are typically assumed to take constant time. 08/30/2024 CCS 104 - Data Structures and Algorithms  Time Complexity classes O(1): Constant time complexity, meaning the algorithm's execution time does not depend on the input size. O(log n): Logarithmic time complexity, meaning the algorithm's execution time grows logarithmically with the input size. O(n): Linear time complexity, meaning the algorithm's execution time grows linearly with the input size. O(n log n): Linearithmic time complexity, which is commonly seen in sorting algorithms like merge sort and quick sort. 08/30/2024 CCS 104 - Data Structures and Algorithms  Time Complexity classes O(n^2): Quadratic time complexity, which is commonly seen in nested loops and some sorting algorithms, like bubble sort and insertion sort. O(n^3): Cubic time complexity, which occurs less frequently but can be found in some algorithms dealing with three-dimensional data or in algorithms with three nested loops. O(2^n), O(n!): Exponential and factorial time complexity, which are typical in brute-force algorithms and some combinatorial problems. 08/30/2024 CCS 104 - Data Structures and Algorithms  Space Complexity Space complexity is a measure of the amount of memory an algorithm uses as a function of the input size. It takes into account the memory required by the input data, any auxiliary data structures, and the memory used by the algorithm itself. Like time complexity, space complexity is typically expressed using asymptotic notation. 08/30/2024 CCS 104 - Data Structures and Algorithms  Space Complexity classes O(1): Constant space complexity, meaning the algorithm uses a fixed amount of memory regardless of the input size. O(log n): Logarithmic space complexity, meaning the algorithm's memory usage grows logarithmically with the input size. O(n): Linear space complexity, meaning the algorithm's memory usage grows linearly with the input size. 08/30/2024 CCS 104 - Data Structures and Algorithms  Time Complexity Order A list of commonly occurring algorithm Time Complexity in increasing order: Name Notation Constant O(1) Logarithmic O(log n) Linear O(n) N-LogN O(n log n) Quadratic O(n2) Cubic O(n3c) Exponential O(2n) Factorial O(n!) or O(nn) 08/30/2024 CCS 104 - Data Structures and Algorithms  Time Complexity Order Function Growth Rate (Approximate) N O(1) O(log n) O(n) O(n log O(n2) O(n3) O(2n) n) 10 1 3 10 30 102 103 103 102 1 6 102 6x102 104 106 1030 103 1 9 103 9x103 106 109 10300 104 1 13 104 13x104 108 1012 103000 105 1 16 105 16x105 1010 1015 1030000 106 1 19 106 19x106 1012 1018 10300000 From the above table, it is clear that the time required to complete some algorithms changes drastically with the growth rate. For the same data set, some algorithms will give results in minutes if not seconds, while others will not be able to complete in days. 08/30/2024 CCS 104 - Data Structures and Algorithms  Constant Time O(1) An algorithm is said to run in constant time if the output is produced in constant time regardless of the input size. Examples: 1. Accessing the nth element of an array 2. Push and pop of a stack 3. Add and remove a queue 08/30/2024 CCS 104 - Data Structures and Algorithms  Logarithmic Time O(log n) An algorithm is said to run in logarithmic time if the execution time of the algorithm is proportional to the logarithm of the input size. At each step of an algorithm, a significant portion of the input is pruned/rejected without traversing it. Examples: 1. Binary Search algorithm 08/30/2024 CCS 104 - Data Structures and Algorithms  Linear Time O(n) An algorithm is said to run in linear time if the execution time of the algorithm is directly proportional to the input size. Examples: 1. Array operations like search element, find min, find max etc. 2. Linked list operations like traversal, find min, find max etc. 08/30/2024 CCS 104 - Data Structures and Algorithms  N-LogN Time O(n log n) An algorithm is said to run in nlogn time if execution time of an algorithm is proportional to the product of input size and logarithm of the input size. In these algorithms, each time the input is divided into half (or some proportion) and each portion is processed independently. Examples: 1. Merge-Sort 2. Quick-Sort (Average case) 3. Heap-Sort 08/30/2024 CCS 104 - Data Structures and Algorithms  Quadradic Time O(n2) An algorithm is said to run in quadratic time if the execution time of an algorithm is proportional to the square of the input size. In these algorithms each element are compared with all the other elements. Examples: 1. Bubble-Sort 2. Selection-Sort. 3. Insertion-Sort. 08/30/2024 CCS 104 - Data Structures and Algorithms  Exponential Time O(2n) In these algorithms, all possible subsets of elements of input date are generated. 08/30/2024 CCS 104 - Data Structures and Algorithms  Deriving the Runtime Function of an Algorithm  Constants Each statement takes a constant time to run. Time Complexity is O(1)  Loops The running time of a loop is a product of the running time of the statement inside a loop and the number of iterations in the loop. Time Complexity is O(n) 08/30/2024 CCS 104 - Data Structures and Algorithms  Deriving the Runtime Function of an Algorithm  Nested Loop The running time of a nested loop is a product of the running time of the statements inside the loop multiplied by a product of the size of all the loops. Time Complexity is O(nc). Where c is several number of loops. For two loops, it will be O(n2)  Consecutive Statements Add the running times of all the consecutive statements 08/30/2024 CCS 104 - Data Structures and Algorithms  Deriving the Runtime Function of an Algorithm  If-Else Statement Consider the running time of the larger of if block or else block and ignore the other block.  Logarithmic statement If constant factors decrease each iteration the input size. Time Complexity = O(log n). 08/30/2024 CCS 104 - Data Structures and Algorithms  Example 1 class TimeComplexity { public static void main(String[] args) { System.out.println(sum(1500000000L, 150000000L)); } static long sum(long n, long m) { long l = m * n; return l; } } O(1 ) 08/30/2024 CCS 104 - Data Structures and Algorithms  Example 1.1 class TimeComplexity1 { public static void main(String[] args) { System.out.println(func1(100)); } static int func1(int n) { int m = 0; for (int i = 0; i < n; i++) { m += 1; } return m; O(n } } ) 08/30/2024 CCS 104 - Data Structures and Algorithms  Example 2 class TimeComplexity2 { public static void main(String[] args) { System.out.println(func2(100)); } static int func2(int n) { int i, j, m = 0; for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { m += 1; } } return m; O(n2) } 08/30/2024 } CCS 104 - Data Structures and Algorithms  Example 3 class TimeComplexity3 { public static void main(String[] args) { func1(10); } static void func1(int n) { int counter = 1; int i, j, m = 0; for (i = 0; i < n; i++) { for (j = 0; j < i; j++) { //n*(n-1)/2 counter++; } } O(n ) 2 } 08/30/2024 } CCS 104 - Data Structures and Algorithms  Example 4 class TimeComplexity4 { public static void main(String[] args) { System.out.println(func4(100)); } static int func4(int n) { int i, m = 0; i = 1; while (i < n){ m += 1; i *= 2; } return m; O(log } } n) 08/30/2024 CCS 104 - Data Structures and Algorithms  Example 5 class TimeComplexity6 { public static void main(String[] args) { System.out.println(func6(100)); } static int func6(int n) { int i, j, k, m = 0; for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { for (k = 0; k < n ; k++) { m += 1; } } } return m; O(n ) 3 } 08/30/2024 } CCS 104 - Data Structures and Algorithms  Example 6 class TimeComplexity5 { public static void main(String[] args) { System.out.println(func5(100)); } static int func5(int n) { int i, m = 0; i = n; while (i > 0){ m += 1; i /= 2; } return m; O(log } } n) 08/30/2024 CCS 104 - Data Structures and Algorithms  Example 7 class TimeComplexity9 { public static void main(String[] args) { System.out.println(func9(100)); } int func9(int n) { int i, j, m = 0; for (i = n; i > 0; i /= 2) { for (j = 0; j < i; j++){ m += 1; } } return m; O(n } } ) 08/30/2024 CCS 104 - Data Structures and Algorithms