Homework Assignments
     Due Dates January 12 January 17 January 19 January 21 January 24 January 26 January 28 January 31 February 2 February 4 February 7 February 9 February 14 February 23 February 25 March 1 March 6 March 13 March 15 March 31 April 19 April 24 April 26 May 2
January 12
Respond to email.

January 17
Exercise 1 - Logon to the network, start up Matlab, do some simple calculations in the command window, and print the command window.
Write your name on the printout and turn it in.

January 19
Exercise 2 - Write a program which examines the numbers from 1 to 100.
If a number is divisible by three and by five, then the program should print "orange and white".
If a number is divisible by three and not divisible by five, then the program should print "orange".
If a number is not divisible by three but is divisible by five, then the program should print "white".
If a number is not divisible by three or by five, then the program should simply print the number.

January 21
Exercise 3 - Write a program which prints out all the Fibonacci numbers from 1 to 100.
The first two Fibonacci numbers are 1 and 1.
Each succeeding Fibonacci number is defined as the sum of the two preceding numbers.

January 24
Exercise 4 - Let x = [-1.0 -0.75 -0.5 -0.25 0 0.25 0.5 0.75 1.0] and compute a vector, y, using the formula y = 2*x.^2 - 1.
Plot y as a function of x.
Title the plot with your name.
Label the x axis as 'Independent Variable', and
label the y axis as 'Dependent variable.
You will probably want to check out "help plot", "help title", "help xlabel", and "help ylabel".

January 26
Exercise 5 - Write a program which examines the numbers from 1 to 100.
If a number is divisible by three and by five, then the program should print "Orange and White" on a line by itself.
If a number is divisible by three and not divisible by five, then the program should print "Orange" on the current line followed by a new line.
If a number is not divisible by three but is divisible by five, then the program should print "White" on the current line followed by a new line.
If a number is not divisible by three or by five, then the program should simply print the number. Numbers should be printed on the current line, and they should be separated by a comma and a space from any following numbers or words.
You may want to check out "help fprintf". As a bonus, can you insure that there are no empty lines, and no lines that start or end with a comma and a space.

January 28
Exercise 6 - Write two functions which test for set containment and set equality.
You have received a copy of the following memberOf function
```			function y = memberOf(x, S)
%
%  y = memberOf(x, S)
%
%  This function returns false ( 0 ) if
%  x is not an element in the array S, and
%  it returns true ( 1 ) if it is.

%  Dan Warner  1/26/2000

y = 0;
for u = S
if x == u
y = 1;
break;
end
end
```
which tests whether x is an element in the set S.

Write a function y = subsetOf(S, T) which tests whether the set S is a subset of the set T.
Also write a function y = equalSets(S, T) which tests whether the set S is equal to the set T.
These functions should build on each other. subsetOf should use memberOf and equalSets should use subsetOf. Keep them as simple as possible.

January 31
Exercise 7 - First, based on the discussion in class, fix any mistakes in your subsetOf or equalSets functions. Run the Ex6.m program that was sent if a previous email message. Your results should match the predictions in the comments.

Second, change the memberOf, subsetOf, and equalSets functions to handle sets of rational numbers which are represented by arrays of fractions. Call the new functions ratMemberOf, ratSubsetOf, and ratEqualSets, respectively. In addition to appropriate name changes you will have to adjust one line of code to handle the equivalence test.

Run the test program, Ex7.m, which was sent in a previous email message. Your results should match the predictions in the comments. Turn in printouts of your three functions and a printout of the command window when you run Ex7.

Below, are appropriate function declarations and help comments. Paste them into your routines.

```			function y = ratMemberOf(x, S)
%
%  y = ratMemberOf(x, S)
%
%  This function returns false if the rational
%  number represented by the fraction, x, is an
%  element of the set of rational numbers represented
%  by the array of fractions, S.
%
%  In other words ratMemberOf returns true if the
%  fraction x is equivalent to any of the fractions
%  in the array, S.
%
%   A single fraction, x, is stored as a 2-by-1 array
%   with the numerator stored in x(1) and the
%   denominator stored in x(2).
%
%   An array of n fractions is stored as a 2-by-n array
%   where each column represents a single fracation.
```

