1. Do not look at the test before the proctor starts the round.
2. This test consists of 10 short-answer problems to be solved in 60 minutes. Each question is
worth one point.
3. Write your name, team name, and team ID on your answer sheet. Circle the subject of the
test you are currently taking.
4. Write your answers in the corresponding boxes on the answer sheets.
5. No computational aids other than pencil/pen are permitted.
6. All answers are integers.
7. If you believe that the test contains an error, submit your protest in writing to Porter 100.
CMIMC 2016 Computer Science Reference Sheet
Pseudocode A function f (n) = ⌦(g(n)) if there The neighbors of a vertex is the set of
exists a constant c > 0 such that all vertices adjacent to it. The degree
Code f (n) > c·g(n) holds for all sufficiently of a vertex is the number of neighbors.
Code is written with line numbers in- large n. A path is a sequence of vertices
dicated to the left. A function f (n) = ⇥(g(n)) if f (n) = v0 , . . . , vk such that vi ⇠ vi+1 for all i
Bold and caps lock indicates a spe- O(g(n)) and f (n) = ⌦(g(n)). and no vi is visited twice. A cycle is
cial tag, including but not limited like a path but with v0 ⇠ vk .
to TRUE, FALSE, IF, ELSE IF, A graph is connected if for every two
FOR, IN, WHILE, FUNCTION,
Data Structures
vertices there exists a path from one
RETURN, etc. Arrays to the other. Otherwise, it is discon-
A collection of elements accessed by nected. The distance between any two
Variable Assignment indices. vertices in a connected graph is the
[variable name] [value] length of the shortest path from one
This assigns [value] to [variable ··· to the other.
name].
0 1 2 ··· n 1
Conditionals Logic
IF [condition] Lists
A boolean function is a function f :
[code] A sequence of elements, each pointing
{0, 1}n 7! {0, 1}. We can write its
This executes [code] if [boolean con- to the next element and the last one
truth table by listing all possible in-
dition] is true. pointing to null.
puts with its outputs.
ELSE IF [condition] The three main boolean operators are
···
[code] NOT (¬), AND (^), OR (_), and
This executes [code] if the previ- XOR ( ). Their truth tables are be-
ous boolean conditions are false and Stacks low:
[boolean condition] is true. A set with a top and bottom where
elements are added to the top and re-
ELSE [condition] moved from the top (first-in last-out). x y ¬x x^y x_y x y
[code] 0 0 1 0 0 0
This executes [code] if all other 0 1 0 1 1
boolean conditions are false and 1 0 0 0 1 1
[boolean condition] is true. .. 1 1 1 1 0
.
Loops Strings
FOR [variable] IN [list]
[code] Queues An alphabet is any finite set of sym-
This executes [code] iteratively for A set with a front and back where bols. We usually denote an alphabet
each value of [variable] in [list]. elements are added to the back and by ⌃.
removed from the front (first-in last- A string is a sequence of elements
WHILE [conditional] out). from an alphabet. We denote the
[code]
empty string by ".
This executes [code] iteratively while ··· The length of a string is the length of
[conditional] is true.
the sequence it represents. Length is
Trees denoted by | · |.
Functions For a string s = s0 s1 s2 . . ., the
FUNCTION [name]([arguments]) A set of elements, each with at most
two children. substring starting at i ending at
This defines a function that takes in
j, denoted s[i, j), is the string
[arguments].
si si+1 . . . sj 1 . This is only well-
RETURN [value] defined when 0 i j 1, but we
This causes the function to immedi- also define the substring to be empty
ately return [value]. if i = j.
The concatenation of two strings A
Big O, ⌦, ⇥ Graph Theory and B is the string AB. The concate-
nation of n copies of the string s is
A function f (n) = O(g(n)) if there A graph is a set of vertices V and a denoted by sn , where s0 = ".
exists a constant c > 0 such that set of edges E ✓ V ⇥ V . Two vertices
f (n) < c·g(n) holds for all sufficiently V1 , V2 are adjacent (denoted V1 ⇠ V2 )
large n. if there is an edge connecting them.
Computer Science
1. For how many distinct ordered triples (a, b, c) of boolean variables does the expression a _ (b ^ c) evaluate to
true?
2. In concurrent computing, two processes may have their steps interwoven in an unknown order, as long as the
steps of each process occur in order. Consider the following two processes:
Process A B
Step 1 x x 4 x x 5
Step 2 x x·3 x x·4
Step 3 x x 4 x x 5
Step 4 x x·3 x x·4
One such interweaving is A1, B1, A2, B2, A3, B3, B4, A4, but A1, A3, A2, A4, B1, B2, B3, B4 is not since
the steps of A do not occur in order. We run A and B concurrently with x initially valued at 6. Find the
minimal possible value of x among all interweavings.
3. Sophia writes an algorithm to solve the graph isomorphism problem. Given a graph G = (V, E), her algorithm
iterates through all permutations of the set {v1 , . . . , v|V | }, each time examining all ordered pairs (vi , vj ) 2 V ⇥V
to see if an edge exists. When |V | = 8, her algorithm makes N such examinations. What is the largest power
of two that divides N ?
4. Given a list A, let f (A) = [A[0] + A[1], A[0] A[1]]. Alef makes two programs to compute f (f (...(f (A)))),
where the function is composed n times:
1: FUNCTION T1 (A, n) 1: FUNCTION T2 (A, n)
2: IF n = 0 2: IF n = 0
3: RETURN A 3: RETURN A
4: ELSE 4: ELSE
5: RETURN [T1 (A, n 1)[0] + T1 (A, n 1)[1], 5: B T2 (A, n 1)
T1 (A, n 1)[0] T1 (A, n 1)[1]] 6: RETURN [B[0] + B[1], B[0] B[1]]
Each time T1 or T2 is called, Alef has to pay one dollar. How much money does he save by calling T2 ([13, 37], 4)
instead of T1 ([13, 37], 4)?
5. We define the weight of a path to be the sum of the numbers written on each edge of the path. Find the
minimum weight among all paths in the graph below that visit each vertex precisely once:
9 16
11
3 4 4 11
20 18
19 8 2 17
6
3 14
6. Aaron is trying to write a program to compute the terms of the sequence defined recursively by a0 = 0, a1 = 1,
and (
an 1 an 2 n ⌘ 0 (mod 2)
an =
2an 1 an 2 else
However, Aaron makes a typo, accidentally computing the recurrence by
(
an 1 an 2 n ⌘ 0 (mod 3)
an =
2an 1 an 2 else
For how many 0 k 2016 did Aaron coincidentally compute the correct value of ak ?
7. Given the list
A = [9, 12, 1, 20, 17, 4, 10, 7, 15, 8, 13, 14],
we would like to sort it in increasing order. To accomplish this, we will perform the following operation
repeatedly: remove an element, then insert it at any position in the list, shifting elements if necessary. What
is the minimum number of applications of this operation necessary to sort A?
8. Consider the sequence of sets defined by S0 = {0, 1}, S1 = {0, 1, 2}, and for n 2,
Sn = Sn 1 [ {2n + x | x 2 Sn 2 }.
For example, S2 = {0, 1, 2} [ {22 + 0, 22 + 1} = {0, 1, 2, 4, 5}. Find the 200th smallest element of S2016 .
9. Ryan has three distinct eggs, one of which is made of rubber and thus cannot break; unfortunately, he doesn’t
know which egg is the rubber one. Further, in some 100-story building there exists a floor such that all normal
eggs dropped from below that floor will not break, while those dropped from at or above that floor will break
and cannot be dropped again. What is the minimum number of times Ryan must drop an egg to determine
the floor satisfying this property?
10. Given x0 2 R, f, g : R ! R, we define the non-redundant binary tree T (x0 , f, g) in the following way:
(a) The tree T initially consists of just x0 at height 0.
(b) Let v0 , . . . , vk be the vertices at height h. Then the vertices of height h + 1 are added to T by: for
i = 0, 1, . . . , k, f (vi ) is added as a child of vi if f (vi ) 62 T , and g(vi ) is added as a child of vi if g(vi ) 62 T .
For example, if f (x) = x + 1 and g(x) = x 1, then the first three layers of T (0, f, g) look like:
1 1
2 2
If f (x) = 1024x 2047bx/2c and g(x) = 2x 3bx/2c + 2bx/4c, then how many vertices are in T (2016, f, g)?
