CS440-Machine Problem Assignment 1 Solved

Problem 1 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 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 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.

 

Problem 4 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 isthis 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 . 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.