Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Homework 4

CS535

Due Date:  October 31st, 2023

CS Department, IIT

1.  Suppose we are given a sequence of medical tests, conducted after giving a medicine and representing blood pressure values b1 , b2 ... bn.  To evaluate the effectiveness of the medicine, the doctor wants to detect a falling trend.  A trend is a subsequence (not necessarily contiguous) of values at time instances i1  < i2 < ... < ik . Devise an algorithm to find the longest falling trend, i.e. a sequence of values bi1 bi2 ... bij such that bir ≥ bir+1 and ir < ir+1 .

2.  Given aset of points in the plane (two dimensional Euclidean space), the goal is to determine a minimum cost travelling salesman tour that starts at the topmost point and returns back in a monotone traversal of the other points. In a monotone traversal the tour can only travel down and then back up to reach the starting point. The cost of going from point p to q is the Euclidean distance between the two. Design an algorithm to find such a tour.

3.  Given a directed graph with edge distances, design an algorithm to determine the all-pairs shortest path problem that tries out paths of hop length  (number of edges in the path) 1,2 etc.  Write the recurrence and analyze the complexity.

4.  Alice and Bob play a game of guessing number.  Alice picks a number between 1 and n.  Bob each time guesses a number k.  If k is the picked number, the game is over.  If not, Bob gives Alice k coins and Alice tells Bob whether k is too high or too low.  Given n, how many coins does Bob need to finish the game? Write the recurrence and analyze the complexity.