Algorithms Analysis & Design - Lecture 6

Introduction to the Design and Analysis of Algorithms

1. Algorithms
By Mohamed Gamal
© Mohamed Gamal 2024

3. Exhaustive Search
–When dealing with problems where the domain size grows exponentially with the
instance size, such as with permutations, combinations, or subsets, the challenge often
involves finding an element with a special property.
–These are usually optimization problems, where the goal is to maximize or minimize a
characteristic like path length or assignment cost.
–Exhaustive search is a brute-force method for solving these problems by generating and
evaluating every possible element to find one that meets the constraints or optimizes an
objective function.
–We illustrate exhaustive search by applying it to three important problems: the traveling
salesman problem, the knapsack problem, and the assignment problem.

4. Exhaustive Search (Cont.)
Approach:
•Generate a list of all potential solutions to the problem.
•Evaluate potential solutions one by one, disqualifying infeasible ones and,
for an optimization problem, keeping track of the best one found so far.
•When search ends, announce the solution(s) found.

5. NP-hard Problem

6. Traveling Salesman Problem (TSP)
–Given ?????? cities with known distances between each pair, find the shortest tour that
passes through all the cities exactly once before returning to the starting city.
–The problem can be modeled by a weighted graph, vertices representing cities and
edge weight’s specifying the distances.
–More Formally: Find shortest Hamiltonian circuit in a weighted connected graph.
Sir William Rowan
Hamilton

7. Basic Operation: Permutations
Time Complexity: O??????!
Objective: Minimum value
O(??????!) = O(4!) = 24 probabilities
… …
Where ?????? is the number of
different ways to arrange ?????? cities.

8. NP-hard Problem

9. Knapsack Problem
–Given n items of known:
–Find most valuable subset of the items that fit into the knapsack.
•weights: w
1 w
2 … w
n
•values: v
1 v
2 … v
n
•A knapsack of capacity W
Time Complexity: O(2
??????
)
n = number of items
Knapsack Problem

10. Example
–Use brute-force and exhaustive search to solve the following knapsack problem with
•4 items (item 1, item 2, item 3, item 4) — ??????=4
•The items weights are �
1=7, �
2=3, �
3=4 , �
4=5.
•The items values are �
1=$42, �
2=$12, �
3=$40, �
4=$25.
•The knapsack weight is 10.

11. 2
4 items
= 16 Probabilities
O2
??????

12. Assignment
–Use brute-force and exhaustive search to solve the following knapsack problem with
•4 items (item 1, item 2, item 3, item 4) — ??????=4
•The items weights are �
1=2, �
2=4, �
3=5 , �
4=3.
•The items values are �
1=$3, �
2=$5, �
3=$8, �
4=$4.
•The knapsack weight is 8.

14. Assignment Problem
–There are ?????? people who need to be assigned to ?????? jobs, one person per job.
–The cost of assigning person � to job � is ??????�,�.
–Find an assignment that minimizes the total cost.
–Algorithmic Plan: generate all legitimate assignments, compute their costs, and select
the cheapest one.

15. Cost Matrix
Assignments/Jobs Total Cost
… …
O4!
24 Probabilities
Optimal Path:
<
2, 1, 3, 4
>

16. Thank You!