Scribd
Upload
52 views3 pages

Algo Spring24 Lab4

This document provides information about Lab 4 for the course SWE212 - Algorithms Analysis & Design taught in Spring 2024. It describes an assignment problem to find the optimal assignment that minimizes the total cost of assigning 4 people to 4 jobs based on a cost matrix. It also briefly describes the knapsack problem, breadth-first search, and depth-first search algorithms. Students are instructed to write C++ code to implement these algorithms.

Uploaded by

abdulrahman yasser
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
52 views3 pages

Algo Spring24 Lab4

This document provides information about Lab 4 for the course SWE212 - Algorithms Analysis & Design taught in Spring 2024. It describes an assignment problem to find the optimal assignment that minimizes the total cost of assigning 4 people to 4 jobs based on a cost matrix. It also briefly describes the knapsack problem, breadth-first search, and depth-first search algorithms. Students are instructed to write C++ code to implement these algorithms.

Uploaded by

abdulrahman yasser
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/ 3

SWE212 - Algorithms Analysis & Design - Spring 2024

Instructor: Dr. Ashraf AbdElRaouf

Eng. Salma Osama - Eng. Reem Khaled - Eng.Yasmin Kandil

Algorithms Analysis & Design

Lab 4
2

Tracing: Assignment Problem


There are 4 people who need to be assigned 4 jobs, one person per job. The cost of
assigning person i to job j is C[ i , j ]. Find an assignment that minimizes the total cost
(use brute force).
J1 J2 J3 J4
P1 9 2 7 8
P2 6 4 3 7
P3 5 8 1 8
P4 7 6 9 4

Algorithm:

1. Knapsack Problem:
● Problem:
Find the most valuable subset of the items that fit into the knapsack.

● Inputs (parameters): array weights containing the weights of each item,


positive integers n & capacity representing the number of items and total
capacity that can be hold respectively , array of values values containing
the values of each item.
● Outputs: Knapsack value i.e. maximum value that can be returned out of
the combination of the given items with respect to their weights.
● Steps?

2. Breadth-First Search (BFS):


• Problem: This algorithm visits all graph vertices by moving across to all the
neighbors of the last visited vertex, the algorithm uses a traversal queue
with the numbers indicating the order in which the vertices are visited, i.e.,
added to (and removed from) the queue.
• Refer to .h on moodle
3

3. Depth-First Search (DFS):


• Problem: This algorithm visits graph’s vertices by always moving away
from the last visited vertex to the unvisited one, backtracks if no adjacent
unvisited vertex is available, the algorithm uses a traversal stack with the
numbers indicating the order in which the vertices are visited, i.e., added to
(and removed from) the stack.
• Refer to .h on moodle

Algorithms’ Implementation:
Write a c++ code for all the algorithms given in the above section.

You might also like