Final Project: Advanced Algorithms and Implementation

Go back to home page

Project Summary | Executive Summary | Implementation | Slides | Prog. Challenge | PC Test Cases | PC Solution

This page contains the project requirements. Please make sure you read this page very carefully and adhere to everything.

Summary of Project Deliverables

To complete this project, you will produce multiple deliverables. You will push each of these deliverables to this Github Repository. The deliverables are:

1. Executive Summary: 4-8 page description of everything that has been delivered in this packet / project.
2. Implementation: In C++, Java, and Python. The code needs to be thoroughly commented.
3. Instructional Slides: Two sets of instructional slides. The first, a thorough, well designed, informative slideset that briefly teach the topic to an advanced undergraduate audience (about one lecture or 10-15 slides in length). A second, shorter, set of slides will be submitted that will be used for your 10 minute presentation.
4. PC: Custom Programming Challenge: A programming assignment that asks students to use the algorithm in question, but with at least one notable twist / change to the topic / algorithm in question.
5. PC Test Cases: At least 20 test cases that cover likely edge cases and test for speed / efficiency.
6. PC Solution: A solution to your custom PC in all three languages (C++, Java, Python).

You can find more detail about each of the requirements below.

Executive Summary

Your executive summary will be a 4-8 page pdf that summarizes ALL of the information in your final project. It will serve as an initial resource for readers to understand the topic / problem you are addressing, how you solve it, how you designed your programming challenge, etc.

There is no strict page minimum or maximum for this document. When writing your exective summary, you should make sure to include ALL of the following sub-sections, clearly labeled:

• Introduction / Problem Statement: Describe and motivate the topic your final project is focused on. Some topics will be focused on broad algorithmic approaches (e.g., Dynamic Programming) and some topics will be specific algorithms (e.g., Quicksort). Either way, you should describe what problem is being addressed. What is the weakness in other approaches that necessitates this topic? What is the target runtime (if applicable)? What are the primary challenges that need to be addressed? After reading this section, the reader should understand the nature of the problem and what the goals are.
• Overall Intuitive Approach / Solution: Describe the solution / algorithm at a high-level. Focus on the key ideas that are necessary to solve the problem. Include graphics and code-snippets where appropriate. Remember that your goal is to explain the approach at a senior-undergraduate level, but you should assume the reader has NOT already studied this topic. Do not dive directly into the details. This section might look slightly different depending on the nature of your topic. For a broad algorithmic approach, you might describe the approach in general and provide a simple example problem. For a specific algorithm project, you will probably focus on the solution for that one algorithm instead. This section should NOT contain all of the intuition details.
• Implementation: Discuss the algorithmic and implementation details for your topic / algorithm. Include code or pseudocode if appropriate. This section should have enough detail that a reader can proceed to implement the algorithm or apply the general algorithmic approach after reading.
• Summary of Programming Challenge: Summarize the programming challange that you developed. We are particularly interested in a high-level description of what the learning objectives of your programming assignment are, and why you think your assignment achieves them. You should also focus on the key twist / idea, that goes beyond the basic topic, that is required to complete your assignment. Remember that finding a good level of additional challenge is important. Problems that go far beyond what can reasonably be expected from an average upperclass undergraduate student will incur grade penalties.
• Key Ideas for Solving Programming Challenge: Describe the key ideas for solving your programming challenge. What are the main challenges to overcome? Why do you believe these changes are interesting, but not too difficult? What is the complexity of the model solution and why?
• Conclusion: Briefly wrap up the document by summarizing all of the information that was contained in your summary and provide proper closure.

Implementation

You will create / provide a working implementation that showcases your topic in three different programming languages (C++, Java, Python). If your topic is a general algorithmic approach, then you will need to choose a simple, straightforward example of applying that approach. Make sure to describe in your executive summary what the problem statement for this example is.

In addition to providing working solutions in all three programming languages, you will write a couple of simple, small sample test cases that we can easily run on your code to verify that it works on small examples. You should have at least three test cases

Lastly, to showcase your understanding of the code / algorithm, and to assist other students who read your code, you will comment the code (in all three languages) extensively. You should have a detailed comment for each block of 3-5 lines of code. Every comment should meaningfully interpret your code intuitively, not simply translate exactly what the code states. For example, don’t say things like “sets x to 5 times the value of y”, say things like “multiply x by 5 to calculate the maximum value the solution could possibly be”.

Instructional Slides

You will develop two sets of instructional slides that teach your topic / algorithm in a college, lecture format. The first set of slides will be traditional set of lecture slides, that provide a thorough overview of the algorithm with details, code, examples, visuals, etc. This set should be about 10-15 slides in length and would take approximate one traditional college lecture to deliver to an audience.

Your second slide deck will be used for your class presentation and will be delivered in a maximum of 10 minutes. For many topics, you will not be able to completely cover all details of your topic in this limited amount of time. Your slides (and eventually your presentation) should cover as much detail as you reasonably can comfortably within the time limit. For some topics, this might be very detailed and for others this might be more surface / high level. We would expect this second eck to have somewhere between 5-8 slides.

Both sets of slides should prioritize showing, over telling. In other words, try to maximize your use of images, tables, graphs, code snippets, etc. over text boxes. An undergraduate student should be capable of reading your executive summary above, and then using your slides to teach the topic. Your slides should cover everything regarding your topic including the motivation, the overall approach, the implementation, and the analysis. You do not need to cover your programming challenge and solution in your slide decks.

Programming Challenge

Produce a 1-2 page pdf (similar to our homework assignments in class) that present a programming challenge to students that involves the application / implementation of your topic. When doing this, you should consider what the learning obectives of your programming challenge are. Do you want students to focus on implementation of some problem and getting correct inputs / outputs? Do you want to focus on experimentation / tweaking / playing around with the algorithm? Do you want to do some kind of comparison with a related algorithm? All of this is up to you. However, the assignment should be clearly stated.

Your programming challenge needs to involve some twist / extension on the topic / algorithm you are studying. You will lose points if your programming challenge is simply a naive and direct application of your topic / algorithm. You can run this by course staff if you unsure if your “extension” is significant or interesting enough.

PC: Test Cases

To whatever extent is relevant, you will provide at least 20 test cases that test the edge cases and efficiency of solutions for your programming challenge. Your test cases should be clearly named, so that it is obvious which files are the inputs, which are the output, and which inputs map to which outputs.

PC: Solution

You will implement a solution to your programming challenge in three programming languages (C++, Java, Python). As before, you will comment your solution thoroughly (see Implementation section above for more detail).