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 minheap and the unionfind
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., nQueens implementation:
HSR text Exercises nQueens ##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., 15puzzle; 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/1618/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.
