there are no outbound links

8.6. EXERCISES 9
the sum is zero, meaning there are no outbound links, then it assigns each entry
in the column to be the same and add to 1, which pretends that the page is
linked to every other page equally.
Finally we assign the matrix 0.15/pagecount*part1 + 0.85*part2 to return.
8.6 Exercises
Exercise 8.1. Consider this mini-internet:
P1 P2
(a) Try to rank the pages in order of importance without doing any calculation.
(b) Find the pagerank of each of the pages.
(c) If there are any disparities between your answer to (a) and (b) explain (if
you can) what the cause of this disparity might be.
Exercise 8.2. Consider this mini-internet:
P1
P2
P3
P4
P5
P6
(a) Try to rank the pages in order of importance without doing any calculation.
(b) Find the pagerank of each of the pages.
(c) If there are any disparities between your answer to (a) and (b) explain (if
you can) what the cause of this disparity might be.
Exercise 8.3. Suppose that the rule that there is a 15% probability that RW
jumps to a random page were removed, and instead the full 100% (instead of
85%) from each node were distributed across all outbound links. If there are
no outbound links then there is still a 100% probability that RW jumps to a
random page. This could lead to the possiblility that T is not regular.
(a) Give an example of an internet with a non-regular T such that there is no
x¯∗ such that T kx¯0 converges to ¯ x∗ for all ¯ x0.
10 CHAPTER 8. GOOGLE PAGERANK
(b) Give an example of an internet with a non-regular T such that there is some
x¯∗ such that T kx¯0 converges to ¯ x∗ for all ¯ x0 but that this causes serious
problems with the ranking of the pages. Hint: Can you design an internet
where some of the pages will end up with a pagerank of zero?
Exercise 8.4. The Google Pagerank algorithm works even if the internet is
disconnected. Consider this example:
P1
P2
P3
P4
P5
P6
Find the pagerank of each of the pages.
Exercise 8.5. Given the transition matrix T we generally find the pagerank
vector by solving the eigenvector equation (A – I)¯ x = ¯ 0, meaning we find the
eigenvector corresponding to the eigenvalue λ = 1. However it’s also possible
simply to pick an arbitrary ¯ x0 and then find T kx¯0 for successive values of k
until successive entries of T kx¯0 all differ by a predetermined number. Starting
with ¯ x0 = [1, 0, 0, 0, 0, 0]T and using the T from the previous problem, find the
smallest k so that all entries in T kx¯0 and T k-1x¯0 are equal up to and including
the fourth decimal place.
Exercise 8.6. In an internet with n pages all of which link to one another it
makes sense that all of the pages have the same pagerank. Show that this is the
case – find the matrix T and show that the vector with all entries equal (and
adding to 1) is an eigenvector corresponding to eigenvalue λ = 1.
Exercise 8.7. A valid question is whether the 85/15 split has an impact not
just on the pagerank but on the order of the pages in terms of ranking. For
example if we used 60/40 instead would a higher ranked page using 85/15 still
be higher ranked using 60/40.
(a) Justify informally why it seems reasonable that the order of the pages in
terms of ranking would not be affected.
(b) Test this assumption on the following internet by finding the pageranks
using both 85/15 and 60/40 splits.
8.6. EXERCISES 11
P1 P2
P3
(c) The above internet can also be analyzed with a 1/0 split. Find the pageranks
using this split.
Exercise 8.8. Find the pagerank of the pages in the following internet. You
will definitely want to use technology for this!
P1
P3 P2
P4
P5
P6
P7 P8
P9
P10
Exercise 8.9. Explain why having outbound links on your webpage will not
affect your Google Pagerank.
Exercise 8.10. Write down the transition matrix for an internet with n pages
for which the only links are from page 1 to page 2, page 2 to page 3, … page
n – 1 to page n.
Exercise 8.11. Why does the Google Pagerank produce more reasonable results than simply assigning a page a ranking in accordance with the number of
pages that link to it?
10 CHAPTER 9. SINGULAR VALUE DECOMPOSITION

