<strong> <br><a href="http://www.unlv.edu/">University of Nevada Las Vegas </a> <br><a href="http://www.egr.unlv.edu/"> Howard R. Hughes College of Engineering </a> <br><a href="http://www.cs.unlv.edu/"> School of Computer Science </a><br> <a href="http://www.cs.unlv.edu/~larmore"> My Home Page</a><br> </strong> UNLV CSC 302 Spring 2013 Assignment 8

CS 302 Assignment 8

Due date: Thursday, May 2, 2013, 10:00 PM in class.

All written assignments must be handwritten (not typed or printed from a computer file) in your own handwriting, on 8.5 by 11 inch paper, or on A4 paper. Write your name on each sheet, and do not fold the pages or crimp the corners. (You may use a paper clip or a staple.)
Turn the pages in to me or to the graduate assistant on the due date.
These problems can all be worked using either Divide and Conquer or Dynamic Programming.
Do not hand in any program that solves any of these problems. The algorithms should be handwritten on paper, not typed.
  1. Greatest Weight Independent Subsequence. We define an independent subsequence of a sequence x to be a subsequence which contains no two consecutive terms of x. Write an algorithm which finds the greatest total of any independent subsequence of a given sequence.
  2. Median of Two Sorted Lists. You have two sorted lists, one of length n, the other of length n+1. Design an algorithm for finding the median item of the union of those lists. For example, if the two lists are A J T V W and B C D Y, the median item is J.
    What is the time complexity of your algorithm? Faster is better.
    There are several correct answers. One of them takes O(n log n) time. Another takes O(n) time . Yet another is even faster than that.
  3. Directed Traveling Pair of Salesmen. You are given a weighted acyclic directed graph G. Two salesmen start at a source vertex s, and must end up at a target vertex t. Write an algorithm that determines the least-cost way that the two salesmen can each pick a directed path, so that every vertex is visited by at least one of them.
    Of course, there might be no solution. Your algorithm should find the best solution if there is one, and simply report that there is no solution otherwise.
    The salesmen cooperate. That is, they try to minimize the cost of the team.
    Of course, you can solve the problem by constructing every possible solution, then picking the best. Since there can be exponentially many solutions, that is not a good algorithm. It can be done in O(n2) time.
    But, can you do better?
  4. Pebble Game. You have a weighted directed graph G, with a start vertex s, and an end vertex t. Each node is colored, either red or blue.
    From every vertex, there is at least one path to t. (So the game cannot deadlock.)
    Every edge is from a red to a blue vertex, or from a blue to a red vertex.
    The game is played as follows.
    1. There is one pebble, which is initally placed at s.
    2. There are two players, Red and Blue.
    3. If the pebble is at a red vertex, Red pushes the pebble to an out-neighbor, and collects the amount of money indicated by the weight on that edge.
    4. If the pebble is at a blue vertex, Blue pushes the pebble to an out-neighbor, and collects the amount of money indicated by the weight on that edge.
    5. The pebble will eventually reach t. The winner is the player with the most money at the end.
    Design an algorithm that takes such a graph G as input, and decides whether Red wins, assuming both player play optimally.