CS303– Programming Assignment 1

Homework will be due at the BEGINNING of class on the date due. Your answers should be written

legibly if handwritten and your name should be clearly written on your homework assignment. Try to

make your answers as clear and concise as possible; style will count in your overall mark. Be sure to read

and know the collaboration policy in the course syllabus. Be sure to check the back of the page; problems

occasionally show up there too!

Assigments are expected to be turned in electronically in pdf format (by using latex).

An Erdos-Renyi random graph G(n,p) is generated by two parameters

• n: the number of vertices.

• p: a number in [0,1], which is the probability that each of the n(n-1)/2 edges is independently included

in the graph.

• You can check wiki for more details.

Problems

1. Generating a random graph. Write a function to generate a random graph given n and p.

• Input: an integer n > 1 and real number p in [0, 1] Output: an undirected graph G. You can use

whatever format to store the graph (e.g., adjacency list or matrix). Hint: Initiate G to be an

empty graph (no edges). For each i < j, generate a random number q between 0 and 1. If q < p

then add the edge (i, j) to G (if you are using adjacency list then this involves updating the lists

of both i and j). In Python, you can generate a random number in [0,1] using random.random()

after importing random.

2. Computing the size of the largest connected component. Given a graph G and a threshold

t, write a function to test whether G contains a connected component of t vertices or more.

• Input: a graph G and and a number t

• Output: 1 if G contains a connected component of t vertices or more; 0 otherwise.

• Hint: One solution is the following. For each vertex, you can compute the number of vertices in

its connected component by BFS or DFS. Then, the function returns 1 if there exists a vertex

whose connected component has at least t vertices. There are much faster ways to do this using

BFS or DFS.

• Please test your code thoroughly! A lot of students double-count the nodes, ending up with

incorrect component sizes, sometimes even with components larger than the number of nodes

in G, which is impossible. To test this, return a list of all the nodes in a connected component

(not just its size), and then make sure that no node appears in your list twice, and that the

number of nodes in the list equals the size of the component which you computed.

3. Testing your algorithm on randomly generated graphs.

• Let n = 40.

1

• For each c in [0.2, 3.0] with step size 0.2, let p = c/n, generate 500 random graphs G(n, p) using

your function for step 1.

• Use your function for step 2 to calculate the percentage of graphs (out of the 500 graphs with

the same c) whose largest connected component has at least t=30 vertices.

• Output: a graph where the x-axis is c and the y-axis is the percentage. As c increases, more

and more graphs should have large components, since they have more and more edges. Hint:

The total number of graphs you should generate is 500 × 15—there are 15 different c’s and for

each c you should generate 500 graphs. Note that the percentage is calculated for each c.

4. (Optional) Based on your findings, in a random graph of size 40 about how many others

does each node need to have edges to, in order for most of the graph to become one

connected component? Investigate the same question for other values of n: how large

does c needs to be in order for most of the nodes in the graph to become connected

with high probability?

Other hints

• If your computer is produced after 2011 and it is at least as powerful as a regular laptop (meaning

that it is not a netbook, tablet, or smartphone), then part 3 should finish in at most a few minutes.

• To debug your code, try small n first.

• Make sure that some calculations are done as float numbers (e.g., it is safer in Python to use p =

c/float(n)). Be careful about the automatic integer conversion. You don’t have to generate a figure

directly from your code. To receive credit, you just need to show the figure to your TA.

2

Sale!

# CS303– Programming Assignment 1

$30.00

## Reviews

There are no reviews yet.