[go: up one dir, main page]
Scribd
Upload
6 views10 pages

Algorithms ADA

The document outlines various algorithms including Fractional Knapsack, Job Sequencing, Prim's and Kruskal's algorithms for Minimum Spanning Trees, Binary Search, 0/1 Knapsack, Multistage Graph, All Pairs Shortest Path, 8 Queens Problem, Graph Coloring, Hamiltonian Cycle, and Sum of Subsets. Each algorithm is described with step-by-step procedures for implementation. The content serves as a comprehensive guide to solving optimization and search problems using these algorithms.

Uploaded by

barhatedamodar25
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
6 views10 pages

Algorithms ADA

The document outlines various algorithms including Fractional Knapsack, Job Sequencing, Prim's and Kruskal's algorithms for Minimum Spanning Trees, Binary Search, 0/1 Knapsack, Multistage Graph, All Pairs Shortest Path, 8 Queens Problem, Graph Coloring, Hamiltonian Cycle, and Sum of Subsets. Each algorithm is described with step-by-step procedures for implementation. The content serves as a comprehensive guide to solving optimization and search problems using these algorithms.

Uploaded by

barhatedamodar25
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/ 10

Algortithms

Fractional Knapsack:

1. Calculate the ratio (profit/weight) for each item.


2. Sort all the items in decreasing order of the ratio.
3. Initialize res = 0, current capacity= given capacity.
4. Do the following for every item i in the sorted order:
If the weight of the current item is less than or equal to the remaining capacity, then
add the value of that item into the result
Else add the current item as much as we can and break out of the loop.
5. Return res.

Job Sequencing and Deadlines:

1. Store jobs as pairs of (Profit, Deadline): Since we need to prioritize jobs with higher
profits, we pair the profit and deadline together.
2. Sort Jobs Based on Profit: We sort the jobs array in descending order of profit so that
we prioritize scheduling the most profitable jobs first.
3. Create a Slot Array: We create a slot [] array of size n (equal to the number of jobs)
initialized with zeroes. This array will help track which time slots are occupied.
4. Iterate Over Each Job and Try to Schedule It:
a. For each job, check if it can be placed in an available time slot.
b. The job should be scheduled as late as possible but before its deadline.
c. If an empty slot is found, schedule the job there, increment the job count,
and add its profit to the total.
d. After processing all jobs, return the number of jobs completed and the total
profit earned.

Prim's Algorithm

Step 1: Determine an arbitrary vertex as the starting vertex of the MST. We pick 0 in the
below diagram.

Step 2: Follow steps 3 to 5 till there are vertices that are not included in the MST (known as
fringe vertex).
Step 3: Find edges connecting any tree vertex with the fringe vertices.

Step 4: Find the minimum among these edges.

Step 5: Add the chosen edge to the MST. Since we consider only the edges that connect
fringe vertices with the rest, we never get a cycle.

Step 6: Return the MST and exit

Kruskal's Algorithm:

1. Sort all edges in non-decreasing order of their weight

2. Initialize a forest (a set of trees where each vertex is its own tree)

3. Add edges one by one from the sorted list:

a. If adding the edge doesn't form a cycle, include it in the MST

b. Otherwise, discard it

4. Repeat until there are (V-1) edges in the MST (where V is number of vertices)

Binary Search Algorithm

1. Divide the search space into two halves by finding the middle index "mid".
2. Compare the middle element of the search space with the key.
3. If the key is found at middle element, the process is terminated.
4. If the key is not found at middle element, choose which half will be used as the next
search space.
5. If the key is smaller than the middle element, then the left side is used for next
search.
6. If the key is larger than the middle element, then the right side is used for next
search.
7. This process is continued until the key is found or the total search space is
exhausted.

0/1 Knapsack Problem


Case 1 (pick the nth item): Value of the nth item + maximum value obtained by remaining
(n-1) items and remaining weight i.e. (W-weight of the nth item).
Case 2 (don't pick the nth item): Maximum value obtained by (n-1) items and W weight.
If the weight of the 'nth' item is greater than 'W', then the nth item cannot be included, and
Case 2 is the only possibility.

Multistage Graph:
1. Input: A weighted multistage graph G with s and t as source and target vertices,
respectively.
2. Output: The shortest path from s to t in G.
3. Set d(t) = 0 and d(v) = ? for all other vertices v in G.
4. For i = k-1 to 1:
5. a. For each vertex v in stage i:
6. i. Set d(v) = min(w(v, u) + d(u)) for all vertices u in stage i+1.
7. Return d(s) as the shortest path from s to t.

All Pairs Shortest Path:


1. Start by updating the distance matrix by treating each vertex as a possible
intermediate node between all pairs of vertices.
2. Iterate through each vertex, one at a time. For each selected vertex k, attempt to
improve the shortest paths that pass through it.
3. When we pick vertex number k as an intermediate vertex, we already have
considered vertices {0, 1, 2, .. k-1} as intermediate vertices.
4. For every pair (i, j) of the source and destination vertices respectively, there are two
possible cases.
5. k is not an intermediate vertex in shortest path from i to j. We keep the value of
dist[i][j] as it is.
6. k is an intermediate vertex in shortest path from i to j. We update the value of
dist[i][j] as dist[i][k] + dist[k][j], if dist[i][j] > dist[i][k] + dist[k][j]
7. Repeat this process for each vertex k until all intermediate possibilities have been
considered.
8 Queens Problems:
1. Initialize an empty 8×8 chessboard with all positions set to 0.
2. Start with the first row (row 0) and try placing a queen in each column.
3. For each placement, check if the position is safe (not attacked by any previously
placed queen). A position is unsafe if another queen is in the same column or on the
same diagonal.
4. If a safe position is found, place the queen (set position to 1) and recursively try to
place queens in subsequent rows. Otherwise, backtrack by removing the queen and
trying the next column.
5. If all rows are successfully filled (8 queens placed), a valid solution is found.

Graph Coloring:
1. Create a recursive function that takes the graph, current index, number of vertices,
and color array.
2. If the current index is equal to the number of vertices. Print the color configuration
in the color array.
3. Assign a color to a vertex from the range (1 to m).
4. For every assigned color, check if the configuration is safe, (i.e. check if the
adjacent vertices do not have the same color) and recursively call the function with
the next index and number of vertices else return false
5. If any recursive function returns true then break the loop and return true
6. If no recursive function returns true then return false

Hamiltonian Cycle:

1. Start at any vertex (we'll use vertex 0 as the starting point).


2. Try adding adjacent vertices one by one.
3. Check if the vertex can be added to the path without violating Hamiltonian
constraints:
a. It must not already be in the path.
b. If it's the last vertex, it must connect back to the start.
4. If a cycle is found, return it.
5. If no valid path, backtrack and try a different vertex.
Sum of Subsets:

1. Sort the input array (optional but helps in pruning)

2. Use backtracking to explore all possible subsets:

a. Include the current element and recurse

b. Exclude the current element and recurse

3. Prune branches where the remaining elements cannot possibly reach the target

sum

You might also like