Husky Maps

Husky Maps is an educational web app for mapping the world, searching for places, and navigating around Seattle. All these features are powered by data structures and algorithms, programming abstractions designed to represent data and automate processes. In your prior programming experience, you learned how to implement specifications by writing Java programs that used data structures to solve problems. But why was the specification written that way in the first place?

Husky Maps consists of 4 educational programming projects that aim to highlight the relationship between abstractions, implementations, and problems. The purpose of these projects is to help us explore the capabilities and design effort that goes into writing a specification. Under each project are relevant lessons from the Wiki.

1. Deques
   1. Dynamic Arrays and Linked Nodes
   2. Asymptotic Analysis
   3. Iterative Sorts
2. Autocomplete
   1. Binary Search and Merge Sort
   2. Binary Search Trees and Tries
   3. 2–3 Trees and Left-Leaning Red-Black Trees
3. Priority Queues
   1. Quicksort and Counting Sorts
   2. Binary Heaps and Hash Tables
   3. Affordance Analysis and Graph Data Type
4. Shortest Paths
   1. Graph Traversals
   2. Shortest Paths Trees and Problems and Solutions
   3. Topological Sorting and Dynamic Programming
5. Build Your Own Feature
   1. Minimum Spanning Trees and Disjoint Sets

Getting started

Warning

These instructions are designed for students enrolled in a University of Washington course!

Install Java, VS Code, and Git

Let's install the Java Development Kit (JDK) and VS Code.

1. Download and install Eclipse Temurin (JDK).

2. Download and install VS Code.

3. Install Git by following the instructions for your computer's operating system.

Generate SSH keys

Your project code will be stored on CSE GitLab, a service provided by the Allen School to securely and privately store your coursework. CSE GitLab requires SSH keys: computer-generated passwords used to securely authenticate your computer to CSE GitLab.

1. From VS Code, open the Terminal with the keyboard shortcut Ctrl ` (backtick key, which is typically above your tab key). If this doesn't work on MacOS, you can instead open the Terminal app.

2. In the terminal, generate an SSH key pair with the command ssh-keygen -t ed25519. When asked to enter a file name or a passphrase, just press Enter to accept the default settings for both questions.

3. Print your public SSH key with the command cat ~/.ssh/id_ed25519.pub and copy the contents to your clipboard.

4. In your browser, open the SSH Keys user settings. Sign into GitLab using your UW NetID. Then, paste the public SSH key in the Key field.

5. Give it a title representing your computer (any title of your choice) and press Add key.

Obtain project code

Now that you've installed the required software and configured our computer so that it can securely communicate with CSE GitLab, let's get the project code! This step requires the project repositories to be setup, which will be ready for enrolled students by the end of the first week of the course.

1. Visit CSE GitLab and you'll be greeted by a private repository with your personal copy of the project.

2. Visit your private repository, press the blue Code button and, under the heading Open in your IDE, choose Visual Studio Code (SSH). Be sure to choose the SSH option because you are using SSH keys. If this doesn't work, you can copy the Clone with SSH address, find the Git: Clone tool in the VS Code command palette, and paste the SSH address. You can choose where you would like to store the project.

3. If you see an SSH Confirmation window, check that the fingerprint matches the CSE GitLab fingerprint. Compare the value to the table entries, most likely under SHA256. If it matches one of the values, accept the connection. If it doesn't match any of the values, do not accept the connection and write an Ed Discussion question with the mismatch.

The first time you open the project, VS Code should prompt for a few permissions:

1. Respond to the prompt Yes, I trust the authors so that VS Code has your permission to run code.

2. Respond to the notification in the bottom right to Install recommended extensions. (If you already installed them from CSE 123, you won't get this notification.)

After installing extensions, at the very bottom of VS Code, the status bar should show the current state of the Java environment setup. While you wait for it to report "Java: Ready", right-click the file README.md in VS Code and choose Open Preview to see exactly these instructions in VS Code.

Run project code

After the status bar shows "Java: Ready", let's try running the project code.

1. In the Explorer (file explorer), navigate to the src | main | java folder. This folder contains all the Java program logic for this project.

2. Open the BrowserHistory.java file and drag these instructions off to the side to split the VS Code window left and right.

3. Run Java using the ▷ play button at the top of the tab strip or right above the main method.

If all the software was installed correctly, you should be able to see some text indicating that the class is being run. If you can find the following main method output somewhere, you're all set!

[uw.edu, my.uw.edu, cs.uw.edu, canvas.uw.edu]
[cs.uw.edu, notify.uw.edu]

Now that you're able to run the simple BrowserHistory class, let's try running the more complicated MapServer class. If everything is successful, you'll see this flurry of messages appear indicating that the app has launched.

[main] INFO io.javalin.Javalin - Starting Javalin ...
[main] INFO org.eclipse.jetty.server.Server - ...
[main] INFO org.eclipse.jetty.server.session. ...
[main] INFO org.eclipse.jetty.server.handler. ...
[main] INFO org.eclipse.jetty.server.Abstract ...
[main] INFO org.eclipse.jetty.server.Server - ...
[main] INFO io.javalin.Javalin -
       __                  ___          _____
      / /___ __   ______ _/ (_)___     /__  /
 __  / / __ `/ | / / __ `/ / / __ \      / /
/ /_/ / /_/ /| |/ / /_/ / / / / / /     / /
\____/\__,_/ |___/\__,_/_/_/_/ /_/     /_/

       https://javalin.io/documentation

[main] INFO io.javalin.Javalin - Javalin started in ...
[main] INFO io.javalin.Javalin - Listening on ...
[main] INFO io.javalin.Javalin - You are running ...

You're done! You can now visit the link that Javalin is Listening on ... to view the app.

All the basic app features except for map images work because we've provided reference implementations for each interface that we'll learn in this class. The study of data structures and algorithms is the study of different approaches to implementing the same functionality, which is exactly what we'll be exploring through these projects.

Optional: Load map images with MapBox

If you're interested to try the web app for yourself, the map images won't load without a MapBox access token. This access token is used to track your usage and (if you exceed free limits) bill you for their service.

To see the map images, sign up for a free MapBox account to get an access token. Husky Maps primarily uses the Static Images API which, at the time of writing, has a free limit of up to 50,000 requests per month.

Once you have your access token, in VS Code, create a new workspace configuration through the Run | Add Configuration... menu. In the configurations section, find the entry for MapServer and add the following JSON:

"env": {
    "TOKEN": "..."
}

Remember to replace the ellipsis with your token, include double quotes around your token string, and add a comma to the end of the preceding line so that the JSON syntax is valid. Finally, re-run the MapServer class to launch the web app and enjoy the "Ice Cream" map style by Maya Gao.

Optional: Web deployment

When you run MapServer in VS Code, it can only be accessed from your own computer. Optionally, follow these instructions to deploy MapServer to the web using the cloud application provider, Render. Render offers a free tier with 0.1 CPUs (one-tenth of a virtual CPU) and 512MB of RAM.

1. Render does not support CSE GitLab repositories, so you will need to sign up for a GitHub, GitLab, or BitBucket account if you do not already have one.

2. Create a private repository in your GitHub, GitLab, or BitBucket account and push your Husky Maps implementation to it.

3. Register for a Render account using your linked GitHub, GitLab, or BitBucket account.

4. Follow the sign-up flow and, when prompted, create a new Web Service.

5. For Source Code, connect your private repository.

6. For Name, choose a name for your project that will become part of the URL.

7. For Language, choose Docker.

8. Under Environment Variables, add an entry for the variable name TOKEN with your MapBox default public token as the value.