CS 252: Algorithms
Problem Set #3
Graphs and greed
- Consider the graph G = (V, E)
where V = {1, 2, 3, 4, 5, 6, 7, 8} and
E = {(1,2), (8,1), (3,2), (5,3), (5,6), (8,4),
(3,4), (3,8), (4,7).
- Assuming G is an undirected
graph, show the order in which the nodes will get visited
if you do a breadth-first search starting at node 1. Whenever
you have a choice between nodes to visit next, break the tie
using the smallest numbered node.
- Assuming G is an undirected
graph, show the order in which the nodes will get visited
if you do a depth-first search starting at node 1. Whenever
you have a choice between nodes to visit next, break the tie
using the smallest numbered node.
- Assuming G is a directed
graph (so, for example, there's an edge going from node 8 to node 1,
but not from 1 to 8), show a topological sort.
- Consider the set of time intervals {8-13, 0-2, 5-7,
8-10, 12-17, 0-4, 1-6, 15-16, 3-9, 11-14}. Show the optimal
schedule that results when you apply the algorithm developed in
section 4.1 (page 118) of your textbook.
- Consider the set of (duration, deadline)
pairs {(3,5), (3,8), (1,16), (2,3), (6,14), (1,7).
Show the minimum-lateness schedule provided by the algorithm developed
in section 4.2 (pages 127-128).
- Do problem 2 on page 107.
- Do problem 3 on page 107.
- Do problem 7 on pages 108-109.