Algorithms Problem Set 1

CSCI 3104: Algorithms
Problem Set 1 (45 points total)

Advice 1 : For every problem in this class, you must justify your answer: show how you arrived at it
and why it is correct. If there are assumptions you need to make along the way, state those clearly.
Advice 2 : Verbal reasoning is typically insufficient for full credit. Instead, write a logical argument,
in the style of a mathematical proof.
1. (5 points) Give an example of an application that uses a proprietary algorithm (i.e.
Spotify’s ”Discover Weekly” playlist, Google’s PageRank algorithm, etc.). Find an
article that discusses this algorithm and give a summary of its content. Provide at
least 4-5 sentences for full credit.
1
CSCI 3104: Algorithms
Problem Set 1 (45 points total)
Instructor Buxton
Summer 2019, CU-Boulder
2. (15 points) Consider two algorithms that perform the same function, that run in n/4
and log2(n), respectively, where n ∈ N (i.e. natural numbers). n represents the input
size and n/4 and log2(n) represent runtimes with respect to the input size.
(a) Plot these runtimes on the same graph with the values n ∈ [1, 50] (don’t forget
labels). Provide the set of intervals over N, where n/4 is the strictly better
algorithm to use (think greater than, not greater than or equal).
2
CSCI 3104: Algorithms
Problem Set 1 (45 points total)
Instructor Buxton
Summer 2019, CU-Boulder
3. (15 points) Harry the Wizard needs your help solving a riddle deep in an abandoned
dwarven mine. There are two doors marked A and B, respectively, and a stone pedestal
in the middle of the room inscribed with the following text:
”The dwarves who dwelled in this mine were fond of mathematical drinking games. Two dwarves, Arnold and Barry,
are chosen as the participants for this game, and pick functions that they think will best predict the number of people
who enter the pub in an hour (p) based on the number of drinks they consume in that hour (d). They choose p(d) = d/2
and p(d) = 2ln(d), respectively. Below is a record of the number of drinks consumed and the corresponding number of
patrons patrons who entered the bar over four hours.
Number Drinks (d) Number Patrons (p)
5 4
10 10
15 4
20 8
Which dwarf, Arnold or Barry, chose the most accurate function?”
Due to an error in Harry’s mental calculations in the last puzzle causing Grog the
Barbian to lose his pinky finger, the party demands a written explanation of the solution
to the puzzle. Additionally, since Grog doesn’t know how to read, provide a relevant
figure in your solution so Grog can believe he is part of the discussion.
3
CSCI 3104: Algorithms
Problem Set 1 (45 points total)
Instructor Buxton
Summer 2019, CU-Boulder
4. (10 points) Consider the following recurrence relation:
Gn =



1 if n = 0
-1 if n = 1
2 if n = 2
(Gn−1)(Gn−2)+Gn−3 otherwise
(a) Write pseudocode for this function that takes in a positive integer, n, and returns
the nth number in the sequence.
(b) What is the 10th number in the sequence?
4