MTAT.03.286: Design and Analysis of Algorithms University of Tartu

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Hi! I have Design and analytics of Algorithm's midterm exam tomorrow, so I would like to hire a person who can be available at 12:00 in Estonian time.

The questions will be related to minimum spanning trees, network flow and its applications (including Ford-Fulkerson and Edmonds-Karp algorithms), divide-and-conquer (including Fast Fourier Transform), and randomized algorithms, etc. I can share some materials as well.

 

MTAT.03.286: Design and Analysis of Algorithms University of Tartu

Homework assignment 2

Due date: October 19, 2021

1. 30 points. Find a maximum flow between s and t in the following network by using EdmondsKarp algorithm:

s

a

b

c

d t

2

5

4

10

3

6

5

4

1

Demonstrate the main steps in the algorithm. Show all minimum cuts. How many different

minimum cuts can you find?

2. 35 points. You are given a maximum integer flow function f : E → N ∪ {0} in the flow

network N (G(V, E), s, t, c), where G is a finite directed graph, and c : E → N is an integer

capacity function. The capacities of the seven edges e1, e2, · · · , e7 are increased by 1 each. It is

required to find a maximum flow in the new network. Describe an algorithm with complexity

O(|E|) that does that, and prove its correctness.

3. 35 points. The group of n students participates in the sports competition. There are

four sports teams: the basketball team that has m1 vacancies, the soccer team that has

m2 vacancies, the cycling team that has m3 vacancies, and the running team that has m4

vacancies. Denote m = m1 + m2 + m3 + m4. Each student chooses a subset of teams that

he/she is capable to participate in.

Propose an algorithm that assigns the students to the teams, under the following conditions:

ˆ Each student participates in at most one team.

ˆ The algorithm can only assign the student to the team that he/she has selected.

ˆ The number of students that are assigned to each team is equal to the number of vacancies.

If there is no suitable assignment of students to the teams, the algorithm will output an

appropriate message.

Prove the correctness of the proposed algorithm. The required time complexity is O(n · m).

4. Bonus: 20 points. Let N (G(V, E), s, t, c) be a flow network. Consider two sets of vertices

S1 and S2, where

{s} ⊆ S1 ⊆ V \ {t} and {s} ⊆ S2 ⊆ V \ {t} .

It is known that both (S1 : S1) and (S2 : S2) are minimum cuts in N . Define sets of vertices

T1 = S1 ∪ S2 and T2 = S1 ∩ S2. Prove that both (T1 : T1) and (T2 : T2) are minimum cuts

too.

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