# 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?

- 5
- 10
- 15
- 25
- None of the above

## Show solution

## 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$

- No, there will not.
- Yes, there will.
- There isn’t enough information to determine.

## Show solution

## Problem 3 #

In binary, what is $10111111 + 00000001$?

- 10000000
- 10111111
- 11111101
- 11000000
- None of the above

## Show solution

## 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 // 2)
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

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(☹)$

- $\spadesuit$
- $\heartsuit$
- $\diamondsuit$
- $\clubsuit$
- None of the above

$\spadesuit(\square(☺, ☹))$

- $\spadesuit$
- $\heartsuit$
- $\diamondsuit$
- $\clubsuit$
- None of the above

$\diamondsuit(☹, \spadesuit(\square(☺, ☺)))$

- $\spadesuit$
- $\heartsuit$
- $\diamondsuit$
- $\clubsuit$
- 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?

- A
- B
- C
- D
- E
- None of the above

## Show solution

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:

`A`

is`True`

and`B`

is`True`

`A`

is`True`

and`B`

is`False`

`A`

is`False`

and`B`

is`True`

`A`

is`False`

and`B`

is`False`

`(not A) and (not B)`

is`True`

## Show solution

`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:

`A`

is`True`

and`B`

is`True`

`A`

is`True`

and`B`

is`False`

`A`

is`False`

and`B`

is`True`

`A`

is`False`

and`B`

is`False`

## Show solution

`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?

*array**binary search tree**hash table**linked list**none of the above*

## Show solution

*hash table*