代写COMP2870 Theoretical Foundations of Computer Science II Activity sheet 3代写数据结构程序

2025.10.29 - 首页 >> Algorithm 算法

Theoretical Foundations of Computer Science II

COMP2870

Activity sheet 3

This worksheet contains a combination of formative activities (which contribute towards your learning) and summative activities (which you will complete and submit to be assessed as part of your portfolio) .

Every exercise marked with a red border is a summative exercise and must be submitted as part of your portfolio. You should use Gradescope to submit portfolio activities. In addition, you may be required to submit other activities — the module teaching staff will provide instructions.

Activities marked by (*) are advanced, and may take some time to complete.

Expectations:

1. Timeliness You should complete all of the activities in the order provided and submit your portfolio evidence on Gradescope before the completion date (Friday 24 October 2025, 5:00pm) .

2. Presentation: You should present all of your work clearly and concisely following any addi- tional guidance provided by the module staff in the module handbook.

3. Integrity: You are responsible for ensuring that the evidence you submit as part of your portfolio is entirely your own work. You can find out more about Academic integrity on the Skills@Library website. All work you submit for assessment is subject to the academic integrity policy.

Feedback: Feedback on formative activities will be provided via tutorials. Feedback on evidence submitted as part of the portfolio will be available on Gradescope.

Support opportunities: Support with the activity sheet is available in the tutorials and Maths Lunch Hour drop-in sessions. Individual support is available via the online booking system.

Statement on the Use of Generative AI (Red Category): .

For this assessment is RED according to the GenAI traffic light system. Generative AI (GenAI) tools cannot be used. The aim of this task is for you to develop and demonstrate the specific skills and knowledge covered in the taught sessions. We want you to independently develop your understanding, critical thinking skills and demonstrate fundamental skills that will be required throughout your programme. Reliance on GenAI could prevent you from achieving the intended learning outcomes and may impede your skill development.

You are still permitted to use dictionaries, thesauri, spelling and grammar-checking software to help identify and correct spelling mistakes and grammatical errors (even if they are powered by Gen AI) . However, you should not use any software to rewrite sentences or make substan- tive changes to your original text, as this would be against the rules of this category.

Failure to comply with these requirements may be considered academic misconduct under University regulations.

Expected time for completion: 3-4 hours.

Expected completion date: Friday 24 October 2025, 5:00pm

Coursework summary

These tutorial exercises cover the material from the lectures in Week 3, focussing on network flows and matchings in bipartite graphs. You are advised to carefully read and understand the lecture notes that pertain to the questions in the worksheet, before attempting to do the exercises.

Tutorial 2 of Week 3 and Tutorial 1 of Week 4 will cover the exercises on this worksheet. There will also be time to answer questions about material from the lectures.

Exercise 7 and Exercise 10 are the summative exercises for this worksheet.

Learning outcomes

On completion of this activity sheet you will have:

1. understood and found solutions to maximum flow and matching problems

2. constructed new algorithms based on similar ideas to the Ford-Fulkerson algorithm

3. understood proof of correctness details for the Ford-Fulkerson algorithm

4. practised writing clear and logically structured proofs

5. used maximum flow and matching problems to model real-life applications

Questions

1. Consider the following diagrams of network G1, with source s and sink t, where the edge la- bels denote a flow in parentheses followed by the capacity of each edge. For each part decide whether the flow is a feasible flow and justify your answer .

(a) f1

(b) f2

2. Consider the following network G2 , with source s and sink t, where the edge labels denote a feasible flow f in parentheses followed by the capacity of each edge.

(a) Calculate the value of flow f.

(b) Let S1 = {s, b} and T1 = {a, t}. Calculate the capacity of the cut [S1, T1].

(d) Is there a feasible flow with greater value than f? Explain the reasons for your answer.

3. Consider the following network G3 , with source s and sink t, where the edge labels denote a feasible flow f in parentheses followed by the capacity of each edge.

Which of the following are f-augmenting paths?

(a) P1 = s, a, t

(b) P2 = s, a, b, c, d, t

4. Consider the following network G4 , with source s and sink t, where the edge labels denote a feasible flow f in parentheses followed by the capacity of each edge.

Consider also the f-augmenting path P = s, b, c, a, t.

(a) Calculate the leeway of P.

(b) Using P, find a feasible flow with greater value than f.

5. For the following network G5, with source s and sink t, use the Ford-Fulkerson algorithm to find a feasible flow with maximum value, and prove that your answer is correct.

6. Suppose G is a network with edge capacities c : E → N, source s and sink t.

(a) Complete the following proof that: “If G contains no directed path from s to t, then the maximum value of a feasible flow in G is 0.”

Proof: Let G = (V, E) be a network, with source s ∈ V , sink t ∈ V, and edge capacities c : E → N. Suppose that there is no directed path from s to t in G . We proceed by showing that there is a source/sink cut in G with capacity 0 .

Let S be the set of vertices made up of s and all v ∈ V such that there is a directed path from s to v. Let T = V \ S .

Complete the proof by showing that [S, T] is a source/sink cut in G that has capacity 0.

(b) Consider the converse statement: “If the maximum value of a feasible flow in G is 0, then there is no directed path in G from s to t.” Is this statement true? Write a short proof if it is true or find a counterexample if it is false.

7. Let G = (V, E) be a network with feasible flow f, source s, sink t, and edge capacities c : E → N. Answer parts (a) and (b) to prove that: f is a maximum flow in G if and only if no f-augmenting path from s to t exists.

(a) Use Lemma 4.1 from the lecture notes to prove that: if there is an f-augmenting path then f is not a maximum flow .

(b) Complete the following proof that: if there is no f-augmenting path then f is a maxi-mum flow .

Proof: Suppose that there is no f-augmenting path in G. Let S be the set of vertices made up of s and all vertices in V that can be reached from s by an undirected “path” such that every forward edge has excess capacity and every backward edge has non-zero flow. Let T = V \ S .

Complete the proof by showing that [S, T] is a source/sink cut in G and that cap(S, T) = val(f) . You may use Lemma 4.2 and Corollary 4.3 from the lecture notes.

8. Consider the following graph G6 .

For each of the following subsets of edges, decide whether or not it is: (i) a matching, (ii) a maximum matching, and (iii) a perfect matching.

(a) M1 = {ab}

(b) M2 = {ab, cd, ed, fg}

9. Consider the following graph G7 .

(a) Show that G7 is bipartite by giving a bipartition of vertices (V1 , V2 ) .

(b) The maximum matching problem for bipartite graphs reduces to the maximum flow

problem for networks. Construct a network G7(′) from G7 . Then find a maximum flow in G7(′) .

10. A company has access to 5 cloud servers and 5 different tasks to perform . The table below shows which servers are capable of processing which tasks.

The company wants to complete all 5 tasks such that each server processes exactly 1 task.

(a) Draw a bipartite graph that represents this assignment problem.

(b) Find a maximum matching in the graph G that you have drawn in part (a), using the method described in Section 5.1 of the lecture notes.

You should: construct a network G ′ from the graph G you have drawn, find a maxi- mum flow f in G ′ , and then use Theorem 5.1 from the lecture notes to extract from f a maximum matching for G .