Reference no: EM132468448

Complete the below exercises:

Assignment

Part a) Compare Approach: In your own words discuss the differences and similarities between Divide and Conquer, Dynamic Programming, and Greedy Approach design approaches. What type of problems are well suited or not for each approach and why. Give specific examples to support your discussion. The comparison should be about two pages in length (max 12-point font) not including any tables or charts and must be written in essay format. Note that work which is not written in student's own words will not earn credit. Changing words to their synonyms is not sufficient and often changes the meaning of the context or makes it read as garbage because technical terms are changed incorrectly.

Part b) Graph: Given the below graph,

a. give the graph representation in adjacency matrix and adjacency list
b. using v1 as starting point, what is the order of vertices visited using DFS and BFS
c. In video explain your answers

Part c) Write solution to the below exercise in Python programming language. Program file should have your name at the top in comment, with short description of what is implemented in that file. Make sure your file(s) have appropriate names as indicated in each exercise. Program should write output to the Console and have hard coded input in main.

Note: Submitting wrong files or in the wrong format or corrupted files will not be accepted nor will any re-submission be allowed for any such mistake.

Floyd (Dynamic prog): Implement the Floyd algorithm we went over in class (textbook's p. 108 A3.4). Then write a test program and code the below graph to pass to the Floyd algorithm method you implemented. Your program should print to the console the contents of P (matrix for shortest path) and D (matrix for intermediate vertex) arrays. In the video, explain how Floyd works and your implementation and run the program.

Then explain how to read the P and D arrays to get the shortest path value and the intermediate vertices on that path using the path from V3 to V1 and V5 to V4 for your explanation.

Part d) Optimum Binary Search Tree: Given the below trees and probabilities determine which is the optimum tree. Show the calculations.

P1=0.5, P2=0.1, P3=0.3, P4=0.1

Part e) Schedule (Greedy): Manually solve the below scheduling problem instance by tracing through A4.4 as shown in class. Then determine all the feasible sequences for max jobs allowed. Discuss in writing what is the optimal sequence and the maximum total profit, and explain why. Document all your answers. In the video explain how the algorithm A4.4 works and your solution to the exercise.

Job	Deadline	Profit
1	2		76
2	2		52
3	1		80
4	4		68
5	5		35
6	2		90
7	3		32

Question 2. Record a video about 15-20min long discussing the above exercises as indicated in their instructions.

Attachment:- Assignment.rar