Data Structures and Algorithms
Tutorial Problems: Part 4

Tutorial 4

Heap Sort

  1. What would be the
    1. minimum,
    2. maximum
    number of elements in a heap of height h?
  2. Where in a heap would I find the smallest element?
  3. Is an array that is sorted in reverse order a heap?
  4. Is { 23, 17, 14, 6, 13, 10, 1, 5, 7, 12 } a heap?
  5. Convert the Heapify function to an iterative form.
  6. How could I make a FIFO queue with a heap? Is this likely to be a practical thing to do?
  7. 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.
  8. 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

  1. What is the space complexity of the "standard" recursive quicksort?
    Hint: Consider the stack frames used.
  2. Convert a recursive quicksort to an iterative one.
  3. 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.
  1. 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.
  2. 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

  1. Collisions in linked lists
    1. What is the worst case performance of a hash table in which collisions are stored in linked lists attached to the primary table?
    2. Could I improve this by keeping the items in the linked lists in sorted order?
    3. Could I use any other auxillary structure to improve the worst case performance?
  2. 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

  1. How many binary search trees can I make from the list A B C D E?
  2. 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.

Continue on to Tutorials: Part 5 Back to the Table of Contents
© John Morris, 1998