Scribd
Upload
37 views

KIE1008 (Theory Tutorial) Session 2016/2017 (Semester 2)

This tutorial covers trees and graphs. It includes (1) constructing and modifying binary trees and AVL trees, (2) analyzing an adjacency matrix and list, (3) finding minimum spanning trees and shortest paths using algorithms like Prim's and Dijkstra's, and (4) analyzing a graph using depth-first search, breadth-first search, and finding shortest distances with a greedy algorithm.

Uploaded by

Mazen Jamal
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
37 views

KIE1008 (Theory Tutorial) Session 2016/2017 (Semester 2)

This tutorial covers trees and graphs. It includes (1) constructing and modifying binary trees and AVL trees, (2) analyzing an adjacency matrix and list, (3) finding minimum spanning trees and shortest paths using algorithms like Prim's and Dijkstra's, and (4) analyzing a graph using depth-first search, breadth-first search, and finding shortest distances with a greedy algorithm.

Uploaded by

Mazen Jamal
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/ 1

KIE1008 (Theory Tutorial) Session 2016/2017 (Semester 2)

Tutorial 6: Trees and Graphs

1. a) Show the construction of binary tree for the following nodes according to the sequence of
appearance: J, I, L, A, H, B, E, D, G, C, K and F.
b) Show the deletion of the following nodes according to the sequence: A, B, C, D and E.
c) Show the insertion of the following nodes M, O, N, and P
d) Show the traversal sequences (preorder, inorder and postorder) for the binary tree after (c).
2. Repeat (1) for AVL tree.
3. Draw graph for the adjacent matric AG1 given, give the adjacent list. Then, give the depth-first
and breath-first search sequences.

0 1 0 1 0 1 0 1 0 0 0 0 0 2 3 0 0 0 2 3 0 5 0 0
0 0 1 0 1 0 1 0 1 0 1 0 2 0 4 0 0 0 0 0 3 0 0 0
0 0 0 0 0 1 0 0 0 0 1 0 3 4 0 2 2 0 0 0 5 3 0 0
0 0 0 0 0 1 0 0 0 0 0 1 0 0 2 0 4 0 0 0 0 0 3 0
1 0 1 0 0 0 0 1 0 0 0 1 0 0 2 4 0 2 0 0 0 0 5 3
𝐴𝐺1 = 0 1 0 0 1 0 0 1 0 0 0 1 𝐴 = 0 0 0 0 2 0 0 0 0 0 0 4
0 0 0 1 0 0 0 0 0 1 0 0 𝐺2 2 0 0 0 0 0 0 4 0 0 0 0
1 1 0 1 0 0 0 0 0 0 0 0 3 0 0 0 0 0 4 0 2 1 0 0
0 0 1 0 0 0 0 0 0 0 1 0 0 3 5 0 0 0 0 2 0 4 0 0
1 0 1 0 1 0 1 0 0 0 0 0 5 0 3 0 0 0 0 1 4 0 2 2
0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 3 5 0 0 0 0 2 0 4
[0 1 0 1 0 0 0 0 1 0 0 0] [0 0 0 0 3 4 0 0 0 2 4 0]

4. Find the minimum spanning tree for the graph given as AG2 using Prim’s algorithm. What is the
minimum weight? Is there only one minimum spanning tree?
5. Find the shortest path from node A to all other nodes for the graph given as AG2. Repeat for
node E.
6. Given the graph below.

4 3 i. Find the weight matrix.


7 ii. List the node in depth-first search traversal from 0.
0
3 12 iii. List the node in breadth-first search traversal from 0.
1 5
15 5 iv. Find the shortest distance from node 0 to every other
8 8 node using Greedy algorithm. Show the steps.
2
2 4
3

---END---

You might also like