Questions 1) Kris is the prsedent of “The Climbing Club” . The club has n climbers, who are members of The Club. In order for them to retain their membership, they need to participate in various competitions yearly. There are m competitions each year and the j’th competition needs kj participants from The Club. Kris, trying to fulfil his president duties, asked each member to volunteer to participate in a few competitions. Let Si ? {1, 2, . . . ,m} be the set of competitions that a climber i has volunteered for. A competition assignment consists of sets S01, S02, . . . , S0n where S0i ? {1, 2, . . . ,m} is the set of competitions that club member i will participate in. A valid competition assignment has to satisfy two constraints: (i) for each club member i, S0i ? Si, that is each member is only participating in competitions that he/she has volunteered for, and (ii) each competition j has kj club members assigned to it, or in other words j occurs in at least kj of the sets S01, S02, . . . , S0n. Kris noticed that often there is no valid competition assignment because climbers naturally are inclined to volunteer for as few competitions as possible . To overcome this, the definition of a valid assignment is relaxed as follows. Let ` be some integer. An assignment S01, S02, . . . , S0n is now said to be valid if (i) |S0i – Si| = ` and (ii) each competition j has kj club members participating at it. The new condition (i) means that a member i may participate up to ` competitions not on the list Si that he/she volunteered for. Describe an algorithm to check if there is a valid competition assignment with the relaxed definition. 2) Augmenting Paths in Residual Networks. a) You are given an integral instance G of network flow. Let C be the value of the maximum flow in G. Given a flow f in G, and its residual network Gf , describe how to compute, as fast as possible, the highest capacity augmenting path flow from s to t. Prove the correctness of your algorithm. Prove, that…