```			function y = ratSubsetOf(S, T)
%
%  y = ratSubsetOf(S, T)
%
%  This function returns true if the set of
%  rational numbers represented by S is a subset
%  of the rational numbers represented by T.
%
%  That is, it returns false if there is a
%  fraction in S which is not equivalent to
%  any of the fractions in T.
%
%  Otherwise it returns true.
```

```			function y = ratEqualSets(S, T)
%
%  y = ratEqualSets(S, T)
%
%  This function returns true if the set of
%  the rational numbers represented by S is
%  same as the set of rational numbers
%  represented by T.
```

Here's a copy of the Ex7 test routine.

```			%  Exercise 7.  Tests for function on Rational Sets
%
%  MTHSC 360  1/28/2000

%  Set up some fractions
u = [1; 2]
v = [2; 3]
w = [ 4; 8]
x = [12; 18]
y = [15; 30]
z = [4; 7]

%  Setup three arrays of fractions
F = [u v]
G = [u v w x y z]
H = [v w x y]

%  Test u for membership if F, G, and H
%  Should get true, true, and true.
t1 = ratMemberOf(u,F)
t2 = ratMemberOF(u,G)
t3 = ratMemberOf(u,H)

%  Test z for membership if F, G, and H
%  Should get false, true, and false.
t4 = ratMemberOf(z,F)
t5 = ratMemberOF(z,G)
t6 = ratMemberOf(z,H)

%  Test F, G, and H for all possible
%  subset relationships.
%  Should get true, true, true, false,
%  true, false, true, true, and true.
t7  = ratSubsetOf(F,F)
t8  = ratSubsetOf(F,G)
t9  = ratSubsetOf(F,H)
t10 = ratSubsetOf(G,F)
t11 = ratSubsetOf(G,G)
t12 = ratSubsetOf(G,H)
t13 = ratSubsetOf(H,F)
t14 = ratSubsetOf(H,G)
t15 = ratSubsetOf(H,H)

%  Test whether F is equal to F, G, and H
%  Should get true, false, and true.
t16 = ratEqualSets(F,F)
t17 = ratEqualSets(F,G)
t18 = ratEqualSets(F,H)
```

February 2
Project 1 is due this date.

February 4
Exercise 8 - We will represent a graph by nV, the number of vertices, and E, the edgelist, which will be an array of two rows and as many columns as there are edges.

Write a funtion, y = edgeOf(x,E), which returns true if x is an edge in the edgelist, E, and false otherwise.

Write a second function, y = subgraphOf(nV1, E1, nV2, E2), which returns true if the graph (nV1, E1) is a subgraph of the graph (nV2, E2), and false otherwise. In this exercise we will require that a subgraph must have its vertices labeled the same as those of the super graph.

If you can, make use your memberOf and subsetOf functions.

1. Turn in a printout of your edgeof function.
2. Turn is a printout of your subgraphOf function.
3. Fun Ex8.m (sent as a separate message), and turn in a printout of the command window.
4. Draw a picture by hand of two graphs, one of which is a subgraph of the other but which would not be classified as a subgraph function by your subgraphOf function because of the way the vertices are labeld.

Here's a copy of the Ex8 test routine.

