[SOLVED] CS Homework 5, part 1

Homework 5, part 1

Math 157: Intro to Mathematical Software
UC San Diego, Winter 2022

Copyright By Assignmentchef assignmentchef

Homework 5 (part 1 of 2): due Thursday, February 17 at 8PM Pacific

Reminders:

While you are free to create additional notebooks in which to do scratch work, please do not copy/paste from any notebooks outside this folder. Evidence to the contrary may trigger an investigation for potential academic integrity violations.

You do not need to do anything to submit your homework. It will be collected automatically at the due time. Once it is graded, it will be returned into the same folder with feedback and a score.

Collaboration and outside research are strongly encouraged, but you must write up answers in your own words.

Collaborators and outside resources

Please list in the following answer box:

all students you worked with on this homework;
all outside resources you consulted, other than ones that appeared in any course materials (including discussion sections and office hours). Be as specific as possible: i.e., dont cite Wikipedia, but rather link to a specific article.

Remember that collaboration is strongly encouraged, but you must write up answers in your own words. Again, do not copy/paste except from other files in this folder.

Answer box:

Each notebook will specify the kernel that should be used. This may vary within a single homework.

In this notebook, all computations should use the SageMath 9.4 kernel. You may freely combine SageMath with other Python packages.

Problem 1: The connectivity threshold for random graphs

Grading criteria: code correctness, plus conceptual correctness and thoroughness in 1d.

For this problem, you may use either NetworkX graphs or SageMath graphs, but be consistent.

1a) (2 points) Define a function that, on input a graph G, returns True if there is a connected component that contains at least $frac{1}{3}$ of the vertices of G and False otherwise.

def is_mostly_connected(G):
l = G.connected_components()
for i in l:
if len(i) >= 1/3 * len(G.vertices()):
return True
return False

1b) (2 points) Define a function that, on input a positive integer n and a float p, choose ten random graphs $G(n,p)$ from the Erds-Rnyi model, and return True if is_mostly_connected returns True on all ten graphs and False otherwise.

def test_connectivity(n, p):
for i in range(1,11):
G[i] = nx.erdos_renyi_graph(n, p)
if is_mostly_connected(G[i]) == True:
return True
return False

1c) (2 points) Define a function that, on input a positive integer n, does the following binary search.

Start with $a=0, b=1$. Then repeat the following 10 times:Set $p = (a+b)/2$.
If test_connectivity(n,p) returns True, then replace $b$ with $p$; otherwise, replace $a$ with $p$.

Return $(a+b)/2$.

a = 0; b = 1
p = (a+b)/2
for i in range(1,11):
if test_connectivity(n, p) == True:
return (a+b)/2

1d) (4 points) The Erds-Rnyi model has a connectivity threshold at $frac{log n}{n}$ (see Wikipedia). Explain briefly why the function f should return a good approximation of this threshold. Then make a plot comparing f with the threshold, using at least 10 data points evenly spaced on a log scale.

Answer box:

## Your code goes here

Problem 2: The world

Grading criteria: conceptual correctness, plus code correctness in 2c.

2a) (3 points) Suppose you had a map of the world in which each countrys territory is connected. Explain how to obtain a planar representation of the corresponding graph (i.e., the one in which each vertex represents a country and each edge represents a land border of positive lengthno corners). By the four color theorem, this implies that such a graph admits a vertex coloring using at most 4 colors.

Hint: first draw this representation on a sphere, then use stereographic projection.

Answer box:
We firstly construct the graph on the sphere by coloring each vertex which represents each country. Then, the unit sphere $S^2$ in dimensional space $R^3$ is the set of points (x,y,z) such that $x^2 + y^2 + z^2 = 1$. Let N = (0,0,1) be the north pole, and let M be the rest of the sphere. Then we can convert those three dimensional coordinates into a 2 dimensional coordinates on the plane by using Cartesian coordinates or spherical coordinates. After that, we can color our vertices on the planar graph following the four color theorem.