-0.2079 0.7246 -0.3584 -0.9171 -0.1139 0.3788 -0.0103 0.6615 0.2666 -0.3400 -0.1560 -0.8106 S =
5.5200 0 0
9.6 Exercises
Exercise 9.1. Find the singular value decomposition of each of the following
matrices. First do this by computing both AAT and AT A, finding the eigenvalue/eigenvector pairs of each, finding the corresponding singular values, and
putting the results together. Then check your answer via technology.
(a) A =
⎡⎢⎢⎣
1.0 2.0 -3.0
0 1.0 1.0
1.0 2.0 5.0
-1.0 0 2.0
⎤⎥⎥⎦
(b) A =
⎡⎣
-1.0 0 2.0 2.0 2.0
0 2.0 3.0 0 1.0
1.0 2.0 -2.0 1.0 2.0
⎤⎦
10.8. EXERCISES 15

0 1 2
>> [U,S,V] = svd(A)
U =
-0.2079 0.7246 -0.3584 -0.9171 -0.1139 0.3788 -0.0103 0.6615 0.2666 -0.3400 -0.1560 -0.8106 S =
5.5200 0 0
0 0 0
V =
-0.5380 0.4090 0.7371
-0.3049 0.7208 -0.6225
-0.7859 -0.5596 -0.2631
>> SP=S;SP(3,3)=0;
>> U*SP*transpose(V)
ans =
1.3743 1.6839 -0.1336
10.8 Exercises
Exercise 10.1. Find the (vector) direction in which the following set of points
have the most variance, then plot the points and the corresponding line.
(1, 2), (4, 3), (-1, -3), (-5, -8)
Exercise 10.2. Find the (vector) direction in which the following set of points
16 CHAPTER 10. MATRIX (DATA) APPROXIMATION
have the most variance, then plot the points and the corresponding line.
(1, -1), (3, -2), (6, -4), (10, -4)
Exercise 10.3. For each of the following matrices find the SVD and identify the
direction in which the column data is most spread out, as well as the variance
and proportion of total variance in that direction.
(a) A =
⎡⎣
5.0 6.0 5.0 5.0 6.0
6.0 5.0 5.0 6.0 5.0
5.0 6.0 5.0 6.0 5.0
⎤⎦
(b) A =
⎡⎢⎢⎢⎢⎣
0 1.0 1.0 2.0 2.0
1.0 2.0 2.0 0 1.0
7.0 8.0 8.0 8.0 9.0
8.0 9.0 9.0 8.0 7.0
7.0 7.0 7.0 9.0 7.0
⎤⎥⎥⎥⎥⎦
(c) A =
⎡⎢⎢⎣
4.0 5.0 0 0 0
5.0 5.0 0 0 0
0 1.0 7.0 8.0 8.0
0 0 8.0 7.0 7.0
⎤⎥⎥⎦
(d) A =
⎡⎢⎢⎣
2.0 3.0 0 0 0 0
0 0 1.0 0 0 0
3.0 3.0 0 0 0 0
0 0 5.0 5.0 5.0 5.0
⎤⎥⎥⎦
Exercise 10.4. Given the matrix
A =
⎡⎢⎢⎣
2.0 3.0 0 0 0 0
0 0 1.0 0 0 0
3.0 3.0 0 0 0 0
0 0 5.0 5.0 5.0 5.0
⎤⎥⎥⎦
(a) Find the singular value decomposition of A.
(b) Find an approximation A′ to A preserving the largest two singular values
only. What proportion of the total variance is preserved?
Exercise 10.5. Given the matrix
A =
⎡⎢⎢⎢⎢⎣
1 2 -1 0 5
0 1 1 -1 6
-1 0 -2 1 4
2 2 1 2 -5
2 1 0 0 -5
⎤⎥⎥⎥⎥⎦
(a) Find the singular value decomposition of A.
10.8. EXERCISES 17
(b) Find an approximation A′ to A preserving the largest three singular values
only. What proportion of the total variance is preserved?
Exercise 10.6. Find an approximation to the following matrix which preserves
at least 95% of the total variance using as few singular values as possible:
A =
⎡⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣
1 0 1 1 0 1 1
0 1 1 0 1 1 0
1 0 0 1 0 0 1
0 0 1 1 1 0 1
0 1 1 0 0 1 0
1 1 0 1 1 1 1
0 1 0 1 0 1 0
1 0 1 1 1 0 1
⎤⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦
Exercise 10.7. Consider the points stored in the columns of this matrix:
⎡⎣
2.0 -0.1 5.9 2.3 2.9 -5.1 1.9 3.6
3.2 4.8 -2.2 5.5 0.9

