=========================preview======================
(COMP171)comp171-wa2-sol.pdf
Back to COMP171 Login to download
======================================================
The Hong Kong University of Science & Technology
Department of Computer Science and Engineering
COMP 171: Data Structures and Algorithms
Written Assignment 2
Suggested solution

Suggested solution of Q1:
- First, find the path from the root to the nodes P and Q. Store then in two arrays. Then find the last common element in the two arrays. It is the closest common ancestor of two nodes.
-Pseudo code:
int found=FALSE;
BinaryNode* Find_Near_Ancient(BinaryNode* T,BinaryNode* p,BinaryNode* q)
{ BinaryNode* pathp[ 100 ],pathq[ 100 ] Findpath(T,p,pathp,0); found=FALSE; Findpath(T,q,pathq,0); for(i=0;pathp[i]==pathq[i]&&pathp[i];i++);
return pathp[--i]; }//Find_Near_Ancient
void Findpath(BinaryNode* T,BinaryNode* p,BinaryNode* path[ ],int i)
{ if(T==p) {
found=TRUE;
return;

}
path[i]=T;
if(T->left) Findpath(T->lchild,p,path,i+1);
if(T->right&&!found) Findpath(T->right,p,path,i+1);
if(!found) path[i]=NULL;

}//Findpath
Solution of Q2: 1)


ASL=1/12 (1 1 + 2 2 + 3 3 + 4 3 + 5 2 + 6 1) = 3.5 2)

ASL=1/12 (1 1 + 2 2 + 3 4 + 4 4 + 5 1) 3.17

Suggested solution of Q3: -Description of the algorithm: Do DFS traversal starting from each node with zero indegree. Store the longest path for traversal each time. In the end, output the overall longest path. -Pseudo code.
int maxlen,path[MAXSIZE]; // the current path int mlp[MAXSIZE]; // the current longest path
void Get_Longest_Path(Graph G)
{ maxlen=0; FindIndegree(G,indegree); for(i=0;i<G.vexnum;i++) {
for(j=0;j<G.vexnum;j++) visited[j]=0; if(!indegree[i]) DFS(G,i,0);// DFS traversal starting from each node with zero indegree
}
printf("Longest Path:");
for(i=0;mlp[i];i++)

printf("%d",mlp[i]); //output the longest path }//Get_Longest_Path
void DFS(Graph G, int i, int len)
{ visited[i]=1; path[len]=i; if(len>maxlen&&!G.vertices[i].firstarc) //find a new longest path {
for(j=0;j<=len;j++) mlp[j]=path[j];
maxlen=len;
}
else
{
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{

j=p->adjvex;
if(!visited[j]) DFS(G,j,len+1);
}
}//else
visited[i]=0;

}//DFS
The complexity of each DFS is O(|V|+|E|), so the overall time complexity is O(|V|*(|V|+|E|)).

Another BFS-based solution to Q3:
-Description: For each node with zero indegree, we do BFS traversal. Let maxlen[i] be the maximum length of the longest path starting from node i. Since we are given a DAG, maxlen[i] should be (1+ max(maxlen[] of the children of node i)).
-Pseudo code.
int mlp[MAXSIZE]; // the longest path
int maxlength, maxlen[n]; // n = |V|
int succ[n]; // record the succeeding node of each node on the longest path
void Get_Longest_Path(Graph G)
{ int start=-1; // the starting node of the longest path FindIndegree(G,indegree); for(i=0;i<G.vexnum;i++) {
succ[i]=-1;
maxlen[i]=0;
maxlength=0;
if(!indegree[i])
{

BFS_maxlen(G,i);
if (maxlen[i]>maxlength)
start=i;
}
}

int pos