CSCI 204 (Data Structures and Algorithms) Final Project

Project Objectivs & Overview

• Phase 1
• Phase 2
• Final Phase

Project Deliverables

• Phase 1
• Phase 2
• Final Phase

Project Point Breakdown
Project Milestones & Dates

Scruffy the crime dog wants you to take a bite out of crime

Teams of three or four students
Teams will be assigned by Prof. Dancy

Due-Dates:

• (Team info on Classroom): 08-Nov
• Phase 1: 15-Nov (11:55pm)
• Phase 1 presentations on 15-Nov (in class)
• Phase 2: 22-Nov (11:55pm)
• Phase 2 presentations on 22-Nov (in class)
• Final Phase: 10-Dec (11:55pm)
• Final presentations on 09-Dec (in class)

Final Project Overview

Back to shortcuts

Scenario

Scenario

You're group is an elite group of developers that have been contracted by the Chicago Information Sciences Department. You've been asked by the Police Chief to develop a new police patroll dispatch system that his officers can use to fight crime in the most efficient way possible.

The police chief is relying on you to help combat crime

The Chief made this back of the napkin drawing to help you think about what he envisions as the final system (the Decision Engine)

To help with this, he's given you a dataset of previous crimes so that you can decide how you'll handle those new data that you'll be reading in.

Getting Familiar with the dataset

The first step is to explore the dataset a bit. Your dataset is contained in the file called Chicago_Crimes_2018-2019_Train.csv.
As indicated by the name, the values in this file are comma-separated.

• If you don't want to worry about opening the whole file up, the easiest thing would be to write some a portion of the lines, say the first ~1000 to another file, that would be more manageable to open up in most editors (though using something like excel or another spreadsheet program might be the easiest way to take a look if this is your first rodeo in data wranglin'.)
  
  

Using AVL Trees to store your data and keep it in order

You will need to create an AVL tree class that you can use to store data so that you can make decisions on how to prioritize any crime coming in.
For your decision-making, you should store at least 2 AVL Trees:

• The AVL should hold a representation of locations as the key of the payload and some priority ranking as the value payload
  • Note that there may be multiple ways to represent location...it's up to you to pick something that makes sense
• One additional AVL that uses some aspect of those past crime data as a key and matches those keys to some priority ranking (value) to provide alternative priorities (e.g., if you want to use several factors to combine priorities to make a decision)

How should I determine the priority?

This is part of the challenge! How should you determine priority? There might be many ways, but I'll leave it up to you to think about that.

• It's important to remember that you have multiple phases and your idea can evolve as you move between phases (and see what others are doing during their presentations!)
  
  

Creating visualizations of your data

This part of Phase 1 is meant to give you an opportunity to find a visualization package you like and get familiar with it.

• For this Phase, you will build visualizations for your AVL Trees

How do I draw this thing

Great question! There are several options out there for your AVL tree:

• You could use the Bridges API
  • They even have AVL tree examples (don't get too excited, it's really just a BST ;-))\
• You could use a combination of Matplotlib and Networkx. This looks like it might be one of the more straight-forward examples of how to use these two to create a top-down tree visualization.
• If you're going to have to determine position anyway, you could also use something like turtle graphics. This might also be useful in the future as you have more visualizations to carry out.

If you're talking about general drawing (e.g., drawing other aspects of those data you have):

• Again, Matplotlib works well enough
• Seaborn also works fairly nicely for graphing data
• ggplot is popular among users of the R statistical package/language, the python version might be interesting to you as well, though the others might be a bit more updated & thus feature-rich

How should I design my viz? What should my visualization convey?

The starter code

class ChicagoCrimeFun:

	def init(self):
		"""
		Constructor that could do several things, including read in your training data
		"""
		pass

	def build_loc_priority(self):
		"""
		Should be used to build your location-priority AVL tree
		"""
		pass

	def build_crime_priority(self):
		"""
		Should be used to build your location-priority AVL tree
		"""
		pass

	def decide_next_patrol(self, new_request=None):
		"""
		You will need this later, but I'm just giving this here for you to keep it as a placeholder
		"""
		pass

Phase 1 Presentations

Phase 1 reflection

Making a decision based on past data