⎤⎦
These points mostly lie close to a plane through the origin.
(a) Find the equation of this plane by finding the two directions with the most
variance, finding a normal vector for the plane, then finding the equation.
(b) Using this equation predict which z-value would correspond to x = 10 and
y = -3.
Exercise 10.8. Consider the points stored in the columns of this matrix:
⎡⎣
1.9 0.9 2.6 6.1 3.4 -0.5 4.5 6.0
5.3 11.0 3.9 7.0 8.2 9.2 12.0 2.6
-0.5 1.6 -1.6 -13.0 -10.0 3.3 -18.0 -8.8
⎤⎦
These points mostly lie close to a plane but not through the origin.
(a) Find the mean of all the points. This is basically where all the points are
centered.
(b) Center the points around the origin by subtracting this mean from each
point.
(c) Find the two directions with the most variance and use these to find a
normal vector for the plane.
(d) Find the equation of the plane using this normal vector and also the mean.
18 CHAPTER 10. MATRIX (DATA) APPROXIMATION
(e) Using this equation predict x so that (x, 1, -2) is on the plane, predict y so
that (0, y, 10) is on the plane, and predict z so that (3, 4, z) is on the plane.
Exercise 10.9. Suppose n points are placed as columns in a 2 × n matrix. If
A = UΣV T is the SVD and if the points are plotted below, say as much as you
can about the matrices U and Σ
(a) n = 10 points: (b) n = 100 points:
(c) n = 50 points: (d) n = 20 points:
Exercise 10.10. Suppose a 100 × 100 matrix has 100 singular values whose
squares add to 9512 and in decreasing order are 82.2, 27.6, 23.3, 19.1, 16.3, 8.5, 5.3, ….
How many singular values must be preserved in order to keep 90% of the data
variance? How about 80%?
Exercise 10.11. Explain the mathematical process by which you would approximate a 200 × 200 matrix while keeping 99% of the variance.
12 CHAPTER 11. IMAGE COMPRESSION

Okay, so how about calculating the proportion of variance? Well, we can use the
diag command to extract the values out of our Σ and play with the resulting
vector of values. For example here’s the proportion of variance in the first 100
singular values of the original Justin picture from this chapter, loaded earlier:

