Advanced Programming Techniques (2011, 2013)
Appendix B. Answers to Desk Checks
117
Chapter 1. Arrays
Desk Check 1.1 Fill |
||||||
list |
x |
i |
||||
8.3 |
8.3 |
8.3 |
8.3 |
8.3 |
0 |
|
[0] |
[1] |
[2] |
[3] |
1 |
||
2 |
||||||
3 |
||||||
4 |
Desk Check 1.2 Ramp |
||||||
list |
i |
|||||
0 |
1 |
2 |
3 |
4 |
0 |
|
[0] |
[1] |
[2] |
[3] |
[4] |
1 |
|
2 |
||||||
3 |
||||||
4 |
||||||
5 |
Desk Check 1.3 Reverse Ramp |
|||||||
list |
high |
i |
|||||
4 |
3 |
2 |
1 |
0 |
4 |
0 |
|
[0] |
[1] |
[2] |
[3] |
[4] |
1 |
||
2 |
|||||||
3 |
|||||||
4 |
|||||||
5 |
Desk Check 1.4 Reverse |
||||||||
list |
left |
right |
swap |
|||||
|
|
|
|
|
0 |
4 |
3.4 |
|
1 |
3 |
−2 |
||||||
[0] |
[1] |
[2] |
[3] |
[4] |
2 |
2 |
Desk Check 1.5 Rotate Left |
||||||||
list |
i |
swap |
last |
|||||
|
|
|
|
|
0 |
9 |
4 |
|
1 |
||||||||
[0] |
[1] |
[2] |
[3] |
[4] |
2 |
|||
3 |
||||||||
4 |
118
Desk Check 1.6 Rotate Right |
||||||||
list |
i |
last |
swap |
|||||
|
|
|
|
|
4 |
4 |
8 |
|
3 |
||||||||
[0] |
[1] |
[2] |
[3] |
[4] |
2 |
|||
1 |
||||||||
0 |
Desk Check 1.7 Rotate |
||||||||||
list |
group |
one |
two |
save |
||||||
|
|
|
|
|
|
0 |
0 |
4 |
11 |
|
4 |
2 |
|||||||||
[0] |
[1] |
[2] |
[3] |
[4] |
[5] |
2 |
0 |
|||
1 |
1 |
5 |
23 |
|||||||
k |
n |
groups |
5 |
3 |
||||||
2 |
6 |
2 |
3 |
1 |
||||||
4 |
2 |
Desk Check 1.8 gcd |
|||
a |
b |
r |
return |
2 |
6 |
2 |
|
2 |
6 |
2 |
|
6 |
2 |
0 |
Desk Check 1.9 printRotated |
|||||||||
list |
index |
i |
console output |
||||||
11 |
23 |
−5 |
9 |
−3 |
14 |
−2 |
[−3,14,11,23,−5,9] |
||
[0] |
[1] |
[2] |
[3] |
[4] |
[5] |
4 |
|||
5 |
0 |
||||||||
k |
n |
separator |
6 |
1 |
|||||
2 |
6 |
"" |
0 |
2 |
|||||
", " |
1 |
3 |
|||||||
2 |
4 |
||||||||
3 |
5 |
||||||||
4 |
6 |
Desk Check 1.10 Linear Search |
||||||||
list |
key |
i |
return |
|||||
28.1 |
20 |
23.6 |
0 |
15 |
23.6 |
0 |
2 |
|
[0] |
[1] |
[2] |
[3] |
[4] |
1 |
|||
2 |
119
Desk Check 1.11 Binary Search |
|||||||||||||
list |
|||||||||||||
−2.1 |
−1 |
3.9 |
6.2 |
7.1 |
9.7 |
10 |
12 |
13.1 |
15.6 |
18 |
19 |
20.1 |
24.5 |
[0] |
[1] |
[2] |
[3] |
[4] |
[5] |
[6] |
[7] |
[8] |
[9] |
[10] |
[11] |
[12] |
[13] |
key |
left |
right |
mid |
cmp |
return |
15.6 |
0 |
13 |
6 |
5.6 |
9 |
7 |
10 |
−2.4 |
|||
9 |
8 |
2.5 |
|||
9 |
9 |
0 |
Desk Check 1.12 Find a Range |
|||
purchase |
rate |
discount |
return |
$708.00 |
0.025 |
17.7 |
690.3 |
Desk Check 1.13 Find a Range |
|||
purchase |
rate |
discount |
return |
$708.00 |
0.025 |
17.7 |
690.3 |
Desk Check 1.14 Find a Range |
|||||||
limits |
rates |
||||||
300 |
600 |
1000 |
0 |
0.02 |
0.025 |
0.03 |
|
[0] |
[1] |
[2] |
[0] |
[1] |
[2] |
[3] |
purchase |
i |
rate |
discount |
return |
$708.00 |
0 |
0.025 |
17.7 |
690.3 |
1 |
||||
2 |
Desk Check 1.17 Arabic to Roman |
||||
arabic |
exponent |
divisor |
digit |
roman |
1987 |
"" |
|||
987 |
3 |
1000 |
1 |
"M" |
87 |
2 |
100 |
9 |
"MCM" |
7 |
1 |
10 |
8 |
"MCMLXXX" |
0 |
0 |
1 |
7 |
"MCMLXXXVII" |
Desk Check 1.18 Roman to Arabic |
|||||
roman |
exponent |
length |
chars |
digit |
arabic |
"MCMLXXXVII" |
0 |
||||
3 |
4 |
"MCML" |
−1 |
||
3 |
"MCM" |
−1 |
|||
2 |
"MC" |
−1 |
|||
1 |
"M" |
1 |
1000 |
||
"CMLXXXVII" |
2 |
4 |
"CMLX" |
−1 |
|
3 |
"CML" |
−1 |
|||
2 |
"CM" |
9 |
1900 |
||
"LXXXVII" |
1 |
4 |
"LXXX" |
8 |
1980 |
"VII" |
0 |
4 |
"VII" |
7 |
1987 |
120
Desk Check 1.20 Sort by Name or Age |
||||
students |
console output |
|||
"Jane" 18 |
"Sam" 17 |
"Nigel" 14 |
[Jane 18, Sam 17, Nigel 14] |
|
[0] |
[1] |
[2] |
[Jane 18, Nigel 14, Sam 17] |
|
[Nigel 14, Sam 17, Jane 18] |
Desk Check 1.21 Insertion Sort |
||||||||||
list |
first |
last |
i |
swap |
j |
|||||
6 |
−8 |
9 |
7 |
0 |
0 |
4 |
3 |
7 |
4 |
|
6 |
−8 |
9 |
0 |
7 |
5 |
|||||
2 |
9 |
3 |
||||||||
6 |
−8 |
0 |
7 |
9 |
4 |
|||||
5 |
||||||||||
1 |
−8 |
2 |
||||||||
6 |
−8 |
0 |
7 |
9 |
||||||
0 |
6 |
1 |
||||||||
−8 |
0 |
6 |
7 |
9 |
2 |
|||||
[0] |
[1] |
[2] |
[3] |
[4] |
3 |
|||||
−1 |
Desk Check 1.22 findCandidates |
||||||
candidates |
||||||
"cash" |
"charity" |
"clothing" |
"dentist" |
"dividend" |
"doctor" |
"education" |
[0] |
[1] |
[2] |
[3] |
[4] |
[5] |
[6] |
prefix |
index |
first |
last |
bounds |
"c" |
1 |
1 |
1 |
null |
0 |
2 |
0, 2 |
||
−1 |
3 |
|||
0 |
2 |
Desk Check 1.23 findAnyCandidate |
||||||
candidates |
||||||
"cash" |
"charity" |
"clothing" |
"dentist" |
"dividend" |
"doctor" |
"education" |
[0] |
[1] |
[2] |
[3] |
[4] |
[5] |
[6] |
prefix |
left |
mid |
right |
term |
cmp |
return |
"c" |
0 |
3 |
6 |
"dentist" |
−1 |
1 |
1 |
2 |
"charity" |
0 |
Desk Check 1.24 startsWithCompare |
||||||
prefix |
term |
preLen |
minLen |
i |
diff |
return |
"c" |
"charity" |
1 |
1 |
0 |
0 |
0 |
1 |
121
Desk Check 1.25 findBestCandidate |
||||||
candidates |
||||||
"cash" |
"charity" |
"clothing" |
"dentist" |
"dividend" |
"doctor" |
"education" |
[0] |
[1] |
[2] |
[3] |
[4] |
[5] |
[6] |
prefix |
index |
max |
save |
i |
freq |
return |
"d" |
3 |
7 |
3 |
2 |
4 |
|
3 |
||||||
4 |
10 |
4 |
14 |
|||
5 |
11 |
|||||
6 |
Desk Check 1.26 findAnyCandidate |
||||||
candidates |
||||||
"cash" |
"charity" |
"clothing" |
"dentist" |
"dividend" |
"doctor" |
"education" |
[0] |
[1] |
[2] |
[3] |
[4] |
[5] |
[6] |
prefix |
left |
mid |
right |
term |
cmp |
return |
"d" |
0 |
3 |
6 |
"dentist" |
0 |
3 |
Chapter 2. Array Lists
Desk Check 2.1 append |
||||||
this.array |
this.count |
c |
||||
'U' |
'n' |
'd' |
2 |
'd' |
||
[0] |
[1] |
[2] |
[3] |
3 |
Desk Check 2.2 append |
||||||||||
this.array |
this.count |
i |
||||||||
'U' |
'n' |
'd' |
'a' |
'u' |
'n' |
3 |
0 |
|||
[0] |
[1] |
[2] |
[3] |
[4] |
[5] |
[6] |
[7] |
4 |
1 |
|
5 |
2 |
|||||||||
a |
6 |
3 |
||||||||
'a' |
'u' |
'n' |
||||||||
[0] |
[1] |
[2] |
Desk Check 2.3 append |
||||||||||
this.array |
this.count |
i |
||||||||
'U' |
'n' |
'd' |
'a' |
'u' |
'n' |
3 |
0 |
|||
[0] |
[1] |
[2] |
[3] |
[4] |
[5] |
[6] |
[7] |
4 |
1 |
|
5 |
2 |
|||||||||
sb.array |
sb.count |
6 |
3 |
|||||||
'a' |
'u' |
'n' |
3 |
|||||||
[0] |
[1] |
[2] |
[3] |
122
Desk Check 2.4 append |
|||||||||||||
this.array |
this.count |
||||||||||||
'U' |
'n' |
'd' |
'a' |
'u' |
'n' |
't' |
'e' |
'd' |
6 |
||||
[0] |
[1] |
[2] |
[3] |
[4] |
[5] |
[6] |
[7] |
[8] |
[9] |
[10] |
[11] |
9 |
newLen |
s |
9 |
"ted" |
Desk Check 2.5 expandCapacity |
|||||||
old |
this.count |
suggest |
capacity |
||||
'U' |
'n' |
'd' |
3 |
6 |
8 |
||
[0] |
[1] |
[2] |
[3] |
this.array |
|||||||
'U' |
'n' |
'd' |
|||||
[0] |
[1] |
[2] |
[3] |
[4] |
[5] |
[6] |
[7] |
Desk Check 2.6 findFibonacci |
||
value |
index |
return |
6 |
−2 |
8 |
1 |
Chapter 4. Iteration and Recursion
Desk Check 4.1 Iterative n factorial |
|
n |
fact |
4 |
4 |
3 |
12 |
2 |
24 |
1 |
Desk Check 4.2 Recursive n factorial |
||
Function |
Variables |
|
factorial |
n |
return |
4 |
24 |
|
factorial |
n |
return |
3 |
6 |
|
factorial |
n |
return |
2 |
2 |
|
factorial |
n |
return |
1 |
1 |
123
Desk Check 4.4 Iterative GCD |
||
x |
y |
r |
472 |
24 |
16 |
24 |
16 |
8 |
16 |
8 |
0 |
8 |
0 |
Desk Check 4.5 Recursive GCD |
||||
Function |
Variables |
|||
gcd |
x |
y |
rem |
return |
472 |
24 |
16 |
8 |
|
gcd |
x |
y |
rem |
return |
24 |
16 |
8 |
8 |
|
gcd |
x |
y |
rem |
return |
16 |
8 |
0 |
8 |
Desk Check 4.8 Recursive Sum |
|||||
Function |
Variables |
||||
sum |
a |
return |
|||
6.5 |
7.1 |
6.9 |
20.5 |
||
[0] |
[1] |
[2] |
|||
sumR |
i |
return |
|||
0 |
20.5 |
||||
sumR |
i |
return |
|||
1 |
14.0 |
||||
sumR |
i |
return |
|||
2 |
6.9 |
||||
sumR |
i |
return |
|||
3 |
0 |
Desk Check 4.9 Tail Recursive Sum |
||||||
Function |
Variables |
|||||
sum |
a |
return |
||||
6.5 |
7.1 |
6.9 |
20.5 |
|||
[0] |
[1] |
[2] |
||||
sumR |
s |
i |
return |
|||
0 |
0 |
20.5 |
||||
sumR |
s |
i |
return |
|||
6.5 |
1 |
20.5 |
||||
sumR |
s |
i |
return |
|||
13.6 |
2 |
20.5 |
||||
sumR |
s |
i |
return |
|||
20.5 |
3 |
20.5 |
124
Desk Check 4.11 Tail Recursive n Factorial |
|||
Function |
Variables |
||
factorial |
n |
return |
|
4 |
24 |
||
factorialR |
f |
n |
return |
1 |
4 |
24 |
|
factorialR |
f |
n |
return |
4 |
3 |
24 |
|
factorialR |
f |
n |
return |
12 |
2 |
24 |
|
factorialR |
f |
n |
return |
24 |
1 |
24 |
Desk Check 4.12 Recursive Pre-Order Traversal of a Binary Tree |
|||||||||||||||||||
Function |
Variables |
||||||||||||||||||
maxLen |
return |
||||||||||||||||||
7 |
|||||||||||||||||||
maxLenR |
curr |
max |
len |
||||||||||||||||
Simon |
|
5 |
|||||||||||||||||
maxLenR |
curr |
max |
len |
curr |
max |
len |
|||||||||||||
John |
|
4 |
Thomas |
7 |
6 |
||||||||||||||
maxLenR |
curr |
max |
len |
curr |
max |
len |
curr |
max |
len |
curr |
max |
len |
|||||||
null |
5 |
Phillip |
|
7 |
null |
7 |
null |
7 |
|||||||||||
maxLenR |
curr |
max |
len |
curr |
max |
len |
|||||||||||||
null |
7 |
null |
7 |
Desk Check 4.13 Iterative Pre-Order Traversal |
||||||
stack |
curr |
len |
max |
|||
0 |
||||||
Simon |
||||||
Simon |
5 |
5 |
||||
Thomas |
John |
|||||
John |
4 |
|||||
Thomas |
Phillip |
null |
||||
null |
||||||
Phillip |
7 |
7 |
||||
Thomas |
null |
null |
||||
null |
||||||
null |
||||||
Thhomas |
6 |
|||||
null |
null |
|||||
[0] |
[1] |
[2] |
null |
|||
null |
125
Desk Check 4.14 Recursive In-Order Traversal |
|||||||||
Function |
Variables |
||||||||
toList |
list |
||||||||
John |
Phillip |
Simon |
Thomas |
||||||
toListR |
curr |
||||||||
Simon |
|||||||||
toListR |
curr |
curr |
|||||||
John |
Thomas |
||||||||
toListR |
curr |
curr |
curr |
curr |
|||||
null |
Phillip |
null |
null |
||||||
toListR |
curr |
curr |
|||||||
null |
null |
Desk Check 4.15 Iterative In-Order Traversal |
||||||
list |
||||||
John |
Phillip |
Simon |
Thomas |
|||
stack |
frame |
|||||
Simon, CheckLeft |
node |
todo |
||||
Simon |
CheckLeft |
|||||
Simon, Process |
John, CheckLeft |
|||||
John |
CheckLeft |
|||||
Simon, Process |
John, Process |
|||||
John |
Process |
|||||
Simon, Process |
Phillip, CheckLeft |
|||||
Phillip |
CheckLeft |
|||||
Simon, Process |
Phillip, Process |
|||||
Phillip |
Process |
|||||
Simon, Process |
||||||
Simon |
Process |
|||||
Thomas, CheckLeft |
||||||
Thomas |
CheckLeft |
|||||
Thomas, Process |
||||||
Thomas |
Process |
|||||
Desk Check 4.16 Recursive Fibonacci Function |
||||||||||||||
Function |
Variables |
|||||||||||||
fibonacci |
n |
return |
||||||||||||
4 |
3 |
|||||||||||||
fibonacci |
n |
return |
n |
return |
||||||||||
2 |
1 |
3 |
2 |
|||||||||||
fibonacci |
n |
return |
n |
return |
n |
return |
n |
return |
||||||
0 |
0 |
1 |
1 |
1 |
1 |
2 |
1 |
|||||||
fibonacci |
n |
return |
n |
return |
||||||||||
0 |
0 |
1 |
1 |
126
Desk Check 4.17 Iterative Fibonacci Function |
|||||||
stack |
frame |
n |
fib |
||||
−1 |
4 |
0 |
|||||
4 |
0 |
||||||
−1 |
4 |
||||||
3 |
2 |
1 |
|||||
0 |
2 |
||||||
3 |
1 |
0 |
2 |
||||
1 |
0 |
||||||
0 |
1 |
1 |
|||||
−1 |
3 |
||||||
2 |
1 |
1 |
|||||
0 |
1 |
2 |
|||||
−1 |
2 |
||||||
1 |
0 |
1 |
|||||
[0] |
[1] |
[2] |
[3] |
0 |
0 |
||
−1 |
1 |
3 |
Desk Check 4.18 Iterative Fibonacci Function |
|||
future |
past |
present |
n |
0 |
1 |
4 |
|
1 |
1 |
1 |
3 |
2 |
1 |
2 |
2 |
3 |
2 |
3 |
1 |
5 |
3 |
5 |
0 |
Desk Check 4.19 Tail Recursive Fibonacci Function |
||||
Function |
Variables |
|||
fibonacci |
n |
return |
||
4 |
3 |
|||
fibonacciR |
past |
present |
n |
return |
0 |
1 |
4 |
3 |
|
fibonacciR |
past |
present |
n |
return |
1 |
1 |
3 |
3 |
|
fibonacciR |
past |
present |
n |
return |
1 |
2 |
2 |
3 |
|
fibonacciR |
past |
present |
n |
return |
2 |
3 |
1 |
3 |
|
fibonacciR |
past |
present |
n |
return |
3 |
5 |
0 |
3 |
127
Desk Check 4.20 Fibonacci Formula |
||||
SQRT5 |
GOLDEN |
n |
numer |
return |
2.236 |
1.618 |
4 |
6.708 |
3 |
Desk Check 4.23 Iterative Binary Search |
|||||||||||||
list |
|||||||||||||
−2.1 |
−1 |
3.9 |
6.2 |
7.1 |
9.7 |
10 |
12 |
13.1 |
15.6 |
18 |
19 |
20.1 |
24.5 |
[0] |
[1] |
[2] |
[3] |
[4] |
[5] |
[6] |
[7] |
[8] |
[9] |
[10] |
[11] |
[12] |
[13] |
key |
left |
right |
mid |
cmp |
return |
15.6 |
0 |
13 |
6 |
5.6 |
9 |
7 |
10 |
−2.4 |
|||
9 |
8 |
2.5 |
|||
9 |
9 |
0 |
Desk Check 4.24 Recursive Binary Search |
|||||||||||||
list |
|||||||||||||
−2.1 |
−1 |
3.9 |
6.2 |
7.1 |
9.7 |
10 |
12 |
13.1 |
15.6 |
18 |
19 |
20.1 |
24.5 |
[0] |
[1] |
[2] |
[3] |
[4] |
[5] |
[6] |
[7] |
[8] |
[9] |
[10] |
[11] |
[12] |
[13] |
Function |
Variables |
|||||
binarySearch |
key |
return |
||||
15.6 |
9 |
|||||
binarySearchR |
key |
left |
right |
mid |
cmp |
return |
15.6 |
0 |
13 |
6 |
5.6 |
9 |
|
binarySearchR |
key |
left |
right |
mid |
cmp |
return |
15.6 |
7 |
13 |
10 |
−2.4 |
9 |
|
binarySearchR |
key |
left |
right |
mid |
cmp |
return |
15.6 |
7 |
9 |
8 |
2.5 |
9 |
|
binarySearchR |
key |
left |
right |
mid |
cmp |
return |
15.6 |
9 |
9 |
9 |
0 |
9 |
Desk Check 4.25 Future Value |
||||||
principal |
annualRate |
years |
periodsPerYear |
rate |
periods |
fv |
10000 |
0.06 |
2 |
4 |
0.005 |
8 |
11265 |
Desk Check 4.26 Iterative Future Value |
||||||
i |
principal |
annualRate |
years |
periodsPerYear |
rate |
periods |
10000 |
0.06 |
2 |
4 |
0.005 |
8 |
|
1 |
10150 |
|||||
2 |
10302 |
|||||
3 |
10457 |
|||||
4 |
10614 |
|||||
5 |
10773 |
|||||
6 |
10935 |
|||||
7 |
11099 |
|||||
8 |
11265 |
|||||
9 |
128
Desk Check 4.27 Recursive Future Value |
|||||||
Function |
Variables |
||||||
futureValue |
principal |
annualRate |
years |
periodsPerYear |
rate |
periods |
return |
10000 |
0.06 |
2 |
4 |
0.005 |
8 |
11265 |
|
futureValueR |
principal |
rate |
period |
return |
|||
|
0.005 |
|
11265 |
||||
futureValueR |
principal |
rate |
period |
return |
|||
|
0.005 |
|
11265 |
||||
futureValueR |
principal |
rate |
period |
return |
|||
|
0.005 |
|
11265 |
||||
futureValueR |
principal |
rate |
period |
return |
|||
|
0.005 |
|
11265 |
||||
futureValueR |
principal |
rate |
period |
return |
|||
|
0.005 |
|
11265 |
||||
futureValueR |
principal |
rate |
period |
return |
|||
|
0.005 |
|
11265 |
||||
futureValueR |
principal |
rate |
period |
return |
|||
|
0.005 |
|
11265 |
||||
futureValueR |
principal |
rate |
period |
return |
|||
|
0.005 |
|
11265 |
||||
futureValueR |
principal |
rate |
period |
return |
|||
11265 |
0.005 |
|
11265 |
Chapter 5. Counting Bits
129
Desk Check 5.14 Naive |
|||
word |
word & 1 |
n |
i |
0 |
0 |
||
0011 0101 |
1 |
1 |
1 |
0001 1010 |
0 |
2 |
|
0000 1101 |
1 |
2 |
3 |
0000 0110 |
0 |
4 |
|
0000 0011 |
1 |
3 |
5 |
0000 0001 |
1 |
4 |
6 |
0000 0000 |
0 |
7 |
|
0000 0000 |
0 |
8 |
130
Desk Check 5.15 Loop Termination |
||
word |
word & 1 |
n |
0 |
||
0011 0101 |
1 |
1 |
0001 1010 |
0 |
|
0000 1101 |
1 |
2 |
0000 0110 |
0 |
|
0000 0011 |
1 |
3 |
0000 0001 |
1 |
4 |
0000 0000 |
Desk Check 5.16 Addition |
||
word |
word & 1 |
n |
0 |
||
0011 0101 |
1 |
1 |
0001 1010 |
0 |
1 |
0000 1101 |
1 |
2 |
0000 0110 |
0 |
2 |
0000 0011 |
1 |
3 |
0000 0001 |
1 |
4 |
0000 0000 |
Desk Check 5.17 Skip Zero Bits |
||
word |
n |
word − 1 |
0 |
||
0011 0101 |
1 |
0011 0100 |
0011 0100 |
2 |
0011 0011 |
0011 0000 |
3 |
0010 1111 |
0010 0000 |
4 |
0001 1111 |
0000 0000 |
Desk Check 5.18 Combinatorial |
||||
word |
word >>> 1 |
ones |
word >>> 1 & ones |
word & ones |
0011 0101 |
0001 1010 |
0101 0101 |
0001 0000 |
0001 0101 |
word >>> 2 |
twos |
word >>> 2 & twos |
word & twos |
|
0010 0101 |
0000 1001 |
0011 0011 |
0000 0001 |
0010 0001 |
word >>> 4 |
(word >>> 4) + word |
fours |
||
0010 0010 |
0000 0010 |
0010 0100 |
0000 1111 |
|
0000 0100 |
Desk Check 5.19 Lookup |
||
word |
(int)word & 0xff |
onbits[(int)word & 0xff] |
0011 0101 |
0011 0101 |
4 |
131
Chapter 6. Sets
Desk Check 6.1 Contains |
||||
array |
||||
"apple" |
"pear" |
"plum" |
"cherry" |
"peach" |
[0] |
[1] |
[2] |
[3] |
[4] |
term |
i |
return |
"plum" |
0 |
true |
1 |
||
2 |
Desk Check 6.2 Is Subset |
||||||||
i |
termA |
return |
||||||
this |
"elm" |
"pine" |
"rose" |
0 |
"elm" |
false |
||
[0] |
[1] |
[2] |
1 |
"pine" |
||||
2 |
"rose" |
|||||||
setB |
"lilac" |
"pine" |
"fir" |
"elm" |
3 |
|||
[0] |
[1] |
[2] |
[3] |
|||||
Desk Check 6.3 Intersection |
|||||||||
ceil |
i |
termA |
n |
||||||
this |
"elm" |
"pine" |
"rose" |
"lilac" |
3 |
0 |
|||
[0] |
[1] |
[2] |
[3] |
0 |
"elm" |
||||
setB |
"lilac" |
"pine" |
"fir" |
1 |
"pine" |
1 |
|||
[0] |
[1] |
[2] |
2 |
"rose" |
|||||
arrayC |
"pine" |
"lilac" |
3 |
"lilac" |
2 |
||||
[0] |
[1] |
[2] |
4 |
||||||
Desk Check 6.4 Relative Complement |
|||||||||
ceil |
i |
termA |
n |
||||||
this |
"elm" |
"pine" |
"rose" |
"lilac" |
4 |
0 |
|||
[0] |
[1] |
[2] |
[3] |
0 |
"elm" |
1 |
|||
setB |
"lilac" |
"pine" |
"fir" |
1 |
"pine" |
||||
[0] |
[1] |
[2] |
2 |
"rose" |
2 |
||||
arrayC |
"elm" |
"rose" |
3 |
"lilac" |
|||||
[0] |
[1] |
[2] |
[3] |
4 |
|||||
132
Desk Check 6.5 Union |
|||||||||||
ceil |
i |
termB |
n |
||||||||
this |
"elm" |
"pine" |
"rose" |
"lilac" |
7 |
0 |
|||||
[0] |
[1] |
[2] |
[3] |
1 |
|||||||
2 |
|||||||||||
setB |
"lilac" |
"pine" |
"fir" |
3 |
|||||||
[0] |
[1] |
[2] |
4 |
4 |
|||||||
0 |
"lilac" |
||||||||||
arrayC |
"elm" |
"pine" |
"rose" |
"lilac" |
"fir" |
1 |
"pine" |
||||
[0] |
[1] |
[2] |
[3] |
[4] |
[5] |
[6] |
2 |
"fir" |
5 |
||
3 |
Desk Check 6.6 Is Subset |
||||||||||
sizeA |
sizeB |
a |
b |
cmp |
return |
|||||
this |
"elm" |
"pine" |
"rose" |
3 |
4 |
0 |
0 |
0 |
false |
|
[0] |
[1] |
[2] |
1 |
1 |
10 |
|||||
2 |
4 |
|||||||||
setB |
"elm" |
"fir" |
"lilac" |
"pine" |
3 |
0 |
||||
[0] |
[1] |
[2] |
[3] |
2 |
4 |
Desk Check 6.7 Intersection |
|||||||||||
a |
termA |
b |
termB |
cmp |
n |
||||||
this |
"elm" |
"lilac" |
"pine" |
"rose" |
0 |
||||||
[0] |
[1] |
[2] |
[3] |
0 |
"elm" |
0 |
"fir" |
−1 |
|||
1 |
"lilac" |
6 |
|||||||||
setB |
"fir" |
"lilac" |
"pine" |
1 |
"lilac" |
0 |
1 |
||||
[0] |
[1] |
[2] |
2 |
"pine" |
2 |
"pine" |
0 |
2 |
|||
3 |
3 |
||||||||||
arrayC |
"lilac" |
"pine" |
sizeA |
sizeB |
ceil |
||||||
[0] |
[1] |
[2] |
4 |
3 |
3 |
Desk Check 6.8 Relative Complement |
|||||||||||
a |
termA |
b |
termB |
cmp |
n |
||||||
this |
"elm" |
"lilac" |
"pine" |
"rose" |
0 |
||||||
[0] |
[1] |
[2] |
[3] |
0 |
"elm" |
0 |
"fir" |
−1 |
1 |
||
1 |
"lilac" |
6 |
|||||||||
setB |
"fir" |
"lilac" |
"pine" |
1 |
"lilac" |
0 |
|||||
[0] |
[1] |
[2] |
2 |
"pine" |
2 |
"pine" |
0 |
||||
3 |
"rose" |
3 |
2 |
||||||||
arrayC |
"elm" |
"rose" |
4 |
||||||||
[0] |
[1] |
[2] |
[3] |
sizeA |
sizeB |
ceil |
|||||
4 |
3 |
4 |
133
Desk Check 6.9 Union |
|||||||||||
a |
termA |
b |
termB |
cmp |
n |
||||||
this |
"elm" |
"lilac" |
"pine" |
"rose" |
0 |
||||||
[0] |
[1] |
[2] |
[3] |
0 |
"elm" |
0 |
"fir" |
−1 |
1 |
||
setB |
"fir" |
"lilac" |
"pine" |
1 |
"lilac" |
6 |
2 |
||||
[0] |
[1] |
[2] |
1 |
"lilac" |
0 |
3 |
|||||
2 |
"pine" |
2 |
"pine" |
0 |
4 |
||||||
sizeA |
sizeB |
ceil |
3 |
"rose" |
3 |
5 |
|||||
4 |
3 |
7 |
4 |
arrayC |
"elm" |
"fir" |
"lilac" |
"pine" |
"rose" |
||
[0] |
[1] |
[2] |
[3] |
[4] |
[5] |
[6] |
Desk Check 6.10 Add |
|||||||
universe.list |
|||||||
"elm" |
"pine" |
"rose" |
"lilac" |
"fir" |
|||
[0] |
[1] |
[2] |
[3] |
[4] |
[5] |
[6] |
[7] |
bitset |
term |
index |
found |
i |
return |
0101 0000 |
"fir" |
null |
false |
4 |
true |
0101 1000 |
Desk Check 6.11 Remove |
|||||||
universe.list |
|||||||
"elm" |
"pine" |
"rose" |
"lilac" |
"fir" |
"ash" |
||
[0] |
[1] |
[2] |
[3] |
[4] |
[5] |
[6] |
[7] |
bitset |
term |
index |
i |
found |
return |
1101 1000 |
"pine" |
1 |
1 |
false |
true |
1001 1000 |
true |
Desk Check 6.12 Contains |
|||||||
universe.list |
|||||||
"elm" |
"pine" |
"rose" |
"lilac" |
"fir" |
"ash" |
||
[0] |
[1] |
[2] |
[3] |
[4] |
[5] |
[6] |
[7] |
bitset |
term |
index |
found |
1101 1000 |
"lilac" |
3 |
true |
134
Desk Check 6.13 Is Subset |
|||||||
universe.list |
|||||||
"elm" |
"pine" |
"rose" |
"lilac" |
"fir" |
"ash" |
||
[0] |
[1] |
[2] |
[3] |
[4] |
[5] |
[6] |
[7] |
this.bitset |
setB.bitset |
temp |
return |
1110 000 |
1101 1000 |
1110 0000 |
false |
1100 0000 |
Desk Check 6.14 Intersection |
|||||||
universe.list |
|||||||
"elm" |
"pine" |
"rose" |
"lilac" |
"fir" |
"ash" |
||
[0] |
[1] |
[2] |
[3] |
[4] |
[5] |
[6] |
[7] |
this.bitset |
setB.bitset |
result.bitset |
1110 0000 |
1101 1000 |
1110 0000 |
1100 0000 |
Desk Check 6.15 Relative Complement |
|||||||
universe.list |
|||||||
"elm" |
"pine" |
"rose" |
"lilac" |
"fir" |
"ash" |
||
[0] |
[1] |
[2] |
[3] |
[4] |
[5] |
[6] |
[7] |
this.bitset |
setB.bitset |
result.bitset |
1110 0000 |
1101 1000 |
1110 0000 |
0010 0000 |
Desk Check 6.16 Union |
|||||||
universe.list |
|||||||
"elm" |
"pine" |
"rose" |
"lilac" |
"fir" |
"ash" |
||
[0] |
[1] |
[2] |
[3] |
[4] |
[5] |
[6] |
[7] |
this.bitset |
setB.bitset |
result.bitset |
1110 0000 |
1101 1000 |
1110 0000 |
1111 1000 |
135
Chapter 7. Statistics
Desk Check 7.1 Minimum |
||||||
data |
i |
min |
||||
9 |
12.3 |
−3 |
5 |
9 |
||
[0] |
[1] |
[2] |
[3] |
1 |
||
2 |
−3 |
|||||
3 |
||||||
4 |
Desk Check 7.2 Sum |
||||||
data |
i |
s |
||||
7 |
3 |
−2 |
4.4 |
0 |
||
[0] |
[1] |
[2] |
[3] |
0 |
7 |
|
1 |
10 |
|||||
2 |
8 |
|||||
3 |
12.4 |
|||||
4 |
Desk Check 7.3 Sum |
||||||
data |
x |
s |
||||
7 |
3 |
−2 |
4.4 |
0 |
||
[0] |
[1] |
[2] |
[3] |
7 |
7 |
|
3 |
10 |
|||||
−2 |
8 |
|||||
4.4 |
12.4 |
Desk Check 7.4 Mean |
||||||
data |
s |
return |
||||
7 |
3 |
−2 |
4.4 |
12.4 |
3.1 |
|
[0] |
[1] |
[2] |
[3] |
Desk Check 7.5 Two Pass Variance |
||||||||||
data |
m |
i |
x |
t |
sqsum |
var |
||||
7 |
3 |
−2 |
4.4 |
3.1 |
0 |
10.73 |
||||
[0] |
[1] |
[2] |
[3] |
0 |
7 |
3.9 |
15.21 |
|||
1 |
3 |
−0.1 |
15.22 |
|||||||
2 |
−2 |
−5.1 |
41.23 |
|||||||
3 |
4.4 |
1.3 |
42.92 |
|||||||
4 |
136
Desk Check 7.6 One Pass Variance |
|||||||||||
data |
i |
x |
sum |
sqsum |
n |
mean |
var |
||||
7 |
3 |
−2 |
4.4 |
0 |
0 |
4 |
3.1 |
10.73 |
|||
[0] |
[1] |
[2] |
[3] |
0 |
7 |
7 |
49 |
||||
1 |
3 |
10 |
58 |
||||||||
2 |
−2 |
8 |
62 |
||||||||
3 |
4.4 |
12.4 |
81.36 |
Desk Check 7.7 One Pass Correlation |
||||||||||||
dataX |
i |
x |
y |
sumX |
sumY |
sumX2 |
sumY2 |
sumXY |
||||
12 |
4 |
3.9 |
2.1 |
0 |
0 |
0 |
0 |
0 |
||||
[0] |
[1] |
[2] |
[3] |
0 |
12 |
12 |
12 |
12 |
144 |
144 |
144 |
|
1 |
4 |
3.2 |
16 |
15.2 |
160 |
154.24 |
156.8 |
|||||
dataY |
2 |
3.9 |
3.5 |
19.9 |
18.7 |
175.21 |
166.49 |
170.45 |
||||
12 |
3.2 |
3.5 |
1.9 |
3 |
2.1 |
1.9 |
22 |
20.6 |
179.62 |
170.1 |
174.44 |
|
[0] |
[1] |
[2] |
[3] |
4 |
n |
meanX |
meanY |
sdevX |
sdevY |
covar |
correl |
4 |
5.5 |
5.15 |
3.83 |
4.00 |
15.29 |
0.998 |
Desk Check 7.8 Stable Mean |
|||||||
data |
i |
delta |
mean |
||||
−2 |
3 |
4.4 |
7 |
−2 |
|||
[0] |
[1] |
[2] |
[3] |
1 |
5 |
0.5 |
|
2 |
3.9 |
1.8 |
|||||
3 |
5.2 |
3.1 |
Desk Check 7.9 Stable Variance |
||||||||||
data |
i |
weight |
delta |
mean |
sqsum |
var |
||||
−2 |
3 |
4.4 |
7 |
−2 |
0 |
10.73 |
||||
[0] |
[1] |
[2] |
[3] |
1 |
0.5 |
5 |
0.5 |
12.5 |
||
2 |
0.67 |
3.9 |
1.8 |
22.64 |
||||||
3 |
0.75 |
5.2 |
3.1 |
42.92 |
||||||
4 |
Desk Check 7.11 Multiple Statistics |
||||||||||
data |
i |
x |
weight |
delta |
mean |
sqsum |
||||
−2 |
3 |
4.4 |
7 |
−2 |
0 |
|||||
[0] |
[1] |
[2] |
[3] |
1 |
3 |
0.5 |
5 |
0.5 |
12.5 |
|
2 |
4.4 |
0.67 |
3.9 |
1.8 |
22.64 |
|||||
3 |
7 |
0.75 |
5.2 |
3.1 |
42.92 |
|||||
4 |
count |
min |
med |
max |
sum |
var |
sdev |
4 |
−2 |
3.7 |
7 |
12.4 |
10.73 |
3.28 |