Department of Computer Science and Engineering Tandon School of Engineering, NYU CS1133 Exam II, 2019.04.16
• Do not consult anyone in any way or means, or look up any materials in any way during the exam.
• Use of any electronic devices such as computers and calculators are prohibited.
• Need to show your NYU ID card to take the exam and to return your exam paper.
• Put the answers to be graded in your bluebook.
• Write your name and your lab section clearly on the front page of the bluebook. Circle your last name.
• You can use any page of your bluebooks as scratch paper, but do not tear off any. Cross out anything that you do not want to be graded.
• Return your bluebook and sign your name before leaving the exam room.
• You should keep the question sheets with you. Do not return those with the bluebooks.
• No need to put comments in your programs.
• Unless the problem specifies a particular output format, there is no need to display any results.
• Make sure you do the problems using only materials covered in the course thus far, otherwise no credits will be given.
• Write programs that are reasonably flexible. Do not deal only with a given example, and avoid hardwiring as much as possible.
The following list provides you the names of the built-in MATLAB functions that you may use on this exam. You are not allowed to use any other functions! If you believe that you need to use any other functions not on this list, you need to ask me during the exam.
log log10 exp asin acos atan sinh cosh tanh fix round ceil mod rem rand rand randn randi
For this exam you can also use the following programming constructs if else elseif for while end
Notice that the use of the break is not allowed.
sin
asind
length
floor
input
zeros ones
cos tan sind
acosd atand double
size sqrt abs
sum mean max min find transpose all any nnz
1
cosd tand logical linspace num2str disp
Problem 1 [100 pts]
A person is initially located at the center of a square. The square is divided into a 2m − 1 by 2m − 1 grid of smaller squares. He can get out from the small square at the center (marked by a cross) if he takes m consecutive steps along the same direction either all to the east, north-east, north, north-west, west, south-west, south, or south-east (as shown in the figure on the left where we assume m is 5). However he is a little disoriented and the entire square is sloping downward to the west. Every step that he makes can be in any one of 8 possible directions: (1) east, (2) north-east, (3) north, (4) north-west, (5) west, (6) south-west, (7) south, or (8) south-east (as shown in the figure on the right where the cross marks the current position and the number specifies the direction of the step, east, north-east, etc.) and ends up in one of the neighboring small squares. However the probabilities for each of the choices are not equal because of the slope. They are given according to the direction of the step as follows:
4
3
2
5
1
6
7
8
Step Direction Probability
1 2/32 2 3/32 3 4/32 4 5/32 5 6/32 6 5/32 7 4/32 8 3/32
We want to perform a computer simulation involving many trials to find the average total number of steps that he needs to take to get out of the square. Your simulation must work for any positive m. Here you should set m = 15 and no need to produce any display.
You should assume that the following row vector Prob containing the various probabilities has already been given to you:
Prob = [ 2 3 4 5 6 5 4 3 ] / 32;
Hint: The first step is to compute the cumulative sum of Prob. In general given a vector Vec, its cumulative sum, say CumSum is a vector of the same length as Vec. The n-th element of CumSum, is given by the sum of all the elements in Vec that precede Vec(n), including Vec(n) itself. This resulting vector will be useful in your simulation to generate the 8 possible moves with the required probabilities in a given time step. Use the vector CumSum to perform the simulation even if you don’t know how to compute it.
Forexample,ifVec = [ 0.5 0.1 0.4 1.0 ]thenCumSum = [ 0.5 0.6 1.0 2.0 ]. 2