 ## A1

`12,0.5,"%.f"`

`2`

`1`

## A4

`1`

In this value set, addition wraps after 4 (i.e. mod 5) so 6 becomes 1.

## A5

`3`

Since `int` requires 4 bytes, the value is stored in a block that occupies addresses 400, 401, 402, and 403.

`1`

## A7

`22`

Trace it: m is 18%11 (which is 7) plus 15.

## A8

`6`

Reverse engineer it: if the output is 9 then it was obtained by computing 3a-m so 15-m=9.

## A9

`2`

One object with state 2 and another with state 5. The first statement creates a new object with state 2. The second does not create a new object. The third creates a new object with state 5. The fourth creates a new object with state 2. Hence, the fragment creates 3 objects in total but only 2 of them have distinct states.

`9`

## A11

`12`

Reverse engineer it: If m were equal to EDGE the return would have been 20-3=17, which is wrong. And if m were less than EDGE the return would have been m/EDGE=0, which is also wrong. Hence, m must be greater than EDGE and the return is m+3=15, so m=12.

## A12

`2`

Trace it:

cb
-20
-11
02
13
24

The loop exits when b stops being less than m=4

## A13

`5`

`s==null` means we have a reference and no object. Hence (1) is wrong because if s has not been declared than there is neither an object nor a reference. (2) and (4) are wrong because they describe an object with state "" so there is an object. (3) is wrong because it describes a string with state "null" so there is an object.

## A14

`2`

Reverse engineer it: if the return is "d" then it must have been extracted from the given string at position p=18. The length of the given string is 20, so we have 18 = 20 - m.

## A15

`2`

At minimum, y must have one digit followed by one letter (X, Y, or Z).

## A16

`hr hs hhr hhs`

## A17

`PPACP`

The first replacement leads to "3PAC3". The second replaces 3 with P.

## A18

`-5`

Reverse engineer it: the toString returns "[x,y,z...]", where x,y,z are the elements of the set in sorted order. The index/substring extraction returns x. Since the return is -5 then m must have been -5.

`3`

`2`

## B1

The method returns the largest or the smallest of the two passed integers depending on whether the passed boolean is false or true, respectively.

## B2

The shown implementation is incorrect if the list has three or more elements because the positions are shifted after each removal, so some elements will not be removed. For example, if the list is [a,b,c] then remove(0) in the first loop iteration makes it [b,c], and remove(1) in the second (and last) iteration makes it [b], which is incorrect.

OR

