Hello,
I’ve got an exercise to do today, March 8th, in class which will have to be done within 1 hour from 3:30PM – 4:30PM PST (California Time) as it will be given at the start of the class period and I will have to submitted at the end of the same class period.
It will be a pretty simple and straightforward exercise with detailed instructions to follow along with for each question.
I will attach a practice/sample exercise pdf document that I’ve gotten provided along with detailed answers for your reference, down below.
Detailed Instructions are attached in the pdf document and answers are pasted down below for each part.
Thank you so much in advance!
**********************************************************************************************
package problem1;
// Give Theta of the running time (as a function of n) of the following code snippets:
// Your answer:
// (a) Theta(n^2)
// Explanation:
// Consider the k loop. We start with k = 1, go to k = n and multiply k by 2 at every iteration.
// How many times do I need to multiply by 2 before I get to n?
// 2^x = n, when x = log n. So the running time of the k loop is log n.
// The number of iterations of the l loop is n, and sum1++ has a constant running time.
// So the k and l loop combined have Theta (n log n) running time.
// Consider the i and j loops. Since j depends on i, we need to compute the running time of these two loops together.
// for i = 1, how many times will the j loop execute? 0.
// for i = 2, how many times will the j loop execute? 1.
// for i = 3, how many times will the j loop execute? 2.
// ...
// for i = n, how many times will the j loop execute? n - 1.
// To get the running time of both loops, we need to sum up 0 + 1 + 2 + ... + (n-1) =
// (n-1)*n / 2 = Theta(n^2)
// The total running time of func1 is Theta(n log n) + Theta (n^2) = Theta(n^2).
// (b) Theta(n^4).
// Explanation:
// sum = sum + k + func1(n); has the running time Theta(n^2) becase this is the running time func1(n) from
// question 1a.
// The i loop executes n times, and the k loop executes n times (going backwards). Since they are nested,
// and k does not depend on i, we can the total number of iterations of both loops by
// multiplying n * n = n^2.
// Since the running time of sum = sum + k + func1(n); is Theta(n^2), the total running time of func2 is
// Theta(n^4).
public class Problem1 {
// (a)
public static int func1(int n) {
int sum1 = 0, sum2 = 0;
for (int k = 1; k <= n; k = k * 2) {
for (int l = 1; l <= n; l++)
sum1++;
}
for (int i=1; i <= n; i++) {
for (int j = 1; j < i; j++)
sum2++;
}
return sum1 * sum2;
}
// (b)
public static void func2(int n) {
int sum = 0;
for (int i = 1; i <= n; i++) {
for (int k = n; k >= 1; k--)
sum = sum + k + func1(n); // here we call func1 from (a)
}
System.out.println(sum);
}
}
********************************************************************************************************
Problem 2:
(a) Show the following list after the first partition operation, using the last element as a pivot:
9, 39, 3, 15, 17, 7, 29, 1, 10, 28, 21, 18
Your Answer:
First, we swap 39 and 10, then 29 and 1. Then i and j cross, and we swap the element at index i with 18, the pivot.
9 10 3 15 17 7 1 18 39 28 21 29
(b) Consider the following array: 1, 0, 13, 50, 22, 14
If this is the result after the first partition, which of these elements could have been the pivot?
Your Answer:
13
Elements on the left are smaller than 13. Elements on the right are larger.
No other element could be the pivot in this example.
*******************************************************************************************************
package problem3;
// Problem 3:
// (a) Fill in the code of the bubble sort:
// elements should be sorted from 0 to arr.length-1 in descending order
// (b) Copy the same code to method bubbleSortSubarray and
// change the code so that we sort the array from index low to arr.length - 1, in descending order
import java.util.Arrays;
public class Problem3 {
// (a)
public static void bubbleSortDescending(int[] arr) {
for (int pos = 0; pos < arr.length - 1; pos++) {
for (int j = arr.length - 1; j > pos; j--) {
if (arr[j] > arr[j-1]) {
int tmp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = tmp;
}
}
}
}
// (b)
public static void bubbleSortSubarrayDescending(int[] arr, int low) {
for (int pos = low; pos < arr.length - 1; pos++) {
for (int j = arr.length - 1; j > pos; j--) {
if (arr[j] > arr[j-1]) {
int tmp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = tmp;
}
}
}
}
public static void main(String[] args) {
int[] arr = {8, 10, 4, 6, 1, 10, 45, 16, 78, 3, 5, 90, 2, 4, 87, 56, 45, 906, 246, 26, 73, 7, 3};
// bubbleSortDescending(arr);
bubbleSortSubarrayDescending(arr, 0);
System.out.println(Arrays.toString(arr));
}
}
**************************************************************************************************
Problem 4: Consider the following function:
public int func(int n) {
if (n <= 1)
return 1;
else
return func(n - 1) + func(n - 1) + func(n - 1);
}
(a) Give a recurrence relation for this function.
T(0) = C1
T(1) = C2
T(n) = 3T(n - 1) + C
(We are solving 3 subproblems of size (n - 1) and perform some constant amount of work doing comparison, adding
the results of the subproblems and returning from the function).
(b) Solve the recurrence relation using repeated substitution or recursion trees to get the big Theta of the running time.
T(n-1) = 3T(n-2) + C
We can plug that into the original equation instead of T(n-1) to get:
T(n) = 3*(3*T(n-2) + C) + C = 9*T(n-2) + (3*C + C)
We can write that T(n-2) = 3*T(n-3) + C and plug that into the equation for T(n) to get:
T(n) = 9*(3*T(n-3) + C) + (3*C + C) = 27*T(n-3) + (9*C+ 3*C + C)
Observe that for C, after these substitutions we have the following sum: C *(3^2 + 3^1 + 3^0).
After k substitutions, we will get:
T(n) = 3^k* T(n-k) + C*( 3^0 + 3^1 + 3^2 + ... + 3^(k - 1))
The sum of powers of 3 is geometric series, and the formula for this summation is (3^k - 1) / (3 - 1) = (3^ k - 1) / 2.
So after k substitutions, we will get:
T(n) = 3^k* T(n-k) + C*(3^k - 1) / 2 (*)
We will reach the base case T(1) when n-k = 1, so when k = n - 1
Plugging k = n-1 into the (*) equation, we get:
T(n) = 3^(n-1) * T(1) + C * (3^(n-1) - 1) / 2 = = Theta(3^n)
so the running time of this recursive function is exponential, 3 to the power of n.
***************************************************************************************************
package problem5;
/** A class representing a linked list. */
public class LinkedList {
private Node head, tail;
/** Constructor */
public LinkedList() {
head = null;
tail = null;
}
/**
* Creates a new node with the given element and adds it to the back of the
* list
*/
public void append(int elem) {
Node newNode = new Node(elem);
if (tail != null) {
tail.setNext(newNode);
tail = newNode;
} else {
head = tail = newNode;
}
}
/** Prints all the nodes in the link list */
public void printNodes() {
Node current = head;
while (current != null) {
System.out.print(current.elem() + " ");
current = current.next();
}
}
/**
* Builds a new linked list from "this" linked list by including elements larger than a given threshold
* @param threshold threshold
* @return head of the new linked list
*/
public Node elementsLargerThanThres(int threshold) {
Node newListHead = null; // head of the new linked list
Node newListTail = null; // tail of the new linked list
Node current = head; // head of "this" linked list
// current will iterate over "this" list
while (current != null) {
if (current.elem() > threshold) { // found the element we want to include in the list
Node newNode = new Node(current.elem()); // create a new node
if (newListHead == null) { // we are inserting the first node
newListHead = newNode;
newListTail = newNode;
}
else {
// append to the newListTail:
newListTail.setNext(newNode);
newListTail = newNode;
}
}
current = current.next();
}
return newListHead;
}
// You can use this main method to test your code */
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.append(2);
list.append(40);
list.append(16);
list.append(3);
list.append(30);
list.append(1);
list.append(5);
list.append(67);
System.out.println("Input list: ");
list.printNodes();
System.out.println();
Node newHead = list.elementsLargerThanThres(15);
// Print elements in the new linked list
System.out.println("The result of calling elementsLargerThanThres with the threshold of 15");
Node current = newHead;
while (current != null) {
System.out.print(current.elem() + " ");
current = current.next();
}
}
} ***********************************************************************
package problem5;
/* A class representing a node in a singly linked list */
public class Node {
private int elem;
private Node next;
public Node(int elem, Node next) {
this.elem = elem;
this.next = next;
}
public Node(int elem) {
this.elem = elem;
next = null;
}
public int elem() {
return elem;
}
public void setElem(int elem) {
this.elem = elem;
}
public Node next() {
return next;
}
public void setNext(Node other) {
next = other;
}
}
*******************************************************************************************************
Problem 6
(a) Show the counter array (used in counting sort) for the following array of integers:
5, 8, 1, 9, 8, 1, 0, 4, 8, 3, 4, 6
Assume that each element is in the range from 0 to 9.
Solution:
Counter array: (indices go from 0 to 9)
[1, 2, 0, 1, 2, 1, 1, 0, 3, 1]
(b) Consider the following array of elements:
(3, Pablo), (4, Colin), (5, Julie), (1, Sean), (9, Leah), (12, Tom), (8, Xin), (7, Elsa)
Assume the range of elements is from 0 to 14.
Use Bucket Sort to sort the array, using four buckets that represent the following ranges: 0-3, 4-7, 8-11 and 12-14.
Show the bucket array.
Solution:
The bucket array will have 4 elements.
The first element will point to the following linked list:
(1, Sean) - > (3, Pablo)
The second element will point to the following linked list:
(4, Colin)-> (5, Julie)->(7, Elsa)
The third element will point to the following linked list:
(8, Xin) -> (9, Leah)
The fourth element will point to the following linked list:
(12, Tom)
After iterating over the bucket array and putting everything back into arr, we get: (1, Sean), (3, Pablo), (4, Colin), (5, Julie), (7, Elsa), (8, Xin), (9, Leah),(12, Tom)
0 comments