ALGORITHM DESIGN Exercise Sheet 1 Provide an algorithm that computes the gˆi and ˆbi in polynomial time. Prove its correctness and analyze its run time.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

I cannot solve the following 4 questions.

 

ALGORITHM DESIGN

Exercise Sheet 1

Lecturer: Prof. Stefano Leonardi Academic Year 2021/2022

Teaching Assistants: November 18, 2021

Philip Lazos, Rebecca Reiffenhauser ¨ Due Date: December 5, 2021

General Terms: You can work on the exercises in teams of two people, and hand them in accordingly. However,

make sure that each one of you has fully understood every solution you present. Do not copy any work from other

students, the internet or other sources, and do not share your work with others outside your team. If at any point, any

part of the exercises you hand in is apparent to be a copy of other work, this will result in the following consequences:

All of your exercises, previous as well as upcoming ones, will be treated as if you did not hand them in at all, and

you will have to participate in the written exam to make up for this. Please note that there will be no exception made,

even if you are the original author of work someone else copied, or if your exercise partner is the one responsible.

Therefore, please make sure to only choose a partner that you trust, and do not hand out your exercise solutions to

others.

Late Policy: If you hand in your exercises after the due date, each day that you are late will result in a discount to

your score, i.e. you will only receive 90% of the points if you are one day late, 80% on the second day after the due

date, and 70% on the third. If you are late by more than three days, the assignment will get zero points in total.

Formal Requirements: Please typeset your solutions (11 pt at least), and state the names of both team members at

the beginning of each sheet you hand in. Make sure to name the exact exercise each part of the solution refers to,

otherwise it will not be graded. Please start a new page for each main exercise in the assignment (i.e. exercise 1,

2, etc., but not for each subquestion in them). Make sure your solution takes no more than one page for each main

exercise (plus at most one extra page for the code, if an implementation is required). Everything after the first page

will not be taken into account. So, for example, when the assignment has four exercises, please hand in four pages,

one for each exercise. All solutions have to be sent via email to

lazos@diag.uniroma1.it or rebeccar@diag.uniroma1.it

Office Hours: There will be special hours for questions about the exercises announced via the piazza site. Presumably,

this will take place in form of a zoom meeting due to the Covid19-measures.

Exercise 1

Your birthday is coming up. You have n relatives R, who would each be willing to spend at most some value vr ∈ R+

on your gift, for any r ∈ R. All of them are asking you for your wishes.

However, these people have different proximity to you in the family tree, given by the length dist(r), r ∈ R of a

path from the vertex representing you, to the one representing the respective relative r. (You can assume you are the

root of the tree, your closest relatives will be connected to you via an edge (length 1), the second-closest via a path of

two edges (length 2), and so on.) Now, to not be untasteful, if dist(r) < dist(r

0

) you should never ask relative r

0

for a

more expensive gift than r, i.e. the prices pr, r ∈ {1, . . . , n} of presents that you suggest should satisfy the following:

if dist(r) < dist(r

0

), then also pr ≥ pr

0 . To make sure relative r will actually buy the present you suggest for price pr,

of course you must also ensure that pr ≤ vr - if not, r will not buy the gift, and you collect value 0.

a) Give an algorithm (short description!) computing the maximum-possible, accumulated value of all your gifts in

time polynomial in n. Prove its correctness and analyze its running time.

b) Solve the problem via a short(!) Python program, and provide the according code as well as the output number

for the following instance:

• Distance 1: v1 = 15.2, v2 = 9.4, v3 = 11.1

• Distance 2: v4 = 9.7, v5 = 12.2, v6 = 7.5, v7 = 10.8

• Distance 3: v8 = 5.2, v9 = 6.3, v10 = 5.6, v11 = 10.2

• Distance 4: v12 = 4.9, v13 = 2, v14 = 3.5, v15 = 2.9

• Distance 5: v16 = 1, v17 = 6.4, v18 = 4.6, v19 = 2.1

1

Exercise 2

You are the owner of a large chain of franchise shops, and you would like to expand to a new city. The blocks in your

city make an n × n grid. However, although your products are awesome and in high demand, the city will not allow

you to open a shop in each block. Instead, for every row of blocks i, you are are given a number ri that limits the

maximum number of shops opened there - and for every column j, there also is a maximum number cj .

a) Find the maximum number of franchise shops you can legally open in the city. To do so, model the problem as a

flow network. Then, describe how to get the right answer using Ford-Fulkerson, and prove the correctness of your

construction.

b) To really become known, you would like to make sure that people driving through the city have a good chance

at seeing at least one of your shops. Therefore, at least one shop should be placed every few streets. More exactly,

for row {1, . . . , 5} of the grid, there should be at least one block in these rows that has a shop, and the same should

hold for row {6, . . . , 10}, et cetera. Conversely, for every five columns of the grid, you want to ensure also at least

one shop. Adjust your network such that it can be used to determine whether this requirement can be fulfilled. Here,

you are allowed to not also pose upper bounds on the capacity on each edge, but also state a lower bound on the

minimum amount of flow you want on the edge. Give a variation of the Ford-Fulkerson algorithm that solves the

problem for this richer type of network. Prove that together, your network and the algorithm solve the decision

problem described above, while also maximizing the number of shops in case of a ’yes’-instance.

Exercise 3

You are tasked with creating a competitive programming squad, selecting students from schools around Italy. There

are n schools in total and every school i has gi ≥ 0 girls and bi ≥ 0 boys. You need to select exactly k students from

each school, but be careful: the total number of girls and boys need to be as close as possible. In particular, you need

to select ˆbi boys and gˆi girls from each school i, respecting that 0 ≤ gˆi ≤ gi

, 0 ≤ ˆbi ≤ bi and gˆi + ˆbi = k, in order to

minimize:











Xn

i=1

gˆi −

Xn

i=1

ˆbi











.

You are guaranteed that for every school i, we have bi + gi ≥ k.

a) Provide an algorithm that computes the gˆi and ˆbi

in polynomial time. Prove its correctness and analyze its run

time.

Exercise 4

The grinch is planning to make all the city’s kids sick the day before christmas, by overfeeding them with sweets.

Each kid has a set of sweets they like, and the grinch would like to give them all of those. He needs to give each kid

some bags of sweets from Santa’s supply that cover their needs, but also wants to minimize the number k of times he

has to steal the most popular bag: if more than k of the same kind are missing, Santa might notice... More formally,

from a given set S of sweets, bag types B1, B2, . . . , Bn ⊆ S and preferred sets of sweets K1, K2, . . . , Km, you need to

find a set of bags Bˆ(j) ⊆ {B1, B2, . . . , Bn} for each kid i such that:

Ki ⊆ ∪B∈Bˆ(j)B.

Moreover, for all bags Bi

, you need to make sure that

|

n

Bˆ(j)|Bi ∈ Bˆ(j), j ∈ {1, . . . , m}

o

| ≤ k.

Planning this is taking the grinch a long time. Prove that indeed, the problem is NP-complete.

Hint: For your reduction, use a version of SAT where every clause has either all positive or all negative literals, which

is an NP-Complete problem (i.e., all clauses are of the form (x1 ∨ x2 ∨ . . .), or (x1 ∨ x2 ∨ . . .)).

2

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of