AGT END 23 Solution

1 (a) Why is it important to study program running time, and what factors influence it?

Answer:

• Importance:

  • Predict performance, optimize resource use, and compare algorithms’ efficiency.

• Factors:

  • Input size ($n$).
  • algorithm complexity
  • Hardware (CPU, memory).
  • Programming language and compiler.
  • Operating System

1 (b) Deduce the Satisfiability problem in Clique decision problem or vice versa

Video:

Question 2

Part(a) Prove that every graph G with maximum degree r is an induced subgraph of an r- regular graph

link link

Part (B)

AGT_Complexity, p.12

AGT_Complexity, p.13

Question 4

Part (b)

^0b0c5c

Question 5

Part (b)

^a2eaf5

Question 6

Part (a) & (b)

AGT Complete, p.57

Part (c)

^19910a

Question 10

Part (a)

Depth-First Search (DFS) Algorithm

Algorithm (Recursive):

1. Input: A graph G and a starting vertex v.
2. Mark v as visited.
3. For each neighbor w of v in G:
   • If w is not visited:
     • Recursively call DFS(G, w).

Algorithm (Iterative using a Stack):

4. Input: A graph G and a starting vertex v.
5. Create an empty stack S.
6. Push v onto S.
7. Mark v as visited.
8. While S is not empty:
   • Pop a vertex u from S.
   • For each neighbor w of u in G:
     • If w is not visited:
       • Mark w as visited.
       • Push w onto S.

Breadth-First Search (BFS) Algorithm

Algorithm (Iterative using a Queue):

9. Input: A graph G and a starting vertex v.
10. Create an empty queue Q.
11. Enqueue v into Q.
12. Mark v as visited.
13. While Q is not empty: * Dequeue a vertex u from Q. * For each neighbor w of u in G:
    • If w is not visited:
      • Mark w as visited.
      • Enqueue w into Q.