Notation Note: The reason we use .^ instead of ^ is that diag(S) and hence
svals and svals(1:100) are all vectors which are treated as matrices in Matlab.
Simply doing, for example, svals^2 would attempt in this case to multiply a
200 × 1 matrix by itself, which doesn’t work. What we really want to do is take
each entry in that matrix and square it, and this is what .^2 does. Basically it
applies the ^2 operation element-by-element.
11.6 Exercises
Exercise 11.1. Consider the following image:
(a) Enter this image into a 4×4 matrix A. Assume the shades you see are only
0, 0.5 and 1.
(b) Find the SVD for A.
(c) Simplify the matrix preserving 3, 2 and then 1 singular value. Draw the
best image representation you can of each matrix.
11.6. EXERCISES 13
Exercise 11.2. Consider the following image:
(a) Enter this image into a 5×5 matrix A. Assume the shades you see are only
0, 0.5 and 1.
(b) Find the SVD for A.
(c) Simplify the matrix preserving 4, 3, 2 and then 1 singular value. Draw the
best image representation you can of each matrix.
Exercise 11.3. Find a square image on the internet of reasonable size; 200×200
or thereabouts is good.
(a) Load this into the Matlab matrix A, convert to grayscale if necessary and
scale the values between 0 and 1.
(b) Find the SVD for A.
(c) How many singular values are there?
(d) Simplify the image by preserving only 75% of the singular values. What is
the percentage of data quality preserved? Print the result.
(e) Simplify the image by preserving only 50% of the singular values. What is
the percentage of data quality preserved? Print the result.
(f) Simplify the image by preserving only 25% of the singular values. What is
the percentage of data quality preserved? Print the result.
(g) What is the minimum number of singular values that must be preserved in
order to preserve 99.9% of the data quality? What level of data compression
would this achieve? Simplify the image accordingly and print the result.
Exercise 11.4. Try to find two images, both 200×200, both photographs, one
requiring as few singular values as possible and one requiring as many singular
values as possiboe, both to achieve 99.9% image variance. Identify, if you can,
what about the images leads to this disparity. Lots of darks and lights? Regular
patterns? Anything you can find!
Exercise 11.5. Assume for each of the following that the singular values have
14 CHAPTER 11. IMAGE COMPRESSION
been given for a 10 × 10 image. Determine the minimum number of singular
values in decreasing order that would need to be preserved to keep 99.9% of the
image variance and what the resulting data compression ratio would be.
(a) 80.2608, 63.3520, 20.5871, 8.4696, 2.8841, 1.6763, 0.7962, 0.6926, 0.6553, 0.6520
(b) 138.5481, 49.5181, 16.5869, 4.9396, 3.2379, 1.5248, 1.1992, 1.0277, 1.0208, 0.9786
(c) 446.1649, 163.4218, 43.8892, 13.7979, 4.7417, 1.3437, 1.0500, 0.6422, 0.4532, 0.4484
(d) 209.4851, 28.1916, 22.8720, 11.8304, 6.3254, 2.7847, 1.2043, 0.9255, 0.8765, 0.8722
Exercise 11.6. Suppose we simplify an m × n (not necessarily square) image
using k singular values. What is the resulting data compression ratio? What
criteria on k would make this worth doing?
18 CHAPTER 12. CHARACTER RECOGNITION
The notation here is that : takes all rows and 1:3 takes columns 1 through 3.
So now if we had another unrolled matrix x for a digit we could see how far it
is from the above:
>> norm(x – B*transpose(B)*x)
12.6 Exercises
Exercise 12.1. Suppose your alphabet consists of the two 3 × 3 characters:
and you wish to identify each of the following characters:
Convert these into matrices (white = 1 and black = 0) and unroll into vectors.
Then identify each of the four characters using simple distance checking.
Exercise 12.2. Suppose your alphabet consists of the two 3 × 3 characters:
and you wish to identify each of the following characters:
Convert these into matrices (white = 1 and black = 0) and unroll into vectors.
Then identify each of the four characters by using simple distance checking.
12.6. EXERCISES 19
Exercise 12.3. Suppose your alphabet consists of the two 3×3 characters that
look like a 1 and a 9 respectively:
(a) Design a character that looks like a 1 that will be recognized as a 9 using
simple distance comparison. Show the calculations.
(b) Design a character that looks like a 9 that will be recognized as a 1 using
simple distance comparison. Show the calculations.
Exercise 12.4. Suppose your alphabet consists of the two 3×3 characters that
look like a C and an L respectively:
(a) Design a character that looks like a C that will be recognized as an L using
simple distance comparison. Show the calculations.
(b) Design a character that looks like an L that will be recognized as a C using
simple distance comparison. Show the calculations.
20 CHAPTER 12. CHARACTER RECOGNITION
Exercise 12.5. Suppose you have the following four versions of the letter O:
And you have the following four versions of the letter J:
(a) Assuming values of 1.0 for white, 0.5 for gray and 0.0 for black, create letter
basis matrices for O and for J using the two most important vectors from
each associated U.
(b) Categorize the following two ”unknown” characters by finding the distance
between each character and the letter subspaces you constructed in (a).
(c) For each letter basis matrix take the most important vector, multiply it by
an appropriate scalar so all values lie between 0 and 1 with the largest value
being 1, roll it back up to a matrix and plot. You are welcome to plot it
by hand (reasonable shading) if you’re not familiar enough with the Matlab
commands. Do these look like an O and a J respectively?
Exercise 12.6. Suppose you have the following four versions of the letter C:
And you have the following four versions of the letter L:
12.6. EXERCISES 21
(a) Assuming values of 1.0 for white, 0.5 for gray and 0.0 for black, create letter
basis matrices for C and for L using the two most important vectors from
each associated U.
(b) Categorize the following two ”unknown” characters by finding the distance
between each character and the letter subspaces you constructed in (a).
(c) For each letter basis matrix take the most important vector, multiply it by
an appropriate scalar so all values lie between 0 and 1 with the largest value
being 1, roll it back up to a matrix and plot. You are welcome to plot it
by hand (reasonable shading) if you’re not familiar enough with the Matlab
commands. Do these look like an C and a L respectively?
Exercise 12.7. Suppose that in generating the basis matrix for one letter of
your alphabet you took 256 versions of that letter with resolution 16 × 16 and
just to be precise you took the entire of U as your letter basis matrix. Why
would this be a bad idea?
Hint: Probably all the singular values will be distinct, why would this be a
problem? Even if only most of them were, why would this be a problem?
Exercise 12.8. Suppose instead of using lots of different versions of the same
letter to build a letter basis matrix you accidentally used the same version over
and over.
(a) What would the letter basis matrix look like and why?
(b) If the letter looked like this 3 × 3 letter what would the leftmost vector in
the letter basis matrix be?
Exercise 12.9. Suppose that your alphabet has two letters of size 2×2. When
you build the letter basis matrices for them you find the following:
For the first letter when you do the SVD you find:
22 CHAPTER 12. CHARACTER RECOGNITION
U =
⎡⎢⎢⎣
√2/2 -√2/2 …
√2/2 √2/2 …
0 0 …
0 0 …
⎤⎥⎥⎦
For the second letter when you do the SVD you find:
U =
⎡⎢⎢⎣
√3/3 √2/2 …
0 0 …
√3/3 -√2/2 …
√3/3 0 …
⎤⎥⎥⎦
Identify this letter as either the first letter or second letter:
34 CHAPTER 13. GRAPH THEORY
13.6 Exercises
Exercise 13.1. Consider the following graph:
2 1
3 4
(a) Find the number of walks of length 3 from vertex 1 to vertex 3.
(b) Find the number of walks of length 20 from vertex 2 to vertex 4.
(c) There are no walks of length 3 from vertex 4 to itself. Rather than using
A3, explain intuitively why this is.
Exercise 13.2. Consider the following graph:
1
2
3
4
5
(a) Find the number of walks of length 3 from vertex 1 to vertex 2.
(b) Find the number of walks of length 10 from vertex 2 to vertex 4.
(c) Examine the number of walks of length k from vertex 3 to vertex 5 for
various even k. What do you notice? Give an intutive explanation for this.
(d) Examine the number of walks of length k from vertex 2 to vertex 4 for
various odd k. What do you notice? Give an intutive explanation for this.
Exercise 13.3. A small theorem in the book shows that the number of triangles
in a graph G equals 1 6tr(A3), where A is the adjacency matrix for G. Why does
this not work for squares, etc.? In other words why does the number of squares
not equal some multiple of tr(A4), why does the number of pentagons not equal
some multiple of tr(A5), and so on?
Exercise 13.4. Consider the following graph:
13.6. EXERCISES 35
2 1
3 4
(a) Intuitively how would you partition the graph into two subgraphs in a reasonable manner?
(b) Apply the Fiedler Method to partition the graph.
(c) Do the results match?
Exercise 13.5. Consider the following graph:
1
2
3
4
5
(a) Intuitively how would you partition the graph into two subgraphs in a reasonable manner?
(b) Apply the Fiedler Method to partition the graph.
(c) Do the results match?
Exercise 13.6. Consider the following graph:
1
2 3
4
5
36 CHAPTER 13. GRAPH THEORY
(a) Write down the Laplacian matrix for this graph.
(b) This matrix has eigenvalues 0, 1.3820, 2.3820, 3.6180, 4.6180 with corresponding eigenvectors
⎡⎢⎢⎢⎢⎣
-0.447
-0.447
-0.447
-0.447
-0.447
⎤⎥⎥⎥⎥⎦
,
⎡⎢⎢⎢⎢⎣
-0.195
-0.632
-0.195
0.512
0.512
⎤⎥⎥⎥⎥⎦
,
⎡⎢⎢⎢⎢⎣
0.372
0
-0.372
-0.602
0.602
⎤⎥⎥⎥⎥⎦
,
⎡⎢⎢⎢⎢⎣
0.512
-0.632
0.512
-0.195
-0.195
⎤⎥⎥⎥⎥⎦
,
⎡⎢⎢⎢⎢⎣
0.602
0
-0.602
0.372
-0.372
⎤⎥⎥⎥⎥⎦
Using this, partition the graph with the Fiedler method.
Exercise 13.7. Consider the following graph:
1
2
3
4
5
6
7
8
9
10
11
12
The Fiedler vector is:
[0.37, 0.23, -0.12, -0.34, -0.28, -0.04, -0.03, 0.42, -0.36, -0.34, 0.42, 0.06]T
Use this vector to partition the graph into three components and then use this
to draw a more understandable picture of the graph.
13.6. EXERCISES 37
Exercise 13.8. Without doing any calculation match the following graphs with
their Fiedler Vectors. Explain your decision.
G1 shown here:
2 1
3 4
5 6
G2 shown here:
1 2 3 4 5 6
G3 shown here:
1
2
3
4
5 6
with:
v¯ =
⎡⎢⎢⎢⎢⎢⎢⎣
-0.56
-0.41
-0.15
0.15
0.41
0.56
⎤⎥⎥⎥⎥⎥⎥⎦
and ¯ w =
⎡⎢⎢⎢⎢⎢⎢⎣
0.46
0.46
0.26
-0.26
-0.46
-0.46
⎤⎥⎥⎥⎥⎥⎥⎦
and ¯ x =
⎡⎢⎢⎢⎢⎢⎢⎣
0.32
0.51
0.32
-0.12
-0.51
-0.51
⎤⎥⎥⎥⎥⎥⎥⎦
38 CHAPTER 13. GRAPH THEORY
Exercise 13.9. Consider the following graph:
1
2
3
4
5
6
7
8
(a) Use the Fiedler Method to partition the graph.
(b) Draw and label the separated components neatly and individually and then
indicate with dashed lines the edges that go between them.
(c) From the previous step are there any insights you gain about the structure
of the graph?
Exercise 13.10. Consider the following graph:
1
2
3
4
5
6
7
8
(a) Use the Fiedler Method to partition the graph.
(b) Draw and label the separated components neatly and individually and then
13.6. EXERCISES 39
indicate with dashed lines the edges that go between them.
(c) From the previous step are there any insights you gain about the structure
of the graph?
Exercise 13.11. Consider the following graph:
1
2 3
4
5
(a) Write down the Laplacian Matrix for the graph.
(b) The Fiedler Vectors span a two-dimensional subspace. Analyze all possible
partitions which result. Be methodical.
Exercise 13.12. Consider the following graph:
2 1
3
4 5
6
(a) The Fiedler Value has a two-dimensional corresponding eigenspace. Find a
basis v¯1, v¯2 for the set of all Fiedler Vectors
(b) Any nonzeo linear combination of ¯ v1 and ¯ v2 will give a reasonable partition
using the Fiedler Method. Experiment to see how many different partitions
you can find.
(c) Suppose ¯ v = c1v¯1 + c2v¯2 for constants c1, c2. Assuming neither of the 1-
entry and 4-entry of v are 0 explain why vertices 1 and 4 will be in different
40 CHAPTER 13. GRAPH THEORY
subgraphs. Repeat for the 2-entry and 5-entry and for the 3-entry and
6-entry.
Exercise 13.13. Let Ln be the Laplacian Matrix for the complete graph Kn
(the graph with n vertices with edges between all pairs). By testing various
values of n make an educated guess about the eigenvalues of Ln for any n.
13.6. EXERCISES 41
Exercise 13.14. Consider the following graph:
1
3 2
4
5 6
7
8
9
10
11
(a) Find a Fielder vector.
(b) The values in this Fiedler Vector, when sorted, can be grouped into three
separated subsets. Do so.
(c) Use this grouping to partition the graph into three subgraphs.
(d) Draw and label the separated components neatly and individually and then
indicate with dashed lines the edges that go between them.
(e) From the previous step are there any insights you gain about the structure
of the graph?
Exercise 13.15. Consider the graph with n vertices:
1 2 n
(a) Before doing any calculation what do you think the outcome of the Fiedler
Method might be? You may need cases. Justify informally.
(b) Check your hypothesis with a few values of n.
42 CHAPTER 13. GRAPH THEORY
Exercise 13.16. Consider the following graph:
1
2
4 3
5
6
7
8
9
10 11
12
13
14
(a) Find a Fiedler vector.
(b) Separate the values into three groups.
(c) Use these groups to partition the graph into three subgraphs.
(d) Draw and label the separated components neatly and individually and then
indicate with dashed lines the edges that go between them.
(e) Which vertex seems like the most critical and why?
(f) From the previous step are there any insights you gain about the structure
of the graph?
13.6. EXERCISES 43
Exercise 13.17. Suppose the following graph shows all of the people in a small
part of a social network. An edge connecting two people indicates that they are
friends.
1
2
3
4
5
6 7
8
9
10
11
12
13
(a) Use the Fiedler Method to identify the group which is most strongly connected to Person 10.
(b) Why is this method ineffective in terms of providing a reasonable answer
to (a)? Hint: Is anyone missing from your answer to (a) that is probably
important to Person 10?
Exercise 13.18. Suppose a small LAN (local area network) consists of ten
computers connected as follows:
• C1 is connected to C8, C9, C10
• C2 is connected to C5, C6.
• C3 is connected to C4, C9.
• C4 is connected to C3, C9.
• C5 is connected to C2, C7.
• C6 is connected to C2, C7, C8.
• C7 is connected to C5, C6.
• C8 is connected to C1, C6, C10.
• C9 is connected to C1, C3, C4.
• C10 is connected to C1, C8.
44 CHAPTER 13. GRAPH THEORY
(a) Write down the Laplacian Matrix for this graph. You don’t need to draw
the graph!
(b) Find the Fiedler Vector and re-order the entries in increasing order.
(c) Partition the graph into some obvious number of subgraphs.
(d) Draw each of the subgraphs neatly and then use dashed lines to represent
the edges that go between them.
(e) From the previous step are there any insights you gain about the structure
of the graph?
Exercise 13.19. Suppose a small LAN (local area network) consists of ten
computers connected as follows:
• C1 is connected to C6.
• C2 is connected to C3, C7, C8 and C9.
• C3 is connected to C2, C4 and C7.
• C4 is connected to C3, C5, C6 and C7.
• C5 is connected to C4 and C6.
• C6 is connected to C1, C4 and C5.
• C7 is connected to C2, C3, C4 and C9.
• C8 is connected to C2, C9 and C10.
• C9 is connected to C2, C7 and C8.
• C10 is connected to C8.
(a) If a network technician wishes to divided these into two groups in order
to connect two backup power supplies how should this be done using the
Fiedler Method?
(b) If we define the most important links as those that would be removed using
the Fiedler Method what are the most important links in this network?
13.6. EXERCISES 45
Exercise 13.20. The following is a simplified map of some countries. What
we’d like to do is divide the countries into two subsets in a way that tries to
balance the number of countries in each subset while minimizing the number of
border crossings between subsets.
(a) Create a graph from this map by assigning a vertex for each country and
connecting two vertices by an edge if the two countries share a border.
(b) Use the Fiedler Method to partition the graph.
(c) Explain in terms of the map what the Fiedler Method has attempted to do.
(d) Shade one subset of the countries in accordance with the result.
Exercise 13.21. The following is a simplified map of some countries. What
we’d like to do is divide the countries into two subsets in a way that tries to
balance the number of countries in each subset while minimizing the number of
border crossings between subsets.
(a) Create a graph from this map by assigning a vertex for each country and
connecting two vertices by an edge if the two countries share a border.
(b) Use the Fiedler Method to partition the graph.
46 CHAPTER 13. GRAPH THEORY
(c) Explain in terms of the map what the Fiedler Method has attempted to do.
(d) Shade one subset of the countries in accordance with the result.
Exercise 13.22. A class of ten students needs to be split up. The goal is
to get two groups of size as close as possible while minimizing the number of
friendships that must be broken up. If the friendships are given in the following
table use the Fiedler method to split up the class. How many friendships must
be broken up? Draw the two resulting friend networks and indicate with dotted
lines where the broken friendships are.

