Pre-class Assignment: Project Brainstorming & Graph Theory and Cell Towers

Pre-class Assignment: Project Brainstorming & Graph Theory and Cell Towers#

Day 11#

CMSE 202#

In this pre-class assignment you will work to develop a program to generate a graph from a set of points on an XY-plane using the nearest neighbor graphing algorithm. This will set the stage for work that we will do in-class where you will work with your group to solve the problem of assigning cell phone tower frequencies and visualizing them as a graph. You’ll being using networkx to create a Graph() object that you can manipulate to accomplish this task.

Before you get to that part though, you’re going to spend a little time brainstorming possible project ideas.

✅ Put your name here
#

Goals for today’s pre-class assignment#

Project brainstorming
Create a function for finding the nearest neighbor for a given node in a graph.
Make a simple Graph Theory graph using matplotlib
Experiment with the networkx module

Assignment instructions#

This assignment is due by 11:59 p.m. the day before class and should be uploaded into the appropriate “Pre-class assignments” dropbox folder in the Desire2Learn website.

Notes about the assignment: The most important pieces of the second part of this assignment (the graph theory component) are Steps 1 and 2. Step 3 might be a bit challenging because you have to figure out the right syntax to get the NetworkX module to work. Feel free to discuss issues you run into with others on Slack. It’s OK if you can’t get Part 3 figured out before class as long as you’ve tried it. Make sure you complete the final part of the assignment where you’re asked to come up with an outline for how you would solve the cell phone tower problem.

1. Project Brainstorming#

We would like you to start thinking about your semester project. Ideally, your project will incorporate the concepts that you have been learning and will eventually learn in the course.

Project Details#

You can find details about what is expected of you for the semester projects here.

Coming up with possible project ideas#

Right now the goal is to just come up with project ideas that sound interesting to you! Later, we’ll work together to shape them into concepts that fit well within the bounds of the course!

You may also find it useful to consider the following examples from previous semesters:

Example 1: Agent based spread of disease#

This group developed an agent based model to study the spread of a disease. The model consisted of people that lived, worked and went to school. The interaction between the agents determined the likelihood of the spread of the virus.

name-019

Example 2: Planetary Habitable_zone#

This project developed an API (advanced programming interface) to existing online databases of exoplanets (planets outside of our solar system). The user could query the database and the program would generate an idealized picture of the solar system and show if the planet is inside the “goldilock zone.” This is the zone where a planet is likely to sustain liquid water.

Example 3: Star Spectral Analysis#

This project developed an algorithm to automatically categorize stars based on their visible spectral signatures. This categorization process is often difficult and the students wanted to see if a model could be generated using a learning algorithm.

Example 4: Image Classification of Filamentous Fungi#

This project involved the creation of a image classifier using machine learning to classify images of fungi to the correct phylum based on microscope images. It was intended to improve the efficiency of identifying unknown fungi isolated from soil. Currently there are 248 images in the database.

Example 5: Prediction of NFL draft first pick#

This project involved the creation of three model in order to predict who will be picked first in the NFL draft. The students used an SVM, Perceptron, and Logistic regression to predict the first picks.

And many more!#

Other past projects have used a variety of models and data analysis techniques to look at things like:

What factors influence how often people take their dog to the dog park?
What’s the best way to build your stock portfolio to maximize performance?
How can rumors, memes, and reddit influence stock performance?
How has basketball as a sport evolved as a function of time?
Is it possible to predict which teams will will the NHL Stanley Cup?
How do various hormones influence brain chemistry?
Which blackjack betting strategy leads to the most wins?
How do you build an accurate orbital model of the solar system? Other planetary systems?
How does currently available data help us understand the causes and impacts of climate change?
Is it possible to automatically detect shipping boats in satellite images?
How has the rise and fall of COVID cases effected the stock market?
How can network graphs be used to find the shortest past through a city?
How accurately can a neural network perform image recognition?
Can an agent-based model accurately model local animal populations?

✅ Do This: Now that you’ve had a chance to think about some examples of past project, brainstorm ideas you have for projects. These can be rough, general ideas.

✎ Do This - Erase the contents of this cell and replace it with your ideas here. (double-click on this text to edit this cell, and hit shift+enter to save the text)

Once you’ve come up with some ideas for project, fill out the following survey so that your ideas can be compiled into list of possible ideas for the entire class. The combined list will be used to seed ideas that will eventually lead to semester projects!

from IPython.display import HTML
HTML(
"""
<iframe 
	src="https://forms.office.com/Pages/ResponsePage.aspx?id=MHEXIi9k2UGSEXQjetVofbihPqVa-WtNjOGYhCwpOgRUMlFNOEoyV0NUU0s1NzAwNjZXMFkzUVlZSi4u"
	width="900px" 
	height="600px" 
	frameborder="0" 
	marginheight="0" 
	marginwidth="0">
	Loading...
</iframe>
"""
)

2. Application of Graph Theory#

Defining the problem#

The signals from different cellphone towers that are close together can interfere.

From: http://www.onlivespot.com/2011/08/dido-wireless-technology-explained.html

