 |
![[Courses]](../icons/up.png){kind=icon}
![[Rich]](../icons/prev.png){kind=icon}
![[Home]](../icons/home.png){kind=icon}
![[Rich]](../icons/next.png){kind=icon}
![[PHome]](../icons/author.png){kind=icon}
| Spring Quarter 2003 |
Objectives Addressed
- Be able to apply asymptotic time complexity analysis to choose among competing algorithms.
- Understand how graph and tree structures are implemented.
- Be familiar with engineering applications for many of the fundamental algorithms discussed in the course.
Purpose
This lab assignment is designed to provide stimulate creative solutions to graph theory problem that is difficult to solve efficiently. Upon completion of the assignment, students should have a better understanding of how graphs may be represented and manipulated within a software system.
Overview
One reason for studying algorithms is to find efficient ways to solve problems. While asymptotic analysis allows us to evaluate an algorithm's efficiency, it ignores other important issues like implementation complexity and time constants. In this assignment, you should focus on developing an algorithm that will solve the pizza delivery problem as quickly as possible.
Assignment
Suppose the following:
- You have at your disposal an experimental vehicle that can transport you and 550 of your "favoritely" topped pizzas between two arbitrary points on the Earth at a fixed rate of 100 kilometers per minute.
- All of your customers get hungry and call in their orders at exactly the same time.
- You are able to take orders for and make 550 pizzas in ten minutes.
- You require two minutes to get all 550 pizzas in your experimental vehicle.
- It takes you less than three seconds to deliver a pizza to a customer once you arrive within the city limits of the city in which the customer resides (all payments are made when the order is placed).
- You love delivering pizzas.
- Your pizza isn't very good.
You have been asked to determine delivery time guarantee for three potential service areas.
Burma
Evidently there is currently a strong demand for pizza delivery service in fourteen cities in Burma. The location of each city is specified in burma.txt. The file contains some information at the beginning which you may ignore. The data starts on the line that begins with a 1 and ends one line before the line with EOF. The data consists of latitude and longitude values (format: DDD.MM where DDD is the degrees and MM is the minutes) for each city. For example, the first city in the file is located at 16 degrees 47 minutes North and 96 degrees 10 minutes East. The distance between two cities may be calculated by approximating the Earth as an idealized sphere with a radius of 6378.388 kilometers.
When performing the distance calculation, you should first convert the
latitude and longitude from degree-minutes to radians as follows:
The distance between to cities, i and j, is calculated by:
q1 = cos( longitude[i]-longitude[j] ) q2 = cos( latitude[i] - latitude[j] ) q3 = cos( latitude[i] + latitude[j] ) distance = 6378.388*arccos(((1+q1)*q2-(1-q1)*q3)/2)+1
US Capitols
The theory goes that legislators typically eat a lot of pizza. In this scenario, you are to determine the minimum delivery time for the capitols of the 48 contiguous United States. The distances between the capitols may be determined from the capitols.txt file.
The format of the file is similar to burma.txt
except the coordinates are no longer latitude and longitude. The distance
between cities may be calculated as:
World Cities
This is the most ambitious plan in which you would deliver pizza to 535 different cities around the globe. The location of each city is specified in world.txt which has the same format as burma.txt.
Details
For each scenario, you may choose to set up shop in any one of the cities. Once you have chosen a city, you will need to determine how quickly you can travel to all of the cities in the service area (and back to base). Since your pizza isn't very good, you should not revisit a city until all pizzas have been delivered, otherwise you may get stuck listening to an unhappy customer. While this may be extremely interesting, it could really mess up your delivery schedule.
Lab report (due 4:00pm, the last day of classes)
This assignment is optional. If submitted, the best 3 out of 4 lab grades will be used in calculating your final grade for the quarter. You may do this assignment individually or with a partner of your choosing.
The lab report need not be self-contained. Your report should include:
- The best delivery time guarantees that you can meet for the three scenarios and a explanation for how you obtained the time guarantees. (You should include the delivery routes so that someone else can take your place in the delivery vehicle... just in case, you suffer from motion sickness.)
- Complete description of your algorithm that determines the shortest route to all of the cities in the file (without visiting any city twice). Be sure to discuss other alternatives that you considered and why you chose your method over other alternatives.
- Time complexity analysis for your algorithm
- Benchmarks for your algorithm for each scenario.
- Narrative (what you learned, suggestions of how the lab could have been better, things you would have done differently, how you worked as a CSP team, etc.)
- CSP spreadsheet (Continue with the spreadsheet you used for lab 2.)
- Documented source code
Your grade will be based on (in order of priority) 1) closeness to optimal solutions, 2) speed of algorithm, 3) description of algorithm, 4) time complexity analysis, 5) narrative report.
Template Lab Report
As with any report you submit, correct spelling and grammar are required. In addition, your report should be submitted electronically following the Electronic Submission Guidelines. (You may wish to consult the sample report before submitting your report.) Be sure to keep copies of all your files, in case something gets lost. It may be wise to keep a diskette backup as well.
If you have any questions, consult the instructor.
