## Data Structures and Algorithms

Data Structures and Algorithms

CSE 310 — Data Structures and Algorithms — Spring 2016

Assignment #2

Available Tuesday, 02/02/2016; due Tuesday, 02/16/2016

See Blackboard for submission time requirements for your CSE 310 section

This assignment covers divide-and-conquer and heaps, and includes material covered in Chapters 2, 4, and

6 of the text. [100 marks total]

1. Simple Recurrences. [15 marks total]

Solve the following recurrences exactly.

(a) T(1) = 1, and for all n ! 2, T(n) = 3T(n – 1) + 2. [5 marks]

(b) T(1) = 1, and for all n ! 2 a power of 2, T(n) = 2T(n/2) + 6n – 1. [5 marks]

(c) T(1) = 1, and for all n ! 2 a power of 2, T(n) = 3T(n/2) + n2 – n. [5 marks]

2. Loop Invariants and Algorithm Correctness. [15 marks total]

In class, we showed the correctness of the insertion sort algorithm using a loop invariant, i.e., we showed

that the three properties of initialization, maintenance, and termination held, and were then able to

conclude that the entire array was sorted.

Consider the following search problem:

Input: A sequence of n integers A = ha1, a2, . . . ,ani and a value v.

Output: An index i such that v = A[i] or the special value Nil if v does not appear in A.

(a) Write pseudocode for linear search, which scans through the sequence, looking for v. [5 marks]

(b) Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant

fulfills the three necessary properties. [10 marks]

3. Ternary Binary Search. [15 marks total]

(a) Write pseudocode for a boolean function search, that performs a ternary search for an integer x

in an integer array A (sorted in increasing order), returning true if x is found in the array and

false otherwise. A ternary function generalizes binary search by splitting the input into three

sets of sizes approximately one third. The function header must be:

bool search( A, x, l, r )

where l is the left index and r is the right index into the array. The function is invoked as

search( A, x, 0, n-1 )

for an array of size n. [10 marks]

(b) Write a recurrence for the worst case run time of the function search in part (a) as a function of

n, and obtain its order using the Master Theorem. [5 marks]

4. Binary Trees. [15 marks total]

Recall that a binary tree is defined as a fintie set of nodes that is either empty or consists of a root

and two disjoint binary trees TL and TR, respectively, the left and right subtree of the root. Since

the definition itself divides a binary tree into two smaller structures of the same type, the left and the

right subtree, many problems about binary trees can be solved by applying the divide-and-conquer

technique.

1

(Do not use any asymptotic notation such as O( ) to state your answer.)

(State your loop invariant, and follow three steps explained in class.)

Height: The height of a binary tree is defined as the length of the longest path from the root to a leaf

(i.e., count the edges in the path not the nodes).

(a) Write pseudocode for a divide-and-conquer algorithm that returns the height of a binary tree

T. The function should return -1 as the height of an empty tree. [5 marks]

(b) Write a recurrence to count the number of comparisons made to compute the height in part

(a) and solve it exactly. [5 marks]

Leaf: A node in a binary tree with no children is a leaf node.

(a) Write pseudocode for a divide-and-conquer algorithm that returns the number of leaves in a

binary tree T. [5 marks]

5. Tournaments. [15 marks total]

Consider the design of a round robin tennis tournament schedule for n = 2k players. Each player must

play every other player, and each player must play one match per day for n – 1 days, the minimum

number of days needed to complete the tournament.

The tournament schedule is thus an n row by n – 1 column table whose entry in row i and column j

is the player i must content with on the jth day.

The divide-and-conquer approach constructs a schedule for one-half of the players. This schedule is

designed by a recursive application of the algorithm by finding a schedule for one half of these players

and so on. When we get down to two players, we have the base case and simply pair them up.

Suppose there are eight players. The schedule for player 1 through 4 fills the upper left corner (4 rows

by 3 columns) of the schedule being constructed. The lower left corner (4 rows by 3 columns) of the

schedule must pit the high numbered players (5 through 8) against one another. This subschedule is

obtained by adding 4 to each entry in the upper left.

We have now simplified the problem. All that remains is to have the lower-numbered player play

high-numbered players. This is easily accomplished by having players 1 through 4 play 5 through 8,

respectively, on day 4, and cyclically permuting 5 through 8 on subsequent days. Round robin schedules

for two, four, and eight players are given below.

1

1 2

2 1

1 2 3

1 2 3 4

2 1 4 3

3 4 1 2

4 3 2 1

1 2 3 4 5 6 7

1 2 3 4 5 6 7 8

2 1 4 3 6 7 8 5

3 4 1 2 7 8 5 6

4 3 2 1 8 5 6 7

5 6 7 8 1 4 3 2

6 5 8 7 2 1 4 3

7 8 5 6 3 2 1 4

8 7 6 5 4 3 2 1

(a) You should now be able to generalize the ideas to write pseudocode for a divide-and-conquer

algorithm to produce a round robin tennis tournament schedule for 2k players for any k. [5 marks]

(b) Take your pseudocode from part (a) and implement it in C/C++. It should read in an integer

k ? 6, and output a round robin tennis tournament schedule for 2k players similar to the output

above. Include your source code with you solution, as well as the output your program produces

on k = 1, 2, 3, and 4. [10 marks]

6. Heaps. [15 marks total]

A (binary) heap is a nearly complete binary tree represented in an array. Each node of the tree

corresponds to an element of the array. The array on the left is a max-heap, while the one on the right

is not a max-heap.

2

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9

16 14 10 8 7 9 3 2 4 1 16 10 15 14 7 9 3 2 8 1

(a) Write a boolean function in C/C++ that takes as parameters an array h and an integer n ! 1,

and returns true if h is an n element max-heap, and false otherwise. Be sure to take advantage

of what you know about leaf nodes! [10 marks]

(b) What is the worst case run time of your algorithm in part (a) in O(·) notation? Justify your

answer. [5 marks]

7. More on Heaps. [10 marks total]

(a) Design an e