CS 136 Assignment 7

Due Wednesday, Nov. 7 at 11:59 am sharp. Late submissions will receive half marks if submitted before Dec. 3 at 11:59 AM sharp.

There will be no hand-marking for this assignment.

Part I -- Binary Search Trees

Use the provided bst modules (bst.h, bst.c, and bst.rkt ) to solve the following problems. For Part I, you may not modify the definitions of the structs in bst.rkt and bst.c

Assignment 7, Problem 1a. 6 marks. File bst.rkt

Provide a function (printbst t) that prints a BST constructed from BST as provided by bst.rkt in the following format:

Each node in the BST should be printed on a separate line;
the left subtree should be printed after the root;
The right subtree should be printed before the root;
The key value should be indented by 2d spaces where d is its depth, or distance from the root. That is, the root should not be indented, the keys in its subtrees should be indented 2 spaces, the keys in their subtrees 4 spaces, and so on.

For example, the complete tree containing {1,2,3,4,5,6} would be printed like this:

Observe that if you rotate the output clockwise and connect each node to its subtrees, you arrive at the conventional graphical representation of the tree. Do not use mutation.

A second example of what your output should look like can be found here.

Assignment 7, Problem 1b. 4 marks. File bst.rkt

Provide a function (memberbst i t) that returns true if i is a key in BST t, otherwise false. The running time of your function should be O(height t). Do not use mutation.

Assignment 7, Problem 1c. 4 marks. File bst.c

Define a function bool memberbst(int i, BST t) that returns true if i is an element of BST t, otherwise false. The definition of the data type BST is provided in bst.h. The running time of your function must be O(height t). You may use recursion.

Assignment 7, Problem 1d. 5 marks. File bst.rkt

Provide a nondestructive function (insertbst i t) that inserts i into BST t as a new leaf. That is, it produces a BST with the elements of t and, in addition, i. The argument t must remain unchanged. The running time must be O(height t). Do not use mutation. Hint: Since we promise that the struct BST is not #:mutable, non-destructive operations may share memory between trees.

Assignment 7, Problem 1e. 5 marks. File bst.c

Define a destructive function BST insertbst(int i, BST t) that inserts i into BST t as a new leaf. That is, it modifies t to include i and returns the resulting tree. The running time must be O(height t). You may use recursion.

Assignment 7, Problem 1f. 10 marks. File bst.rkt

Provide a function inbetweenbst: int int BST -> ilist, used as (inbetweenbst i j t), that produces a list of all the keys in the consumed BST t that are strictly between i and j. If there are not any elements in t with a key in this range then the function should produce an empty ilist. Assume i ≤ j.

You will use the ilist ADT as described in Assignment 5. Use the Racket module ilist.rkt. Only use the ADT operations provided. Do not make any assumptions about the implementation of the ADT as we will use a different implementation for testing.

The running time must be O(n), where n is the number of elements in t. Do not use mutation.

The order of the values in the produced ilist does not matter.

Assignment 7, Problem 1g. 10 marks. File bst.c

Repeat the previous question in C by defining a function inbetweenbst: int int BST -> ilist.

Use the ilist ADT as defined in the provided files: ilist.h and ilist.c. Do not assume anything about the implementation in ilist.c, as we will use another implementaton for testing.

The running time must be O(n), where n is the number of elements in t.

Part II -- AVL Trees

An AVL tree is a binary search tree with the additional property that, for every node,

the left and right subtrees are AVL trees; and
the height of the left subtree and the height of the right subtree differ by at most 1.

You can download the AVL tree files for this assignment at this link:
https://www.student.cs.uwaterloo.ca/~cs136/assignments/a7/files/

If the above link doesn't work, check Piazza.

Assignment 7, Problem 2a. 10 marks. File: avl_huh.rkt

Provide a function (avl? t) that produces true if t is an AVL tree, false otherwise. The running time must be O(n), where n is the number of elements in t. You may assume that t is either empty or a BST exactly as defined in bst.rkt, with a number as its key field. Your code may (require "bst.rkt"), as marmoset will provide this for you. Do not make any other assumption about t. Do not use mutation.

Assignment 7, Problem 2b. 10 marks. File: insert-sort-avl.c

For this problem, you are given a C implementation of an AVL tree (avl-cs136.h and avl-cs136.c) which extend the BST interface with functions insertavl and deleteavl, which insert and delete an element from an AVL tree, producing a new AVL tree. The functions are destructive. The running time for both insertavl and deleteavl is O(log n) where n is the number of elements in the tree.

Write a C program file insert-sort-avl.c that defines a main function that reads a sequence of integers (from standard input) and then prints the sequence in sorted increasing order. Your output must contain one number per line and nothing else, with no spaces anywhere and a newline at the end of each line.

Your implementation must have running time O(n*log n) and use O(n) space, where n is the length of the sequence of numbers. Your solution should be an implementation of insertion sort in which you build up the sorted list using an AVL tree.

For example, if the input contains

your program should output

Assignment 7, Problem 2c. 20 marks. File: pool.rkt

For this problem, you are given a Racket implementation of an AVL tree (avl-cs136.rkt) which extends the BST interface with functions insertavl and deleteavl, which insert and delete an element from an AVL tree, producing a new AVL tree. The functions are non-destructive. The running time for both insertavl and deleteavl is O(log n) where n is the number of elements in the tree.

For this problem, you are to implement the registration for a betting pool, where participants bet on the outcome of World Finals Simon Games. As you may recall, the score from a Simon game is an integer with no particular upper or lower bound. A participant bets on an 11-point range that the score may fall in; for example, one might bet that the score is between 10 and 20, inclusive. Each participant bets in turn, and no participant may take a bet whose range intersects that of any previous bet. Implement the following functions:

    bet: integer -> boolean
    (bet mid) 
      attempts to place a bet on the range [mid-5,mid+5]
      returns true if the bet is accepted (if there is no other bet with overlapping range),
      otherwise returns false 

    winner?: integer -> boolean
    (winner? score) 
      returns true if there is a winner, that is,
      if the given score falls within one of the registered ranges
      otherwise returns false

The World Finals is a tournament consisting of several games. Pool participants may register at any time, but will be considered to win the pool only if a score within the range happens after the range is registered. Your implementation must be no more than ten times slower than our solution, which has a running time of O(n log n) where n is the number of registrations plus the number of games. Do not use set-node-data!, set-node-left! or set-node-right!. (Note: This problem forbids the use of mutable structs, but does not forbid set!)