CS代考 Algorithms, November 2022 at CIS – Homework 1

Algorithms, November 2022 at CIS – Homework 1

Please answer the following questions and submit a pdf file to neoscholar education platform

Copyright By PowCoder代写 加微信 powcoder

Suppose you have 2 items: gadgets and widgets. To make a gadget requires 30 minutes of
buying material and 20 minutes to put the material together. To make a widget requires 15
minutes of buying material and 30 minutes to put the material together. The profit on a gadget
is 40RMB and the profit on a widget is 50RMB. The business operates for at most 8 hours
per day. Write a linear program to determine how many gadgets and widgets should be made
to maximize profit, and determine what the maximum profit is.

You are given a set of r triples

2 Rn ⇥ Rn ⇥ R, as well as a number t � 0.

a) You would like to find an n ⇥ n matrix A such that

� ci for all i and such thatP

j=1,…,n |Ai,j |  t or report that no such matrix A exists. Show how to solve this

problem in polynomial time.

b) Now you would like to find an A satisfying the requirements in part a, but among all such
A, you would like to output the one for which the maximum, over i, of

, is minimized.

Show how to solve this problem in polynomial time.

Give an example of a linear program with d variables, O(d) constraints, and 2d vertices. Please
explain your construction.

Suppose you are running Seidel’s algorithm in 2 dimension and there are n constraints and the
current optimum is at point p, and one of the n constraints is randomly removed. What is the
tightest upper bound on the probability that the optimum point changes because of this?

程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com