```			%  Exercise 8.  Tests for Graph functions
%
%  MTHSC 360  1/31/2000

%  Set up some edges
u = [1; 3]
v = [3; 5]
w = [5; 1]
x = [2; 4]
y = [4; 6]
z = [6; 2]

%  Setup and display three graphs
nT  = 6;
T  = [u v w]
PlotG(nT,T)
pause

nSD = 6;
SD = [u v w x y z]
PlotG(nSD,SD)
pause

nS5 = 5;
S5 = [1 3; 3 5; 5 2; 2 4; 4 1]'
PlotG(nS5,S5)

%  Test u for membership if T, SD, and S5
%  Should get true, true, and true.
t1 = edgeOf(u,T)
t2 = edgeOf(u,SD)
t3 = edgeOf(u,S5)

%  Test z for membership if T, SD, and S5
%  Should get false, true, and false.
t4 = edgeOf([2;6],T)
t5 = edgeOf([2;6],SD)
t6 = edgeOf([2;6],S5)

%  Test T, SD, and S5 for all possible
%  subgraph relationships.
%  Should get true, true, false, false,
%  true, false, false, false, and true.
t7  = subgraphOf(nT,T, nT,T)
t8  = subgraphOf(nT,T, nSD,SD)
t9  = subgraphOf(nT,T, nS5,S5)
t10 = subgraphOf(nSD,SD, nT,T)
t11 = subgraphOf(nSD,SD, nSD,SD)
t12 = subgraphOf(nSD,SD, nS5,S5)
t13 = subgraphOf(nS5,S5, nT,T)
t14 = subgraphOf(nS5,S5, nSD,SD)
t15 = subgraphOf(nS5,S5, nS5,S5)
```

Here's a copy of PlotG, the routine which plots a graph.

```			function VCoord = PlotG(nV, E)
%
% VC = PlotG(nV, E)
% This function takes nV, the number of vertices of a graph,
% and E, the edgelist of the graph, and plots the graph.
% The vertices are plotted in order with the first vertex at
% (0,3) and the remaining vertices equally spaced in clockwise
% order around the circle of radius 3.  The x and y coordinates
% of the vertices are returned in the result matrix, VCoord.

% Daniel D. Warner  9/20/94 (revised 9/16/99)

phi = 2*pi/nV;
X = zeros(1,nV);
Y = zeros(1,nV);
for j=1:nV,
X(j) = 3*cos(pi/2 - (j-1)*phi);
Y(j) = 3*sin(pi/2 - (j-1)*phi);
end
axis([-6.5 6.5 -3.1 3.2]);
plot(X, Y, 'ob');
hold on;
for edge = E
source = edge(1)
target = edge(2)
plot([X(source) X(target)], [Y(source) Y(target)], 'b');
end;
hold off;
VCoord = [X; Y]';
```

February 7
Exercise 9 - Examine the following three routines: enum3.m, perm3.m, and comb3.m These routines work for selecting 3 items from a list under the constraints of replacement, no replacement, and only subsets. Rewrite the routines so that they will work for 4 items. Name your routines enum4.m, perm4.m, and comb4.m. Set up the following three variables:
x = 'Jonah'
y = [1 2 3 4]
z = [1 2 3 4 5; 5 4 3 2 1]
and run each routine on each variable. Turn in a printout of each of your routines - enum4.m, perm4.m, and comb4.m.
```			function y = enum3(L)
y = 0;
for k1 = L
for k2 = L
for k3 = L
z = [k1 k2 k3]
y = y+1;
end
end
end
```

```			function y = perm3(L)
[m n] = size(L);
used = zeros(1,n);
y = 0;
for k1 = 1:n
used(k1) = 1;
for k2 = 1:n
if (~used(k2))
used(k2) = 1;
for k3 = 1:n
if (~used(k3))
used(k3) = 1;
z = [L(:,k1) L(:,k2) L(:,k3)]
y = y+1;
used(k3) = 0;
end
end
used(k2) = 0;
end
end
used(k1) = 0;
end
```

```			function y = comb3(L)
[m n] = size(L);
y = 0;
for k1 = 1:n-2
for k2 = k1+1:n-1
for k3 = k2+1:n
z = [L(:,k1) L(:,k2) L(:,k3)]
y = y+1;
end
end
end
```

