graphs

Question 1

types of problems

Answer 1

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.

Question 2

what are maxmization and minmisation problems

Answer 2

Maximization problems: trying to maximize a certain score.
Minimization problems: trying to minimize a cost function.

Question 3

what is Optimization:

Answer 3

choosing the best element from a set of alternatives

Question 4

For an optimization problem you want to find, ………, but the ………..

Answer 4

For an optimization problem you want to find, not just a solution, but the best solution.

Question 4

what is optimization algorithm

Answer 4

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.

Question 5

what types of algorthims we use For solving Optimization problems:

Answer 5

Greedy algorithm
Dynamic programming algorithm
Branch and bound algorithm(BFS)

Question 6

what is the greedy algorthim way of solving a problem
give an example

Answer 6

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

Question 7

T or F: Greedy algorithms always yield optimal solutions

Answer 7

F
Greedy algorithms do not always yield optimal solutions, but for many problems they do.

Question 7

Algorithms for optimization problems typically work as

Answer 7

a sequence of steps, with a set of choices at each step.

Question 8

Examples of Greedy Algorithms :

Answer 8

Minimum-spanning-tree algorithms
Shortest path problems.
Travelling salesman problem.
The knapsack problem (items are divisible).
Task scheduling problem.
Huffman Coding.

Question 8

T or F: The greedy method is quite powerful and works well for a wide range of problems.

Answer 8

T

Question 9

what is a tree

Answer 9

connected undiractional graph with no cycle

Question 10

problems like finding smallest , logest largest are …… problems and ……. algorthims can be used to solve them

Answer 10

problems like finding smallest , logest largest are optimazation problems and greedy algorthim algorthims can be used to solve them

Question 11

what is spanning tree

Answer 11

A Spanning Tree of a graph G is a subgraph of G that is a tree and contains all the vertices of G

Question 12

what are the spanning tree properties

Answer 12

1-a spanning tree of n vertix has n-1 edges
2-connected in all vertices
3-has no cycle

Question 13

Minimum Spanning Trees, why?

Answer 13

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.

Question 14

why we need MST in computer networks and shipping/airlines

Answer 14

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

Question 15

what kind of approach are Kruskal’s algorithm
Prim’s algorithm

Answer 15

greedy approach/ staregy

Question 16

prim and kruksal are …… methods that ……..

Answer 16

greedy strategy is captured by the following generic method, which grows the minimum spanning tree one edge at a time

Question 17

why is kruksal qualifies as a greedy algorithm

Answer 17

each step it adds to the forest an edge of least possible weight.(choosing the best soultion ATM)

Question 18

how kruksal algorthim avoid violating MST rules

Answer 18

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)

Question 19

a safe edge in kruksal; algorthim is

Answer 19

always a least-weight (cheapest) edge in the graph that connects two distinct components (trees).
Without vilating MST

Question 20

a safe edge is a

Answer 20

edgde that we add to the graph witout violating MST rules

Question 21

Steps of kruksal algorithm:

Answer 21

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

Question 22

Kruskal’s Algorithm psudocode and complextiy for each couble of lines and overall eomplextiy

Answer 22

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)

Question 23

walk through solution and show steps find MST using kruksal

Answer 23

Question 24

walk through solution and show steps

Answer 24

final answer

Question 25

draw K4 K6

Answer 25

Question 26

Prim’s algorithm operates much like ……………. algorithm for finding shortest paths in a graph.

Answer 26

Prim’s algorithm operates much like Dijkstra’s algorithm for finding shortest paths in a graph.

Question 27

Prim’s Algorithm discription

Answer 27

ما اتفق بس:. ة
- - 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.

Question 28

Steps of Prim’s Algorithm :

Answer 28

• 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.

Question 29

The running time of Prim’s algorithm depends on how we implement the ………

Answer 29

**min-priority queue Q. **

Question 30

whats the diffrence in running time between prim and kruksal algorthim

Answer 30

The running time of Prim’s algorithm is asymptotically same as for Kruskal’s algorithm.

Question 31

write prim algorthim psuodocode and analyzie its running time

Answer 31

• 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) ).

Question 32

solve MSCT using PRIM

Answer 32

Question 33

solve with table

Answer 33