2b) (3 points) In real life, countries have disconnected territory (even if you draw in some imaginary bridges across water), which causes the world graph not to be planar. Run the following code and explain its output in terms of the three utilities problem.

world = graphs.WorldMap()
world.is_planar(kuratowski=True)[1].plot()

Answer box:
In this case, the line between Azerbaijan and Turkey, the line between Armenia and Georgia crosses each other.
According to the three utilities problem, the minimum number of line crossing in K3,3 is one, which means it is impossible to have all edges not crossing each other. In this case, we have two lines crossing each other, then the graph plotted is not a planar graph.

2c) (4 points) It turns out that this non-planarity can be fixed by removing one edge, which exists because a certain countrys territory is not connected. Identify this edge and the country in question; include code below that confirms your statement.

Answer box:
In this question, the line could be the one between Armenia and Azerbaijan. Since the territory of Azerbaijan is not connected.

# Code here
G = world.is_planar(kuratowski=True)[1]
G.delete_edge((Armenia, Azerbaijan))

Problem 3: The Traveling Salesperson Problem

Grading criteria: code correctness.

The code cell below reads in data about the location of the capitals of the US states, plus DC and Puerto Rico, into a Python dictionary. The data was obtained from here: https://people.sc.fsu.edu/~jburkardt/datasets/states/states.html . The dictionary capitalDict has

keys: a state abbreviation string (i.e. AL for ALABAMA)
values: a tuple of floats (latitude,longitude) representing the coordinates of the state capital.

with open(state_capitals_ll (2).txt,r) as file:
capitalDict = {line.split()[0]:(float(line.split()[1]),float(line.split()[2])) for line in file}

capitalDict[AL] #Here is an example of how the data is formatted.

(32.361538, -86.279118)

3a) (3 points) Write a function which implements the haversine function in order to compute the distance between two points on earth in terms of their latitudes and longitudes. Namely, the function greatCircleDistance should

Take as input two coordinates coord1 and coord2. Each coordinate will be a tuple coord1 = (lat1,long1) of latitudes and longitudes in degrees.
Convert the coordinates to their corresponding latitude and longitude in radians, to give coord1 = (x_1,y_1), coord2 = (x_2,y_2).
Return the distance in miles between the two points as a float, given by $$
d = 2cdot 3959 cdot arcsinleft(sqrt{sin^2(tfrac{x_2-x_1}{2})+cos(x_1)cos(x_2)sin^2(tfrac{y_2-y_1}{2})}right)
Here 3959 is the radius of the earth in miles.

Hint: some easy traps to fall into are the following.

Forgetting to convert to radians. Use math.radians() for this.
Not checking that your answers make sense. Michigan and Illinois are not far apart!
Leaving your return value as a symbolic expression rather than a float.

import math
def greatCircleDistance(coord1,coord2):
coord1 = (math.radians(coord1[0]),math.radians(coord1[1]))
coord2 = (math.radians(coord2[0]),math.radians(coord2[1]))
d = 2*3959*arcsin(sqrt(sin^2((coord2[0] coord1[0])/2)+cos(coord1[0])*cos(coord2[0])*sin^2((coord2[1] coord1[1])/2)))

print(greatCircleDistance(capitalDict[MI],capitalDict[IL]))#Test your answer by computing this distance; make sure it makes sense!

TypeError Traceback (most recent call last)
in
-> 1 print(greatCircleDistance(capitalDict[MI],capitalDict[IL]))#Test your answer by computing this distance; make sure it makes sense!

in greatCircleDistance(coord1, coord2)
3 coord1 = (math.radians(coord1[Integer(0)]),math.radians(coord1[Integer(1)]))
4 coord2 = (math.radians(coord2[Integer(0)]),math.radians(coord2[Integer(1)]))
-> 5 d = Integer(2)*Integer(3959)*arcsin(sqrt(sin**Integer(2)((coord2[Integer(0)] coord1[Integer(0)])/Integer(2))+cos(coord1[Integer(0)])*cos(coord2[Integer(0)])*sin**Integer(2)((coord2[Integer(1)] coord1[Integer(1)])/Integer(2))))
6 return d

