﻿ Answers to Desk Checks - Advanced Programming Techniques (2011, 2013) ﻿

## 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 3.412 −27 55 7−2 −123.4 0 4 3.4 1 3 −2 [0] [1] [2] [3] [4] 2 2
 Desk Check 1.5 Rotate Left list i swap last 923 2318 18−3 −38 89 0 9 4 1 [0] [1] [2] [3] [4] 2 3 4

118

 Desk Check 1.6 Rotate Right list i last swap 98 239 1823 −318 8−3 4 4 8 3 [0] [1] [2] [3] [4] 2 1 0
 Desk Check 1.7 Rotate list group one two save 11−3 2314 −511 923 −3−5 149 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"17 "charity"8 "clothing"6 "dentist"7 "dividend"14 "doctor"11 "education"4 [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"17 "charity"8 "clothing"6 "dentist"7 "dividend"14 "doctor"11 "education"4 [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 057 5 maxLenR curr max len curr max len John 57 4 Thomas 7 6 maxLenR curr max len curr max len curr max len curr max len null 5 Phillip 57 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 1000010150 0.005 87 11265 futureValueR principal rate period return 1015010302 0.005 76 11265 futureValueR principal rate period return 1030210457 0.005 65 11265 futureValueR principal rate period return 1045710614 0.005 54 11265 futureValueR principal rate period return 1061410773 0.005 43 11265 futureValueR principal rate period return 1077310935 0.005 32 11265 futureValueR principal rate period return 1093511099 0.005 21 11265 futureValueR principal rate period return 1109911265 0.005 10 11265 futureValueR principal rate period return 11265 0.005 0−1 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
﻿

﻿