15-110 PS6 Sample Solutions - Spring 2018

1. 

(a) [ [ 4, 3] , [12, 5], [26, 11] [5, 9] ]

(b) matrix[row][col] % 2 == 1   OR    matrix[row][col] % 2 != 0
    count + 1                         count + 1

(c) 4, 2

2. 

(a) Algorithm 2 would be faster. Algorithm 1 would have to shift 
all students one seat over whereas Algorithm 2 would just seat 
the student and have that student point to the original first student.

(b) Algorithm 1 would be faster. Algorithm 2 requires the organizer to 
go through all students, one by one starting with the first student 
alphabetically, to find the last student, whereas Algorithm 1 allows 
the organizer to go directly to the last seat used.

3. 

Stacks (shown sideways):
8 9
8 9 4
8 5
40
40 1
40 1 8
40 1 8 2
40 1 4
40 5
8

Returns 8.

4. 

(a) q.append(z)

(b) (if part:)  len(q) == 0  OR  len(q) < 1  OR  q == []
    (else part:)
    z = q[0]
    q.remove(z)  OR  q.remove(q[0])  OR  q.pop(0)

5. 

"bag":  k = 6447463, bucket = 0, No collision
"bin":  k = 6449518, bucket = 9, No collision
"jug":  k = 6976871, bucket = 0, Collision

6.

(a) crackthecode  (just copy and paste the section into an editor)

(b) Stores more music since the current format on discs is not 
compressed, but MP3 is compressed so the disc could hold more music.

(c) Tom Cortina

(d) In 100 years, there probably won't be any CD players/readers that 
can read the disc.