Description
Problem 1 [25 points]. Implementation of a standard greatest common divisor algorithm. You should implement the function
gcd(a, b)
where you may assume that a and b are positive integers. You are to compute the greatest common
divisor of a and b, and return it at the end of the function call.
Problem 2 [25 points]. Count the number of rectangles on a Rubik’s cube. Beside the
standard 3 × 3 × 3 Rubik’s cube, there are other cubes where each side is divided into n pieces
(n = 3 for the standard Rubik’s cube). Ignoring the colors, the small squares on each surface of a
Rubik’s cube may be combined to form larger rectangular shapes. For an n × n × n Rubik’s cube,
compute the total number of different rectangles (including squares) that can be obtained this way.
You are to implement the function
rubiks(n)
that returns the number of rectangles. For the 2 × 2 × 2 cube, the answer should be 54.
Problem 3 [25 points]. Guessing a number. You are asked to guess a random number x
between 1 and n (inclusive). To test whether your guess is correct, you are provide a function
is this it(a)
that returns True if and only if a == x. Implement the function
guess unlimited(n, is this it)
that returns your guess of x. You may call is this it as many times as you want.
Page 1 © Jingjin Yu ◦ Rutgers University
CS 440 Fall 2018 Machine Problem Assignment 1 Due date: 09/23/2018 11:55pm
Problem 4 [25 points]. Guessing a number, with busting. You are asked to guess a random
number x between 1 and n (inclusive). You are provided a function
is this smaller(a)
that returns True if and only if a < x. Implement the function
guess limited(n, is this smaller)
that returns your guess of x. You may call is this smaller as many times as you want as long
as it returns True. However, you fail if is this smaller returns False three times. You are to
minimize the average number of calls to is this smaller that you make. For grading, you will
get 15 points if you have a basic working implementation that guesses x correctly without having
is this smaller returns False three times. You get the full score if your number of calls to
is this smaller is no more than two plus the optimal number. That is, for a given n, the optimal
number of calls to is this smaller may be k times. You get the full score if you make no more
than k + 2 guesses on average.
Problem 5 [20 bonus points]. Guessing number competition. In this task you are given the
same is this smaller function as in Problem 4. You can make any number of guesses and there
is no limit on how is this smaller may be called. You are to implement your guessing routine in
guess limited plus(n, is this smaller).
Under the condition that your guesses are correct, you want to minimize the total number of calls
to is this smaller plus the number of times is this smaller returns False. For this task, you
will be competing with each other. The top 20 teams will get bonus points in 1 point decrements,
i.e., the top team will get 20 points, the next 19 points, and so on. This problem is optional and if
you choose not to do it, leave guess limited plus unchanged.
Page 2 © Jingjin Yu ◦ Rutgers University
