Algorithms and Data Structures Flashcards
What is the main problem addressed in Insertion Sort?
Given a sequence, find a permutation such that the numbers are comparable.
What is the initial state of the left hand in the Insertion Sort algorithm?
Initially empty, all cards are on the table.
What does the right hand do in the Insertion Sort algorithm?
Picks up cards and puts them in the correct position in the left hand.
What is maintained in the left hand during Insertion Sort?
A sorted sequence.
What is the fundamental characteristic of an incremental algorithm?
It builds up a solution incrementally.
What is a loop invariant?
A condition that is always true at a specific point in the loop.
What does the correctness of an algorithm depend on?
It halts with the output required by the problem for every input instance.
What is runtime complexity related to in sorting algorithms?
The number of comparisons made.
What does space complexity measure?
The memory needed in relation to the input size.
What is assumed about the space required to store a number?
It takes constant space.
What are the three ingredients needed to prove the correctness of an algorithm?
- Initialisation
- Maintenance
- Termination
What is the role of initialisation in proving correctness?
To show that the invariant is true at the start of the first pass.
What does maintenance ensure in the context of loop invariants?
That the invariant is true at each pass of the loop.
What does termination demonstrate in proving correctness?
That the violated loop condition results in correctness.
What is the significance of the loop invariant in Insertion Sort?
It ensures that the elements are sorted after the algorithm completes.
Fill in the blank: An algorithm is ______ if it halts with the output required by the problem.
correct
True or False: The actual execution time of an algorithm is solely determined by runtime complexity.
False
What is the output of a factorial function when n is 0?
1
What is the base case for the factorial function?
If n is 0, return 1.
What happens if the loop in the factorial function is never entered?
It may return an error or an undefined value.
What type of algorithms are defined as finite sequences of instructions?
Algorithms
What is the main concept behind the Divide and Conquer algorithm?
It involves dividing a problem into smaller instances, conquering those sub-problems recursively, and then combining their solutions.
What are the three main steps of the Divide and Conquer strategy?
- Divide
- Conquer
- Combine
In the context of Merge Sort, what does ‘Divide’ refer to?
Dividing an instance into smaller instances of the same problem.
In Merge Sort, what does ‘Conquer’ involve?
Recursively solving the sub-instances until a direct solution is possible.
What does ‘Combine’ mean in the context of Merge Sort?
Combining the partial solutions to form the solution for the original instance.
What is the first step in the MergeSort function?
Check if the array has one or zero elements.
What is the default call for MergeSort?
MergeSort(A, 1, A.length)
What does the Merge function do in Merge Sort?
It combines two sorted arrays into one sorted array.
What is the time complexity for the merging process in Merge Sort?
The merging process is not constant time.
True or False: Merge Sort can be implemented using recursion.
True
What are ‘sentinels’ in the context of Merge Sort?
Sentinels are used to simplify the merging process by preventing out-of-bounds errors.
Fill in the blank: The Merge function creates a new array of size ______.
[size1 + size2]
What is the base case for the MergeSort recursive function?
When the array has one or zero elements.
What happens during the ‘Combine’ step of Merge Sort?
The sorted sub-arrays are merged into a single sorted array.
How does the Merge function determine which element to add next?
By comparing the front elements of the two arrays being merged.
What is the significance of the indices i, j, and k in the Merge function?
They are used to track the current position in the left array, right array, and the merged array respectively.
True or False: Merge Sort is an example of an iterative sorting algorithm.
False
What is the overall time complexity of Merge Sort?
O(n log n)
What role does the recursive nature of Merge Sort play in its efficiency?
It allows the algorithm to break down the sorting process into manageable parts, leading to efficient sorting.
Fill in the blank: Merge Sort is particularly useful for ______.
large datasets
What happens if the input array for Merge Sort is already sorted?
It still performs O(n log n) operations, as it does not take advantage of existing order.
What type of sorting algorithm is Merge Sort classified as?
A comparison-based sorting algorithm.
What is the primary function of MergeSort?
To sort an array using the divide and conquer approach.
MergeSort divides the array into halves, sorts each half, and then merges them back together.
What is the base case for the MergeSort function?
If the array has one or zero elements, it is already sorted.
This condition prevents further recursion.
What does the Merge function do in the MergeSort algorithm?
Merges two sorted subarrays into a single sorted array.
It combines the smallest elements from each subarray.
In the Merge function, what is the significance of the variables L and R?
L represents the left subarray and R represents the right subarray.
These are used to track elements during the merging process.
What is the time complexity of the MergeSort algorithm?
O(n log n).
This complexity arises from the division of the array and the merging process.
True or False: MergeSort is an in-place sorting algorithm.
False.
MergeSort requires additional space for the temporary arrays used during the merge process.
What method is used to prove the correctness of the Merge function?
Loop invariants.
This technique ensures that the smallest elements are correctly merged.
Fill in the blank: MergeSort uses _______ to handle the sorting of subarrays.
recursion.
Each call to MergeSort processes smaller portions of the array.
What is the purpose of the recursion tree in MergeSort?
To visualize the recursive calls and their corresponding subarrays.
The tree structure helps in understanding the divide and conquer approach.
In the context of MergeSort, what does the induction hypothesis state?
MergeSort is correct for arrays of length k or less.
This is used to prove that it holds for arrays of length k+1.
What happens during the termination of the for-loop in the Merge function?
The merged array is complete and sorted.
At this point, all elements from both subarrays have been processed.
List the steps involved in the Merge function.
- Create temporary arrays for L and R
- Compare elements from L and R
- Copy the smallest element back to the main array
- Handle remaining elements
These steps ensure that the merging process is efficient and correct.
What is the initial condition for the Merge function when first called?
At first pass, k = l.
This condition helps in tracking the current position in the array.
What does the ‘if’ condition in MergeSort check for?
It checks if the subarray has more than one element.
This condition controls the recursive calls.
True or False: MergeSort can be implemented iteratively.
True.
Although it is commonly implemented using recursion, an iterative version is also possible.
What are the two cases considered in the maintenance of the Merge function?
- The current element of L is smaller
- The current element of R is smaller
These cases determine which element to copy next.
What is the role of sentinels in the Merge function?
They help handle edge cases where one subarray may be exhausted before the other.
Sentinels act as placeholders to simplify comparisons.
What are the three fundamental questions in algorithm analysis?
Correctness, Running time (Time complexity), Space complexity
In runtime analysis of sorting, what does ‘n’ represent?
The length of the ‘array’
What is the main focus when analyzing running time in sorting algorithms?
We only count comparisons
What does the running time of an algorithm depend on?
The input characteristics, such as sorted or unsorted order
What are the extreme cases to consider when analyzing running time?
Best case, Worst case
What is the worst-case scenario for Merge Sort when ‘n’ is a power of 2?
Let C be the largest number of comparisons that Merge Sort needs to sort n numbers
How do we characterize the behaviors of Insertion Sort and Merge Sort?
By comparing the number of comparisons each algorithm makes
What is the definition of ‘big-Oh’ notation?
Big-Oh of g is the set of all functions that grow at most as fast as g
What is an example of a function that grows quadratically?
f(n) = n^2
When classifying functions, what should you identify?
The additive term with the largest growth
What should you remove from the remaining term when classifying functions?
Constant terms
What does it mean if a function grows ‘exactly’ quadratically?
It grows at the same rate as n^2
What is the typical order of growth for functions used in algorithm analysis?
1 (constant), logarithmic, linear, linearithmic, quadratic, cubic, exponential
True or False: Merge sort is a member of the set of functions that grow quadratically.
False
Fill in the blank: The running time of an algorithm is proportional to the number of _______.
comparisons
What is the rule of thumb for classifying functions based on growth?
Identify the additive term with the largest growth, remove other terms, and remove constants from the remaining term
What is the definition of a data structure?
Concept to store and arrange data, so that they can be found and changed efficiently.
What is the difference between an abstract data type and its implementation?
Abstract data type is the interface of a structure; implementation is how the features are realized.
What is a priority queue?
Abstract data type that manages elements of a set, where each element has a priority.
What operations are supported by a priority queue?
- Insert(element, priority) * FindMax() * ExtractMax() * IncreaseKey(index, priority)
What is the naive implementation for inserting an element into an array for a priority queue?
Increase size of array, assign new element to the end.
What is the time complexity for the FindMax() operation in a naive implementation?
O(n)
True or False: The ExtractMax() operation in a naive implementation has a time complexity of O(1).
False
What does a max-heap property ensure?
For every node, its value is greater than or equal to the values of its children.
What is the definition of a heap?
An array corresponding to a binary tree, where all levels are full except the last one, which is filled left to right.
What is a min-heap property?
For every node, its value is less than or equal to the values of its children.
What is the goal when transforming an array into a max-heap?
To compute a max-heap in O(n) time.
What is the elementary operation used to maintain the heap property?
Heapify or MaxHeapify.
What does the MaxHeapify function do?
It sifts a node down if it is too small compared to its children.
What is the time complexity of the MaxHeapify operation?
O(log n)
Fill in the blank: A heap is an array corresponding to a binary tree, for which all levels are full except the last one, which is filled ______.
left to right.
What is the expected outcome of working bottom-up from the leaves in a heap?
To exploit tree structure for faster heap construction.
What is the requirement of a task management application using a priority queue?
- Add new tasks * Find/delete task of highest priority * Increase the priority of task(s)
What is the purpose of the MaxHeapify function?
To maintain the max-heap property of a subtree rooted at a given index.
What is the time complexity of the MaxHeapify operation?
O(log n) due to the height of the heap.
What is the local strategy used in heap operations?
Top-down.
What is the global strategy used in building a max heap?
Bottom-up.
What does the BuildMaxHeap function do?
It transforms an arbitrary array into a max-heap.
What is the runtime complexity of the BuildMaxHeap function?
O(n).
What is a priority queue?
An abstract data type that manages elements where each element has a priority.
What does the FindMax function do in a priority queue?
Returns the maximum element in the priority queue.
What is the operation of ExtractMax in a priority queue?
Removes and returns the maximum element from the priority queue.
What does the IncreaseKey operation do?
Increases the priority of a given element in the priority queue.
What is the Insert operation in a priority queue?
Adds a new element with a specified priority to the priority queue.
What is the main idea behind HeapSort?
To use a heap to sort an array by repeatedly extracting the maximum element.
What is the first step in the HeapSort algorithm?
Build a max heap from the input array.
What happens during the ExtractMax operation in HeapSort?
The largest element is removed and placed at the end of the array.
What is the worst-case runtime of HeapSort?
O(n log n).
What is the average runtime of HeapSort?
O(n log n).
True or False: HeapSort is a stable sorting algorithm.
False.
Fill in the blank: The runtime of MaxHeapify depends on the __________ of the heap.
height
What is the runtime complexity of the IncreaseKey operation?
O(log n).
What is an elementary operation in the context of heaps?
A single swap or comparison during heap operations.
What does the term ‘in situ’ mean regarding sorting algorithms?
The algorithm sorts the array without needing additional storage.
What is a geometric series in relation to heap runtime analysis?
It is used to analyze the total cost of building the heap.
What is the significance of the theorem stating a heap with n elements can be computed in __________ time?
O(n)