February 9
Exercise 10 - Write a function, subgraph4.m, which, given a grpah (nV, E), plots all the subgraphs with exactly four edges. Since the order in which we plot the edges does not change the graph, the edges in a subgraph will be a subset of the edges in the original graph. To write your subgraph4 routine start with a copy of your comb4 routine and modify it to use plotG(nV,E). Include a pause statement after each plot so that you can print them out.

Run the test program, Ex10.m, which is printed below. Print out the plots for graph and each of its subgraphs. Turn those in along with a printout of your subgraph routine.

```			%  Exercise 10  2/4/2000
%
%  Sets up a graph and then calls subGraph4
%  to find all subgraphs with 4 edges.
nV = 5
E = [1 1 2 2 4; 3 4 4 5 5]
plotG(nV, E);
pause
count = subgraph4(nV, E)
```

February 14
Exercise 11 - Modify your perm4 function from Exercise 9 so that it works for 5 items, and call the new routine perm5. Save this routine. Add your name and the date to the Ex11.m script which was sent in the email and which is also printed below. Run the test program, Ex11.m and print out a copy of Ex11, a copy of perm5, and a copy of the command window.

On a separate piece of paper estimate the time that it would take to generate all the permutations of 16 items. Your calculations should be based on the timing results from Ex11. If you have a statistical bent, you may want to run Ex11 several times and take into account the experimental variation.

```            % Timing Test Program
%
% Date
% Exercise 11

L = [1 2 3 4 5]
% Start the clock
Tstart = clock

count = perm5(L);

% Stop the clock.
Tstop = clock
fprintf('Found %g solutions in %g seconds\n', count, etime(Tstop,Tstart))
```

February 23
Exercise 12 - Write a function, perm.m, which generates all the permuations of length n, from a given list. Do this by modifying the function, enum.m, which you were sent in email and which is also printed below. The function, enum.m, generates all the samples of size n from a given list, where the sampling is done with replacement. The function uses recursion so that it can handle an arbitrary value of n.

Test your program by entering the following two lines into the command window.

perm(3,[],'abcd',0,1)
perm(3,[],[1 2 3 4; 5 6 7 8],0,1)
Turn in a printout of the command window and your function, perm.m
```			function count = enum(n, sample, list, count, printFlag)
%
%  count = enum(n, sample, list, count, printFlag)
%
%  This function calculates all samples (or combinations)
%  of n items from list.
%
%  The total number of samples is returned in count.
%  If printFlag is true then the samples are displayed.
%
%  On the initial call sample should be set to an empty
%  array and count should be set to 0.

%  Daniel D. Warner    Feb 2, 2000.

if n == 0
if printFlag
disp(sample)
end
count = count + 1;
else
[mRows, nCols] = size(list);
for k = 1:nCols
count = enum(n-1, [sample list(:,k)], list, count, printFlag);
end
end
```

February 25
Exercise 13 - Write a function, comb.m, which generates all the subsets of length n, from a given list. Do this by modifying the function, enum.m, which you were sent in email and which is also printed in the previous exercise. The function, enum.m, generates all the samples of size n from a given list, where the sampling is done with replacement. The function uses recursion so that it can handle an arbitrary value of n.

Test your program by entering the following two lines into the command window.

comb(3,[],'abcd',0,1)
comb(3,[],[1 2 3 4; 5 6 7 8],0,1)
Turn in a printout of the command window and your function, comb.m

March 1
Project 2 is due this date.

March 6
Exercise 14 - Write a function, B = attack(B,r,c), which marks off all the squares that are under attack from a queen at row, r, and column, c. You can assume that B is a square matrix, and you may assume that 1 <= r <= n and that 1 <= c <= n. For each entry in B which would correspond to a square under attack, set that value to -1.

Test your program by entering the following three lines into the command window.

B = zeros(7)
B = attack(B, 3, 5)
B = attack(B, 4, 2)
Turn in a printout of the command window and your function, attack.m

