CSCI 385 Spring 2023
Advanced Data Structures and Algorithms
Archived Class
Charles Cusack
Computer Science
Hope College
Main
Schedule
Grading
Gradebook
Homework

Policies
College
    Policies
Advice

Notes
Programs
Tutorials

CSCI 112
CSCI 125
Others

Admin

Homework 6

Details

  1. (6+4+2 pts) Apply the Ford-Fulkerson algorithm to find the maximum flow of the following network.
    Do not forget to:
    1. Show all of the intermediate steps (copy this graph into your file and/or print it multiple times to make it easier!)
    2. Draw the maximum flow and give the value of the maximum flow.
    3. Specify the minimum cut (i.e. give the set X).
  2. (6 pts) IDAA 10.2.10 (page 372).
    Explain how to construct the appropriate graph and explain what a maximum flow tells us about the answer to the question.
    Make sure you clearly explain your solution!
  3. (6 pts) IDAA 10.3.1 (page 378)
    Make sure to fully justify your answer.
  4. (6 pts) IDAA 10.3.10 (page 380)
    To clarify, it is looking for a tiling in which the lower left and upper right squares are empty, but the rest of the board is covered. Looking at a picture of a chess board might help. Make sure to prove your answer.