CompSci 260 - Fundamentals of the Design and Analysis of Algorithms - Winter, 2020 (Dillencourt)
Final Exam topics.
The syllabus for the final exam is:
- All topics on the syllabus for the first two midterms.
(This material is not repeated here.)
- Material from chapters 7 and 8 in the text, corresponding to class
notes 7 and 8. The relevant topics are listed below.
The final is cumulative, in the following sense.
There will definitely be problems covering the new material
(the material from notes 7 and 8).
You should be prepared for questions on earlier topics as well.
You should be prepared to be demonstrate knowledge of and be asked
about the following topics.
- Network flow (Notes 7 up through and including page 7-17.
This corresponds to Sections 7.1 and 7.2 in the text
plus the first two paragraphs of Section 7.3 and the accompanying figure.)
- Definitions:
- Flow network,
(know the difference between the
actual definition and the additional assumptions that we are making.)
capacity, source note, sink node.
- Flow, capacity conditions, conservation conditions, value of a flow.
Notation for value of a flow (|f| is the notation for the value of the flow f.)
Be sure that you understand the difference between a flow and the value of
the flow.
- Maximum flow problem
- Residual graph, augmenting path.
- s-t cut, capacity of a cut.
- Ford-Fulkerson max-flow algorithm.
- Max-flow min-cut theorem. In particular:
- If there is an s-t cut C and a s-t flow F, and if the capacity
of C and the value of F are equal, then C must be a minimmum-capacity
cut and F must be a maximum flow.
- Given a max flow f, how to find a cut with capacity equal to the
value of f. (Slide 7-16 of the notes.)
- NP-completeness (Notes 8, including the two sets of additional notes.
This corresponds to the first four sections of Chapter 8 in the text plus
selected examples, discussed in class, that appear later in the chapter.)
- Decision problems.
- Polynomial-time reducibility
- The classes P and NP
- NP-completeness
- Proving problems NP-complete
Last modified: March 24, 2020