There will be 5 individual programming projects throughout the semester and one final group project. For each project, you will solve a concrete problem by implementing an algorithm in such a way as to meet a conservative performance requirement. A reasonable implementation will sail through the performance requirement. You will prepare a typed report electronically according to the guidelines for each project. You will answer questions posed in the project guidelines and usually report the results of an empirical analysis of your algorithm. All project reports should include a copy of your documented source code and a screenshot demonstrating the working algorithm.

All projects will be done in C# using Visual Studio as our development environment. This software is installed in all open lab machines, and you can also download it for free. Because we will be providing you with code harnesses for the projects, you must work in C# (if this is a new language for you---great!---the more languages you are exposed to, the better). If you prefer to use a different development environment than Visual Studio, that is fine, but there will be no support for it, so you will be on your own. Follow this link for more information on installing and using C# and Visual Studio.

Design Experience: You are developing as a problem solver. In this class, you are also learning the importance of solving a problem and analyzing the solution before you start writing code. For each project, you are required to have a "design experience" after reading the project instructions but before writing any code.

This experience might best be done using a whiteboard to walk through the solution with a one- (or more-) person technical audience, with that person being a CS 312 classmate, another CS major or another technical person with an eye for detail. Make sure you sketch out and understand how to represent a problem instance (both inputs and outputs) and how to map from inputs to outputs (your algorithm). Simulate simple examples and a non-trivial example or two with your marker. Think out loud. Listen to your audience as he or she poses questions or identifies potential complications. In short, make sure you understand what you are going to do before you write a stitch of code. If two students reciprocate for one another, then each person should take a turn as presenter and as audience member. There are other possible approaches to this design experience as well, including back-of-a-napkin illustrations, writing pseudocode, etc. The purpose of your design experience is to get the concept of a working solution out in front of yourself (and possibly other thoughtful people). If you don’t have a solution that appears to work and hold up to scrutiny, then your design experience is not complete. Don’t code without clear thinking up front.

For each design experience, you will complete a simple quiz in Learning Suite by briefly describing and evaluating the quality of your experience. Due dates for these quizes are shown on the schedule; quizes will open one week before the due date and close at 11:59pm on the date they are due. Late design experiences are not accepted, but if you are late you should go through the process anyhow before writing code. Each project's design experience has a submission deadline on the course schedule about a week and a half before the project report submission due date (except for the first project), but I encourage you to finish the design experience as early as possible. The design experience will be worth 10% of your project grade.

Projects

  1. Fermat: The purpose of this project is to get you up and running with VisualStudio and to familiarize you somewhat with the environment we'll be using. You will also gain experience with algorithms for modular arithmetic. In this project, you will implement the prime number test based on Fermat's little theorem.
  2. Convex Hull: In this project, you will implement a divide and conquer algorithm for finding the convex hull of a set of points and you will analyze the algorithm both theoretically and empirically.
  3. Network Routing: In this project you will implement Dyskstra’s algorithm to find paths through a graph representing a network routing problem. You will use two different data structures to implement a priority queue in order to see that both algorithm design *and* data structure implementation significantly affect performance.
  4. Gene Sequencing: In this project, you will implement two versions of a dynamic programming algorithm for computing the minimal cost of aligning gene sequences and extracting (an) optimal alignment. In the process, you will learn a little bit about computational genomics and how domain knowledge can affect algorithm design.
  5. Traveling Salesperson: In this project, you will implement a branch and bound algorithm to find solutions to the traveling salesperson problem (TSP) and get your first taste of dealing with NP-completeness.
  6. TSP Group Project: In this project, you will work in a small group to compare accuracy and the theoretical and empirical complexity of different algorithmic "solutions" to the traveling salesmen problem (TSP), including greedy, branch and bound, and an algorithm of your choice. In this context, a "solution" is an approximation that is found in reasonable time.

Submission: All project reports should be submitted in PDF format via Learning Suite on or before the published due date, except the group project which is due as a hardcopy at the beginning of class on the day you present your group project.