CS 1112 Exercise 8

Due date: Sunday, April 11, 11:00pm EST.

You have until Sunday, April 11, at 11:00 PM EDT to complete and submit Problem 1 of this exercise on CMS (for manual grading). Problem 2 is to be submitted using Matlab Grader by the same deadline.

Random walk

This question requires that you design a solution. Instead of giving you the specifications of a function, we are asking you to design a complete solution: you decide what scripts and/or functions are necessary and implement those functions/scripts. Take some time to do the planning—think about what values you need to keep track of and choose “appropriately-shaped” variables to store them.

A random walk that starts from the center of a 21×21 grid ends when a boundary is reached. On average, which “square” or grid point is visited most often? Function RandomWalk2D() (discussed in Lecture 11) is shown below for your reference; you should call it from your solution, but do not modify its implementation.

function [x, y] = RandomWalk2D(N)
% Simulate a 2D random walk in an (2N+1)-by-(2N+1) grid.
% N is a positive integer.
% Walk starts from the middle and continues until the an edge, abs(N),
% is reached.
% x and y are row vectors with the property that (x(k),y(k)) is the
% location of the token after k hops, k=1:length(x).

% Initializations...
k=0; xc=0; yc=0;

% In general, (xc,yc) is the location after k hops.
while abs(xc) < N && abs(yc) < N
    % Standing at (xc,yc), randomly select a step
    r= rand(1);
    if r < 0.25
        yc= yc + 1; % north
    elseif r < 0.5
        xc= xc + 1; % east
    elseif r < 0.75
        yc= yc - 1; % south
    else
        xc= xc - 1; % west
    end
    % Record location...
    k= k + 1; x(k)= xc; y(k)= yc;
end

Write your solution in a file named MostVisited.m for submitting to CMS.

Two-dimensional interpolation

First use the full Matlab environment to develop, test, and debug your code; then submit your solutions in Matlab Grader.

When you enlarge an image, you are actually adding data points among the existing data (pixels). How do you get the additional data points? One way is to interpolate from the neighboring points—take the average value. First, consider a simple case of one-dimensional interpolation: we add a data point between neighboring pairs of existing data points by taking the simple average. For example,

2.0 1.0 1.0 2.0 becomes 2.0 1.5 1.0 1.0 1.0 1.5 2.0.

In 2-d interpolation, work with one dimension at a time. For example, given a matrix

2.0  1.0  1.0  2.0
6.0  5.0  4.0  3.0
5.0  5.0  5.0  4.0

First we can add a column between two neighboring columns, so the matrix becomes 3×7:

2.0  1.5  1.0  1.0  1.0  1.5  2.0
6.0  5.5  5.0  4.5  4.0  3.5  3.0
5.0  5.0  5.0  5.0  5.0  4.5  4.0

Then add a row between neighboring rows, so the final matrix will be 5×7:

2.0  1.5  1.0  1.0  1.0  1.5  2.0
4.0  3.5  3.0  2.8  2.5  2.5  2.5
6.0  5.5  5.0  4.5  4.0  3.5  3.0
5.5  5.2  5.0  4.8  4.5  4.0  3.5
5.0  5.0  5.0  5.0  5.0  4.5  4.0

Write two functions for doing 2-d interpolation as discussed above: (a) interpolate2d_nv() uses non-vectorized code; (b) interpolate2d_v() uses vectorized code (work with whole columns one at a time; then whole rows). Do not use built-in functions mean(), sum(), and linspace().

function newM = interpolate2d_nv(M)
% Perform 2-d interpolation on the real-valued data in nr-by-nc matrix M
% where nr>1 and nc>1.
% The interpolated data are added between existing data points so newM is
% (2*nr-1)-by-(2*nc-1). Use the simple average as the interpolated value.
% Do NOT use built-in functions mean, sum, and linspace.
% NON-VECTORIZED implementation.

The vectorized version has the name interpolate2d_v() but the same specification as above other than using vectorized code. In addition to submitting your code on Matlab Grader, ask a member of the course staff to look over your vectorized solution to ensure that you are using vectorized code effectively.