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 Relations
A / 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)