Preparation check

# CS51 preparation check #

This self-administered quiz is intended to determine your readiness for CS 51. You should be able to get these problems right easily in a relatively short period of time. Some of the examples use code examples written in C or Python, but no knowledge of the details of those languages should be necessary to understand and complete the problems.

While there is no minimum score required for enrollment, if you ﬁnd yourself confused by any of the concepts, get more than one or two questions wrong for reasons of preparation, or ﬁnd the programming exercises quite difﬁcult, you should carefully consider whether you are prepared for the course and talk to course staff for placement advice.

## Problem 1 #

Consider the following block of C code:

int i, j;
for (i = 0; i < 5; i++)
for (j = i; j < 5; j++)
printf("*");

How many asterisks does this print in total?

1. 5
2. 10
3. 15
4. 25
5. None of the above
Show solution
c. 15

## Problem 2 #

Now, we generalize the code by using a loop limit of n instead of 5:

int i, j;
for (i = 0; i < n; i++)
for (j = i; j < n; j++)
printf(" * ");

If we run this program with different values of n, will there ever be cases in which the number of asterisks printed exceeds $100 \cdot n \cdot \log n$

1. No, there will not.
2. Yes, there will.
3. There isn’t enough information to determine.
Show solution
c. Yes, there will. (The answer can be argued by comparing the time complexity of the algorithm against the provided function using $O$ notation: The program’s time complexity is quadratic ($O(n^2)$), which grows faster than $O(n \log n)$.)

## Problem 3 #

In binary, what is $10111111 + 00000001$?

1. 10000000
2. 10111111
3. 11111101
4. 11000000
5. None of the above
Show solution
d. 11000000

## Problem 4 #

