Algorithms and Complexity (Week 1, Lesson 1) PDF

Algorithms and Complexity Introduction to DSA & Complexity Winter semester 24/25 Program week 1 week no. type of class topic additional activity 1 additional activity 2 week 1 lesson 1...

Algorithms and Complexity Introduction to DSA & Complexity Winter semester 24/25 Program week 1 week no. type of class topic additional activity 1 additional activity 2 week 1 lesson 1 Introduction and Big O / / week 1 lesson 2 Complexity - time and quiz task memory week 1 lesson 3 Mathematical and quiz task Bitwise Algorithms Program week 2 week no. type of class topic additional activity 1 additional activity 2 week 2 lesson 3 Arrays and Matrices quiz task week 2 lesson 4 Stack and Queue quiz task week 2 lab 1 Lab 1 quiz task Program week 3 week no. type of class topic additional activity 1 additional activity 2 week 3 lesson 5 Recursion and quiz task Backtracking Algorithms week 3 lesson 6 Divide and Conquer quiz task Algorithms week 3 lab 2 Lab 2 quiz task Program week 4 week no. type of class topic additional activity 1 additional activity 2 week 4 lesson 7 Searching and Sorting quiz task Algorithms week 4 lesson 8 Linked Lists and Hash quiz task week 4 lab 3 Lab 3 quiz task Program week 5 week no. type of class topic additional activity 1 additional activity 2 week 5 lesson 9 Trees quiz task week 5 lesson 10 Tree Algorithms quiz task week 5 lab 4 Lab 4 quiz task Program week 1 week no. type of class topic additional activity 1 additional activity 2 week 6 lesson 13 Graphs quiz task week 6 lesson 14 Graph Algorithms quiz task week 6 lab 5 Lab 5 quiz task Program week 6 week no. type of class topic additional activity 1 additional activity 2 week 7 lesson 11 Greedy Algorithms quiz task week 7 lesson 12 Dynamic Programming quiz task week 7 lab 6 Lab 6 quiz task Grading type of exam number of units points per unit total points quizes 20 0.8 15 tasks 20 0.8 15 labs 7 1.4 10 exam 1 60 60 Grading 51- 60 percent → 6 61 - 70 percent → 7 71 - 80 percent → 8 81 - 90 percent → 9 91 - 100 percent → 10 Data Structures and Algorithms Refers to the study of data structures used for organising and storing data, along with the design of algorithms for solving problems that operate on these data structures. They are used in solving common software challenges, from managing large data sets to optimising the speed of tasks. Why this is essential Helps in storing and managing data efficiently, making it easier to retrieve and use when needed. Applications from finding the shortest path in a GPS system or optimizing search results in a search engine. By understanding DSA, you can design systems more efficiently, which is very important in areas like web applications, databases, and machine learning etc. How to learn DSA? 1. Choose a programming language 2. Learn about time and space complexities 3. Learn data structures and algorithms 4. Solve best quality problems 5. Compete in coding contests Analysis of Algorithms Analysis of Algorithms is a fundamental aspect of computer science that involves evaluating performance of algorithms and programs. Efficiency is measured in terms of time and space. Asymptotic analysis Asymptotic analysis is a mathematical technique used for understanding the behavior of algorithms as their input increases. Uses asymptotic notations to describe the growth rate or time complexity of an algorithm, which allows us to compare different algorithms and understand how they perform in realistic scenarios. Worst Case Analysis of Algorithms Worst Case Analysis (Mostly used) In the worst-case analysis, we calculate the upper bound on the running time of an algorithm. We must know the case that causes a maximum number of operations to be executed. Best Case Analysis of Algorithms Best Case Analysis (Very Rarely used) In the best-case analysis, we calculate the lower bound on the running time of an algorithm. We must know the case that causes a minimum number of operations to be executed. Average Case Analysis of Algorithms Average Case Analysis (Rarely used) In average case analysis, we take all possible inputs and calculate the computing time for all of the inputs. Sum all the calculated values and divide the sum by the total number of inputs. Big-O Notation Big O notation is a powerful tool used in computer science to describe the time complexity or space complexity of algorithms. It provides a standardised way to compare the efficiency of different algorithms in terms of their worst-case performance. Understanding Big O notation is essential for analysing and designing efficient algorithms. What is Big-O Notation? Big-O, commonly referred to as “Order of”, is a way to express the upper bound of an algorithm’s time complexity, since it analyses the worst-case situation of algorithm. It provides an upper limit on the time taken by an algorithm in terms of the size of the input. It’s denoted as O(f(n)), where f(n) is a function that represents the number of operations (steps) that an algorithm performs to solve a problem of size n. Why is Big-O Notation Important? Big O Notation is important because it helps analyze the efficiency of algorithms. It provides a way to describe how the runtime or space requirements of an algorithm grow as the input size increases. Allows programmers to compare different algorithms and choose the most efficient one for a specific problem. Helps in understanding the scalability of algorithms and predicting how they will perform as the input size grows. Enables developers to optimize code and improve overall performance. Properties of Big-O Notation 1. Reflexivity: For any function f(n), f(n) = O(f(n)). 2. Transitivity: If f(n) = O(g(n)) and g(n) = O(h(n)), then f(n) = O(h(n)). 3. Constant Factor: For any constant c > 0 and functions f(n) and g(n), if f(n) = O(g(n)), then cf(n) = O(g(n)). Properties of Big-O Notation 4. Sum Rule: If f(n) = O(g(n)) and h(n) = O(g(n)), then f(n) + h(n) = O(g(n)). 5. Product Rule: If f(n) = O(g(n)) and h(n) = O(k(n)), then f(n) * h(n) = O(g(n) * k(n)). 6. Composition Rule: If f(n) = O(g(n)) and g(n) = O(h(n)), then f(g(n)) = O(h(n)). Big-O Notation Simplified analysis of an algorithm's efficiency 1. Complexity in terms of input size, N 2. Machine - independent 3. Basic computer steps 4. Time and space Big-O Notation General rules 1. Ignore constants 5n → O(n) 2. Certain terms dominate others O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!) Constant Time Complexity: Big O(n) Complexity Constant time complexity means that the running time of an algorithm is independent of the size of the input. x = 5 + (15 * 20) total time: O(1) x = 5 + (15 * 20) y = 15 - 2 print x + y total time: O(1) + O(1) + O(1) = 3 * O(1) Linear Time Complexity: Big O(n) Complexity Linear time complexity means that the running time of an algorithm grows linearly with the size of the input. bool findElement(int arr[], int n, int key) { for (int i = 0; i < n; i++) { if (arr[i] == key) { return true; } } return false; } Logarithmic Time Complexity: Big O(log n) Complexity Logarithmic time complexity means that the running time of an algorithm is proportional to the logarithm of the input size. int binarySearch(int arr[], int l, int r, int x) { if (r >= l) { int mid = l + (r - l) / 2; if (arr[mid] == x) return mid; if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x); return binarySearch(arr, mid + 1, r, x); } return -1; } Quadratic Time Complexity: Big O(n2) Complexity Quadratic time complexity means that the running time of an algorithm is proportional to the square of the input size. void bubbleSort(int arr[], int n) { for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { swap(&arr[j], &arr[j + 1]); } } } } Cubic Time Complexity: Big O(n3) Complexity Cubic time complexity means that the running time of an algorithm is proportional to the cube of the input size. void multiply(int mat1[][N], int mat2[][N], int res[][N]) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { res[i][j] = 0; for (int k = 0; k < N; k++) res[i][j] += mat1[i][k] * mat2[k][j]; } } } Polynomial Time Complexity: Big O(nk) Complexity Polynomial time complexity refers to the time complexity of an algorithm that can be expressed as a polynomial function of the input size n. In Big O notation, an algorithm is said to have polynomial time complexity if its time complexity is O(nk), where k is a constant and represents the degree of the polynomial. Exponential Time Complexity: Big O(2n) Complexity Exponential time complexity means that the running time of an algorithm doubles with each addition to the input data set. void generateSubsets(int arr[], int n) { for (int i = 0; i < (1