Exercise 13.23. Pick an area of the world which is geographically divided into
at least ten areas. These could be countries, states, counties, anything. Use the
Fiedler Method to partition the area. Show the graph, relevant calculations,
and a resulting map with the regions colored in two separate colors.
Exercise 13.24. The Fiedler method attempts to do two things with regards
to the way it partitions the graph. What are those two things?
Exercise 13.25. What is happening when the Fiedler value turns out to have
two or more linearly independent vectors associated to it? Give an example of
a graph for which you believe that this would be the case and provide a basic
and intutive explanation of why you believe this would be the case.
22 CHAPTER 14. CRYPTOGRAPHY

Finally we need to check that the key that this generates matches the key
fragment at the start.
If we take the first nine bits from the key fragment and these nine bits we found
and we use them to generate a key with the same length as the original fragment
we can compare this generated key with the key fragment to see if this actually
works. To be really fancy we can just take the difference between the vectors:

14.9 Exercises
Exercise 14.1. Encrypt the stream 10110100010100101 using the key 10111.
Exercise 14.2. Encrypt the stream 110110100100000101100101 using the key
110101.
Exercise 14.3. Write down the first 30 digits of the key defined by
[1; 1; 0; 0], [1; 0; 0; 1]
Can you see what the key length is?
Exercise 14.4. Write down the first 30 digits of the key defined by
[1; 0; 1; 1], [1; 0; 0; 1]
Can you see what the key length is?
14.9. EXERCISES 23
Exercise 14.5. Use brute force to find the recursion relation for the key fragment 1011100101 and use it to find the period.
Exercise 14.6. Use brute force to find the recursion relation for the key fragment 0011101001 and use it to find the period.
Exercise 14.7. Use brute force to find the recursion relation for the key fragment 010001101000110 and use it to find the period.
Exercise 14.8. Use brute force to find the recursion relation for the key fragment 010110010001111 and use it to find the period.
Exercise 14.9. Use refined brute force (look for a determinant of 1 followed
by at least three determinants of 0) to find the recursion relation for the key
fragment 01010010001011111011 and use it to find the next three bits of the
key.
Exercise 14.10. Use refined brute force (look for a determinant of 1 followed
by at least three determinants of 0) to find the recursion relation for the key
fragment 01111000010111010101 and use it to find the next three bits of the
key.
Exercise 14.11. Use refined brute force (look for a determinant of 1 followed
by at least three determinants of 0) to find the recursion relation for the key
fragment 101011110000010011101101101010 and use it to find the next three
bits of the key.
Exercise 14.12. Use refined brute force (look for a determinant of 1 followed
by at least three determinants of 0) to find the recursion relation for the key
fragment 010010111000100111001111000001 and use it to find the next three
bits of the key.
Exercise 14.13. Suppose you intercept the following ciphertext along with a
fragment of the plaintext:

