Each of the figures 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 figures 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)
