Where in a heap would I find the smallest element?
Is an array that is sorted in reverse order a heap?
Is { 23, 17, 14, 6, 13, 10, 1, 5, 7, 12 } a heap?
Convert the Heapify function to an iterative form.
How could I make a FIFO queue with a heap? Is this likely to be a practical thing to do?
I have k sorted lists containing a total of n
elements. Give an O(nlogk) algorithm to merge these lists into a
single sorted list. Hint: Use a heap for the merge.
A d-ary heap has d children for each node. (An
ordinary heap is a binary heap.) Show how to store a d-ary heap in an
array.
Quick Sort
What is the space complexity of the "standard" recursive quicksort? Hint: Consider the stack frames used.
Convert a recursive quicksort to an iterative one.
Suggest a simple strategy that can be used to turn any sort into a stable sort.
Radix Sort
In-place sorting algorithms do not require any more space than that occupied by
the records themselves.
I wish to sort a collection of items whose keys can only take the values 0 or 1.
Devise an O(n) algorithm for sorting these items in place.
You may use auxillary storage of constant (O(n)) size.
Can this approach be used to sort n records with
b-bit keys in O(bn) time? Explain your answer.
A sort?
An integer array of n elements has a majority element
if there is an element that occurs more than n/2 times in the array.
For example, the array:
[ 2,2,5,1,5,5,2,5,5 ]
has a majority element, but the array
[ 2,2,5,1,5,5,1,5 ]
does not have a majority element.
Design an alghorithm to determine whether or not an
array contains a majority element and to return that element if it
exists.
Hash Tables
Collisions in linked lists
What is the worst case performance of a hash table in which collisions
are stored in linked lists attached to the primary table?
Could I improve this by keeping the items in the linked lists in sorted order?
Could I use any other auxillary structure to improve the worst case performance?
I have a linked list of items with very long keys, k.
The hash value of each key, h(k) is stored with each item.
How might I make use of the hash value to speed up a search?
Will this strategy work with a search tree?
If yes, under what conditions?
Search Trees
How many binary search trees can I make from the list A B C D E?
When inserting a new node into a red-black tree, we set its colour to red. We could
have set its colour to be black without violating the
"if a node is red, its children are black" property. Why was it set to red?
Key terms
stable sort
A In a stable sort, the order of equal keys
in the original is retained in the output.