Algorithms (Syllabus)

The third semester in a series of programming courses; this course built upon data structures and introduced algorithms and related concepts. Algorithms studied included sorting algorithms, hash tables and hashing algorithms, trees and graphs, and data input/parsing. Algorithm analysis included using Big-O notation to rank algorithms by time complexity and space complexity. Additional OOP topics covered included using inheritance, virtual methods, and polymorphism. The entire course was done in C++. The final project, a culmination of everything we learned, was to create a program that found the shortest path between any two cities in the continental US (using Dijkstra's shortest-path algorithm) and visually display it.

---

Projects

• Quicksort

  A database of people is sorted by last name using quicksort. The example output screenshot only shows 20 people for clarity.

  Code
  Output

• Mergesort

  The same database of people is sorted by last name using mergesort. The output screenshot shows the first couple entries on the sorted list of 1000 people.

  Code
  Output

• Geographical Hash Table

  A database of towns in the USA is read into a hash table. The user can search for towns in the hash table and have their data displayed.

  Code
  Output

• Traveling the USA with Vectors

  Using the geographical hash table data from the previous project along with additional road and intersection data stored in vectors (C++ dynamic arrays), this program allows the user to create a path using roads and highways. I first define custom objects to represent a town, an intersection, and a connection. The program then reads in this data and stores town data in a hash table, and intersection and connection data in vectors. The user chooses a location to start and the program repeatedly prompts the user to choose a connecting road to travel.

  Code
  Output

• Generating Random Trees

  Using recursion my program draws randomly-generated, realistic apple trees.

  Code
  Output

• Mapquest Shortest Path Program

  The final project of the semester. This program will calculate the shortest distance between two points in the continental USA using Dijkstra's shortest-path algorithm and draw it on a map. This project involves reading in binary files of map and elevation data and drawing it, reading and storing the town data in a hashtable, and reading and storing the connection data in vectors. A shortest-path algorithm is implemented using a priority queue.

  Code
  Output