Important Note: Late days applied only to homework assignments; you may not submit either part of the Implementation Project late. No exceptions.
This open-ended project provides you the opportunity to apply everything you have learned in 110 to a program of your choice. You will be responsible for choosing a problem that you can solve using a Java program, analyzing that problem to determine how to solve it, decomposing the functionality of your program to identify its class structure and the API for each class, and then implementing and testing your program. This project will also give you critical skills with implementing a robust generic data structure (a generic LinkedList) that is extensively unit tested.
You are permitted (and strongly encouraged to) work with one partner on this project. Your partner must be currently enrolled in CIS 110; you may work with someone who attends a different lecture or recitation from you. If you need assistance finding a partner, we recommend that you use the Partner Finder feature on Piazza.
Both partners are expected to contribute equally to this project. If we determine that the work was not evenly distributed between the partners, we reserve the right to allocate grades proportional to the work done by each partner.
Only ONE partner per project should submit your work on behalf of both partners -- the partner who submits should be the person whose PennKey comes first in alphabetical order. If both partners on a team submit, the team will receive a point deduction, since it causes us problems when grading.
The one exception to the above rule is that BOTH partners must INDEPENDENTLY submit a brief survey on their participation and their partner's participation in the project.
You are ONLY allowed to share code and discuss the project with your partner; you may NOT collaborate in any way with anyone besides your partner. The course collaboration policy still applies.
You need to determine a way to share code with your partner in a private, secure, and easily accessible manner. We strongly recommend that you create a shared private DropBox or Google Drive folder for this project and use it to share code. Emailing files back and forth will not typically work well. Be careful of synchronization issues though with DropBox/Google Drive -- if both of you edit the same file at the same time, DropBox/Google Drive will not merge the changes together correctly, so one person's work may be overwritten. The BEST way to collaborate is to agree on an API and then divide the files to implement between partners, coordinate the edits between files, and then schedule frequent times to work side-by-side in-person to finish the program. Sitting side-by-side to program, with one person typing and the other person contributing ideas and reviewing code as it is typed in, is so effective it has its own name: "paired programming".
Start early and talk often with your partner! This is NOT an assignment that you can do last minute.
If you choose to work alone, you are still expected to complete a project of the same scope as a two-person team. For that reason, we STRONGLY encourage you to work with a partner.
Important Note: Late days applied only to homework assignments; you may not submit either part of the Implementation Project late. No exceptions.
The project is divided into two parts, each with multiple tasks:
The project itself is very open ended, with the exception of the following requirements:
In terms of project scope, the project should be around twice the size/complexity of the last few homework assignments. Use reasonable judgement on this, and ask one of your TAs if you're in doubt.
Grading: Since everyone will be completing different projects, the projects will be graded against a set of generic criteria, such as:
Project Part 1 will be worth 35% of the Implementation Project grade; Part 2 will be worth the remaining 65% of the Implementation Project grade.
For this project, I strongly recommend that you focus on just applying everything you've learned throughout CIS 110 to complete an interesting project well. Don't worry about trying to meet a particular set of grading criteria. A simple project that is extremely well executed can earn a perfect score. Conversely, a very difficult project that is done poorly will not be scored highly.
Data Visualization Identify an interesting data set on the web (box office revenues, stock prices, annual rainfall, song lyrics, etc.) and visualize it in an interesting way. Your program could load the data, compute statistics on it, and then visualize that data as a graph, colored map, or word cloud. Make the visualization interactive, where the user can interact with it using the mouse, or make it dynamic. Have your program load data dynamically from the internet instead of just from a file. Explore the connection between multiple different data sets, stocks, or songs.
Game Just as we're doing in class, pick a simple game (asteroid, space invaders, etc.) and implement it. Keep it simple, building up your code and the game's functionality as you go. Add your own special twist to the game.
Decision Aid Write a program that helps people make a key decision in their life, such as what house to purchase. For example, your program could load data on housing prices, crime rates, school ratings, etc., overlaying them on a map, where the user could turn on and off different layers of the map and input certain criteria to filter the information that is displayed.
Image Editor Write your own image editor (a la PhotoShop) that you could use to load, manipulate, and save images. Add your own brushes, image filters, etc.
PhotoMosaic Write a program that loads an image and reconstructs it as a photomosaic, using a library of source photos. Add some interaction to give the user control over the photomosaic.
Automatic Menu Translator Write a program that will take in food descriptions on menus in one language and translate them to another language.
Custom News (Advanced) Grab live news feeds from the internet, filter them against the user's preferred topics, and display a customized page of news. Allow the user to dynamically change their preferred topics.
Game Player (Advanced) Write a program that will play Connect Four or Checkers against you!
Sudoku Solver (Advanced) Write a program that will efficiently solve Sudoku puzzles.
Internet of Things (Extremely Advanced) For a real challenge, buy a low-cost Arduino board and build a mechanical device using the Arduino, then write an interface in java to control that mechanical device.
In the first part of the project, you will be implementing the generic LinkedList that will be used in your final program in some significant manner, and planning the rest of your project.
Chose your project and write several paragraphs describing it. These paragraphs will eventually go in the README file for Part 1. Focus on the following aspects:
You must be prepared to discuss your project idea in the recitation immediately following the release of this project (the dates are listed above in the PROJECT ORGANIZATION section).
While planning your project, you should simultaneously be implementing the generic LinkedList, as described next.
Getting started: Download the List interface: List.java
Before you begin looking at the List interface or writing your own list, take a moment to understand generics.
The basic idea behind generics is that we don't need to write different data structures for different types of data (e.g., LinkedListOfStrings, LinkedListOfInts, LinkedListOfImages, etc.). Instead, we can write ONE LinkedList class and then use it with any type of data!
Generics are a built-in feature of Java that allow you to write one LinkedList class that is written to work with a generic type as its element. You can write one LinkedList class and use it multiple times, each with different data types.
The basic idea is that instead of specifying the type of data that will be contained within each node of the linked list, we will use a generic type <T> that will act as a placeholder. We won't know what data type T is at compile time; we will only know this at runtime once the program executes. But, we can use T in our program wherever we would want that data type.
To see how this works in practice, take a glance at the List.java interface that we provided (also described in the next section). You can see that at the top, it doesn't simply say public interface List, but also includes an <T>. This is what signals to Java that whenever you are writing T, you mean whatever type of list this is. So if you see the method to add to the end of the list,
public boolean add(T element)
you are adding an element of type T because you aren't sure what type it is yet.
When you write your own LinkedList, you will also want to keep all the functions generic. You'll also want your Node class to contain a generic item. To use it, just put T as the data type wherever you would want the data type of items contained in your list.
How to use a generic LinkedList in main(): To use a generic data structure, we have to specify what type of data that structure will contain when declaring and initializing the object. For example, here is a snippet that creates a LinkedList to hold Strings and performs some operations on it:
// declare and initialize with String
LinkedList<String> ll = new LinkedList<String>();
// add method takes a String argument now
ll.add("a string");
// get method returns a String
String output = ll.get(0);
System.out.println(output);
We could also use the same LinkedList to hold a Ball object:
// declare and initialize the list of Ball objects
LinkedList<Ball> ll = new LinkedList<Ball>();
// add three balls to the list
ll.add(new Ball());
ll.add(new Ball());
ll.add(new Ball());
// get the ball
Ball b = ll.get(0);
Generic typing is a powerful tool that we only scratch the surface of. For now, just think of it as a placeholder for whatever type you will want. You will get to really dive into the topic if you take CIS120!
The List interface (List.java) defines a basic API that any List should have. You will be writing a type of List ‐ a LinkedList ‐ that will implement the List interface. This means that every function defined in List.java must be implemented in your LinkedList exactly as it is given. You are not permitted to modify List.java.
You should familiarize yourself with List.java before moving on.
public Interface List<T>
-----------------------------------------------------------------------------------------
boolean add(T x) // add x to the end of the list
boolean add(int index, T x) // add x at the specified index
int size() // return the number of elements in the list
T get(int index) // return the element at the specified index
T set(int index, T x) // replace the object at the specified index,
// returning the replaced object
T remove(int index) // remove the object at the specified index
// and return it
boolean isEmpty() // test whether this list has no elements
boolean contains(T element) // test whether the list contains the given element
int indexOf(T element) // return the first index of the specified element
// or -1 if it is not found in the listLinkedList Now that you are familiar with the List interface, it is time for you to write a class to implement it. In order to have Java enforce the interface automatically, your LinkedList.java must be defined as follows:
public class LinkedList<T> implements List<T> { ... }
The implements keyword in Java allows us to specify the name of an interface that the class must use, in this case, List. The standard LinkedList provides a number of other methods that you are not required to implement in this assignment. For a full list of these methods for a standard LinkedList, you can refer to the LinkedList Javadocs .
You must use the List API to create a LinkedList.java. You must also implement an inner class: Node. Method headers and explanations for LinkedList are provided in the skeleton file.
Hint: The Node will need two fields: a next reference and an element.
Some Implementation Notes:
add() method is overloaded in the List. One version, add(element), adds an element to the end of the list and always returns true. The other version, add(index, element), adds an element to a specific index of the list. get(index), take in an index and return an object. In situations where the index is invalid, it doesn't make sense for the method to signify this by returning null, since null is a valid value for an object (and could certainly be contained in the list). Instead, your implementation should throw an IllegalArgumentException (with an appropriately detailed message) when index is invalid. add(index, element) should work correctly if 0 <= index <= size(). For example, this would allow you to call add(0, element) on an empty list and have it insert element as the new head (and tail) element. set(index, element) to work. Therefore, set(index, element) can't be used to add new nodes to a list. List interface, but your LinkedList class must still implement them. The reason for this is that we're writing a general LinkedList that can be used in any program; those other programs may use LinkedList methods that are not necessary to write for your project. Hint: To get started implementing the LinkedList, start by implementing the Node inner class and the constructor, then take the methods one by one.
(Another) Hint: The next section will be about unit testing. You can (and should!) use the unit testing described below to be confident that your completed methods are working before you move on to the others. In particular, being confident when printing the list will allow for easy debugging later.
The submission script runs extensive testing on your LinkedList implementation, so you must be confident that your list works in all cases! However, you should write you own test cases in main() as you implement your program. Don't rely only on the submission test scripts; those tests are not exhaustive.
Important Note: Late days applied only to homework assignments; you may not submit either part of the Implementation Project late. No exceptions.
Complete readme_project1.txt in the same way you have done for previous assignments.
Please have only one member of your team fill out this form.
First fill out the form in B and then submit LinkedList.java and readme_project1.txt on the course website. If you're working with
a partner, both of you may submit to see the submission test output, but make sure that the partner whose project we will be grading (based on your response to the form
above)
submits the final code.
Before submission remove any print statements that were used for debugging or testing your functions. Any testing done in main() can be kept.
Be sure that every method has an appropriate header comment, and that your code is well-documented.
The second part of the project simply involves completing your chosen project! First, agree on a complete design of the program, defining all objects and APIs. Figure out how those objects will interact. Pick the algorithms/techniques you will use for each part of the program.
Once you have a complete design in agreement with your partner. Implement the program slowly, testing as you go. Focus first on the core functionality of your program, adding other features once you're certain that the core functionality works well.
Re-read the section above on WORKING WITH A PARTNER, paying special attention to the tips on how to coordinate, share files, do paired programming, etc.
Approximately one week before the project is due, we will post the Project Part 2 webpage with details on the submission process, the Project Part 2 README, and the partner survey.