Final project
You will complete a final project for CSCI 151 which gives you more practice with data structures and with large software projects.
Requirements
The topic of the project is open-ended; the only requirements are:
The project must be of significant complexity, making use of multiple classes working together.
You must make nontrivial use of at least two data structures we have discussed this semester (list, stack, queue, binary (search) tree, priority queue, hash table, graph). You are encouraged to use the versions of these data structures included in
java.util(though you may also reimplement them or use a version developed in lab if you wish).You may work with a partner if you wish.
The project is due at 2pm on Monday, December 12. During the officially scheduled CSCI 151 final exam slot from 2-5pm, each group will give a 10 minute presentation/demo of their project.
Topics
I realize that it can be overwhelming trying to come up with an appropriate project when the requirements are so open-ended. I suggest trying to connect the project to some other topic you are interested in. Please come and discuss with me—I am happy to help brainstorm project ideas, or to figure out how to take your idea and fashion it into an appropriately-sized project.
What to turn in
You should turn in:
Your code as a
ziportarfile.A document describing your project:
- What is the goal/purpose of your project?
- How does one use it? (i.e. tell me how to run and try out your project.)
- What are the interesting features?
- What challenges or triumphs did you encounter along the way?
Evaluation
The projects will be evaluated according to the following criteria. Each will count for 25% of the total grade.
Presentation. The presentation should be clear, compelling, not overly long, and use appropriate visual aids (e.g. slides, chalkboard, a project demo…).
Effort/complexity. Does the project represent an appropriate amount of effort? Is it sufficiently complex? Does it use multiple data structures appropriately?
Documentation. The project should be well-documented, with plenty of comments explaining the code, and a thorough description in the accompanying document.
Correctness. Does the project work as advertised? Is it relatively bug-free? Does it gracefully handle all inputs?
Resources
Java
Eclipse
Lectures
- W/F Aug 24/26: Intro to Java (caesar.py, Caesar.java)
- M Aug 29: Classes and objects (Main.java, VolleyballGame.java)
- W Aug 31: Eclipse, prisoner’s dilemma
- F Sep 2: Inheritance and subclasses (Animal.java, Goat.java, AnimalMain.java)
- W Sep 7: Extensible arrays (Vector.java (start), VectorMain.java (start))
- F Sep 9: Extending extensible arrays (Vector.java, VectorMain.java)
- M Sep 12: Associations, dictionary (Association.java, Dictionary.java (start))
- W Sep 14: Finish dictionary, generics (Dictionary.java, Association.java (generic), Vector.java (generic), DictionaryDemo.java)
- F Sep 16-F Sep 23: no class
- M Sep 26: Stacks, linked lists
- W Sep 28: Big-O
- F Sep 30: Big-O (BigODemo.java)
- M Oct 3: Linear and binary search (Search.java)
- W Oct 5: Sorting (Sorting.java (start))
- F Oct 7: Insertion sort (Sorting.java)
- M Oct 10: Comparable, Bubble Sort, Merge Sort (Sorting.java)
- W Oct 12: Quicksort
- M Oct 17: Queues
- W Oct 19: Circular array queues, doubly linked lists
- F Oct 21: Doubly linked lists (DNode.java, DoublyLinkedList.java, DLLTest.java)
- M Oct 24: Iterators (VectorIterator.java, VectorIteratorDemo.java, DLLIterator.java, DLLIteratorDemo.java)
- W Oct 26: Binary trees
- F Oct 28: Binary trees (BinaryTree.java, BinaryTreeDemo.java)
- M Oct 31: Binary search trees (BinarySearchTree.java)
- W Nov 2: Array storage for trees, heaps
- F Nov 4: Heap insert, reheapUp
- M Nov 7: Heap removeMin, reheapDown (Heap.java, HeapTest.java)
- W Nov 9: Treesort, heapsort, building a heap in linear time (Heap.java)
- F Nov 11: Comparison-based sorting bounds, tries
- M Nov 14: Tries
Labs
| Lab | Name | Assigned | Due | |||
|---|---|---|---|---|---|---|
| 1 | Java with Codingbat | Mon 8/29 | Mon 9/5 1pm | |||
| 2 | Prisoners’ Dilemma | Tue 9/6 | Tue 9/13 5pm | |||
| 3 | Vectors | Mon 9/12 | Mon 9/19 4pm | |||
| 4 | Vector and Dictionary | Tue 9/20 | Mon 10/3 1pm | |||
| 5 | Stacks | Mon 9/26 | Mon 10/3 1pm | |||
| 6 | RPN calculator | Mon 10/3 | Mon 10/10 1pm | |||
| 7 | Sortimator | Mon 10/10 | Mon 10/17 1pm | |||
| 8 | Generic Stacks and Queues | Mon 10/17 | Mon 10/24 1pm | |||
| 9 | Text Editor | Mon 10/24 | Mon 10/31 1pm | |||
| 10 | Binary search trees | Mon 10/31 | Mon 11/14 1pm | |||
| 11 | Ice cream store | Mon 11/7 | Mon 11/14 1pm | |||
| 12 | Text prediction | Mon 11/14 | Mon 11/21 1pm | |||
| 13 | Hash table tic-tac-toe | Mon 11/21 | Mon 11/28 1pm |