CMSC 655/455 Final Exam 2011
Name_____________________________________________
Do EXACTLY ONE of the problems below--------------------
--------------------------------------------------------
--------------------------------------------------------
parallel and distributed computing --------------------------------
1. a) Draw a DAG for the computation
x1*x2 + x2*x3 + x3*x4 + x4*x5 + x3*x5
b) Suppose you have two processors P_1 and P_2 (underscore
denotes subscript). Give a schedule for the computation of
part a.
c) Neglecting message delay how many time units are needed
for completion of the computation? (with two processors)
d) How many time units would be needed with unlimited
resources (as many processors as you need)?
. Analyze the following parallel algorithm for the addition
of n numbers (you may assume n is a power of 2).
e. the n numbers of divided into sqrt(n) groups, each
of size sqrt(n) elements. (sqrt is 'square root').
The elements in each group are added using the first
addition algorithm discussed in class (tree algorithm)
. The results of
the first additions are then added together using, once
again, the first algorithm we discussed in class.
You may assume you have n/2 processors.
f)Indicate how many time units are needed to complete the
computation.
For a system with p processors the 'speedup' for a given
computational problem is defined as
S_p(n) = T^*(n)/T_p(n)
where n is the size of the input, ^ represents 'superscript'
_ represents 'subscript' and T^*(n) is the time required
by the best single processor algorithm/
the 'efficiency' is defined as
E_p(n) = S_p(n)/p
j) compute the speedup for the algorithm given above
iii) compute the efficientcy for the algorithm given above
---------------------------------------------------------------------------
----------------------------------------------------------------------------
Optimization
2. a) In this problem you are to find everything you can about the
local extrema (max and min) of the function F below. F is
implicitly defined by the matlab 'peaks' command. You should
be able to do this by plotting the function and using matlab
programs available to you.
[X,Y,Z] = peaks(30)
on the domain -4 ,= x <= 4, -3 <= y <= 3
for this function do all of the following steps:
i) Plot the function as a surface in three dimensional space.
ii) Plot the contours of this function in its specified domain.
If possible see if you can make the contours labelled.
-------------------------------------------------------------------------------
-------------------------------------------------------------------------------
Working with Images
3. -------------------
Note -- www.mathworks.com/products/image/
location of Matlab Image Processing Toolbox 6.2
jaconde.jpg
" www.cs.umbc.edu/~stephens/NUM/jaconde.jpg "
a) download the file jaconde.jpg
from our class website at the url above to your matlab directory.
Click on the relevant link and then right click the mouse
over the image to download it.
..
b) use imread to read it into Matlab as an image. Call it 'mona'.
Don't forget to use single quotes and a semicolon..
mona = imread(' ');
c) use size to to determine its dimensions. What are they?
What is the meaning of these dimensions?
d) write the file back to your workspace as a 'png' file.
(pronounced 'ping').
What exactly is a png format? Give a lucid explanation.
e) How many bits are devoted to each pixel in the image
joconde.jpg? (mona)
Are they representational of an integer or real value?
f) Let's just look at a portion of the image. Use the following
apart = mona(50:350, 30:190,:)
display apart (use imshow(apart))and tell me what you see?
Now use image(apart). What's the difference?.
g) Use 'help imcrop' and figure out how to create an image using
the mouse that just crops the nose. Call it 'nose'.Now put the
title 'nose' on the figure. Save it as a jpg file and .
email me the file 'nose.jpg'.***
h) Use matlab to pull out the red part of the image nose.
(call it red) Send me
that image by email ***. Use imshow(red) to make sure that you
have
something. What do you see?
i) reconstruct a part of original image by using cat....use
something similar to
red = mona(:,:,1);
green = mona(:,:,2);
c2 = cat(2,red,green);
what happens when you display c2 =cat(3,red,green,blue); and
c2 = cat(3,green,blue,red);?
where blue = mona(:,:,3)
describe the result..