## 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.