A. 1 2 3 4 5 7 9

B. 2 1 3 4 7 5 9

  0 1 2 3 4 5 6 7 8
  Z X X X Z X Z X X
X 0 2 3 4 0 6 3 8 9
Y 0 0 0 0 0 0 0 0 0
Z 1 1 1 1 5 1 7 1 1

F H A C I D G E B J 

1. 
   

   B. 0: 3, 2, 1
      1: 3, 2, 0
      2: 1, 0
      3: 0, 1
   
   C. dfs(3)
        dfs(0)
          dfs(1)
            check 0
            dfs(2)
              check 1
            2 done
            check 3
          1 done
          check 3
        0 done
        check 1
      3 done
   

in:   A  A A  A A A  B  A A A  A A  B
out: 41   81     82 42     82   81 42 80

key value
AA   81
AAA  82
AAAB 83
BA   84
AAAA 85
AAB  86

A.
aac (4)
aat (2)
ac  (1)
ct  (0)
g   (3)
ta  (5)
ca  (missing index) <=== +1

B. 

          

          


stable
inplace
sublinear

Quicksort
N
Y
Y
Mergesort
Y
N
Y
LSD string sort
Y
N
N
MSD String sort
Y
N
Y
3-way string quicksort
N
Y
Y

1. 0->11 0->1
   1->5 1->9 1->2
   4->8
   5->6
   6->7 6->5
   8->9
   9->1 9->10
   10->13 
   11->12
   12->11 12->13
   

2. 0, 1, 5
   2, 6
   2, 6, 7, 8, 9
   3, 7
   3, 6, 7, 8, 9
   7
   6, 7, 8, 9
   

code 1 none
code 2 A B C
code 3 A
code 4 A C

A A A H H U M U N U K U N U K U M P U U M U
Number of exchanges: 20

Maximize Xbt + Xct subject to constraints
0 <= Xsa <= 7
0 <= Xsb <= 4
0 <= Xac <= 5
0 <= Xba <= 1
0 <= Xbc <= 2
0 <= Xbt <= 6
0 <= Xct <= 3

Xsa + Xba = Xac
Xsb = Xba + Xbc + Xbt
Xac + Xbc = Xct
 

1. st.put(next, new Queue());
2. Queue q = st.get(next);
3. st.delete(next);
4. st.put(next+d, q);
5. N log Q
6. N

1. i, iii, v,
2. i, ii, iii, vi, viii

 a straight line