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.4
12

−2
7

5
5

7
−2

−12
3.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

9
23

23
18

18
−3

−3
8

8
9

0

9

4

1

[0]

[1]

[2]

[3]

[4]

2

3

4

118

Desk Check 1.6 Rotate Right

list

i

last

swap

9
8

23
9

18
23

−3
18

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

23
14

−5
11

9
23

−3
−5

14
9

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

0
5
7

5

maxLenR

curr

max

len

curr

max

len

John

5
7

4

Thomas

7

6

maxLenR

curr

max

len

curr

max

len

curr

max

len

curr

max

len

null

5

Phillip

5
7

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

10000
10150

0.005

8
7

11265

futureValueR

principal

rate

period

return

10150
10302

0.005

7
6

11265

futureValueR

principal

rate

period

return

10302
10457

0.005

6
5

11265

futureValueR

principal

rate

period

return

10457
10614

0.005

5
4

11265

futureValueR

principal

rate

period

return

10614
10773

0.005

4
3

11265

futureValueR

principal

rate

period

return

10773
10935

0.005

3
2

11265

futureValueR

principal

rate

period

return

10935
11099

0.005

2
1

11265

futureValueR

principal

rate

period

return

11099
11265

0.005

1
0

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