algorithm concepts dynamic programming

CSCI 651 Algorithm Concepts Assignment 2

1. Rod Cutting Problem:

Given a rod of length n inches and an array contains prices of all pieces of size smaller than n. Determine the maximum value obtainable by cutting up the rod and selling the pieces. For example, if length of the rod is 8 and the values of different pieces are given as following, then the maximum obtainable value is 22 (by cutting in two pieces of lengths 2 and 6).

Length 1 2 3 4 5 6 7 8 Price 1 5 8 9 10 17 17 20

a. Mention all the known algorithms/approaches to solve the problem. Discuss pseudo-code of each approach.

b. Differentiate all the above algorithms mentioned and explain complexities of all approaches.

c. Implement Rod Cutting problem using Dynamic programming in any programming language. Take the above array and values as input to your program.

[30 Marks]

2. You need to implement a graph data structure using an adjacency list representation and adjacency matrix. The code will prompt the user to the following task:

a. Enter the details of the graph (Edges, Vertices and Weight) b. Create two functions for Adjacency matrix and Adjacency List c. Ask for either to print Adjacency matrix or Adjacency List d. Create and print the Adjacency list representation and Adjacency matrix when it is done.

It is up to you to decide how your program will collect all the information that is necessary to describe the graph. [30 Marks]

3. Prim’s Algorithm (Minimum Spanning Tree in Graph) a. After creating the graph in above question, the program will prompt the user for a random

node in the graph. The program will then use Prim’s algorithm to find the minimum spanning tree in the graph. The output should be in a table format as shown below and also calculate Minimum Cost of the Spanning Tree.

b. Implement Prim’s Algorithm using both Adjacency List and Adjacency Matrix representation.

c. Compare the complexities of your Prim’s program using Adjacency List and Adjacency Matrix.

Run your program using the following graphs as sample input. Assume the weights represent the distance between nodes. [40 Marks]

Graph 1

Graph 2

Submit the above items by the due date via Blackboard. A detailed reported discussing your implementation along with results of running the code against the examples given (screenshots must be included). A detailed readme file that should explain how to run the code in a separate file. All your implemented code, also in separate files.

Edges in Spanning Tree Cost A->B 1