Graphs I

View slides in full screen

Warning

The previous slides are provided as a reminder of the material seen in class. They are intended to be complemented with the vocal part and the blackboard, therefore they are not in any way a substitute of a book, nor some lecture notes. Please use the books provided in the references for the self-study.

Jutge exercises on DFS

The exercises that can be thought as variations on Depth-First Search (DFS) are the following:

• P70690 Treasures in a map (1)
• P90766 Treasures in a map (3)
• X41530 Forest
• P29033 Two colors
• P53547 Tiny bishops
• P40479 Painting a board

Jutge exercises on Topological Sort

The exercises that can be thought as variations on Topological Sort are the following:

• P14952 Topological sort
• P16249 Task ordering
• X21319 Circuit Value Problem ❗

Exercises

Once you have revised the material from this class, you can try to do the problems from the EDA ProblemSet, section 5 Graphs. In particular 5.5, 5.6, 5.12, 5.13, 5.14, 5.17, 5.18, 5.23, 5.24 . Those exercises will be solved in class in the Problem class P6.

Important

If you have doubts while solving the above exercises (after studying the material and the Problem class P6) please write me an email as soon as possible (and/or write an email to your instructor of the problem class P6).