Honors Discrete Chapter 8 Test Review Guide
KEY TERMS:NO straight definition questions on the test, but apply them in a problem.
Arc-Set
Backflow Algorithm
Critical Path
Critical – Path Algorithm
Critical Time
Cycle
Decreasing – Time Algorithm
Digraph
Incident To/ From
Indegree
Independent Tasks
Optimal Schedule
Outdegree
Path
Precedence Relation
Priority List
Processing Time
Project Digraph
DIGRAPH: Students should be familiar with the key elements of digraph and identify them
For Each Digraph - Example Problems:
Find vertices that are incident TO or incident FROM. (list all vertices)
- A is incident TO…
- B is incident FROM …
- E is incident TO …
- D is incident FROM …
- C is incident FROM …
Find INDEGREE and OUTDEGREE
Find a PATH or CYCLE
- Find a CYCLE starting at A
- Find a CYCLE starting at A of length 5
- Find a PATH from E to D
- Find a PATH of length C to B of length 4
Digraph Word Problems:Use incidence to identify the relationship between vertices.
HW: p. 302 #13 and 16 (One Way v. Two Way Streets AND Wins and Loses)
Calculations about Finishing Time and Idle Time:
For tasksA(10), B(7), C(11), D(8), E(9), F(5).
(1)If 4 processors had a finishing time of 16, what is the total idle time?
(2)If 3 processors had a finishing time of 17, what is the total idle time?
(3)What must the finishing time be greater or equal to if there were 2 processors?
(4)What must the finishing time be greater or equal to if there were 4 processors?
PROJECT DIGRAPHS: Remember the START and END.
(1)Draw the project digraph from description:
There are 6 computer programs to complete listed in order of time to complete A(9), B(7), C(7), D(5), E(4), F(4). Both 4-minute programs must be completed before starting both 7-minute tasks, and the 9-minute program must be completed before the 5-minute.
(2)Draw the project digraph from a table
Task / Precedence RelationsA / G→A
B / C→ B
C
D / A→ D, E→ D
E / F→ E
F / G→F, C→ F
G
Task / Precedence Relations
A
B / A → B
C / E →C,F → C
D / A → D
E / B →E, D→ E
F / B →F,D → F
PRIORITY LISTS: FIND THE SCHEDULE AND FINISHING TIME OF A PROJECT
Option #1: GIVEN A PRIORITY LIST
Option #2: DECREASING TIME ALGORITHM:
- PRIORITY LIST = DECREASING order of PROCESSING TIMES
Option #3: CRITICAL PATH ALGORITHM:
- Find Critical Time project digraph and individual tasks
- State the Critical Path or Critical path for a specific vertex
- PRIORITY LIST = DECREASING order of CRITICAL TIMES
PROJECT DIGRAPH #1:
#1: Given Priority List: A, B, C, D, E, F, G, H, I
PROJECT DIGRAPH #1: continued
#2: Decreasing Time Algorithm
Decreasing Time Priority List: ______
Decreasing Time Priority List: ______
#3: Critical Path Algorithm
Critical Time Priority List: ______
Critical Time Priority List: ______
PROJECT DIGRAPH #2:
#1: Given Priority List: H, G, F, E, D, C, B, A
#2: Decreasing Time Algorithm
Decreasing Time Priority List: ______
#3: Critical Path Algorithm
Critical Time Priority List: ______
SCHEDULE INDEPENDENT TASKS: Find an optimal schedule using (1) 2 Processors, (2) 3 Processors, (3) 4 Processors
#1: A(9), B(7), C(6), D(5), E(3), F(12), G(8), H(10)
#2: P(11), Q(7), R(5), S(8), T(16), U(2), V(1), W(6), X(12), Y(4)
Identify if a schedule is illegal or not (Check Precedence Relations – task cannot be started until ALL prerequisites have been completed)