In this project, you will demonstrate the ability to both implement and analyze various algorithms that are related to the material in this course. In part 1, of this project, you will be responsible for implementing and analyzing various sorting algorithms.
To begin the project, you will need to access the link that was shared in-class on Monday, October 4th (and was subsequently sent out through blackboard). When you do so, GitHub will request that you select your name from the list of students and select your team. If you are working alone, simply create a new team when asked. If you intend to work in a group, you should coordinate with your teammate to determine which student will create the team and which will join. You may name your team whatever you would like, but please keep in mind that your instructor, TA, and grader will see the name you give it. You will not be able to change your team or team name after you have created/joined it.
You may choose to implement your assignment in any of the following programming languages. However, you must implement all of part 1 of this project in the same programming language (you cannot implement one algorithm in C and one in Python). The list of acceptable programming languages is as follows:
If you wish to use a programming language not listed above, you must get approval from the instructor first!
No matter which language you select, you are not allowed to use any external packages or libraries that do not come with the standard distribution of the language. You are also not allowed to use any built-in sorting or searching functions that the language may have.
Your program must be able to read in a whitespace-separated (spaces, newlines, horizontal tabs) list of integers from a file specified as a command line argument and then prompt the user for a sorting algorithm to run on those numbers. Your program should then sort the input with the algorithm selected and print out the output with various statistics. The output must be sorted in increasing numerical order (except for the case of the radix sort specified below).
You are to select four of the below algorithms to implement in your assignment. You must select at least one algorithm marked with [*], one algorithm marked with [#], and one algorithm marked with [@]. The final algorithm may be any of the ones you have not already selected.
Please note that the links in the above list may include code. You are not allowed to use the code provided on Wikipedia (or from any other source) to implement your project. You must write all code yourself.
Once your sort has run, you must print out the sorted results. After printing the sorted results, you must print out the following statistics for the run that was performed:
In addition to your code, you are required to produce a report detailing your results. Your report must show your understanding of the algorithms you have implemented. It must include real results from runs of your code (all of the statistical info above). It must also include an analysis of the best and worst case algorithmic complexity of each algorithm (and justification as to how you came up with the complexity number you assert). Finally, your report must include a bibliography with citations for any references you used in preparation of your assignment (both the code and the report). Your report shall be included in your repository as a PDF file named report.pdf in the root directory of the repository.
In addition to the report, you must include a short README.TXT file that explains how to compile and/or run your code. If you are using a compiled language (C, C++, Java, C#, Assembly, etc), you must include a Makefile build your code.
Your final submission of your assignment will include the following things:
You must ensure that all required parts of your project are committed to your Git repository and pushed to GitHub before the assignment is due. It is highly suggested that you view your GitHub repository in a web browser after pushing your code to ensure that it has been submitted properly.
All code you produce for this assignment must be your own. Strict penalties will be applied to any acts of academic dishonesty.
There is an opportunity to earn up to 25% extra credit (12.5 points) on part 1 of the project. For 5% extra credit each, you may implement and document each of the sorting algorithms that you did not already implement as part of your main implementation of the project (there should be four that you didn't implement as part of your main project). In addition, for 5% extra credit, you may turn the project in a week or more early, following the exact instructions given in class for doing so.
In Part 2 of this project, you will be exploring algorithms for solving or approximating solutions to the travelling salesman problem. The decision version of this problem is what is known as a NP-Complete problem, meaning that a solution can be verified to the problem in polynomial time, but it is not known if a problem can be computed in polynomial time.
You will be allowed to select to either implement an exact solution to this problem (which can run in as poor as O(n!) time) or an approximation that can run with a much lower time complexity. Part of your assignment is to research the algorithms and select one to implement. You will then complete a report describing the algorithm you implemented and documenting the performance of the algorithm you selected.
As with part 1 of the project, you are allowed to select which programming language you wish to use to implement your assignment. If you worked with a partner for part 1 of the project, you are also to work with the same partner for this part of the project (and likewise, if you worked alone on part 1, you are to work alone on this part). A link to create your repository on GitHub for this part of the project will be (or was) sent out on Saturday, November 6th.
The travelling salesman problem is documented in your textbook in section 34.5.4 and one approximation algorithm for solving the problem is described in section 35.2 (assuming that the cost function satisfies the triangle inequality). For the purposes of this assignment, you may indeed assume that the cost functions of the edges do satisfy the triangle inequality. In addition, you will only be solving this problem in two dimensions. You are not required to implement the solution in section 35.2 of your textbook — I encourage you to research other approximations of solutions to this problem.
The input to the program will be provided as a text file that consists of a list of vertices of the graph in two dimensions and a list of edges, separated by a line consisting of three hyphens. An example is shown below for a map consisting of five vertices.
0 0 10 0 10 10 0 10 5 5 --- 0 1 1 2 2 3 3 0 0 4 1 4 4 2 4 3
The vertices are listed as X Y coordinate pairs. The edges are listed as a pair of (zero-indexed) vertex indices. Edge costs are calculated as the 2D Euclidian distance between the two vertices, which will indeed satisfy the triangle inequality as described above.
As a simplification of the above format, you may ignore all edges and assume the graph is completely connected, giving an instance of the classic Travelling Salesman problem, rather than the modified version. Implementing the modified version described here with roads as given in the file will give you 5 extra credit points on this portion of the project.
Your program should then calculate/approximate an optimal tour of the nodes and output the order that the vertices are visited and the total cost of the tour.
In addition to the report, you must include a short README.TXT file that explains how to compile and/or run your code. If you are using a compiled language (C, C++, Java, C#, Assembly, etc), you must include a Makefile build your code.
Your final submission of your assignment will include the following things:
You must ensure that all required parts of your project are committed to your Git repository and pushed to GitHub before the assignment is due. It is highly suggested that you view your GitHub repository in a web browser after pushing your code to ensure that it has been submitted properly.
If you implement an approximation algorithm for the project, you may also opt in to the extra credit tournament. In this tournament, you will be competing against all other students who also opt in for the fastest (by wall clock runtime) and most optimal solution to the problem described. The student/group with the fastest, most optimal solution will receive 5 extra credit points (10% of this portion of the project) with all other students/groups participating receiving less based on their performance.
The instructor reserves the right to allow for multiple submitted projects to receive the full extra credit for this portion, even if they do not have identical performance characteristics or identical optimality of their solutions.
Last modified Monday, 22-Nov-2021 12:21:08 EST