CS607 - 1 Assignment Fall 2022-1
CS607 - 1 Assignment Fall 2022-1
CS607 - 1 Assignment Fall 2022-1
Assignment # 01
Fall 2022 Deadline Date
Solution 06 December 2022
Please carefully read the following instructions before attempting the assignment.
You should consult the recommended books to clarify your concepts as handouts are
not sufficient.
OBJECTIVE
The objective of this assignment is to:
Learn and practice basic concepts of Graphs and trees with traversing
techniques.
NOTE
No assignment will be accepted after the due date via email in any case (whether it is the
case of load shedding or internet malfunctioning etc.). Hence refrain from uploading
assignments in the last hour of the deadline. It is recommended to upload the solution
file at least two days before its closing date.
Please consult with your instructor before the deadline if you find any mistake or
confusion in the assignment (Question statement). After the deadline, no queries will be
entertained in this regard.
Given:
No of nodes =11 (Last level of the tree not filled (Occupied by Node))
Several Tree Levels= 4.
Nodes Labeling: R, A, B, C, D, E, F, G, H, I, K (Target Node)
You are required to draw a tree for path searching using BFS.
Solution No 1:
A B
C D E F
G H
K
Searching Path:
Q VISITED
R R
A, B R, A, B
B, C, D R, A, B, C, D
C, D, E, F R, A, B, C, D, E, F
D, E, F, G, H R, A, B, C, D, E, F, G, H
E, F, G, H, I R, A, B, C, D, E, F, G, H, I
F, G, H, I, K R, A, B, C, D, E, F, G, H, I, K
Questions No. 02 10 Marks
Convert mentioned below Tree into a Graph (Directed/undirected).
Directed Graph:
G
F
C
B
Solution No 2:
UNDIRECT GRAPH
R C F