(a) Obtain as large a key fragment as you can.
(b) Use refined brute force to find the recursion relation for the key.
(c) Continue building the key until you see it repeat. At this point you know
the full key.
(d) Use the key to decrypt the full ciphertext.
24 CHAPTER 14. CRYPTOGRAPHY
(e) If groups of five bits, converted to decimal, indicate letters with 1 = A,
2 = B, etc., what does the message say?
Exercise 14.14. Suppose you intercept the following ciphertext along with a
fragment of the plaintext:

(a) Obtain as large a key fragment as you can.
(b) Use refined brute force to find the recursive relation for the key.
(c) Continue building the key until you see it repeat. At this point you know
the full key.
(d) Use the key to decrypt the full ciphertext.
(e) If groups of five bits, converted to decimal, indicate letters with 1 = A,
2 = B, etc., what does the message say?
Exercise 14.15. This method of producing a key can also be used to produce
pseudorandom numbers. These are numbers that appear random but are not
(generating random numbers and even defining what it means to be random is
a difficult thing).
Create the first ten digits of a pseudorandom string of numbers between 0 and
15 as follows:
(a) Consider the key defined by the vectors [1; 0; 1; 1; 1; 0; 0] and [1; 0; 1; 1; 0; 0; 0].
Write down 40 bits of this key.
(b) Break the key into 4-bit chunks and convert each chunk from binary to
decimal.
Exercise 14.16. Suppose you encounter the pseudorandom number sequence:
9,9,10,0,12,7,15,12,5
Assuming these came from 4-bit chunks of a key generated using recursion, find
the next three digits of the sequence.
Exercise 14.17. Suppose you encounter the pseudorandom number sequence:
12,11,4,8,12,11,13,1,15,13
Assuming these came from 4-bit chunks of a key generated using recursion, find
the next three digits of the sequence.
Exercise 14.18. Suppose when attempting to break a recursively defined key
14.9. EXERCISES 25
(from a key fragment you have) you apply the Theorem and find for m = 1, 2,
… that:
det(Mm) = 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0
at which point you can no longer calculate determinants because you run out
of key fragment.
(a) What is your guess for the length of the recursive relation?
(b) Suppose you solve for the corresponding ci but they don’t actually work
when applied to the key fragment. What does this mean?
Hint: If this is confusing, think about what would happen if you’d only had
enough key fragment to generate determinants 0, 1, 0, 0, 1, 1, 0.
Exercise 14.19. Consider the following (repeating key):
11001011100101110010
(a) What is the key length?
(b) Find the recursion relation.
Note: The recursion relation is short and the systems of equations you need
to solve are easy by hand.
Exercise 14.20. Consider the key recursively defined using the vectors ¯ s =
[1; 0; 1; 1] and ¯ c = [1; 1; 0; 1]. This recursive relation has length 4 but show that
the key it generates can in fact be genereated using a recursive relation of length
2.

The post there are no outbound links appeared first on My Assignment Online.

Expert Help With This Assignment — On Your Terms