CMPS 144 Computer Science 2 Name____________________________________ Midterm Exam Spring 2021 (March 30) Dr. McCloskey There are five problems. You will be graded upon your best four answers. 1. In a...

1 answer below »
test questions


CMPS 144 Computer Science 2 Name____________________________________ Midterm Exam Spring 2021 (March 30) Dr. McCloskey There are five problems. You will be graded upon your best four answers. 1. In a list, an inversion occurs where one element has lesser value than its predecessor. For example, in the list 〈3 7 12 4 9 5 6〉, there are two inversions: at the positions where 4 and 5 occur. Develop a method that, given a positional list containing integers, returns the number of inversions within that list. For example, if the given list were as described above, the method should return two. As in Lab 7, we will use PLC and PL With C to refer to the data types corresponding to, respectively, positional list cursors and positional lists. /* Returns the number of inversions in the given list. */ public static int inversionCount(PL_With_C list) { PLC cursor = list.getCursor(); } 1 2. Complete the program on the next page to obtain a solution for the three-color partitioning problem. Given is an array a[] each of whose elements can be classified as being exactly one of RED, WHITE, or BLUE. Using N as a shorthand for a.length, the postcondition is as follows: 0 k m N +-------------+---------------+--------------+ a | all RED | all WHITE | all BLUE | && 0<><><=n +-------------+---------------+--------------+="" in="" words,="" this="" says="" that="" 0="" ≤="" k="" ≤="" m="" ≤="" n="" and="" that="" every="" element="" in="" a[0..k)="" is="" red,="" every="" element="" in="" a[k..m)="" is="" white,="" and="" every="" element="" in="" a[m..n)="" is="" blue.="" the="" loop="" invariant="" must="" be="" as="" follows:="" 0="" j="" k="" m="" n="" +--------+-----------+-------------+------------+="" a="" |="" |="" all="" red="" |="" all="" white="" |="" all="" blue="" |="" &&=""><><><><=n +--------+-----------+-------------+------------+="" in="" words,="" this="" says="" that="" 0="" ≤="" j="" ≤="" k="" ≤="" m="" ≤="" n="" and="" that="" every="" element="" in="" a[j..k)="" is="" red,="" every="" element="" in="" a[k..m)="" is="" white,="" and="" every="" element="" in="" a[m..n)="" is="" blue.="" (it="" says="" nothing="" about="" the="" colors="" of="" elements="" in="" a[0..j).)="" notice="" that="" we="" obtained="" the="" invariant="" by="" replacing="" the="" occurrence="" of="" 0="" in="" the="" postcondition="" by="" a="" fresh="" variable="" j.="" arrive="" at="" your="" solution="" by="" correctly="" supplying="" an="" expression="" for="" each="" underline="" and="" filling="" in="" the="" body="" of="" the="" loop.="" you="" can="" assume="" the="" existence="" of="" boolean="" methods="" isred(),="" iswhite(),="" and="" isblue()="" having="" the="" obvious="" behaviors.="" the="" program="" should="" modify="" the="" array="" only="" by="" swapping="" elements="" using="" the="" swap()="" method:="" the="" invocation="" swap(a,t,s)="" causes="" the="" values="" in="" locations="" t="" and="" s="" of="" a[]="" to="" be="" swapped.="" 2="" *="" precondition:="" every="" element="" in="" a[0..n)="" is="" either="" red,="" white,="" or="" blue="" */="" j="______;" k="______;" m="______;" *="" loop="" invariant:=""><><><><=n &&="" *="" every="" element="" in="" a[j..k)="" is="" red="" &&="" *="" every="" element="" in="" a[k..m)="" is="" white="" &&="" *="" every="" element="" in="" a[m..n)="" is="" blue="" */="" while="" (="" __________________="" )="" {="" }="" *="" post:=""><><><=n &&="" every="" element="" in="" a[0..k)="" is="" red="" &&="" *="" every="" element="" in="" a[k..m)="" is="" white="" &&="" *="" every="" element="" in="" a[m..n)="" is="" blue="" */="" 3="" 3.="" suppose="" that="" graph="" is="" an="" instance="" of="" the="" class="" digraph="" having="" ten="" vertices="" and="" having="" edges="" as="" indicated="" below.="" further="" suppose="" that="" we="" make="" the="" call="" shortpathlens(graph,="" 9)="" to="" the="" method="" shown="" below="" on="" the="" left,="" which="" will="" return="" an="" array="" containing="" the="" lengths="" of="" the="" shortest="" paths="" from="" vertex="" 9="" to="" all="" the="" other="" vertices.="" show="" the="" contents="" of="" this="" array,="" the="" history="" of="" the="" queue="" used="" in="" the="" method="" (using="" the="" notation="" from="" class/lab),="" and="" the="" breadth-first="" search="" tree="" showing="" the="" shortest="" paths.="" (there’s="" space="" on="" the="" next="" page="" for="" the="" tree.)="" public="" int[]="" shortpathlens(digraph="" g,="" int="" source)="" {="" vertex="" has="" edges="" to="" final="" int="" n="g.numVertices();" ------="" ------------="" int[]="" dist="new" int[n];="" 0="" 4,7,9="" for="" (int="" i="0;" i="" !="N;" i++)="" 1="" 3,8,9="" {="" dist[i]="-1;" }="" 2="" 4,5="" dist[source]="0;" 3="" 5,7,9=""> q = new QueueViaX(); // 4 0,3 q.enqueue(source); // 5 2,6,7,8 while (!q.isEmpty()) { // 6 0 int x = q.frontOf(); q.dequeue(); // 7 4 for (int y = 0; y != N; y++) { // 8 4,5,9 if (dist[y] == -1 && g.hasEdge(x,y)) { // 9 0,2,3 dist[y] = dist[x] + 1; // ----------------------- q.enqueue(y); } } return dist; } History of the queue: +----+----+----+----+----+----+----+----+----+----+ | | | | | | | | | | | +----+----+----+----+----+----+----+----+----+----+ Enqueued at Dequeued at Final contents of array returned (dist[ ]): 0 1 2 3 4 5 6 7 8 9 +----+----+----+----+----+----+----+----+----+----+ dist | | | | | | | | | | | +----+----+----+----+----+----+----+----+----+----+ Extra Credit problem described on next page ... 4 Extra Credit: The method shown computes only the lengths of the shortest paths from the source vertex to all the others. It conveys no information about which vertices occur on those paths (except for the first and last vertices, of course). Imagine that, in place of the dist[] array, the method returned an array, say pred[], having the property that pred[v] = u meant that, on the shortest path from the source vertex to v, the last edge went from u to v (i.e., u is v’s predecessor on that path). (a) Describe the changes that you’d make to the method to implement this idea, and show the final contents of pred[] assuming that the method were applied to the same graph as shown. 0 1 2 3 4 5 6 7 8 9 +----+----+----+----+----+----+----+----+----+----+ pred | | | | | | | | | | | +----+----+----+----+----+----+----+----+----+----+ (b) Complete the method below, which, given the pred[] array and a vertex ID, prints the ID’s of the vertices on a shortest path /* Given the pred[] array and a vertex ID v, prints the ID’s of ** the vertices on a shortest path to v from the source vertex ** (in reverse order). */ public static void shortestPath(int[] pred, int v) { 5 4. Apply the familiar algorithm shown below to the fully-parenthesized boolean expression ((¬(T ∨ (F ∧ T ))) ∨ (T ∨ F )) in which literals T and F correspond to true and false, respectively, and ¬, ∧, and ∨ correspond to negation (not), conjunction (and), and disjunction (or), respectively. Show the history of the two stacks in the space provided below. Specifically, for each occurrence of a right parenthesis, show the contents of the stacks immediately before and immediately after it has been processed. operandStk = emptyStack; operatorStk = emptyStack; while ( there are more tokens to process ) { t = nextToken(); if (t is left parenthesis) { } // do nothing else if (t is boolean literal) { operandStk.push(t); } else if (t is boolean operator) { operatorStk.push(t); } else if (t is right parenthesis) { op = operatorStk.pop(); if ( op is negation operator ) { y = operandStk.pop(); z = result of applying op to y; } else { // op is a binary operator y = operandStk.pop(); x = operandStk.pop(); z = result of applying op to x and y; } operandStk.push( z ); } } | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ before 1st after 1st before 2nd after 2nd before 3rd | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ +---+ after 3rd before 4th after 4th before 5th after 5th 6 5. Assume the existence of Java classes CalendarDate and Person, instances of which represent just what their names suggest. Develop a class Marriage, which should include (1) a constructor that establishes the marriage’s two participants (spouse #1 and spouse #2, say) and the date on which it occurred (all provided via parameters), (2) a mutator method to record the date on which the marriage ended (e.g., due to divorce or death), (3) An observer method that, depending upon the value of a boolean parameter, returns either spouse #1 or spouse #2, (4) An observer method that returns the date on which the marriage occurred, (5) An observer method that reports whether or not the marriage is still in effect (as opposed to having ended), and (6) An observer method that, assuming that the marriage has ended, returns the date on which that happened. 7 /* PL_With_C.java (Positional List with Cursors) ** An instance of an implementing class represents a list in which one ** uses a cursor (specifically, an instance of a class that implements the ** interface PositionalListCursor) in order to navigate among (and access ** the data items associated to) the nodes in the list. ** ** Author: R. McCloskey ** Date: 2012 */ public interface PL_With_C { /* Reports whether or not this list has any items in it. */ boolean isEmpty(); /* Reports the number of items in this list. */ int lengthOf(); /* Returns a new cursor for this list. */ PLC getCursor(); } /* PLC.java (Positional List Cursor) ** An instance of an implementing class serves as a cursor within a ** list represented by an instance of a class that implements the ** PL_With_C (Positional List With Cursors) interface. A cursor is ** used for navigating among and accessing the items in such a list. ** ** Author: R. McCloskey ** Date: 2012 */ public interface PLC extends Cloneable { /**** observers ****/ /* Reports whether or not this cursor is at the front of its list. */ boolean atFront(); /* Reports whether or not this cursor is at the rear of its list. */ boolean atRear(); /* Returns the item associated to the node at which this cursor is ** positioned.
Answered 1 days AfterMar 30, 2021

Answer To: CMPS 144 Computer Science 2 Name____________________________________ Midterm Exam Spring 2021 (March...

Rushendra answered on Apr 01 2021
134 Votes
Java-soln/ColorSort.java
Java-soln/ColorSort.java
class ColorSort {
    static void swap(String arr[], int p, int q) {
        String temp = arr[p];
        arr[q] 
= arr[p];
        arr[p] = temp;
    }
    static void sort(String a[], int arr_size) {
        int low = 0;
        int high = arr_size - 1;
        int mid = 0;
        while (mid <= high) {
            switch (a[mid]) {
            case "RED": {
                swap(a, low, mid);
                low++;
                mid++;
                break;
            }
            case "WHITE":
                mid++;
                break;
            case "BLUE": {
                swap(a, mid, high);
                high--;
                break;
            }
            }
        }
    }
    static void printArray(String arr[], int arr_size) {
        for (int i = 0; i < arr_size; i++)
            System.out.print(arr[i] + " ");
        System.out.println("");
    }
    public static void main(String[] args) {
        String arr[] = { "RED", "WHITE", "WHITE", "RED", "WHITE", "BLUE", "WHITE", "BLUE", "RED", "RED", "RED",
                "WHITE" };
        int arr_size = arr.length;
        sort(arr, arr_size);
        System.out.println("Array after seggregation ");
        printArray(arr, arr_size);
    }
}
Java-soln/CountInversions.java
Java-soln/CountInversions.java
import java.util.*;
class CountInversions {
    // Returns inversion count
    static int getInvCount(List arr, int n) {
        // Initialize result
        int invcount = 0;
        for (int i = 0; i < arr.size()-1; i++) {
            for (int j = i + 1; j < arr.size(); j++) {
  ...
SOLUTION.PDF

Answer To This Question Is Available To Download

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here