Please help me with the following questions: (Please write out all the solutions step-by-step and justify your answers)

1. BubbleSort( 21, ..., Ar, array of integers) For i from 1 to n - 1 2. For j from 1 to n-i 3. If a; > 4j+1 then 4. swap a; and a;+1 A permutation is called a one-pass permutation if it is completely sorted after one pass of bubble sort (one iteration of the outer loop.) For example, (3,1,2,4,6,5) is a one-pass permutation of length 6. (Note: we will consider the increasing permutation, e.g. (1,2,3,4,5,6), as a one-pass permutation since it is technically sorted after one pass even though there are no swaps.) (a) In terms of n, how many one-pass permutations are there of length n? (b) How many bits would you need for the most efficient encoding of a one-pass permutation of length n? (c) Develop your own encoding/decoding algorithm where the code uses this number of bits. (Hint: use the algorithm to help with your encoding.) (d) Use your encoding to encode the following one-pass permutations: (6,1,2,3,4,5) [3.1,2,5,4,6] (2,1,4,3,5,6) . (e) Use your decoding to decode the following strings: (put "not decodable" if you can't decode the string.) . 01010 11000 . 01110 1. BubbleSort( 21, ..., Ar, array of integers) For i from 1 to n - 1 2. For j from 1 to n-i 3. If a; > 4j+1 then 4. swap a; and a;+1 A permutation is called a one-pass permutation if it is completely sorted after one pass of bubble sort (one iteration of the outer loop.) For example, (3,1,2,4,6,5) is a one-pass permutation of length 6. (Note: we will consider the increasing permutation, e.g. (1,2,3,4,5,6), as a one-pass permutation since it is technically sorted after one pass even though there are no swaps.) (a) In terms of n, how many one-pass permutations are there of length n? (b) How many bits would you need for the most efficient encoding of a one-pass permutation of length n? (c) Develop your own encoding/decoding algorithm where the code uses this number of bits. (Hint: use the algorithm to help with your encoding.) (d) Use your encoding to encode the following one-pass permutations: (6,1,2,3,4,5) [3.1,2,5,4,6] (2,1,4,3,5,6) . (e) Use your decoding to decode the following strings: (put "not decodable" if you can't decode the string.) . 01010 11000 . 01110