Description
1. [60%] Implement the following 0/1 knapsack algorithms. 1) [10%] Implement the brute force method to solve the 0/1 knapsack problem. Show the final solution. Specifically, (a) print the total profit and weight; and (b) print the selected items. 2) [20%] Implement the four greedy algorithms discussed in class. For each algorithm, (a) print the total profit and weight; and (b) print the selected items together with their profits and weights. 3) [30%] Implement the dynamic programming algorithm for 0/1 knapsack: (a) print the total profit and weight; and (b) print the selected items. Compare the result to the result you have got in 1). If you have implemented the dynamic programming algorithm correctly, the total profit achieved by this backtracking method must be equal to that achieved by the brute force method implemented in 1). Implement each algorithm as a separate program. Pass input file, knapsack.txt, to each program. Your knapsack.txt should include the number of elements in the first line, weights in the second line, profits in the third line, and knapsack capacity in the fourth line. Hence, it should look exactly as the following sample data (This just a sample. Your programs should work correctly for any input.): 3 5, 20, 10 50, 140, 60 30 2. [30%] Implement Dijkstra’s algorithm to find the shortest path from s to all the other nodes in a directed graph. Use the following graph as a sample. (Your program should work correctly for any input though.) 3. [10%] 10% is reserved for good coding style, meaningful comments, and correctly following the submission guidelines below. Submission Guidelines: ○ Please submit a tar.gz file with the below naming convention. _project3.tar.gz ○ Make sure you include all the source code files as mentioned below: ○ Your makefile should be able to compile all the source code and generate .out files. make sure you makefile will not run the executable files. ○ You should run and test your code in remote.cs.binghamton.edu and make sure it works there without any issues. You code will be evaluated in the same environment. If code does not run on remote server the TA will not run it on any other environments. ○ Wrong directory structure and presence of unnecessary files will cost you points. ○ Do not create unnecessary output files, header files, printf statements that are not asked to create. ○ Please do not assume anything, email questions to the TA (avora4@binghamton.edu), and see him during his office hours for any required clarifications. Important Policies: ● All work must represent each individual student’s own effort. You are not allowed to refer to any online or offline source. If you show your code or any other part of your work to somebody else or copy or adapt somebody else’s work found online or offline, you will get zero and be penalized per the Watson School Academic Honesty Code (https://www.binghamton.edu/watson/about/honesty-policy.pdf). To detect software plagiarism, everybody’s code will be cross-checked using an automated tools. On the first violation, you will receive zero point for this project, and have to fill in and sign the official form that will be kept by the Binghamton University. On the second violation, it will be reported to the Watson School Committee for Academic Honesty for an official hearing. ● Your code will be compiled and executed. If your code does not compile or produce any runtime errors such as segmentation faults or bus errors, you will get zero. Before submitting your code, run it in a Linux machine (e.g., a remote machine) to remove any such errors. You can use “valgrind” (https://valgrind.org/) to debug memory errors, such as segmentation faults or bus errors. Note that robust programming is essential for developing high quality software. If you are curious about robust programming, check this out: https://nob.cs.ucdavis.edu/bishop/secprog/robust.html ● You are supposed to figure out how to implement this project. The instructor and TA will be more than happy to explain fundamental algorithms covered in class; however, they will not teach you how to implement them or help you to make any kind of decision. Neither will they read or debug your code. By the same token, the instructor and TA will not take a look at an emailed code. If you have questions about general C/C++ programming or Linux, use Google search, which will be much faster than asking the TA. (Don’t copy from the Internet though.) ● If myCourse says your submission is late, than it’s late. You can submit your code with late penalty 10% for each day upto 3 days max. After 3 days your submission won’t be accept.
