- A large number of PNG files corresponding to the region of the world of the instructor's choice, drawn from the Open Street Map dataset.
- An XML file containing all road, business, and intersection information from the same region as the PNG files, also drawn from the Open Street Map dataset.
- Building one piece of a large application and interacting with an existing code base.
- Writing code that converts a slightly messy real world dataset into useful data structures.
- Implementing a graph search algorithm (BFS, Dijkstra's, A*, or similar, per choice of the instructor).
Starter files (Java): Link
Demo video showing off what students will be building: Link
Hint videos provided to Berkeley students: Link
Web demo of a correct implementation (provided to students for reference): Link Credit to former TA Alan Yao for developing the original assignment idea.
Students write the Java back end of a browser based street mapping application. They must fill in two functions. The first takes coordinates corresponding to a region of the world, and outputs a list of String filenames to display. The second takes a starting and ending point, and generates a route along real streets.
||OOP, working with real data, graphs, graph search, optionally Quad Trees.|
||Medium to difficult. Can be varied based on how much you give them and what you require.
||Rastering is Tricky: Figuring out the correct filenames to display is a tricky and may require considerable hand holding for less mature students. Interaction with a Large Codebase: Students might not feel like the ultimate product is really theirs, given that so much is done for them under the hood.|
||None beyond those provided.|
||The assignment can be made more complex or simplified in many ways. Some ways to enhance the complexity (that we've done at Berkeley): require students to implement a Trie-based Autocomplete feature that allows business name search, require students to parse the XML data containing street (and business) information and build a graph, require students to use A* for routing. Some ways to simplify: require only rastering, require only routing, allow any graph traversal algorithm instead of one that guarantees finding of the shortest route, provide a QuadTree implementation to simplify rastering.|