1. (a) (3 points) Consider the following directed graph with cost on the edges. 1 2 4 8 3 Show the run of Dijkstra's algorithm for shortest path problem starting from 1. Break all ties by picking the vertices with the lowest index (i.e., 3 before 5) (b) (4 points) Consider the following variation on the Interval Scheduling Problem. You have a processor that can operate 24 hours a day, every day. People submit requests to run daily jobs on the processor. Each such job comes with a start time and an end time; if the job is accepted to run on the processor, it must run continuously, every day, for the period between its start and end times. (Note that certain jobs can begin before midnight and end after midnight; this makes for a type of situation different from what we saw in the Interval Scheduling Problem.)