Data Structures and Algorithms Exam 2017
Uploaded by
natembeatalliaData Structures and Algorithms Exam 2017
Uploaded by
natembeatalliaCommon questions
Powered by AIA depth-first search (DFS) algorithm traverses a graph by starting at a root node and exploring as far as possible along each branch before backtracking. DFS employs a stack data structure, either explicitly or via recursive function calls, to keep track of nodes to explore further. It systematically visits nodes, marking them as visited to avoid cycles and finding connected components or spanning trees .
Recursive functions can effectively break down complex problems into simpler sub-problems by repeatedly calling themselves. Two classic examples are the calculation of factorial numbers and solving the Fibonacci sequence, where each problem can be defined in terms of a smaller case of itself, hence systematically arriving at a solution .
Dynamic programming is an optimization technique that breaks problems into subproblems, solving each one only once and storing their solutions to avoid redundant calculations; an example is the matrix chain multiplication. Backtracking is a trial-and-error method to explore possibilities to find solutions; it systematically searches paths and backtracks upon reaching dead ends, exemplified by the N-Queens problem .
Space complexity refers to the amount of memory space required by an algorithm as it runs, whereas time complexity represents the amount of computation time the algorithm needs to complete. Space complexity focuses on the memory usage considering the variables, data structures, and call stack, while time complexity evaluates the algorithm's speed, such as number of iterations or recursive calls .
Merge sort is a divide-and-conquer algorithm that involves dividing the array into halves, recursively sorting each half, and then merging the sorted halves into a complete, sorted array. It leverages recursion to handle partitioning and employs an auxiliary merging step to combine subarrays. The overall time complexity is O(n log n) resulting from the log n levels of recursion needed for division and the linear time merging step at each level .
For a binary tree to be considered a heap, it must satisfy two conditions: it should have a complete binary tree structure, where all levels are filled except possibly for the last one, which is filled from left to right, and it should adhere to the heap property, which means each node's key is greater than or equal to its children for a max-heap or is less than or equal to its children for a min-heap .
The time complexity of the straightforward recursive Fibonacci sequence calculation algorithm is O(2^n). This results from the exponential growth of recursive tree calls, where each Fibonacci number computation involves two previous computations, causing overlapping subproblems without storing intermediate results, leading to a highly redundant and inefficient process .
Big O notation describes the upper bound of an algorithm's running time, providing a worst-case scenario. Conversely, Theta notation offers a tighter bound by describing both the upper and lower bounds, representing the average-case time complexity where an algorithm's performance can be guaranteed to fall between both thresholds .
Re-hashing involves recalculating a new hash index and placing the key in the newly calculated slot upon a collision. Chaining, on the other hand, stores colliding entries in a linked list or another data structure associated with the hash index. Linear probing resolves collisions by sequentially checking the next slots in the hash table until an empty one is found. These techniques balance between handling collisions, managing the load factor, and maintaining efficient retrieval times .
When letters D, C, B, and A are pushed onto a stack and then popped, they will be popped in the reverse order, A, B, C, D. This is because stacks follow a Last In, First Out (LIFO) principle, meaning the last element added is the first to be removed .