0) Review all past lectures, sections, assignments, and exams, especially items that gave you trouble. We will feel free to base questions on past assignments and exams. TIP: (Re)do any projects you didn't (fully) do or had trouble with. TIP: Work through the Online Examples. (You may skip the Optional ones.) TIP: Work things out on paper before trying them out on a computer. TIP: Go through the lecture notes posted to the Announcements page, e.g. there are *tons* of Matlab examples. TIP: Come in to office hours if you need additional help! 1) Write overloaded Java methods $index(a,i,j)$ that take a 2-D array $a$ of integers, 1-D arrays $i$ and $j$ of integers or booleans, and return the Java equivalent of the Matlab expression $a(i,j)$. 2) Write Matlab code for each of the following problems: (a) Given a matrix M, create matrix N that contains all elements of M except the border. The border of M is its first and last rows and columns. (b) Write a function COUNT that accepts a vector V and a scalar value X as input and returns the number of occurrences of X in V. + Do not use loops. Be concise. + Use good style (use comments to explain the function). (c) Write code that calls the function COUNT to find the number of occurrences of the value 99 in the second column of matrix N. Assume that matrix N has at least two columns. 3) Crack ciphertext using hill-climbing on trigram frequencies. HINT: 3-D arrays. (Try cracking a "small" ciphertext, e.g. maybe only the first sentence.) 4) Prove that a best way to rearrange the contents of two equal-length row-vectors $x$ and $y$ to minimize the L1 distance between them is to sort each of them in non-ascending order. (a) Explain why we may assume that $x$ is sorted. (b) Prove the length=2 case. Observe that this means swapping two out-of-order items in $y$ decreases the L1 distance. HINT: let $ymax$ and $ymin$ be the largest and smallest values in $y$. Proceed by case analysis of how $ymax$ and $ymin$ "interleave" with the values of $x$. For example, if x[1] >= ymax >= x[2] >= ymin, then $y$ could either be sorted ($y=[ymax ymin]$) or unsorted ($y=[ymin ymax]$), which yield these distances from $x$: Sorted distance: |x[1]-ymax| + |x[2]-ymin|. Unsorted distance: |x[1]-ymin| + |x[2]-ymax| = (|x[1]-ymax| + |ymax-x[2]| + |x[2]-ymin|) + |x[2]-ymax| = (unsorted distance) + 2 |ymax-x[2]| (c) Prove the general length>2 case. 5) Write a method $sumUpperTri$ that takes a rectangular, row-major matrix (2-dimensional array) as the argument and returns the sum of the elements in the largest possible upper right triangle with equal number of elements on each side. In each of the following examples, the elements in the largest possible upper right triangle with equal number of elements on each side are denoted by $u$: uuuuu uuuu ...uuu .uuuu .uuu ....uu ..uuu ..uu .....u ...uu ...u ....u ..... 6) Complete method $CheckMove$ below. Its parameters are: + $a$: a ragged, column-major 2-D array of integers. By "ragged", we mean that each row may have a different length. + $r$ and $c$: coordinates of a (possible) element in $a$. + $val$: an integer value. The method checks whether $a$ contains an element at row $r$, column $c$, and if so, whether it has a value that is one higher than $val$, and returns a boolean value accordingly. Conciseness counts, e.g. the solution could be a single statement of the form $return _________________ ;$. // check whether position r,c is within the boundaries of $a$ // and the value at that position is 1 higher than val public boolean CheckMove(int[][] a, int r, int c, int val) { +--------------------------------------------------+ | | | | | | | | +--------------------------------------------------+ } 7) Write code to solve the following problem. It is up to you to design the classes, variables, and methods. A telephone directory contains records of people's last names and their phone numbers. Each record contains one name and one phone number. The telephone directory should support a *query* operation that, given a String $s$, displays all the records (last name and phone number) with a last name beginning with $s$. (Technically, we say that $s$ is a *prefix* of the last name.) 8) Write a static method that has two arrays $name$ and $age$ as parameters: the $i$th person has name $name[i]$ and age $age[i]$. The method sorts both arrays (use selection sort) so that ages are in increasing order. If two people have the same name, then they should be sorted in alphabetical order of their name, e.g. "Buffy" comes before "Willow". 9) Write a static method that takes two sorted (non-decreasing) arrays of integers and prints the numbers that are in either array but not the other. 10) For the purpose of this question, we say + A pair of integers is "good" if one or both integers is positive. + A pair of integers is "bad" if it is not "good". You MUST NOT use the not operator (!) below. (a) Fill in the blanks below to complete the code segment to read a sequence of integers and print the first bad pair of consecutive integers. TokenReader in = new TokenReader(System.in); int previous = ________________________________; // previous input number int current = ________________________________; // current input number while ( ____________________________________ ) { // ! IS DISALLOWED __________ = ____________________________________; __________ = ____________________________________; } System.out.println( ___________________________________________________ ); (b) What would the loop guard be if we wanted to print the first good pair of consecutive integers? ________________________________________ // ! IS DISALLOWED 11) Fill in the blanks below to complete the code segment to print whether integer p, p>1, is a prime number. That is, print an appropriate message like "51 is not prime" or "101 is prime". (Recall that a number p>1 is prime if its only divisors are 1 and p. Recall that d is a divisor of p if the remainder is 0 when p is divided by d.) TokenReader in = new TokenReader(System.in); int p = in.readInt(); int d = __________ ; while ( ____________________ ) d = _____________ ; if ( __________ ) System.out.println( ______________________________ ); else System.out.println( ______________________________ ); 12) Two Persons *bilaterally* interact ("bilateral" means "something done in both directions") by having each Person *unilaterally* interact with the other ("unilateral" means "something done in only one direction"). A *source* Person unilaterally interacts with a *target* Person as follows: + The source Person rolls his/her own die to obtain a number from 0 to his/her own $friendliness$ (inclusive). + If the die comes up 0, then the target Person becomes the latest enemy of the source Person, otherwise the source Person's enemy is unchanged. (a) Fill in the blanks and boxes below to complete the code for class Person. class Person { private String name; protected int friendliness; public Person enemy; // Constructor public Person(String n, int f) { _______________ ; _______________ ; _______________ ; } // return description (name, friendliness, name of enemy) // (this is like method $describe$ on Prelim 2) public String toString() { +--------------------------------------------------+ | | | | | | | | +--------------------------------------------------+ } // bilaterally interact with Person p public void interact(Person p) { ________________________________________ ________________________________________ } // unilaterally interact with Person p public void uniInteract(Person p) { if (0 == ______________________________ ) ___________________________________________________________ ; } } (b) Write a subclass WackyPerson of Person. It must have a constructor $WackyPerson(n)$ that for a new instance, sets the $name$ to $n$, $friendliness$ to 2000, and $enemy$ to itself (the new instance). When a WackyPerson unilaterally interacts with another Person (or WackyPerson), it repeatedly does what a Person would normally do a 100 times. (That is: roll, decide; roll, decide; roll, decide; etc. for a total of 100 times.) Use good style. class __________________________________________________ { // constructor: set name to n, friendliness to 2000, enemy to self ____________________ ( ____________________ ) { _______________________________________________________________ ; _______________________________________________________________ ; } // unilaterally interact: do 100 times what a Person would do public void uniInteract(Person q) { for ( ________________ ; ________________ ; ________________ ) ____________________________________________________________ ; } } (c) Discuss the following code fragment, e.g. + Are there errors? If so, how would you fix the errors? + Once any errors are fixed, what does the code do? Person[] p = { new Person("Spike",10), new WackyPerson("Buffy") }; p[1].interact(p[2]); // have Spike and Buffy interact