Lab 5Lab 5Name:To be completed in the lab on Friday 11/06/09 or next Friday 11/13/09. Copy the file lab_5.zip from our course website:http://www.cs.drexel.edu/~knowak/cs265_fall_2009/cs_265_links.htmto your desktop and unzip it. Open a SSH connection with tux. Use SSHfile transferwindow to copy Lab 5 files into your cs265_fall_2009 directory on tux. In order toachieve this task drag the lab_5 file icon from your desktop into yourcs265_fall_2009 directory on tux. All files and subdirectories will be automaticallycopied. (i) Tracing execution of Merge Sortvoid mergesort(IntVector& a,IntVector& b,int s,int r){if(r<=s) return;int m=(r+s)/2;mergesort(a,b,s,m);mergesort(a,b,m+1,r);stl_merge(a,b,s,m,r);}Compile the code of merge sort algorithm with –g option and start the GDB debugger with the executable you have just created. Type commands break stl_merge and then run. When prompted for an input enter number 8. Continue by typing commands where and continue until the program stops execution. Keep track of the values of variables s,m,r reported by the debugger. Draw the resulting tree of recursive calls. Mark its nodes with corresponding values of variables s,m,r.Repeat the above experiment with input value 10. Draw the resulting tree of recursive calls.(ii) Tracing execution of Binary Search. int search(int a[], int v, int l, int r){while(r>=l){int m=(l+r)/2;if(v == a[m])return m;if(v<a[m])r=m-1;else l=m+1;}return -1;}Compile the code of binary search algorithm with –g option and start the GDB debugger with the executable you have just created.Type commands break search and then run. When prompted for an input enter 7, then numbers 1,3,5,7,9,11,13 and then 1. Continue by typing command next until you see the operation of assigning a value to variable m displayed on your screen. Continue with one more execution of command next and then type print m. Repeat the whole process until m gets value 0.Repeat the same search process for all the values 0,…,14 instead of 1, identify consecutive values of m and draw the resulting decision tree. Mark the nodes of the decision tree with corresponding values of m and the edges with the decision symbols <, =, >.Demonstrate to the instructor/TA the histories of debugger commands you were running in both cases (i) and (ii). Instructor/TA’s initials:
View Full Document
Unlocking...