March 13
Project 3 is due this date.

March 15
Exercise 15 - Write a function, function EN = EdgeNode(nV, E), which takes a graph, specified by the number of vertices, nV, and the list of edges, E, and builds the Edge-Node matrix, EN. An Edge-Node matrix has as many rows as the graph has edges, and it has as many columns as the graph has vertices. Each row corresponds to an edge. In each row the column corresponding to the first vertex of the corresponding edge is marked with a +1. The column corresponding to the second vertex is marked with a -1. All other entries are 0.

Test your program by entering the following three lines into the command window.

nV = 5
E = [1 1 2 2 3 4; 2 4 3 5 4 5]
EdgeNode(nV, E)
Turn in a printout of the command window and a printout of your function.

March 31
Exercise 16 - Write a program which does the following five things.
1. Calls BuildBox to get the graph and coordinate of a box that is 2 units wide 3 units high and 1 unit deep.
2. Constructs a rotation matrix, R, which rotates objects around the z axis through an angle of -pi/12 radians.
3. Constructs a rotation matrix, S, which rotates objects around the y axix through an angle of -pi/12 radians.
4. Applies R and then S to the box's coordinates, and then plots the rotated box using PerPlot. Print out the plot.
5. Applies S and then R to the box's coordinates, and then plots the rotated box using PerPlot. Print out the plot.
Turn in the two printouts and a listing of the program. Be sure to indicate which printout corresponds to which sequence of rotations.

April 19
Exercise 17 - Write a program which does the following five things.
• First, save the new BuildTower.m and PerPlot.m files. These copies reflect the changes I mentioned in class on Monday.
• Second, save the following code as Ex17.m, and run it. It should draw a picture of a tower rotated about the z axis by -pi/8 radians. When it runs correctly, print a copy of the picture of the tower.
```			%  Exercise 17

%  Your name   4/19/00

%  Build the wireframe object
[nV, E, VC] = BuildTower

%  Set up the axes of the window.
Ax = [-1 1.5 -2 2]

%  Set up the location of the eye and the distance to the window
xe = 4
d  = 2

%  Draw the wireframe object with perspective
PerPlot(VC,E,d,xe,Ax)

%  Set up a rotation of -pi/8 radians about the z axis
theta = -pi/8
Rz = [cos(theta) -sin(theta) 0 0; sin(theta) cos(theta) 0 0; 0 0 1 0; 0 0 0 1]

%  Rotate the wireframe object and display it
PerPlot(Rz*VC,E,2,4,Ax)
```

• Third, write a function [nV, E, VC] = BuildWHATEVER which works like BuildTower but builds a wireframe object of your own design. This object must consist of two separtate wireframe objects that are moved together and concatenated to form a single object.
• Fourth, change the call in Ex17.m from BuildTower to BuildWHATEVER and run Ex17 to display the wireframe object of your design. Depending on the size of your object, you may need to adjust d, xe, and Ax to get a picture that you like. When you get a good picture print it out.
Turn in a printout of your BuildWHATEVER function, and the two pictures.

April 24
Exercise 18 - Write a function,   count = postree(nV,E,pTree,count,printFlag),
which generates all the subsets of the edgelist, E, which could contain a spanning tree - in other words, all the subsets of E of size nV-1. Do this by modifying the comb function from Exercise 13 or you can modify the version I sent you in email.

Test your program by entering the following lines into the command window.

nV = 6
E = [1 1 1 2 4 4 5; 2 3 6 3 5 6 6]

PlotG(nV, E)

postree(nV, E, [], 0, 1)

Turn in a printout of the command window and your function, postree.m You do NOT need to turn in printout of the plots.

April 26
Project 4 is due this date. Be sure to email me copies of your code.

May 2
The final exam will be an interview exam. Bring your portfolio and a copy of Project 5.
Be sure to email me a copy of the codes for Project 5 prior to our scheduled meeting time.