|
Implement and anlyze an algorithm or compare different algorithms for the same
problem. You need to program the algorithm(s).
You may add a user interface or graphical display.
Notes:
- Up to 3 students will be allowed per project team.
- Relative scores for the parts of the project deliverables will be
as follows:
Proposal: 10 pts.; Prelim. design: 15 points; Design: 20 pts.; Testing design: 10 pts.; Final report and presentation: 45 pts.
- Read in your test data from a file.
Project ideas (exclude project topics that have been given as a regular assignment):
- Problems from computational geometry, e.g., convex hull, intersection problems, geometric searching, visibility and separability, nearest neighbors, Vonoroi diagrams, geometric optimization, triangulation of polygons and point sets, mesh refinement.
- (Other) divide and conquer methods, e.g., multiplication of large
integers.
-
Karatsuba algorithm
- Greedy methods, e.g., Kruskal's algorithm using min-heap and the union-find
disjoint set data structure; its efficiency can be compared (theoretically and in practice) to a version of Prim's algorithm;
job sequencing with deadlines.
- Dynamic programming, e.g., string editing, TSP.
- Backtracking, e.g., n-Queens implementation:
HSR text Exercises n-Queens ##1, 2.
Make a timing graph Time vs. n. Include graph and observations in your report.
Implement the Estimate() algorithm for estimating the number of nodes in the tree. Keep track of the actual number of nodes generated, cf., Ex. #2, and compare to the estimated number.
- Backtracking solution for graph coloring.
- Backtracking solution for Hamiltonian cycles.
- Backtracking solution for 0/1 knapsack.
- Branch and bound, e.g., 15-puzzle; path problem in a network; job scheduling
- Branch and bound solution for 0/1 Knapsack.
- Branch and bound solution for TSP.
Project Milestones
Tasks |
Deliverables |
Deadlines |
- Project description
- Project goals
- References
|
Project proposal:
Proposal document +
Short presentation by team |
02/16/24
02/22/24
|
- Possible approaches
- Research so far
- Preliminary design outline (pseudocode, or flow chart or diagram)
|
Preliminary specification/
Prelim. Design document |
03/12/24 |
- Design Overview
- Design of testing
|
Design overview +
Testing document |
03/26/24 |
- Project description
- Research/Design
- Implementation
- Testing/Samples
- Result analysis
- [Goals reached?]
- User guide
- References
|
Final report
Final presentation
(Overview of report) |
04/16-18/24
|
Notes:
- For the proposal document, upload on Elearning and email to professor.
- For the design overview, submit pseudocode
(reasonably detailed) + description in words of the different blocks,
packages or software tools to be used, and interfaces. This is
basically everything needed to put the project together, in significantly
more detail than for the preliminary design.
- For the design of testing,
we need test problems for the project, how these will be implemented,
and parameters with which they will be run, everything with justification.
|