Unformatted text preview:

CS333: Programming Assignment 2 Instructor: KD Kang TA: Eric Sabbah All programming must be done using C or C++ in Linux where your code will be tested. Create a tar file that includes (1) source code files and a (2) readme file that clearly describes how to compile and run your code. Submit only the tar file through the Digital Drop Box in Blackboard. The name of the tar file should be yourlastname_prog2.tar (Do not use special characters like #, @, or &, as these have caused Blackboard problems in the past). 1. [60%] Implement Floyd's all pairs shortest path algorithm (pages 97- 105). 1) Represent the following graph in an adjacency matrix and store it as a text file to be used as a sample input to your program: 1 2) Read in this file containing test data. Your code will be tested by the TA with different matrices later. 3) Prompt the user to ask which start and end vertices he/she wants to know about. 4) Output the shortest path for the start and end nodes specified by the user, as well as the total distance (weight) of the shortest path. For example, if the user says node 1 to node 5, the path should be v1->v4->v5, and the length is 4. 2. [20%] Implement the dynamic programming solution to solving the binomial coefficient problem (Algorithm 3.2) Prompt the user to ask n and k to compute the binomial coefficient. Compute and show the corresponding binomial coefficient. Note that you are required to implement Algorithm 3.2. You will get zero if you implement a divide-and-conquer approach to computing a binomial coefficient, similar to Algorithm 3.1. v1 v2 v3 v4 v5 3 2 2 4 1 3 9 3 5For both parts of the assignment, keep both time and space efficiency in mind, and once again, 20% of the grade will be based on good style and meaningful comments. • All work must represent your own, individual effort. If you show your code or any other part of your work to somebody else or copy or adapt somebody else´s work, you will get zero. All students involved in any violation of the Student Academic Honesty Code described in http://www.binghamton.edu/watson/Watson_Academic_Honesty_Policy.pdf will get zero with no exception. • Your code will be compiled and executed. If your code does not compile or produce any runtime errors, you will get zero credit. • The instructor will not read or debug your code. The TA is the best person to discuss programming assignments. • The TA or instructor will not take a look at an emailed code. If you need help, show your code to the TA during his office hours. Also note that the TA will not do programming or debugging for you. He will only help you understand algorithms to be implemented and answer basic questions related to


View Full Document

BU CS 333 - Programming Assignment 2

Download Programming Assignment 2
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Programming Assignment 2 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Programming Assignment 2 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?