Graphs, Games and Designs - Unit B2: Optimal Paths, Packing and Scheduling

These flashcards cover key concepts and terminology related to optimal paths, scheduling, and bin packing, helping students prepare for their exam.

What is the purpose of optimal path algorithms in network theory?

They help to find the best or most efficient route through a network, such as the shortest or longest path.

What types of problems are involved when finding paths in a network?

Existence problem, construction problem, enumeration problem, and optimisation problem.

What does the shortest path algorithm aim to achieve?

It finds the shortest distance from a source vertex to a sink vertex in a directed network.

What is a critical path in an activity network?

A critical path is the longest path through an activity network, indicating the minimum completion time for a project.

What two key components does the scheduling problem account for?

The number of workers available and the order of activities determined by their precedence relations.

How does critical path analysis help in project management?

It identifies the sequence of critical tasks that determine the project's duration, allowing for better scheduling and resource allocation.

What is a bin packing problem?

It involves packing a set of items of different sizes into a minimum number of bins of fixed capacity.

What is the first-fit packing algorithm?

A method that places each item in the lowest numbered bin that can accommodate it.

What is a protection scheme in scheduling algorithms?

It allows for adjusting the priority of activities based on their latest starting times to improve scheduling efficiency.

What is the significance of the float in project scheduling?

Float is the amount of time that an activity can be delayed without affecting the overall project completion time.