Description

This assignment consists of two parts. The first part consists of problems that will give you more practice working with linear structures, recursion and recurrence relationships. The second part consists of short coding exercises that will give you additional practice with Java generics, linked lists and recursion.

Part I

1. (5 points)

Provide pseudocode for a recursive version of selection sort that operates on an array of n elements. Use your pseudocode to set up a recurrence relation for the total number of comparisons performed. Solve the recurrence relation to determine the asymptotic complexity of selection sort.

2. (5 points)

The Catalan numbers are defined recursively as:

.

Use this definition to determine C₃. Illustrate your answer using a recursion call tree assuming a na¨ıve recursive implementation.

3. (5 points)

Determine an asymptotic upper bound for the following recurrence relations. Assume that the cost of the base case is a constant.

• T(n) = 2T(n − 1) + 1
• T(n) = T(n − 1) + T(n/2) + n

Part II

1. (10 points)

In this exercise, you are asked to write code to sort a singly linked list using bubble sort. You will also get additional practice with generic classes and methods.

We went over bubble sort in class. In the class version of bubble sort, we go over the array from right (higher indices) to left (lower indices) in each pass and swap adjacent elements that are out of order. During each pass the smallest element bubbles to the left to its appropriate spot. Think about the changes that are needed if, in each pass, we scan the array from left to right and the largest element bubbles to the right to its appropriate spot. Now think about what we would need to do if, instead of an array, we were using a singly linked list, and in each pass, we scanned the list from left to right and swapped adjacent elements that are out of order.

Two files are provided for this exercise:

SLLNode.java – Represents a node in a singly linked list.

SLL.java – A class that encapsulates a singly linked list. Helper methods are provided to add and remove elements, and to query the size.

Implement a generic static method called BubbleSort that takes a singly linked list as an input and sorts it in place using bubble sort. Your method should have the following signature:

public static <T extends Comparable<? super T>> void BubbleSort( SLL<T> list )

Please encapsulate your method in a class called SLLBubbleSort.

Your implementation should only rely on the classes SLLNode.java and SLL.java. You are not allowed to use any classes from the Java collections framework. Test your program with lists consisting of different types of Comparable elements (Integers, Doubles, Strings etc.).

2. (5 points)

A prefix expression is one where the operator appears before the operands. Like the postfix notation, it is also parentheses-free. The order of evaluation is determined by the order in which the operators and the operands appear. For example:

+ * 3 2 6 = + 6 6 = 12

+ – 2 * 3 4 5 = + – 2 12 5 = + -10 5 = -5

Write a recursive method in Java that evaluates a prefix expression. Your method should be encapsulated in a file called Prefix.java that has the following class structure:

public class Prefix {

public static int evaluate( Scanner sc ) {

// your recursive evaluation code

}

}

Please note that you are required to use recursion for the evaluation. You can assume that the provided expression will be in valid prefix notation.