The chief loves what you've done, but needs some help with decision-making
Now that you have a way to lookup the priorities of locations and crimes for any dispatch coming in, we can now start to think about making decisions.
You need to make your decide_next_patrol method should return where the next patrol should go:

• This method should allow a string to be entered that represents a 911 dispatch the format will come in as follows:
  • "ID, Case, Number, Date, Block, IUCR, Primary, Type, Description, Location Description, Arrest, Domestic, Beat, District, Ward, Community, Area, FBI Code, X Coordinate, Y Coordinate, Updated On, Latitude, Longitude" ← string
• Thus this method should return a tuple of 4 latitude-longitude tuples that effectively give us four corners of an area to patrol.
  • Example return value (this is a pretty small area, but gives an example nonetheless):
    • ((41.8763889,87.6216667), (41.6944444,87.6216667), (41.6944444,87.6205556), (41.8763889,87.6205556))

But how should you make these decisions?

Using a Heap Priority Queue to make decisions on dispatches

Create an attribute for your main ChicagoCrimeFun class called dispatch_queue that will be used to decide where to send patrols when you have had 911 dispatch calls.
dispatch_queue should be a MinHeap that holds:

• the Priority as a key
• the dispatch string as a value

As with your AVL Tree, you should be creating a separate MinHeap class.

You should use the following methods to add a dispatch to your MinHeap (You must fill in the body of the metod):

	def add_dispatch(self, dispatch_string):
		'''
		Method to add a dispatch to our dispatch_queue
		Parameters:
			dispatch_string: [string] A string that represents a recent 911 dispatch call request that is reported to the police
		'''

	def decide_next_patrol(self, new_request=None):
		'''
		Used to decide next place to send patrol
		Parameters:
			new_request: [string][optional] A string that represents a 911 dispatch call that is reported to the police
		Returns:
			[tuple] A tuple of length 4 that represents the 4 points of an area to patrol.
		'''
		pass