TypeError: sage.rings.integer.Integer object is not callable

3b) (3 points) Create a complete graph $G$ in Sage whose

vertices are labeled by the state abbreviations (the keys of capitalDict);
edges going between State A and State B are weighted by the distance between the capitals of those states (as computed by your function in 3a).

## Your code goes here
G = graphs.CompleteGraph()

3c) (4 points) Using SageMath builtin functions, find the shortest way to:

Start in Sacramento (the capital of California);
Visit the capitals of the following states in some order: Washington (WA), Oregon (OR), Arizona (AZ), (NM), Nevada (NV), Colorado (CO), Utah (UT), Wyoming (WY), Idaho (ID), Montana (MT);
Return to Sacramento.

Hint: Sage calls this problem the travelling salesman problem. You can find details for solving it in the Algorithmically hard stuff section here: https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/generic_graph.html.

## Your code goes here

Problem 4: The Cheeger constant of a graph

Grading criteria: code correctness, plus mathematical correctness in 4a.

Given a graph $G$, the Cheeger constant of $G$ is a measure of the bottlenecks in that graph. The Cheeger constant $h(G)$ satisfies a few rules:

$h(G)$ is a nonnegative number. It is strictly positive if and only if $G$ is connected.
If you fix the number of vertices in a graph and only vary the edges, then: $h(G)$ is large if $G$ is well connected and small if there are areas of poor connection in $G$.

An analogy is to think of cars driving in traffic. For a fixed number of cars, a road system with a high Cheeger constant will have smoother flowing traffic than one with a low Cheeger constant.

The exact formula can be found at https://en.wikipedia.org/wiki/Cheeger_constant_(graph_theory), but you wont need it here because SageMath has a builtin function which computes the Cheeger constant of a graph $G$:

G = graphs.CycleGraph(5)

print(G.cheeger_constant())

4a) (3 points) For the following three graphs on the same number of vertices (12), compute their Cheeger constants using Sage and rank them by their Cheeger constant. Based on my brief discussion above, why does this answer make sense?

G1 = graphs.CompleteGraph(12)

G2 = graphs.BarbellGraph(4,4)

G3 = graphs.Grid2dGraph(4,3)

print(G1.cheeger_constant(),G2.cheeger_constant(),G3.cheeger_constant())

6/11 1/17 3/17

Answer box:
From the computation above, the rank of cheeger constant is G1,G3,G2. As said in the introduction, with same number of vertices, G1 is mostly well connected but G2 is less connected than any other two of them. So the results really makes sense.

4b) (4 points)
The normalized Laplacian of $G$ is defined by
Delta(G) = D^{-1/2}(D-A)D^{-1/2},
where $D$ is a diagonal matrix whose $i$th diagonal entry equals the degree of vertex $i$, and $A$ is the adjacency matrix of $G$. Here $D^{-1/2}$ just means doing the operation $xto x^{-1/2}$ entrywise on the diagonal entries. You can compute the matrix $(D-A)$ directly in Sage using the .kirchhoff_matrix() function, but I think $D^{-1/2}$ will have to be hard coded. Use this to write a function spectralGap which

Takes as input a graph $G$;
Computes the eigenvalues of the Normalized Laplacian matrix $Delta(G)$;
Returns the second smallest eigenvalue of $Delta(G)$.

To check your answer, there are several calls below.

def spectralGap(G):
#Your code here

File , line 2
#Your code here
IndentationError: expected an indented block

G = graphs.CycleGraph(10)
print(spectralGap(G))

G = graphs.CompleteGraph(8)
print(spectralGap(G))

The Cheeger inequality states that
tfrac{lambda}{2}leq h(G)
where $lambda$ is the eigenvalue found in part 4b) and $h(G)$ is the Cheeger constant of $G$. Verify this inequality on the three graphs from 4a) using your function from 4b).

## Your code here

CS: assignmentchef QQ: 1823890830 Email: [email protected]