Scribd
Upload
12 views

Greedy Algorithms

Uploaded by

thegeotheo
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
12 views

Greedy Algorithms

Uploaded by

thegeotheo
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 7

1

Greedy Algorithms
Greedy algorithms are a class of algorithms that make a series of choices, each of
which looks best at the moment. The basic idea is to pick the locally optimal
solution at each step with the hope of finding a global optimum. Greedy
algorithms are typically used for optimization problems.

Examples of Greedy algorithm


1. Activity Selection Problem: Selecting the maximum number of activities
that don’t overlap.
2. Knapsack Problem (Fractional): Filling a knapsack with items such that the
total value is maximized.
3. Dijkstra's Algorithm: For finding the shortest path in a graph with non-
negative edge weights.

How Greedy Algorithms Work


1. Initialization: Start with an empty solution.
2. Selection: At each step, choose the best option available (locally optimal).
3. Feasibility: Check if the selected option can be part of the solution.
4. Objective Function: Check if adding the current selection will improve the
objective.
5. Solution Check: Repeat until the whole solution is built.

Dijkstra's algorithm
Dijkstra's is an algorithm used to find the shortest paths between nodes in a
graph, which may represent various types of networks such as road maps,
computer networks, or flight connections. Specifically, Dijkstra's algorithm
solves the single-source shortest path problem for a graph with non-negative
edge weights.
2

How Dijkstra's Algorithm Works


1. Initialization:
 Set the distance to the source node to 0 and all other nodes to infinity.
 Mark all nodes as unvisited.
 Set the source node as the current node.
2. Processing:
 For the current node, consider all its unvisited neighbors and calculate
their tentative distances (distance to the current node + edge weight to
the neighbor).
 Update the neighbor's distance if the calculated tentative distance is
smaller than the currently known distance.
 Once all neighbors have been considered, mark the current node as
visited (a visited node will not be checked again).
3. Selection:
 Select the unvisited node with the smallest tentative distance and set it
as the new current node.
 Repeat the processing steps until all nodes are visited or the smallest
tentative distance among the unvisited nodes is infinity (which means
remaining unvisited nodes are not reachable from the source).

Pseudocode for Dijkstra's Algorithm


1. Initialize distances: distance[source] = 0, distance[all other nodes] = ∞
2. Initialize priority queue with (distance, node) pairs, starting with (0, source)
3. While the priority queue is not empty:
a. Extract the node with the smallest distance from the priority queue
(current_node)
b. For each neighbor of current_node:
i. Calculate the tentative distance: distance[current_node] + edge_weight
ii. If tentative distance < known distance[neighbor]:
- Update distance[neighbor]
- Add (tentative distance, neighbor) to the priority queue
4. Return the distances
3

The scheduling problem


The scheduling problem, particularly the Activity Selection Problem, is a classic
example where a greedy algorithm can be used effectively. However, not all
scheduling problems are suitable for greedy algorithms.

Activity Selection Problem


Problem Statement: Given a set of activities, each with a start time and end time,
select the maximum number of activities that do not overlap.

Greedy Approach:
1. Sort the activities by their finish times.
2. Select the first activity (which has the earliest finish time).
3. Iterate through the sorted list, and for each activity, if the start time is
greater than or equal to the finish time of the last selected activity, select it.
Reasoning: By always choosing the activity that finishes earliest, you leave as
much room as possible for the remaining activities, thus maximizing the number
of non-overlapping activities.

Steps in the Greedy Algorithm for Activity Selection


1. Sort the activities based on their finish times.
2. Initialize the first activity as the selected activity.
3. Iterate through the remaining activities:
If the start time of the current activity is greater than or equal to the finish time of
the last selected activity, select it.

Example

Consider the following activities (start, end):

 Activity 1: (1, 4)
 Activity 2: (3, 5)
 Activity 3: (0, 6)
 Activity 4: (5, 7)
 Activity 5: (8, 9)
 Activity 6: (5, 9)
4

Meaning

 Activity 1: (1, 4) - Starts at time 1, ends at time 4.


 Activity 2: (3, 5) - Starts at time 3, ends at time 5.
 Activity 3: (0, 6) - Starts at time 0, ends at time 6.
 Activity 4: (5, 7) - Starts at time 5, ends at time 7.
 Activity 5: (8, 9) - Starts at time 8, ends at time 9.

 Activity 6: (5, 9) - Starts at time 5, ends at time 9.

Steps:

1. Sort by finish time: (1, 4), (3, 5), (0, 6), (5, 7), (5, 9), (8, 9)
2. Select the first activity: (1, 4)
3. Next, (3, 5) is not selected as it overlaps with (1, 4)
4. (0, 6) is not selected as it overlaps with (1, 4)
5. (5, 7) is selected as it doesn't overlap with (1, 4)
6. (5, 9) is not selected as it overlaps with (5, 7)
7. (8, 9) is selected as it doesn't overlap with (5, 7)

Selected activities: (1, 4), (5, 7), (8, 9)

Other Scheduling Problems

While the activity selection problem is well-suited for a greedy approach, other scheduling
problems may require different strategies:

1. Job Scheduling with Deadlines and Profits: This may require dynamic programming or
other optimization techniques.
2. Interval Partitioning: Where the goal is to use the minimum number of resources to
schedule all activities. This is usually tackled by sorting and using a greedy approach,
similar to the activity selection problem.
3. Weighted Interval Scheduling: This requires dynamic programming since simply
selecting activities based on earliest finish time might not yield the optimal solution.
5

Exercises
Conference Room Scheduling Problem
Problem Statement: Given a set of meetings, each with a start and end time,
select the maximum number of non-overlapping meetings that can be scheduled
in the conference room.

Meetings:
Meeting 1: Team Standup (9:00 AM - 10:00 AM)
Meeting 2: Client Call (11:00 AM - 12:00 PM)
Meeting 3: Project Planning (1:00 PM - 3:00 PM)
Meeting 4: Code Review (2:00 PM - 4:00 PM)
Meeting 5: Marketing Sync (10:30 AM - 11:30 AM)
Meeting 6: HR Update (3:30 PM - 4:30 PM)
Meeting 7: Design Discussion (12:00 PM - 1:30 PM)
Meeting 8: Weekly Sync (8:00 AM - 9:00 AM)

Task:
1. Convert the meeting times to a 24-hour format and sort the meetings
based on their end times.
2. Select the maximum number of non-overlapping meetings using the greedy
approach.
6
7

You might also like