If your dispatch_queue is not empty, you should be extracting from it to decide where to send the next patrol (and returning the tuple to represent the area that the patrol should be covering.)
Thus, your decide_next_patrol method should use the dispatch_queue to find & return the next area to patrol if it isn't empty.
Your code should also be able to handle a dispatch with attributes you've never seen before. For example, if the request includes a representation of location that you've never seen before (and thus isn't in your AVL tree), you should pick some way to handle that request.

How should we handle a decide_next_patrol call if our dispatch_queue is empty?

Using a Heap Sort to create a sorted list of all the possible locations to send patrols

So what about calls to our decide_next_patrol when our new_request is None and our dispatch_queue is empty?

To handle this scenario, I want you to create a sorted list from your AVL Trees using Heap Sort.
Your sorted list should be assigned to an attribute called crime_priority_list

Within your sorted list, each item should have a payload that is made up of a key and a value

• The key should be the overall priority
• The value should be a representation of location that would allow you to return "A tuple of length 4 that represents the 4 points of an area to patrol"
  • That is, you could store the actual tuple (and do the computation before you store), or do the computation after you store and instead store location perhaps in the same way it's represented in your AVL tree It will be up to you to determine how you should use the both of your Trees to determine an overall priority you can use for the sorted list.

Creating visualizations of your data

As with Phase 1, you will need to create a visualization for Phase 2.

Visualizing your Heap

Here you need to create a visualization that represents your MinHeap.
You are welcome to use the same tools that you used previously, or to try something new!

To be clearer about what I mean here, I want to see some visualization that is a direct representation of your Heap. If you want more clarity or to see if something you create will get the full credit, ask!

Expanding your AVL visualization

Now is the time to expand your AVL visualization! Revisit your preivous choice of visualization
I want you to expand/modify your original AVL visualization in some way. You should explain what you did and why in your README.md (one of the Phase 2 deliverables)

Phase 2 Presentations

Phase 2 reflection

For the final phase, we'll focus on reflection, revision, and packing our final software product for the police commisioner
In this part of the phase you will (hopefully) begin to think of your solution as more than just a technical solution, but instead a sociotechnical solution.
After all, all systems and artifacts we create are situated within our socio-cultural society and it is part of our jobs as responsible & ethical system designers and developers to realistically and systematically consider this.
You are not always given the tools or rightly forced to consider this, but consider this phase of the assignment a possible beginning to thinking about these things in a world that has (historically) tried to shield the technical from social considerations (even when those solutions are always used by and interact with individuals and social groups!)

1. Let's do some reading!

For this phase, you will need to read and respond to (in your report & code revision) 3 different articles/Book chapters

• All of these are linked on Google Classroom

Weapons of Math Destruction, Chapter 5

This chapter will introduce you to some ideas on "Big Data" and the criminal justice system

• Fun fact, I spent my summers (and some holidays/breaks) in Reading (family) for a good portion of my childhood

The color of law, Chapter 6

This book chapter will introduce you to some ideas on how the make-up of neighborhoods came about. (Related to the topic of "red-lining" if you've ever heard that term)

Vox article on policing

Image from the article

This article will introduce you to some racial issues with regards to policing (and cite some research in that regard).

2. Refactoring And Revising

This should be completed after reading and cognitively digesting the above readings
Given the above readings, refactor and revise your code so that it is, in your estimation, more fair and equitable.

• As an example, this could mean changing how you assign proirity based on location or crime.

You should also refactor your code so that comments, names, etc. are more socially appropriate. A way to think about it is illustrated in the scenario below:

A grieving family of a person shot by a police officer, partially as a result of mistaken identity, during a traffic stop comes to see you and your code that dispatched an officer to patrol that area. Would anything in your code (comments, name, etc.) anger or upset them due to being inappropriate given the severity of the system your developing?

• In your README.md, provide a section titled Code Refactoring and Revsions that deails the changes you make
• In your final resport, provide a section that discusses these changes in the context of the articles you read
  
  

3. Picking where to place police stations

In addition, the commissioner was hoping to have you help him determine where to place police stations.
Unfortunately, the commish' didn't provide this in his original project problem scope, so now all you can do is suggest a design
Thus, your project leader has notified him that you group can provide a design, but not an implementation

• In your README.md provide a section titled Police Station Placement Design. I want you to come up with a general design and algorithm (complete with what data structures you would use in this algorithm) to pick where to place police stations. This section should be written close to the end (i.e., after you read the above reading and complete any revisions to your code)
  
  

4. Final Report

Your final report should be 6-10 pages and should detail design choices you made with your system (you don't need to go into deep detail, your README.md will accomplish the detail)

This report can have several sections, but should have some similar to these main sections:

• Introduction
  • Where you introduce the problem brought to you by the commisioner, your design, the readings, and some revisions you made
  • ~1-2 pages
• System Design
  • Where you provide an overview of your system design and provide a few (1-2) examples of your visualizations
  • ~2-3 pages
• Discussion
  • Where you discuss the your system in the context of the readings for this phase. You also should discuss how your revisions address topics from the readings.
  • A few possible questions to address (just to give you a possible starting point if you're stuck):
    • What do you think the O'Neil reading tells us about what we should do as designers and developers?
    • Do you think that you would have approached things differently had you read the chapter first?
    • What do you think about the title of the starter code's main class?
      • How do you think the family of the most policed neighborhoods would view that naming?
      • Do you think naming it that way affected your initial approach to the task?
    • Reflect upon the way crime is handled where you're from. Do you think these AI systems that predict where to send police would be a good thing? (Why or why not)
  • ~3-4 pages
• Conclusion
  • Bring it home and provide some concluding remarks
  • ~0.5-1 page
• References
  • This section isn't included in the expected report length.
  • You should, at the least, have the three readings in here assigned during this phase
  • You can pick any style for referencing (APA, ACM, etc.), but I do want a coherent style used for referencing in your report and this references/bibliography section.
    
    

Final Phase Presentation

Each team will be required to give a ~6 minute presentation on their implementations and the visualizations that they've created for the Final Phase. You should be sure your presentation works on the classroom computer sometime before your presentation date or you must bring your own laptop, and make sure you know how to project your display on your external monitor port.
These presentations should give a good background on your design choices and the reasons for those choices. It will also be your chance to quickly discuss issues you have had or did have w/ the project.

5. Final Phase Reflections

This is your individual reflection (submitted separately by each group member)

A Note