Description
1. (50 points) There are two players. One player selects a random number between 1 and 32 and the other
one needs to guess this number asking a minimum number of questions with three possible answers to
each question:
• yes – the number is found
• lower – the number to be guessed is smaller than the number in the question
• higher – the number to be guessed is greater than the number in the question
Hint. The number of questions in this case (range [1, 32]) should not exceed 6.
(a) Implement an algorithm for solving this problem in C++ and test it with the following input
in ranges from 1 to: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048. Be sure that your program
throws an exception in case of an invalid dialog entry during the computations.
Note that the “brute force” algorithm is not accepted.
(b) Tabulate the output results in the form (range, guessed number, number of comparisons required
to guess it) in a given range using an STL vector. Plot the number of questions returned by your
algorithm when the number to be guessed is selected as n = 2k
, where k = 1, 2, . . . , 11. You can
use any graphical package (including a spreadsheet).
(c) Provide a mathematical formula/function which takes n as an argument, where n is equal to the
upper value of the testing ranges, and returns as its value the maximum number of questions for
the range [1, . . . , n]. Does your formula match computed output for a given input? Justify your
answer.
(d) How can you modify your formula/function if the number to be guessed is between 1 and N,
where N is not an exact power of two? Test your program using input in ranges starting from 1
to 2k − 1, k = 2, 3, . . . 11.
(e) Use Big-O asymptotic notation to classify this algorithm.
Submit for grading an electronic copy of your code and solutions to the questions above.
Graph for n=range;
2
3
4
(a) Graph for n=range-1;
5
6
7
2. Part C:
(a) max(n)=log2n +1
(b) when the remaining list only has to elements add a check for the second element
(c) Big(O)=log2n
8
3. (50 points) Matrix operations
(a) Write a C++ function to find the total number of additions required to compute the average of
all elements in an n × n two-dimensional array of integers. Provide two implementations for this
problem: vector of vectors of size n and the STL class matrix. Populate the two-dimensional array
using random numbers. Read about the STL matrix class and random functions in “Programming
Principles and Practice Using C++” by B. Stroustrup, chapter 24.
(b) Test your program for different values of n and collect the number of corresponding additions.
(c) Write a formula that expresses the relation between input sizes (n) and the corresponding number
of additions.
(d) Provide a few examples to compare computational results and the numbers of additions obtained
from the formula.
(e) Graph your computational results for n = 10, 20, 100, 1000, 10000. Use the semi-logarithmic scale
with respect to n.
(f) Measure the computational time of the algorithms for n = 10, 20, 100, 1000, 10000, see Remarks
below about ctime.h and Stopwatch.h.
(g) Use Big-O asymptotic notation to classify this algorithm
Submit an electronic copy of your code and results of all your experiments for grading.
Part C: f(n)= n2
(a) Part E:
9
10
11
(c) Part F
(d)
(e) Part G: Big(O)=n2
12
