Algorithms Exam Revision Flashcards
Containing previous exam questions and lecture slides (12 cards)
What are the various approaches to implementing a stack data structure, and in what situations might the use of an array-based implementation or a linked list-based implementation be more beneficial than the other?
Array-based stack: uses contiguous block of memory to store elements. Used when the maximum size of stack is known or memory being tight, having to minimize overhead. Fast access and simple to implement but fixed capacity and resizing stack can be computationally expensive
Linked list-based stack: uses a dynamic data structure where each element is a node that contains data and pointer to next node. top of stack is head of list. used when stack size is unpredictable, memory efficiency is important or applications with frequent memory operations. it dynamically sizes itself and has efficient memory use, but slower access and more complex implementation
Can you explain how greedy algorithms are different from divide and conquer methods? Provide examples to help illustrate each approach. Describe how these methods solve problems, focusing on how they break down problems and put together solutions
Greedy algorithms solve problems by making a sequence of local decisions, each of which appears optimal at the time. Rather than diving the problem into smaller pieces like divide and conquer, this method scans through the input and builds the solution incrementally, without recursion or combining intermediate results.
Whilst divide and conquer solves problems by recursively breaking them down into smaller, independent subproblems. Solving each subproblem then combining the results to form final solution. It solely relies on recursion and often works in a top-down manner. Effective for problems where the subproblems are simpler instances of the original and where combining solutions leads to correct global result.
What exactly is a heap data structure, and why is it valuable in computer science? Can you elaborate on its usefulness using relevant examples to showcase how it’s applied in various problem-solving scenarios? Additionally, discuss its time complexity for common operations like insertion, deletion, and finding the maximum (or minimum) element.
A heap is a specialized tree-based data structure that maintains partial order among elements based on a specific property. One property is max-heap, where each parent is greater than or equal to its children. The other property is min-heap, where each parent is less than or equal to its children. Unlike regular trees, heaps are typically implemented as arrays where the parent-child relationships follow simple index-based formulas, allowing efficient storage and access. What makes them valuable in computer science is their ability to provide fast access to the highest or lowest priority element, which makes them foundational in priority queues, heap sorts and graph algorithms like Dijkstras shortest path. In Dijkstras algorithm, a min-heap is used to efficiently select the node with the smallest tentative (temporary estimate) distance from the source. At each step, the algorithm extracts the node with the lowest cost - operation takes O(1) time to access and O(log n) time to remove due to the heap structure. Node updates take O(logn) time. Without a heap, selecting the minimum-distance node would require a linear scan of all unvisited nodes, resulting in a less efficient O(n^2) implementation. By using a min-heap, the overall time complexity improves to O((V + E) log V) when using a binary heap, where V is a node on the graph and E are the connections between nodes.
What is the difference between linked lists and sorted arrays, sorted heaps? And when would you use each?
Linked list = a linear collection of nodes where each node points to the next + dynamic sizing and efficient insertions/deletions - bad for fast random access, used when resizing is costly or frequent insertions are needed
Sorted arrays = array where elements are kept in a sorted order + fast binary search and predictable memory layout - costly insertions/deletions, used in static/mostly-read datasets or when fast searching is important and updates being rare
Heaps = binary tree-based structure where parent nodes follow the heap property (min heap child >= parent, max heap child <= parent) + quick access to min and max values in dataset - avoid if you need a sorted order of all elements, used to schedule problems and implementing priority queues
What are the different Big O Notations and their meanings?
O(1) constant time = constant time, fastest time complexity
O(log n) logarithmic time = time slowly increases whilst input size grows, efficient for large datasets
O(n) linear time = time grows proportionally to input size, decent performance and scales predictably
O(n log n) linearithmic time = faster than linear but slower than quadratic, best for comparison based sorting. Input size doubles - work load slightly more than double but not by much
O(n^2) Quadratic time = time increases with the square root of the input size, becomes slow in large datasets
O(2n) Exponential time = time doubles with each additional input element, impractical for large inputs
O(n!) Factorial time = every additional element multiplies time by all previous, usable only in very small datasets
Define time complexity
The relationship between growth of input size and growth of operations executed
What are the different sorting algorithms?
Bubble sort = comparing adjacent elements and swaps them, repeats until all elements are sorted. Easy and simple to implement, slow on large datasets T: O(n) S: O(1)
Selection sort = select smallest/largest element and swap with first unsorted element, repeat for each position in array. Simple and predictable, not stable. T: O(n^2) S: O(1)
Insertion sort = inserts each item into its correct position. Stable and efficient for small datasets, not efficient in large datasets. T: O(n) S: O(1)
Merge sort = divides array in half, recursively sorts each half then merge them back together. Good for linked list and is stable, requires additional memory. T: O(n log n) S: O(n)
Quick sort = picks a pivot and partitions array, smaller than pivot go left and larger go right. Recursively sorts partitions. Fast in practice and has in-place sorting, not stable. T: O(n log n) S: O(log n)
Heap sort = max heap structure that extracts largest element to build sorted array. Time complexity never changes, but slower than quick sort and not stable. T: O(n log n) S: O(1)
What are the different searching algorithms?
Linear Search = checks each element in list until it finds target, simple but inefficient in large datasets. T: O(1) S: O(1)
Binary Search = divides sorted array in half to eliminate half the search space each time. Efficient on sorted data but not suitable for linked lists. T: O(1) S: O(1)
Hash table lookup = uses hash function to map keys to values, allowing O(1) average access. Doesn’t need sorted data and fast average case lookups but has more memory usage and needs a good hash function. T: O(1) S: O(n)
What is dijkstras algorithm?
Classic graph algorithm used to find the shortest path from the starting node to all other nodes in weighted graph. Guarantees shortest path and it can find all shortest paths from source, not just 1 destination. but slow on very large graphs. Used in gps routing and network routing protocols.
What is the A* algorithm?
A shortest-path algorithm that uses a heuristic to guide the search towards the goal. Using a formula to determine which node to expand first - f(n) = g(n) {actual cost from start to n} + h(n) {estimated cost from n to goal}
Good in sense where it can be tuned with different heuristics and faster than dijkstras in many cases. But falls behind in needing a good heuristic and only finds shortest path to 1 target, not all nodes. Used in game ai path finding or robotics navigation
Which parameters are considered essential to analysis a good algorithm?
Time complexity and space complexity, scalability and stability (sort algos)
What is the Huffman tree?
It’s a type of binary tree used for lossless data compression, based on the frequency of occurrence of data items. Purpose is to assign shorter binary codes to more frequent characters and longer codes to less frequent characters, reducing the average size of encoded data.
Good is that no data is lost, and easy to implement with greedy strategy. But inefficient with small datasets and not adaptive.
Huffman code is how often you go to a side, 0 being going left and 1 being going right, end up with a number like 100011 to get to a specific number.
