Consider the array A[1...n] of n non-negative integers.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Problem 2 (20 points)

Consider the array A[1...n] of n non-negative integers. There is a frog on the first index of the array. In each step, if the frog is positioned on the ith index, then it can hop to any of the indices i,...,i+A[i] (so the frog can at most hop to the index i + A[i]).

Develop a greedy algorithm to determine the minimum number of hops necessary so that the frog can reach the last index, i.e., the nth index. You must fully explain your algorithm.

Your algorithm must return -1 if the frog cannot reach the last index.

Problem 3 (20 points)

Given a directed weighted graph G with no cycles, develop an algorithm to find the weights of all longest paths from one source vertex s to the other vertices in G in O(|V|+|E) time.

A longest path from u to v is a path of maximum weight from u to v.

Problem 4 (20 points)

Consider a directed graph G = (V,E) where each edge is colored in either red or blue. Develop an O(|V|+|E|) time algorithm that, given vertices u and v in G, determines if there exists a walk from u to v that uses at least one blue edge (note that this walk may have repeated vertices). Justify the correctness of your algorithm and analyze the running time.

(Hint: Try to construct a new graph using an idea similar to HW9 P4.)

Problem 5 (20 points)

Consider the n points P1, P2, ..., Pn in the plane. Each point p; has the xy-coordinates p1 = cost of connecting two points pi = (xi, Yi) and pj = (xj, yj) is defined as

(xi, Yi). The

│Xi — Xj│+ │Yi — Yj\.

For example, the cost of connecting p1 =

(1, 5) and p; = (3, 4) is

|1 3|+|54| = 3.-

We want to make all the points connected such that there is a path between any pair of points. Develop an algorithm that returns the minimum cost to make all the points connected. Your algorithm must run in O(n2) time. Explain all the steps of your algorithm.

 

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of