DSA Notes - Data Structures and Algorithms PDF

lOMoARcPSD|27185262 DSA notes - Samenvatting Data Structures and Algorithms Data Structures and Algorithms (Vrije Universiteit Amsterdam) Scan to open on Studeersnel Studocu is not sponsored or endorsed by any college or university...

lOMoARcPSD|27185262 DSA notes - Samenvatting Data Structures and Algorithms Data Structures and Algorithms (Vrije Universiteit Amsterdam) Scan to open on Studeersnel Studocu is not sponsored or endorsed by any college or university Downloaded by robert jahas ([email protected])  lOMoARcPSD|27185262 I really hate the profffffff :| DSA Notes Computational complexity, often referred to as time complexity, is a measure of how the execution time of an algorithm or program grows with the size of the input data. It helps us understand how efficient an algorithm is in terms of its resource usage. ❖ Time Complexity: o It measures the amount of time an algorithm takes to complete as a function of the size of the input. o It is expressed using Big O notation (e.g., O(n), O(n^2)) to describe the upper bound on the running time concerning the input size. ❖ Space Complexity: o It measures the amount of memory (space) an algorithm uses as a function of the size of the input. o Similar to time complexity, it is expressed using Big O notation to describe the upper bound on the space requirements concerning the input size. Big O Notation: o Represents the upper bound or worst-case scenario for the growth rate of an algorithm. o O(1) - Constant Time Complexity: BEST ▪ Fastest. The algorithm's runtime or space usage does not depend on the input size. o O(log n) - Logarithmic Time Complexity: ▪ Faster than linear, but slower than constant time. Common in algorithms that divide the problem size in each step. o O(n) - Linear Time Complexity: ▪ Linear growth in time or space with the input size. Basic operations increase linearly. o O(n log n) - Linearithmic Time Complexity: Downloaded by robert jahas ([email protected])  lOMoARcPSD|27185262 I really hate the profffffff :| ▪ Faster than quadratic but slower than linear. Common in efficient sorting algorithms like Merge Sort and Heap Sort. o O(n^2) - Quadratic Time Complexity: ▪ Slower than linearithmic and linear. Common in algorithms with nested loops. o O(2^n) - Exponential Time Complexity: ▪ Slower than quadratic. Often seen in brute-force algorithms exploring all possibilities. o O(n!) - Factorial Time Complexity: WORST ▪ Slowest. Extremely inefficient and rarely encountered. o So, from fastest to slowest: O(1) -> O(log n) -> O(n) -> O(n log n) -> O(n^2) -> O(2^n) -> O(n!). o O(1) - Constant Space Complexity: BEST ▪ Requires a constant amount of memory, regardless of the input size. o O(log n) - Logarithmic Space Complexity: ▪ Requires memory that grows logarithmically with the input size. Common in algorithms that use recursion. o O(n) - Linear Space Complexity: ▪ Memory usage grows linearly with the input size. Typically, the size of the input directly correlates with the space used. o O(n log n) - Linearithmic Space Complexity: ▪ Memory usage grows in a linearithmic fashion with the input size. Common in algorithms with recursive divide-and-conquer approaches. o O(n^2) - Quadratic Space Complexity: ▪ Requires memory that grows quadratically with the input size. Common in algorithms with nested loops and 2D arrays. o O(2^n) - Exponential Space Complexity: ▪ Requires memory that grows exponentially with the input size. Often seen in brute-force algorithms exploring all possibilities. o O(n!) - Factorial Space Complexity: WORST ▪ Requires memory that grows factorially with the input size. Extremely inefficient and rarely encountered. o So, from lowest to highest space complexity: O(1) -> O(log n) -> O(n) -> O(n log n) -> O(n^2) -> O(2^n) -> O(n!). Understanding Time Complexity: o Time complexity describes the efficiency of an algorithm in terms of the number of basic operations it performs. o It helps us compare algorithms and choose the most suitable one for a given problem. o Analyzing the worst-case scenario is essential because it provides an upper bound on the running time. Factors Influencing Complexity: o Input Size: The primary factor. How does the algorithm's running time or space usage grow concerning the input size? o Basic Operations: The number of fundamental steps the algorithm takes to solve the problem. o Nested Loops: Each level of nesting typically multiplies the time complexity. Space Complexity: o Similar principles apply to space complexity as with time complexity. o It measures the amount of memory an algorithm uses rather than time. Downloaded by robert jahas ([email protected])  lOMoARcPSD|27185262 I really hate the profffffff :| o Consider factors like data structures, recursion, and auxiliary space (additional memory). Best, Average, and Worst Case: o Best Case: The minimum amount of time or space an algorithm requires, typically rare and often not very informative. o Average Case: The expected time or space on average, considering all possible inputs. o Worst Case: The maximum amount of time or space an algorithm may require, provides an upper bound. Downloaded by robert jahas ([email protected])  lOMoARcPSD|27185262 I really hate the profffffff :| 1. Stacks and Queues: Stacks: A stack is a Last In, First Out (LIFO) data structure. Elements are added and removed from the same end, typically referred to as the "top" of the stack. Common operations include push (addition) and pop (removal). o Time Complexity: O(1) for push and pop operations. o Applications: Function call management, expression evaluation. Queues: A queue is a First In, First Out (FIFO) data structure. Elements are added at the rear (enqueue) and removed from the front (dequeue). It mimics a real-world queue, like people waiting in line. o Time Complexity: O(1) for enqueue and dequeue operations. o Applications: Task scheduling, breadth-first search algorithms. Comparison: o Use stacks for LIFO scenarios, like managing function calls or undo mechanisms. o Use queues for FIFO scenarios, like printing documents or managing resources in shared systems. 2. Breadth-First Search and Depth-First Search: BFS: A search algorithm that explores all the neighbors of a node before moving on to the next level of nodes. It uses a queue to keep track of the nodes to be visited to guarantee the shortest path in an unweighted graph. It requires more memory as it has to store all the neighbors at the current level. Typically used when the shortest path or the level-wise traversal is essential. o Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges. o Applications: Shortest path finding in unweighted graphs, web crawling and network broadcasting, connected components in a graph. Downloaded by robert jahas ([email protected])  lOMoARcPSD|27185262 I really hate the profffffff :| DFS: A search algorithm that explores as far as possible along each branch before backtracking. It can be implemented using a stack or recursion. It consumes less memory as it explores as far as possible along a branch before backtracking, however it may not find the shortest path. Often used in scenarios where memory is a concern or when the goal is to explore deeply into a branch. o Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges. o Applications: Topological sorting (no-cycle graph) of a directed acyclic graph (DAG), solving puzzles like mazes, detecting cycles in a graph. Comparison: o Completeness: ▪ BFS is complete, ensuring that it will find the shortest path in an unweighted graph. ▪ DFS is not necessarily complete and may not find the shortest path. Downloaded by robert jahas ([email protected])  lOMoARcPSD|27185262 I really hate the profffffff :| o Memory Usage: ▪ BFS tends to use more memory due to storing all the neighbors at the current level. ▪ DFS consumes less memory as it explores deeply before backtracking. o Implementation: ▪ BFS often uses a queue. ▪ DFS can be implemented using a stack or recursion. o Search Space: ▪ BFS explores the breadth of the graph. ▪ DFS explores the depth of the graph. 3. Priority Queues: A priority queue is an abstract data type similar to a regular queue, but each element has an associated priority. Elements with higher priority are served before those with lower priority. Time Complexity: Depends on the implementation. Binary heaps offer O(log n) time for both insertion and extraction. Applications: Dijkstra's algorithm, Huffman coding, task scheduling with different priorities. Comparison: Use when tasks need to be prioritized and processed accordingly. 4. Sorting Algorithms: Bubble Sort: Simple and inefficient. Time complexity: O(n^2). o Time Complexity: O(n^2). o Application: Educational purposes, small datasets. o Comparison: Inefficient for large datasets. Selection Sort: Finds the minimum element and puts it at the beginning. o Time Complexity: O(n^2). o Application: Small datasets. o Comparison: Simplicity at the cost of efficiency. Downloaded by robert jahas ([email protected])  lOMoARcPSD|27185262 I really hate the profffffff :| Insertion Sort: Builds a sorted array one element at a time. o Time Complexity: O(n^2). o Application: Small datasets, nearly sorted data. o Comparison: Simple, but not the most efficient. Merge Sort: Divides the array into halves, sorts them, and then merges them. o Time Complexity: O(n log n). o Application: General-purpose, stable sorting. o Comparison: Efficient for large datasets. Quick Sort: Picks a pivot and partitions the array around it. o Time Complexity: O(n log n) on average. o Application: General-purpose, in-place sorting. o Comparison: Efficient for large datasets, but worst-case time complexity can be O(n^2). Downloaded by robert jahas ([email protected])  lOMoARcPSD|27185262 I really hate the profffffff :| Heap Sort: Builds a max heap and repeatedly extracts the maximum element. o Time Complexity: O(n log n). o Application: In-place sorting. o Comparison: Efficient, especially when memory is a concern. 5. Min/Max Heap: Max Heap: A specialized tree-based data structure, in which each parent node has a value greater than or equal to its children. o Time Complexity: O(log n) for insertion and deletion in a heap. o Applications: Priority queues, graph algorithms. Min Heap: A specialized tree-based data structure, in which each parent node has a value less than or equal to its children. o Time Complexity: O(log n) for insertion and deletion in a heap. o Applications: Priority queues, graph algorithms. Downloaded by robert jahas ([email protected])  lOMoARcPSD|27185262 I really hate the profffffff :| Comparison: o Use max heaps for applications where the highest priority element needs quick access. o Use min heaps for applications where the lowest priority element needs quick access. 6. Enqueue and Dequeue: Enqueue: Adding an element to the rear of the queue. o Time Complexity: O(1) o Applications: Task scheduling, managing resources in a shared environment. Dequeue: Removing an element from the front of the queue. o Time Complexity: O(1) o Applications: Task scheduling, managing resources in a shared environment. Comparison: o Use queues for scenarios requiring ordered processing of tasks. o Use dequeues for scenarios requiring unordered processing of tasks. 7. Heap Sorting: Heap Sort uses a max heap to build a sorted array. Steps include building a max heap, repeatedly swapping the root with the last element, and heapifying the reduced heap. Time Complexity: O(n log n). Applications: In-place sorting when additional memory is limited. Comparison: Efficient for large datasets, but other sorting algorithms may be more intuitive in certain scenarios. (useful when you need a stable, in-place sorting algorithm with guaranteed O(n log n) time complexity) Downloaded by robert jahas ([email protected])  lOMoARcPSD|27185262 I really hate the profffffff :| Downloaded by robert jahas ([email protected])  lOMoARcPSD|27185262 I really hate the profffffff :| Python Codes Stacks: Queue: BFS: Downloaded by robert jahas ([email protected])  lOMoARcPSD|27185262 I really hate the profffffff :| DFS: Priority Queue: Downloaded by robert jahas ([email protected])  lOMoARcPSD|27185262 I really hate the profffffff :| Bubble Sort: Selection Sort: Insertion Sort: Downloaded by robert jahas ([email protected])  lOMoARcPSD|27185262 I really hate the profffffff :| Merge Sort: Downloaded by robert jahas ([email protected])  lOMoARcPSD|27185262 I really hate the profffffff :| Quick Sort: Max Heap: Downloaded by robert jahas ([email protected])  lOMoARcPSD|27185262 I really hate the profffffff :| Min Heap: Enqueue / Dequeue: Downloaded by robert jahas ([email protected])  lOMoARcPSD|27185262 I really hate the profffffff :| Heap Sort: Downloaded by robert jahas ([email protected])