Below are four different Python programs that each print the string “hello world” a different number of times. Rank them from 1 to 4 by the number of times each prints “hello world”, where 1 prints “hello world” the fewest times and 4 the most. (For reference, the Python operator // used in hello_two is the integer division operator, so for instance, 5 // 2 is 2.)

def hello_one(n):
if n <= 0:
return
else:
print("hello world")
hello_one(n - 1)
hello_one(50)
def hello_two(n):
if n <= 0:
return
else:
print("hello world")
hello_two(n // 1)
hello_two(50)
def hello_three(n):
if n <= 0:
return
else:
print("hello world")
hello_three(n - 1)
hello_three(n - 1)
hello_three(50)
def hello_four(n):
if n <= 0:
return
else:
print("hello world")
print("hello world")
print("hello world")
hello_four(n - 1)
hello_four(50)
Show solution
b > a > d > c

The next two problems ask you to write short programs. Try to write a correct solution without the aid of a compiler or interpreter and then run your code to check your work. See if you can get the correct output on your ﬁrst try. You may use any programming language of your choice.

## Problem 5 #

Write a program that prints the numbers from 1 to 100, one per line, but for multiples of three print “Fizz” instead of the number and for multiples of ﬁve print “Buzz”. For numbers which are multiples of both three and ﬁve print “FizzBuzz”: 1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, 16…

Show solution

There are many ways to solve this problem. Here is a Python solution:

def fizzbuzz(n):
for i in range(1, n + 1):
if i % 3 == 0:
if i % 5 == 0:
print("FizzBuzz")
else:
print("Fizz")
elif i % 5 == 0:
print("Buzz")
else:
print(i)
fizzbuzz(100)

Write the following functions that deal with lists of ﬂoating-point numbers.

## Problem 6 #

Write a function that returns the arithmetic mean of a list of numbers (that is, their sum divided by the number of elements).

Show solution

A direct implementation performing the sum and length calculations simultaneously is

def mean(lst):
sum = 0
length = 0
for i in lst:
sum += i
length += 1
return sum / length

Making use of some built-in Python functions sum and len:

def mean(lst):
return sum(lst) / len(lst)

The sum and len functions can themselves be implemented recursively as

def sum(lst):
if lst == []:
return 0
else:
return lst[0] + sum(lst[1:])

def len(lst):
if lst == []:
return 0
else:
return 1 + len(lst[1:])

or iteratively as

def sum(lst):
accum = 0
for i in lst:
accum += i
return accum

def len(lst):
accum = 0
for i in lst:
accum += 1
return accum

## Problem 7 #

The median element in a list is the element in the “middle”, with the same number of larger and smaller elements in the list. For instance, the median element of the list 5, 1, 8, 3, 2, 4, 8 is 4, since there are three elements smaller (1, 2, 3) and three larger (5, 8, 8). (For even length lists (like 1, 2, 3, 4), you can use either of the two middle elements (2 or 3) as the median.) Write a function that returns the median of a list of numbers.

Show solution

Here is a simple Python implementation. For even length lists, it uses the larger of the two middle elements.

def median(lst):
sorted_list = sorted(lst)
midpoint = len(lst) // 2
return sorted_list[midpoint]

## Problem 8 #

Alice has fallen down the rabbit hole into Wonderland, where she meets the Queen of Hearts and her King. While the Queen challenges Alice to Croquet, the King challenges Alice to a series of puzzles. The King tells Alice that the Queen is always either happy (☺) or sad (☹). There are four different spells the King can put on the Queen to try to change her mood: $\heartsuit, \diamondsuit, \clubsuit, \spadesuit$. If the Queen is happy about someone being beheaded, but sad about losing croquet, the King can put the $\diamondsuit$ spell on her to make her completely happy again. In our symbolic notation, this would mean that: $\diamondsuit$(☺, ☹) = ☺.

The other spells can inﬂuence the Queen’s moods as follows:

\begin{aligned} \spadesuit(☺) &= ☹ \cr \spadesuit(☹) &= ☺ \cr \heartsuit(☺, ☺) &= ☺ \cr \heartsuit(☺, ☹) &= ☹ \cr \heartsuit(☹, ☹) &= ☹ \cr \diamondsuit(☺, ☺) &= ☺ \cr \diamondsuit(☺, ☹) &= ☺ \cr \diamondsuit(☹, ☹) &= ☹ \cr \clubsuit(☺, ☺) &= ☹ \cr \clubsuit(☹, ☺) &= ☺ \cr \clubsuit(☹, ☹) &= ☹ \end{aligned}

Note that the order of moods within the spells does not matter, so $\clubsuit(☺, ☹) = \clubsuit(☹, ☺)$. In all of the following situations, Alice must tell the King which spell he should use in place of the $\square$ symbol to make the Queen happy! Choose the corresponding answers below.

• $\square(☹)$

1. $\spadesuit$
2. $\heartsuit$
3. $\diamondsuit$
4. $\clubsuit$
5. None of the above
• $\spadesuit(\square(☺, ☹))$

1. $\spadesuit$
2. $\heartsuit$
3. $\diamondsuit$
4. $\clubsuit$
5. None of the above
• $\diamondsuit(☹, \spadesuit(\square(☺, ☺)))$

1. $\spadesuit$
2. $\heartsuit$
3. $\diamondsuit$
4. $\clubsuit$
5. None of the above
Show solution
• $\square(☹)$: a. $\spadesuit$
• $\spadesuit(\square(☺, ☹))$: b. $\heartsuit$
• $\diamondsuit(☹, \spadesuit(\square(☺, ☺)))$: d. $\clubsuit$

## Problem 9 #

Consider the following pseudocode program:

for each student
if student average > 60
award student a D
else if student average > 70
award student a C
else if student average > 80
award student a B
else if student average > 90
award student an A
else
award student an E

If a student gets 100 in the class, what grade is that student awarded?

1. A
2. B
3. C
4. D
5. E
6. None of the above
Show solution
d. D (Given standard grading assumptions, the code is undoubtedly buggy.)

In the next two problems, you’ll work with Python logical values and operators). In Python, the values True and False are used for the logical values indicating truth and falsity, the logical negation operator is not, the logical conjunction operator is and, the logical disjunction operator is or, the equality operator is ==, and the inequality operator is !=.

## Problem 10 #

Which of the following conditions are sufficient for not (A or B) to evaluate to True? Select all options that apply:

1. A is True and B is True
2. A is True and B is False
3. A is False and B is True
4. A is False and B is False
5. (not A) and (not B) is True
Show solution
d. A is False and B is False
e. (not A) and (not B) is True

## Problem 11 #

Which of the following conditions are sufficient for (A != B) and (A or B) to evaluate to True? Select all options that apply:

1. A is True and B is True
2. A is True and B is False
3. A is False and B is True
4. A is False and B is False
Show solution
b. A is True and B is False
c. A is False and B is True

## Problem 12 #

Imagine that the school registrar has asked you to build a program to verify student enrollments. You have one text file containing the names of all students in good standing with the University, and another set of files containing the names of all students who have enrolled in courses. You need to ﬁnd out which students enrolled in courses are not in good standing, and plan to read one of the text files into a data structure.

Which of the following data structures is best suited for this task?

1. array
2. binary search tree
3. hash table