Exam Flashcards
What is a peak in an array of numbers?
A peak is a number greater than or equal to its neighbors. The first and last number can be a peak if greater than or equal to its only neighbor.
What is meant by a ‘neighbour’ in the context of peak finding?
A neighbour is a number immediately next to the current number
Is the largest value in an array always a peak?
Yes
What’s the downside of finding the max in a large array?
It looks at every element in the array. This can be inefficient if n is large.
How does the sequential search algorithm find the maximum in an array?
It iterates through the array, comparing each value to the current maximum and updating the maximum when a larger value is found.
In the sequential search, what do “values” and “position” represent?
“values” represents the array (like a shopping list). “position” stores the index of the current maximum.
Is the maximum always the only peak in an array?
No. A peak is a local maximum. There can be multiple peaks.
What does the linear search algorithm look for?
It looks for the first value which is greater than or equal to its neighbors, which defines a peak.
How efficient is the linear search for peaks?
Efficiency depends on the peak’s position.
Best case: 1 comparison. Worst case: n comparisons.
What’s the key concept behind binary search for finding peaks?
It divides the array, focusing on the midpoint, to find a peak by comparing with its neighbors.
What’s the difference between the binary search and binary search with termination?
Binary search with termination stops when ‘start’ is greater than or equal to ‘end’
In an array of length 6, is the first position indexed as 0 or 1?
This depends on the context. In most programming languages, arrays start at index 0, but the given pseudo-code starts at 1.
In a 2D table, how is a peak defined?
A peak is a number greater than or equal to all of its up to 4 neighbours: left, right, above, and below.
How does the Steepest Ascent algorithm work?
It compares an arbitrary element to its neighbours. If smaller, select the largest neighbour and repeat. Otherwise, a peak is found.
What’s the basic idea behind 2D peak finding in the middle column?
Find the largest element in the middle column. Compare with left and right. Throw away half based on comparison till a peak is found.
How efficient is the 2D peak finding algorithm?
Each iteration eliminates half the data. Worst case: Work down to a single column. It takes m*log2n operations.
What are the considerations when determining the “best” algorithm?
Speed, size, generality, and understandability
What is meant by the complexity of an algorithm?
It refers to the rate of growth in the number of operations as the problem size grows.
What is the complexity class of finding the first name in a phone book regardless of its size?
Constant
What is the complexity of finding a phone number in a directory where the numbers aren’t sorted?
Linear
When searching for a specific name in an alphabetically sorted phone book, what is the complexity?
Logarithmic
What is the complexity of the quicksort algorithm?
Linearithmic
In the quicksort example, what value is selected as the pivot initially?
4
What is the complexity of covering extra zeros in n phone books with n entries each?
Quadratic
Which complexity class grows as 2^n?
Exponential
What is meant by an algorithm having factorial complexity?
The number of iterations grows as n!, where n! = 1x2x3x…xn.
When comparing algorithms, what do we usually use to refer to the problem size?
n.
What’s an informal way to think about problem size?
How many things the problem contains, like the number of items to be sorted.
What is the main property that a number must have to be considered a peak?
It must be greater than or equal to its neighbors.
How do we informally compare the speed of algorithms?
By looking at how many operations they perform. More operations typically mean longer execution time.
What is the time complexity of a linear search for peak finding?
O(n).
Name a common method to compare algorithms
Big O notation
What does O(1) represent
Constant time complexity
Define P in complexity classes
It represents the class of problems that can be solved in polynomial time
What is a 2D peak in a matrix
An element greater than or equal to its adjacent elements both horizontally and vertically.
How does binary search help in peak finding
It reduces the problem size by half in each iteration
What does NP stand for in complexity classes
Nondeterministic Polynomial time
Which class represents problems for which answers can be verified in polynomial time?
NP
What does O(n^2) signify
Quadratic time complexity
What is an array in data structures
An array is a data structure consisting of a fixed number of data items of the same type.
How is any array element accessed?
Any array element is directly accessible via an index value.
Can arrays have more than one index?
Yes, those are called multidimensional arrays.
What special pointers are maintained in lists?
Head (and tail for doubly linked lists) to point to the first (and last) elements
How many operations does initializing an array of n elements take?
n operations
Describe a stack.
A stack holds multiple elements of a single type and follows the LIFO principle - Last In First Out.
What is the procedure to add an element to a stack?
‘push’
How can a stack be implemented?
With an array and an integer counter to indicate the current number of elements in the stack.
How do you remove an element from a stack?
Using the ‘pop’ procedure.
Describe a queue
A queue holds multiple elements of a single type and follows the FIFO principle - First In First Out.
How can a queue be implemented?
With an array and two integer counters to indicate the current start and next insertion positions.
What is the procedure to add an element to a queue?
‘enqueue’
What is a record?
A data structure consisting of a fixed number of items. Unlike arrays, the elements in a record may be of different types and are named.
How can an array be used in relation to records?
An array may appear as a field in a record, and records may appear as elements in an array.
How are records typically addressed?
As a pointer.
How do you remove an element from a queue?
Using the ‘dequeue’ procedure.
How are fields of a record accessed?
Via the field name.
What are the key considerations for storing a large number of text strings
Minimum storage usage, quick and efficient access, and avoiding dynamic memory overhead.
What are string pools?
Data structures are for storing large numbers of strings that vary widely in length.
What is the fundamental difference between arrays and linked lists?
Arrays use contiguous memory, while linked lists use pointers to connect nodes.
What are the advantages of string pools?
: They provide an attractive alternative for storing strings with varying lengths, offering efficiency in storage and access.
How many iterations are required to sort a list of n numbers using insertion sort
n-1 iterations
In which data structure are elements arranged in a sequence based on priority?
Priority Queue
How many comparisons are typically required for insertion sort?
n-1 iterations
How many comparisons are typically required for insertion sort?
n^2/2 comparisons.
What is the unique approach of Merge Sort?
It uses a second array to hold the intermediate results and works recursively by dividing the unsorted array into two parts and merging them in order.
In a hash table, what helps in quickly locating a data value given its search key?
A hash function.
Name the two types of binary trees where values follow a specific order.
Binary Search Tree (BST) and Heap.
What does a balanced tree mean in data structures?
A tree where the depth of two subtrees of every node never differs by more than
What does the insertion sort start with?
The second element in the list
How is the complexity of the SiftUp operation determined?
The complexity is log(n) because we only swap nodes on a single branch.
What does the Siftdown operation do in a Min-Heap?
It moves the last node temporarily and ensures the correct order by swapping nodes as needed.
How do you create a binary tree from an array?
Create a complete binary tree, keeping the nodes leftmost.
How is a max-heap formed using siftdown?
Starting from a non-leaf node, elements are swapped with the largest child if they are not the largest in their subtree.
What is a heap in data structures?
A heap is an essentially complete binary tree with an additional property of being either a max-heap or min-heap.
Define Max-Heap.
A binary tree where the value in any node is less than or equal to the value in its parent node (except for the root node).
How can a heap be stored?
A heap can be stored in an array where Heap[1] is the root of the tree, and Heap[i] has children Heap[2i] and Heap[2i+1].
What is the purpose of the SiftUp operation?
To ensure the newly added element is in the correct position, maintaining the heap’s order.
What is the sorted order for Max-Heap and Min-Heap?
Max-Heap sorts the list in ascending order, and Min-Heap sorts the list in descending order.
Describe the Heapsort method briefly.
Convert an array to max-heap, remove the root element, place it at the end of the sorted array, and restore max-heap property using siftdown. Repeat until sorted.
How is a heap stored in an array?
Heap[1] is the root, Heap[2] and Heap[3] are the children of Heap[1], and in general, Heap[i] has children Heap[2i] and Heap[2i+1].
What’s the definition of a Binary Tree?
A data structure composed of nodes where each node has at most two children, organized hierarchically from a root node at the top to leaf nodes at the bottom
What is the significance of using a second array in Merge Sort?
The second array holds intermediate results.
How does Merge Sort work?
It divides the unsorted array into two parts recursively and merges them in order.
How many levels are there in a merge sort for an array of n items?
log n levels
How many operations does merge sort require
n * log n operations.
How can you convert a non-heap into a heap?
By using the Makeheap/Heapify operation
What are the children indices of Heap[i] in an array representation of a heap?
Heap[2i] and Heap[2i+1].
How is the pseudocode representation of the merge sort algorithm structured?
It uses a temporary array, a main mergesort procedure that divides and calls itself recursively, and a merge procedure that merges two halves in order.
What are the main steps in the Heapsort algorithm?
Convert the array to max-heap, repeatedly remove the root, and perform siftdown.
How do you ensure that a heap remains a binary tree after adding a new element?
Add a new leaf to the end and then swap with the parents as needed to maintain the heap property.
In the context of sorting, what is an “in-place” algorithm?
An algorithm that requires only a constant amount of additional space.
Which sorting algorithm uses the divide-and-conquer strategy?
Merge Sort
Which sorting algorithm is beneficial for nearly sorted data?
Insertion Sort
Why is QuickSort considered efficient?
Because its average case time complexity is O(n log n) and it’s in-place.
How does the Shell Sort improve upon Insertion Sort?
By comparing elements distant from each other and then progressively reducing the gap.
What’s the difference between Max Heap and Min Heap?
In a Max Heap, every parent node has a value greater than or equal to its children. In a Min Heap, it’s the opposite.
What are the key features of a vector?
It’s a dynamic array-like container, can resize automatically, allows element access using subscript, and has functions like size(), push_back(), and pop_back().
What happens during the 1st and 2nd steps of Heapsort?
1st step: Makeheap requires roughly n operations. 2nd step: Siftdown requires roughly log n operations and is repeated n-1 times.
How is the complexity of the Siftdown operation determined?
The complexity is log(n) because we only swap with numbers on one branch.
How many operations does heapsort roughly require?
n + (n-1) x log n operations.
