Algorithm Design-Homework 1 Solved

Exercise 1
You are given a long string of letters, w = (w1,...,wn). You are interested in the longest palindrome, i.e. the longest sequence P = (wi,...,wj) that is the same forwards and backwards, meaning (wi,wi+1,wi+2,...,wj−1,wj) = (wj,wj−1,wj−2,...,wi+1,wi).

1.   Give an algorithm that in O(n2) time outputs the longest palindrome, and prove its running time.

2.   Give an algorithm for the case that the palindrome does not have to be a continuous subsequence of w, i.e. the case that it is any sequence P = (wi1,wi2,...,wij) for which (wi1,wi2,...,wij) = (wij,wij−1,...,wi1) and i1 < i2 < ··· < ij. Show that the algorithm solves the problem in time O(n3).

Exercise 2
You are organizing an event where investors can meet founders of young startups during an evening of interesting presentations and good food. You plan to equip the room with round tables of at least three people each, and to enable fruitful conversations, you plan on arranging the seating such that each investor i ∈ I has only founders f ∈ F as neighbors and vice versa. At the same time, since you know the interests of each investor, you have narrowed down the good pairs (i,f) into a list P ⊆ I ×F. Design a flow network N such that finding a maximum flow in N solves the problem of whether it is possible to find a seating arrangement with only good pairings. Make sure you give a formal definition of the vertex and edge set of N, and show the correctness of your construction.

Exercise 3
As a freelance programmer, you work via a website that offers projects. The website has n projects p ∈ P that currently interest you, but in order to work on each, you need to have a certain credit score cp to demonstrate the suitability of your skills. Your current score is C. However, working on each project will also influence your credit by some amount bp (positive or negative), so after doing one project, your suitability for some of the others might have changed. You can assume that for any p, cp + bp ≥ 0. Give an algorithm that finds out whether you can do all n projects in P in some order, or not. Your algorithm must run in time O(nlogn). Prove your algorithm’s correctness and running time.

Exercise 4
You are tasked with finding the best COVID-19 cure. So far, n candidates have been developed, with codenames c1,c2,...,cn. To test a single cure, you can add a small amount of it to a vial containing a viral solution. All of them are somewhat effective, but might require a different dose to kill the virus: for example, it could take a4 = 42 units of c4 but only a31 = 6 units of c31. After putting a certain amount of a cure in a test vial, to decide if the virus has been eliminated you need to perform a complicated test which requires rare and expensive reagents. Since the world will need a very large amount of the cure, you want to find the most effective one with high precision: i.e., you want the cure ci ∈ {c1,...,cn} such that ai is minimal. Specifically, you already know that d units of any cure will kill the virus and want to find the best one. Describe an algorithm to solve this task, using as few tests as possible.

1.   Find a deterministic algorithm that uses O(nlogd).

2.   Find a randomized algorithm that uses O(n + logn · logd) tests.