CPSC 33 HW2

CPSC 33 HW2 HW2 

 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 = Xn 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 void BubbleSort ( SLL  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. Submission Instructions Please pay attention to the following when preparing your work for submission. The TAs will test your code during tutorials after the due date. Please ensure that your classes and methods exactly follow the naming specifications. Part I Please prepare a file called part1.pdf (scanned or typeset) that is packaged with the rest of the files for Part II. Part II Please package your Java class files in a compressed archive called hw2.zip. Please remove any driver programs (main methods) that you used to test your implementations. Please make sure that your name appears at the beginning of each file. Please do not place the files in different folders. Your archive should only contain the following Java files: SLLNode.java, SLL.java, SLLBubbleSort.java and Prefix.java. Please also include the file part1.pdf in your archive. 2