Review questions
-------------------------------------------
1. TopHalf
function C = topHalf(A)
% Refer to Lecture 20.
% Suppose A is a length-50 structure array; each struct has two
% fields: name and pop.
% Assume A(k).name is a string that names a state and A(k).pop
% is an integer whose value is the states population.
% Assume that the states are ordered alphabetically.
% C is a length-25 cell array of strings that names all the
% states whose populations are above the median state population.
% The states should be ordered alphabetically in C.
2. BigTriplets
function N = BigTriplets(A)
% Refer to Lecture 20.
% Suppose A is a length-50 structure array; each struct has two
% fields: name and pop.
% Assume A(k).name is a string that names a state and A(k).pop
% is an integer whose value is the states population.
% We say that three different states form a "big triplet" if
% the sum of their populations is greater than 15 million.
% N is the number of big triplets.
3. Point struct and sorting
% See Lectures 20 and 26.
% Given a structure array Pts where each structure has two fields, x and y,
% sort Pts so that the structures are in the order of
% increasing distance from (0,0).
% Write two different scripts to solve this problem:
% (a) Make effective use of built-in function sort.
% (b) Use the INSERTION SORT algorithm; do not use built-in function sort.
4. (Lecture 28)
Consider the following function:
function y = mergeSort(x)
% x is a column n-vector.
% y is a column n-vector consisting of the values in x sorted
% from smallest to largest.
n = length(x);
if n==1
y = x;
else
m = floor(n/2);
% Sort the first half..
yL = mergeSort(x(1:m));
% Sort the second half...
yR = mergeSort(x(m+1:n));
% merge...
disp(’Call merge’)
y = merge(yL,yR);
end
How many lines of output are produced by the call
y = mergeSort(rand(7,1))?
5. (Lecture 26)
Consider the function
function MeshTriangle(x,y,L)
% x and y are 3-vectors. L is a nonnegative integer.
% Adds to the current figure window a level-L partitioning of the
% triangle whose vertices are specified by the 3-vectors x and y.
% Assumes that hold is on.
if L==0
% No subdivision required...
fill(x,y,'y','linewidth',1.5)
else
% A subdivision is called for...
% Determine the side midpoints (a(1),b(1)), (a(2),b(2)), and (a(3),b(3))
a = [(x(1)+x(2))/2 (x(2)+x(3))/2 (x(3)+x(1))/2];
b = [(y(1)+y(2))/2 (y(2)+y(3))/2 (y(3)+y(1))/2];
% Color the interior triangle magenta...
fill(a,b,'m','linewidth',1.5)
% Apply the process to the three "outer" triangles...
MeshTriangle([x(1) a(1) a(3)],[y(1) b(1) b(3)],L-1)
MeshTriangle([x(2) a(2) a(1)],[y(2) b(2) b(1)],L-1)
MeshTriangle([x(3) a(3) a(2)],[y(3) b(3) b(2)],L-1)
end
Assume that the length-3 vectors x and y define an equilateral triangle
and that MeshTriangle(x,y,2) is executed. What fraction of the original
triangle is displayed yellow?
6. (Lab 15)
Suppose z = MyF(x) is a function that accepts a real value x and
returns a real value y. Assume that MyF is very expensive to evaluate.
Write a script that sets up an n-by-n array Z with the property that
Z(i,j) is assigned the value of MyF(1+abs(i-j)). Assume that n is
initialized.
7. (Lectures 27 and 28)
Assume that insertSort(x) is faster than mergeSort(x) if the length of
the input vector is less than 500. How would you modify the mergeSort
function to make it more efficient?
8. (Matrix)
% Let A be a connectivity matrix, i.e.,
% if A(i,j) is one, then there is a link on webpage j
% to webpage i. Write a fragment that prints "yes" if it is
% possible to go from web page #100 to webpage #200 in one or two clicks.
% Assume that the number of webpages is >=200.
% Thus, if A(101,100) = 1 and A(200,101) = 1 then "yes".
9. (OOP)
Refer to class Interval from Lecture 24. Implement the following function:
function idxs = greatestOverlap(iArray)
% Find the biggest pairwise overlap between Intervals in iArray.
% iArray is an array of Interval references. iArray has a length greater than 1.
% idxs is a vector of length 2 storing the indices of the two Intervals in
% iArray that overlap the most. If there is not a pair of overlapping
% Intervals in iArray, idxs is the empty vector.
% Write efficient code: avoid unnecessary iteration.
10. (OOP)
Implement the following class as specified:
classdef LengthUnit < handle
% A LengthUnit represents a length (distance) in imperial units: feet and
% inches. The values are non-negative and inches must be less than 12.
properties
feet % a non-negative integer value
inches % a non-negative value
end
methods
function L = LengthUnit(ft, in)
% Constructor: Create a LengthUnit object with ft feet and in inches.
% If one or both parameters are negative, halt the program and
% display an error message.
%--Write your code here
end
function ft = inFeet(self)
% self references a LengthUnit. ft is self represented in feet.
%--Write your code here
end
function L = add(self, other)
% self and other reference LengthUnits. L references a new
% LengthUnit that is the sum of self and other.
%--Write your code here
end
function yesno = isLongerThan(self, other)
% self and other reference LengthUnits. yesno is true (1) if
% self is longer than other; otherwise yesno is false (0).
% For full credit, make effective use of method inFeet.
%--Write your code here
end
end %methods
end %classdef
11. (OOP)
Write a script that
(a) generates 10 values, each uniformly random in (0,50). Let these
random values be lengths in inches and use an array of LengthUnit objects
to store these lengths.
(b) determines which LengthUnits are shorter than or equal in length to
the first LengthUnit in the array; display their indices and their
lengths in feet. Make efficient use of available methods in class
LengthUnit.
12. Questions from "Insight":
P10.1.5, P10.1.7
P10.2.2, P10.2.7, P10.2.8, P10.2.10
M10.3.1, P10.3.5
P14.1.2, P14.1.3
Errata: P14.1.3 part (b) should read "... then the reverse of s
is the concatenation of the reverse of s(2:n) and s(1) in
that order.'' The subvector was incorrectly specified as s(1:n-1).
Please see the Insight Errata link for the full errata list.