Week 13: Exercises

1. Worst-Case Quicksort

Suppose that in writing quicksort we choose the middle element a[length(a) / 2] rather than a random element as the pivot. Then for certain inputs quicksort will always run in time O(N²). Write a procedure badArray(out a: array of integer) that fills the given array with integers for which this quicksort implementation will perform quadratically.

2. Order Check

Write a function isSearchTree(p: pnode): boolean that returns true if the given binary tree satisfies the ordering requirements of a binary search tree.

3. Biggest Gap

Write a function that returns the greatest difference between any two consecutive values in a binary search tree.

4. Tree Successor

Write a function which, given a binary search tree of non-negative integers and an integer i, returns the next highest value in the tree, i.e. the smallest value in the tree that is greater than i. Return -1 if there are no values greater than i. Assume that all integers in the tree are unique. The value i may or may not be present in the tree. Your function should run in time O(h), where h is the height of the tree.

5. Tree Range

Write a function which determines how many values v in a binary search tree of unique integers fall in the range a ≤ v ≤ b, where a and b are function parameters. The function should run in time O(h + n), where h is the tree height and n is the number of integers in the range.

6. On the Path

Write a function that takes a graph that is a tree, i.e. a connected, undirected, acyclic graph. The function should also take three vertex ids v, w, and x. The function should return true if w is on the (unique) path that leads from v to x.

7. Cyclic Graph

Write a function that takes an undirected graph and returns true if the graph contains a cycle. (Hint: an undirected graph is cyclic if a depth-first search ever encounters a node that has already been visited.)

8. Directed Cyclic Graph

Write a function that takes an directed graph and returns true if the graph contains a cycle.

9. Twin Primes

Two integers are twin primes if they differ by exactly 2. Write a program that reads an integer N and prints all pairs of twin primes that are less than or equal to N.

Enter N: 20
3 5

5 7

11 13

17 19

Your program should run in time O(N log N) at most.

10. Infix String

Write a function evalInfix(s: string) that takes a string containing an infix expression such as ((2 + 3) * (4 + 5)) and returns an integer containing the value of the expression. The expression may contain embedded spaces. The set of valid expressions is defined by this grammar:

digit -> '0' | '1' | ... | '9'
op -> '+' | '-' | '*' | '/'
expr -> digit | '(' expr op expr ')'

11. Multidigit Numbers

Extend your function from the previous exercise so that numbers in the expression may have multiple digits: ((23 + 15) * (100 / 8)) is now a valid expression.

12. Prefix to Postfix

Write a procedure that reads an expression in prefix syntax and writes it in postfix syntax. Assume that an expression may contain single-digit numbers and the operators +, -, * and /.

13. ABC without Recursion

Write a procedure abc that takes an integer N and writes out all N-character strings containing only the letters a, b, and c. Write the procedure non-recursively by iterating over integers.

14. ABC without Recursion II

Write a procedure abc that takes an integer N and writes out all N-character strings containing only the letters a, b, and c. Write the procedure non-recursively by iteratively modifying an N-character string.

15. Drawing a Tree

Write a procedure drawTree that can print out a binary tree in a way that looks more or less like this:

    10
   /  \
  6    17
 / \   / \
2   4 15  20

16. Magic Square

A magic square is an N x N matrix of distinct positive integers in the range 1, 2, …, N² such that the sum of every row, column and diagonal is the same. For example:

2 7 6
9 5 1
4 3 8

In the square above, all rows, columns and diagonals add up to 15.

Write a program that reads an integer N followed by an N x N matrix of integers. The program should print 'magic' if the square is magic, or 'ordinary' otherwise.

17. Day of the Week

This record type represents a date:

type
  date = record
    day : 1 .. 31;    // 1 .. 31
    month : 1 .. 12;  // 1 .. 12
    year : integer;
  end;

Write a function

function dayOfWeek(d: date): integer;

that takes a date and returns an integer from 0 to 6 representing a day of the week (0 = Monday, 1 = Tuesday, …, 5 = Saturday, 6 = Sunday). You may assume that 2000 ≤ year ≤ 2099.

Hints:

• Every year divisible by 4 in the given range (including 2000) is/was a leap year.

• January 1, 2000 was a Saturday.

18. Integer Square Root

Write a function

  function intSqrt(n: integer): integer;

that finds the integer square root of n, i.e. the non-negative integer i such that i * i = n. If no such integer exists, return -1. Do not call any library functions. Your function must run in time O(log N) in the worst case.