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