graphs Flashcards
types of problems
Decision problems: trying to decide whether a statement is true or false.
They have either yes or no as the solution.
Optimization problems: trying to find the solution with the best possible score according to some scoring scheme.
what are maxmization and minmisation problems
Maximization problems: trying to maximize a certain score.
Minimization problems: trying to minimize a cost function.
what is Optimization:
choosing the best element from a set of alternatives
For an optimization problem you want to find, ………, but the ………..
For an optimization problem you want to find, not just a solution, but the best solution.
what is optimization algorithm
is a numerical method or algorithm for finding a value x such that f(x) is as small (or as large) as possible, for a given function f, possibly with some constraints on x.
what types of algorthims we use For solving Optimization problems:
Greedy algorithm
Dynamic programming algorithm
Branch and bound algorithm(BFS)
what is the greedy algorthim way of solving a problem
give an example
by always making the choice that looks the best at the moment
-it makes locally optimal choices in hope that it will lead to glopal optimal solution
T or F: Greedy algorithms always yield optimal solutions
F
Greedy algorithms do not always yield optimal solutions, but for many problems they do.
Algorithms for optimization problems typically work as
a sequence of steps, with a set of choices at each step.
Examples of Greedy Algorithms :
Minimum-spanning-tree algorithms
Shortest path problems.
Travelling salesman problem.
The knapsack problem (items are divisible).
Task scheduling problem.
Huffman Coding.
T or F: The greedy method is quite powerful and works well for a wide range of problems.
T
what is a tree
connected undiractional graph with no cycle
problems like finding smallest , logest largest are …… problems and ……. algorthims can be used to solve them
problems like finding smallest , logest largest are optimazation problems and greedy algorthim algorthims can be used to solve them
what is spanning tree
A Spanning Tree of a graph G is a subgraph of G that is a tree and contains all the vertices of G
what are the spanning tree properties
1-a spanning tree of n vertix has n-1 edges
2-connected in all vertices
3-has no cycle
Minimum Spanning Trees, why?
To make multiple pins in an electronic circuit electrically equivalent, they are connected using wires. If there are ( n ) pins, ( n-1 ) wires are needed to connect all pins. The optimal arrangement is the one that uses the least amount of wire, as it is generally preferred to minimize the total wire length.
why we need MST in computer networks and shipping/airlines
Computer Networks
To find how to connect a set of computers using the minimum amount of wire.
Shipping/Airplane Lines
To find the fastest way between locations
what kind of approach are Kruskal’s algorithm
Prim’s algorithm
greedy approach/ staregy
prim and kruksal are …… methods that ……..
greedy strategy is captured by the following generic method, which grows the minimum spanning tree one edge at a time
why is kruksal qualifies as a greedy algorithm
each step it adds to the forest an edge of least possible weight.(choosing the best soultion ATM)
how kruksal algorthim avoid violating MST rules
If it were to form a cycle, it would simply link two nodes that were already part of a single connected tree, so that this edge would not be needed (REGECTED)
a safe edge in kruksal; algorthim is
always a least-weight (cheapest) edge in the graph that connects two distinct components (trees).
Without vilating MST
a safe edge is a
edgde that we add to the graph witout violating MST rules
Steps of kruksal algorithm:
intialze empty set A={};
create set of trees for all vertiexes in graph
sort all edges in non decresing order
for each edge (u,v) examine wether endpoint vertix belong in the same tree
-if same then edge cant be added and should be discarded
-if no edge belong to diffrent tree then add it to the tree
Kruskal’s Algorithm psudocode and complextiy for each couble of lines and overall eomplextiy
The running time of Kruskal’s Algorithm is :
Line 1: initialize set A is O(1)
Line 2-3: Make-Set() is |V|.
Line 4: sort the edges is O(E lg E).
Line 5: for loop is O(E)
Line 6-8: find and union by rank is O(lg V) time
D = {c,n,b} => D2 = D x D = {c,n,b} x {c,n,b} = {(c,c), (c,n),(c,b), (n,c), (n,n), (n,b), (b,c), (b,n), (b,b)}
Overall complexity is O(E lg E + E lg V) time.
Note: lgV = lgE (Why?): E can be at most O(V2).
E→{(x,y)| (x,y)∈V 2 ∧ x≠y} every edge maps to anordered pairofdistinctvertices.
O(E lg E) = O(E lg V2) = O(E 2lg V) = O(E lg V) time.
So, overall complexity is O(E lg E) or O(E lg V)
walk through solution and show steps find MST using kruksal
walk through solution and show steps
final answer
draw K4 K6
Prim’s algorithm operates much like ……………. algorithm for finding shortest paths in a graph.
Prim’s algorithm operates much like Dijkstra’s algorithm for finding shortest paths in a graph.
Prim’s Algorithm discription
ما اتفق بس:. ة
- - Prim’s algorithm builds a single tree, set A, to find the minimum spanning tree.
- At each step, it adds the least-weight edge that connects the tree to a vertex not yet in the tree.
- The tree starts from an arbitrary root vertex and expands until it includes all vertices.
- Each added edge connects the current tree to an isolated vertex.
- Prim’s algorithm is similar to Dijkstra’s algorithm, but instead of finding shortest paths, it finds the edges of the minimum spanning tree.
Steps of Prim’s Algorithm :
- Start with any vertex, v.
- Choose the shortest edge from v to a vertex w that is not part of the tree.
- Add edge (v, w) to the (MCST).
- At each step, add the shortest edge from a vertex in the MCST to a vertex outside the MCST, without considering the overall graph structure.
- Stop once all vertices are included in the MCST.
The running time of Prim’s algorithm depends on how we implement the ………
**min-priority queue Q. **
whats the diffrence in running time between prim and kruksal algorthim
The running time of Prim’s algorithm is asymptotically same as for Kruskal’s algorithm.
write prim algorthim psuodocode and analyzie its running time
- Lines 1-5: Initializing key, parent, and queue takes ( O(V) ) time (using BUILD-MIN-HEAP).
- Line 6: The body of the while loop is executed (|V|) times.
- Line 7: Each Extract-Min() operation takes ( O(\log V) ) time, with total cost ( O(V \log V) ).
- Line 8: The for loop runs ( O(E) ) times.
- Lines 9-10: Constant time ( O(1) ).
- Line 11: Decreasing key value in min-heap takes ( O(\log V) ).
- Total running time: ( O(V \log V + E \log V) = O(E \log V) ).
solve MSCT using PRIM
solve with table