In order to avoid this overlap cell phone companies use different frequency ranges in the Electromagnetic spectrum. Two towers that are close together but have differences in frequencies (shown as colors, red/green/black in the following figure) do not cause nearly as much interference.

From: http://www.onlivespot.com/2011/08/dido-wireless-technology-explained.html

However, cellphone towers are never distributed in such an even pattern. Consider the following map which shows the location of cell towers around Michigan State. (Note: this map may have changed since the time it was first created.)

From: http://www.antennasearch.com/

Another problem is that cellphone companies have to pay for each frequency range they use. So they would like to minimize the number of frequencies that they need to purchase while also minimizing the interference between the cell towers.

Between this pre-class assignment and the assignment you’ll do in class, we’ll try to solve this cell phone tower problem using Graph Theory!

Step 1: Generate random cell towers.#

To start out, we’re going to keep things simple and use artificial data to create our cell phone tower network. Specifically, we’ll just populate a network of towers randomly.

✅ Do This: Write a function to randomly create a 2D numpy array with \(N\) rows representing cell towers and 2 columns representing the \(x\) (longitude) and \(y\) (latitude) positions of the cell towers on a map. You may assume that the map is a 2D plane and not a sphere. You can also assume that the “latitude” and “longitude” values are all in the range of 0 to 1.

# Put your code here.

✅ Do This: Generate \(N=50\) towers using your above function and plot the results as a scatter plot. It should look something like this (though your points will be in different positions):

# Put your code here.

Step 2: Nearest Neighbor Graph#

Next, we’re going to write a function that returns an adjacency list (implemented as a dictionary of lists) from this set of points using the Nearest Neighbor Graph algorithm. More information about the algorithm can be found here:

https://en.wikipedia.org/wiki/Nearest_neighbor_graph

Basically, the algorithm should loop though all of the points and find the nearest neighbor to each point. To do this, you can use the distance function that is provided below, or you can take your own approach.

Again, for each point, we’re going to check the distance to all other points and find the one that is the closest.

In order to aid you in this process, we’ve provided a function called distance() in the cell below that will calculate the distance between two points. You can use this function to tackle this or you can write your own code for calcuating the distance.

import math
# Function for computing the distance between two points
def distance(p1,p2):
    '''Returns the distance betwen two numpy points'''
    return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)

✅ 2.1 Do This: To get things started, first write a piece of code that takes the first data point in the array from Step 1 and uses the distance function to find the point closest to it (smallest distance). Make sure you keep track of the index of the closest point!

Note: When writing this bit of code, you may find it useful to create a temporary number as a starting point that is very large, one good “number” to use is np.inf. Any other number you calculate should be smaller than “infinity”.

#Write your code here

✅ 2.2 Do This: Now extend your code so that it runs over all data points (not just the first) and finds the nearest neighbor for each point. Make sure to store the nearest neighbor for each point in either a list or a dictionary. Make sure to turn this code into a proper function that takes the full list of points as an input and returns the nearest neighbor for every point.

Note: this isn’t a trivial function, so don’t worry if you can’t quite get it figured out. Do your best to work through the logic and implement a solution. If you get stuck, try to make a note of where you got stuck and include this in your follow-up survey.

#Write your code here

✅ 2.3 Do This: Run your nearest neighbor graphing function on the points you generated in step 1. Generate a plot of the points and include the edges of the graph. Your plot should look something like the following:

#Write your code here

Preparing for the in-class assignment#

Finally, think about how you would solve the cell phone tower problem discussed in the beginning of the assignment. Outline a program to do the following:

Generate a list of x-y points from the longitude and latitude given by a list of cell towers.
Run the Nearest Neighbor graph algorithm to generate a graph.
Plot the resulting map

You can outline the program in the cell below using “stub” functions where you define the functions you think you’ll need, what the inputs will be for the functions, and some comments for what the functions will do. If you end the function with pass, Python will be able to successfully “run” your code. An example of what is meant by as stub function is included below. This is just an outline to guide your thinking when you get to class, it doesn’t have to be perfect!

# Example "stub" function
def stubby(param1, param2, param3):
    '''
    This function takes input parameters and
    uses them to compute things and make plots.
    '''
    pass

#
# Using stub functions, put your outline for your program below this comment block.
# Make sure to include comments about what the inputs are and what the functions need to do.
#

Follow-up Questions#

Copy and paste the following questions into the appropriate box in the assignment survey include below and answer them there. (Note: You’ll have to fill out the assignment number and go to the “NEXT” section of the survey to paste in these questions.)

Do you have any questions about the semester projects at this time? If so, what are they?

Assignment Wrap-up#

Please fill out the form that appears when you run the code below. You must completely fill this out in order to receive credit for the assignment!

from IPython.display import HTML
HTML(
"""
<iframe 
	src="https://cmse.msu.edu/cmse202-pc-survey" 
	width="800px" 
	height="600px" 
	frameborder="0" 
	marginheight="0" 
	marginwidth="0">
	Loading...
</iframe>
"""
)

Congratulations, you’re done with your pre-class assignment!#

Now, you just need to submit this assignment by uploading it to the course Desire2Learn web page for this assignment’s submission folder (Don’t forget to add your names in the first cell).