The shown implementation is incorrect if the list has four or more elements because the list size shrinks after each removal whereas n is fixed, so we will refer to a non-existing element. For example, if the list has 4 elements then remove(2) in the 3rd iteration would throw an exception because, by then, the list has only two elements at positions 0 and 1 (i.e. position 2 doesn't exists).

## B3

`2`

The loop iterates N times. Each iteration involves O(1) operations, so the overall is O(N). Note that had the list been an instance of LinkedList then the answer would have been 4 (i.e. O(N2)) because `get` is O(N).

## B4

`4`

Two nested loops each iterating N times, hence N2. The operations in the body are all N-independent; i.e. O(1).

## B5

The shown implementation is incorrect because it bases the return on the uniqueness of the last value of the map only rather than all the values. For example, if the last value is unique then the return would be true even if all the other values are equal.

## C1

```public static int sumDiv11(int a, int b)
{
int result = -1;
for (int n = a; n <= b && result == -1; n++)
{
int sum = 0;
for (int m = n; m > 0; m /= 10)
{
sum += m % 10;
}
if (sum % 11 == 0) result = n;
}
return result;
}
```

## C2

```public static double specialSum(double x, double e)
{
double sum = 0;
int n = 0;
double term = 1.0;
while (term >= e)
{
sum += term;
n++;
term = Math.pow(x, n) / Math.pow(2, 2*n);
}
return sum;
}
```

## C3

```public static double multiply(String query)
{
double result;
String regex = "(\\d+)\\s*[\\*x]\\s*(\\d+)";
Pattern pattern = Pattern.compile(regex);
Matcher matcher = pattern.matcher(query);
if (matcher.find())
{
int a = Integer.parseInt(matcher.group(1));
int b = Integer.parseInt(matcher.group(2));
result = a * b;
} else
{
result = Double.NaN;
}
return result;
}
```

## C4

```public static int vowel(String s)
{
final String VOWELS = "aeiouAEIOU";
int count = 0;
for (int i = 0; i < s.length(); i++)
{
if (VOWELS.indexOf(s.substring(i, i+1)) != -1) count++;
}
return count;
}
```

## C5

```public static Set<Integer> negativeSubset(Set<Integer> set)
{
Set<Integer> result = new TreeSet<Integer>();
for (int x : set)
{
}
if (result.size() == 0) result = null;
return result;
}
```

## C6

```public static Map<Integer,Integer> lengthStat(List<String> list)
{
Map<Integer,Integer> result = new TreeMap<Integer,Integer>();
for (String word : list)
{
int len = word.length();
if (!result.containsKey(len))
result.put(len,  1);
else
result.put(len,  1 + result.get(len));
}
return result;
}
```

## C7

```public static List<String> aboveAverage(Map<String, Integer> map)
{
List<String> result = new ArrayList<String>();
int sum = 0;
for (String k : map.keySet())
{
sum += map.get(k);
}
double average = sum / (double) map.size();
for (String k : map.keySet())
{
int mark = map.get(k);
}
return result;
}
```

## C8

```public static void sortByLength(List<String> list)
{
Map<Integer,String> map = new TreeMap<Integer,String>();
for (String s : list) map.put(s.length(), s);
list.clear();
for (int i : map.keySet()) list.add(map.get(i));
}
```

## C9

```public static int largestEven(Set<Integer> set)
{
int result = 0;
for (int x : set)
{
if (x % 2 == 0 && x > result) result = x;
}
return result;
}
```

## C10

```public static List<String> oldest(Map<String, Integer> map)
{
List<String> result = new ArrayList<String>();
int maxAge = 0;
for (String k : map.keySet())
{
int age = map.get(k);
if (age > maxAge) maxAge = age;
}
for (String k : map.keySet())
{
int age = map.get(k);
}
return result;
}
```

## C11

```public static Set<Integer> pair(Set<Integer> set, int sum)
{
Set<Integer> result = new TreeSet<Integer>();
for (int a : set)
{
for (int b : set)
{
if (a != b && a + b == sum && result.size() == 0)
{
}
}
}
return result;
}
```

## L5.11

In order to find out if the given path is indeed the shortest, we compute its length (which is only O(N)) but then we need to compare this length to the lengths of all other possible paths, which are N! in number. Hence, our verification process involves N! iterations, which is not in P.

## L5.12

If P=NP then the effort needed to verify is placed at the same level as the effort needed to solve, which is bothersome because verification is normally thought of as mechanical or straightforward whereas solving is normally associated with innovation and ingenuity. For example, we don't feel that "recognising good music" is of the same calibre as "composing good music". Similarly, conducting experiments to verify the predictions of (say) the theory of relativity is not equated with the act of inventing the theory.

## L2.1

1. The number in question is: 1000 * the number of seconds since then. If the number of years since then is 50, then we need 1000 * 3600 (sec/hr) * 24 (hr/day) * 365 (day/year) * 50 years, which is over 1500 billion, and our int can hold only about 2 billion.

(If we store seconds rather than milliseconds, then int can hold that but only up to the year 2038.)

2. There only 4 significant figures in \$107.5 trillion, so double can easily store this GDP. The remaining zeros will be held in the exponent.
3. You cannot set a boolean to zero!
4. This fragment will not even compile (x is declared by not set) so we cannot run it.
5. No, it will evaluate as ((a*b)*c)/d

## L2.2

The first and the second and the fourth do increment x. The third adds 0 to it so it doesn't increment it. The fifth is a syntax error (the RHS is double while the LHS is int).

## L1.1

Both approaches correctly perform the conversion but the second is the preferred best-practice because it uses indirection (see the CS Trail of this Chapter). The advantage here is clarity through self-documenting code. If the exchange rate is to be changed, the second approach makes the change easy especially if this code is burried in a big application. The first approaches does not indicate whether the magic number 1.33 is an exchange rate or something else.

## L1.2

The input is the values of w and h. The output is the value of result.