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:
C0 = 1,
Cn+1 =
n X i=0
CiCn−i, n ≥ 0.
Use this definition to determine C3. 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:
1
CPSC 331: Spring 2018 HW2
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
