Description
1. Given the friendship graph below, calculate and plot the degree distribuFon of the graph.
Be sure to label the plot axes.
2. Draw the graph specified in the adjacency matrix below. Is this graph connected? If yes, is it
weakly connected or strongly connected?
⎣
⎢
⎢
⎢
⎢
⎡
0 4 0 0 0 0
0 0 2 0 0 0
0 0 0 0 0 2
7 0 3 0 0 0
0 0 0 2 0 0
0 0 0 0 1 0⎦
⎥
⎥
⎥
⎥
⎤
3. Use Dijkstra’s or Prim’s Algorithm to create a shortest path table for the friend graph from
problem 1. What is the diameter of this graph? Show a minimum spanning tree of this
graph as an adjacency matrix.
4. Given the following flow network from v0 (source) to v7 (sink), use the Ford-Fulkerson
algorithm to determine the maximum flow. Provide the resulFng flow, and draw and label
the flow network and residual network.
Edge list:
{(v0,v1,1),(v0,v2,3),(v0,v3,3),(v1,v6,4),(v2,v1,2),(v2,v5,1),(v3,v2,3),(v3,v4,2),(v4,v7,4),
(v5,v1,5),(v5,v4,3),(v5,v7,3),(v6,v2,3),(v6,v5,2),(v6,v7,3)}
5. For the friendship graph in problem 1, calculate the degree centrality, betweenness
centrality and closeness centrality for each node. Provide a table showing the rank of each
node for each measure.
6. For the friendship graph in problem 1, what is the clustering coefficient?
7. For the friendship graph in problem 1, assume that Cindy is a foe of Nicholas and Priyanka,
Tushar is a foe of Wusheng and Komal and all the other edges in the graph represent
friendship. According to social balance theory, is this new friend/foe graph balanced?
8. Calculate PageRank values for the graph below when
• a=1, b=0
• a=b=0.3
• a=0.85, b=1
• a=0, b=1
Discuss the effects of different values of a and b for this parFcular problem.
9. You have been tasked to design a classifier that decides whether students will be admiied
to a CS graduate program. ApplicaFons to the program are received from students all
around the world. ApplicaFons contain student name, address, mobile phone number, final
grade point average in undergraduate program and transcript. Describe what informaFon
from the applicaFon you would use as input to your classifier. For each piece of
informaFon, what (if anything) would need to be done to clean or transform the informaFon
into input data.
For each of the transformed data input, idenFfy the type (nominal, ordinal,
interval or raFo). Give at least 3 other pieces of informaFon that would be helpful and
describe why you think they would help.
10. You are given the following set of data
Name City Likes
Beyoncé
In a
relaFonship
Age Number of
concerts
per year
Bought
Fcket to
see Taylor
Swi@
Kate Chicago Yes No 23 8 Yes
Joe New York No No 36 4 Yes
Mena New York Yes Yes 43 20 No
Pat Chicago No Yes 19 2 No
Tim Chicago Yes No 20 14 Yes
Tina Chicago Yes Yes 54 7 Yes
Using entropy as a measure of purity, design a decision tree to predict whether someone
bought a Fcket to see Taylor Swi@ or not. Show how each decision node was selected.