## Each of the ﬁgures below represents a partial spanning tree. Determine whether it could possibly be obtained from,Prim’s algorithm, Kruskal’s algorithm, both or neither.

### computer science

##### Description

Question (1)Minimum Spanning Tree Algorithms (12 points)

Each of the ﬁgures below represents a partial spanning tree. Determine whether it could possibly be obtained from,Prim’s algorithm, Kruskal’s algorithm, both or neither.

Question (2)    Analysis of Algorithms (10 points)

For each code fragment on the left, check the best matching order of growth of the running time. You may use an answer more than once or not at all. Explain your selection.

Question (3)- five sorting algorithms (10 points)

The column on the left is the original input of strings to be sorted the column on the right are the strings in sorted order; the other columns are the contents at some intermediate step during one of the algorithms listed below. Match up each algorithm by writing its number under the corresponding column. Use each number exactly once, explain your answer.

0  deer bass bass bear bear bull bass

1  clam bull bear bull bull clam bear

2  bear bear bull calf calf bear bull

3  myna crow calf clam clam bass calf

4  tuna deer clam deer deer crow clam

5  slug clam crab dove dove crab crab

6  dove calf crow gnat lynx calf crow

7  moth dove deer lynx moth deer deer

8  lynx hoki dove moth myna lynx dove

9  bull duck duck myna slug moth duck

10 calf crab gnat pony sole dove gnat

11 sole mule hoki seal tuna sole hoki

12 pony moth pony slug gnat pony lion

13 seal lynx seal sole hoki seal lynx

14 gnat gnat myna swan mule gnat moth

15 swan puma swan tuna pony swan mule

16 mule myna mule mule seal mule myna

17 hoki seal sole hoki swan hoki pony

18 duck lion tuna duck bass duck puma

19 crab sole slug crab crab slug seal

20 crow pony lynx crow crow tuna slug

21 bass tuna moth bass duck myna sole

22 lion slug lion lion lion lion swan

23 puma swan puma puma puma puma tuna

---- ---- ---- ---- ---- ---- ----

0                                                             1

(0) Original input  (1) Sorted     (2) Selection sort  (3) Insertion sort

(4) Shellsort  (5) Mergesort (6) Quicksort

Question (4) insert the following number in a redblack tree (2,1,4,5,9,3,6,7)

, show each step and show the color of each node (10 points).

Question (5) Find longest common subsequence (LCS) BETWEEN Algorithm and Alignment  using daynamic programming Show detailed steps(10 points)