i don't understand how to answer any of these :( please help and explain

Suppose you want to rearrange a music playlist so that all of your Taylor Swift songs play first, followed by all of your Kool \& the Gang songs, followed by the songs of all other artists. In this problem you will formulate, solve, prove correct, and analyze an algorithm to achieve this task. The data for the problem is simply a vector whose entries each represent a song, denoted by a single character indicating its artist. So, for example, the array PLbad =[T,T,K,A,K,B] consists of two songs by Taylor, followed by a song by Kool followed by a fourth whose artist is denoted by A, another by Kool, and finally, a song by an artist denoted by B. That playlist does not satisfy our constraints, because the songs by Kool do not all precede the songs by everyone else. The playlists represented by PLgood1 =[T,K,K,B],PLgood2=[K,K,A, B], and PLgood3 =[T,T,T], are all good playlists. For simplicity, you may assume that the playlist is non-empty. You do not care about the order of the songs within the blocks, and those orders can change. You do not know how many Taylor Swift songs or Kool \& the Gang songs you possess! Please use n to represent A. size(), unless you are writing code. The playList Function Assume that you are given a function void swap (char \& a, char \& b) that correctly exchanges the data in two vector locations. In your argument for correctness of your playlist algorithm, please refer to this assumption as (fact Swap). Our nearly-complete algorithm for solving the playlist problem is given below. Your first task is to complete the playList function so that it successfully creates a playlist according to the constraints above. Tell us how to complete the code in the answer box. (Do not include a semicolon in your response.) two vector locations. In your argument for correctness of your playlist algorithm, please refer to this assumption as (fact Swap). Our nearly-complete algorithm for solving the playlist problem is given below. Your first task is to complete the playList function so that it successfully creates a playlist according to the constraints above. Tell us how to complete the code in the answer box. (Do not include a semicolon in your response.) Any of the images below would be a reasonable sketch of the state of the array during the execution of a function that solves the problem. Which image reflects our solution? (b) (c) (d) At the start of every iteration of the while loop, how many songs do you know have been placed correctly? (You may use the variables n,u,v, and w in your response.) Show the state of the A vector after 6 songs have been correctly placed by playList (i.e. after 6 iterations of the loop Note that this does not mean a song won't change position again, we just know it's in the right place relative to the songs we have seen so far). The following problems ask you to assemble a proof that the playList function is correct: it produces a playlist according to the rules specified in the original description of the problem. In order to prove correctness of this algorithm we need to establish a meaningful loop invariant. Note that the notation A[j] refers to elements i through j in vector A, inclusive. In this problem we should assert, among other things, that our code does not change the overall number of each artist's songs. We will call this characteristic of our data stability when we use it in the argument for correctness. You will complete the rest of the loop invariant in the problem below. Fill in the blanks to describe rest of the loop invariant for playList: At the start of the iteration described by variables u,v, and w : - (inv Order) The order of the variables is: - (inv T): the playlist represented by A [ | consists of Taylor Swift songs, and only her songs. (Use variables n,u,v, and/or w in your response.) - (inv K): the playlist represented by A [ I consists of Kool \& the Gang songs, and only their songs. (Use variables n,u,v, and/or w in your response.) - (inv O): the playlist represented by A [ I consists of songs by other artists, and no songs by Taylor or Kool. (Use variables n,u,v, and/or w in your response.) Correctness The base case of the inductive argument is proven by arguing that the initial state of the variables is consistent with the loop invariants. Use this opportunity to make sure your choice of u, and your loop invariants are correct. For the inductive step of the correctness proof, we assume that the loop invariant is true at the beginning of an iteration and show that it is also true at the beginning of the next iteration after executing our code. A complete proof of correctness would require us to consider every conditional code path in a proof by cases. For this homework assignment we explore only one: the case where A[u]==T ' (You should think about the argument for the other two cases!) In our argument, we will refer to this as (assume case). Stability is maintained because only the swap function changes the content of the array, and that function is correct by (fact Swap). To restore (inv Order): - The first inequality in the invariant is maintained by which line of code? (a) line 6 (b) line 10 (c) line 8 (d) line 7 (e) line 9 - The second inequality in the invariant is maintained by which lines of code? (a) line 8 (b) line 10 (c) line 7 (d) line 6 (e) line 9 Select all possible options that apply. To justify the restoration of the remaining invariants, we trace effect of the code swap(A[u],A[W+1]);u++; Before the swap, we know that A[u]= by (a) inv K (b) line 9 (c) assume Case (d) invT (e) stability (f) inv 0 (g) line 7 (h) line 10 (i) fact Swap (j) line 6 (k) inv Order and we know A[w+1]= by (unless w+1==u ). If u!=w+1, then after the call to swap(A[u],A[w+1]); , we have A[u]= and A[w+1]= These values, together with line 10 restore which invariants? (a) inv 0 (b) inv K (c) inv T The remaining loop invariant is restored trivially for the case A[u]==T '. To finish the iterative argument for this case, we need to prove that we have made progress -- that we have increased the number of completed songs. At the end of every iteration of the while loop, how many songs have been placed correctly? (You should plug the new values of the variables into your expression for the number of correctly placed songs, above.) Termination The loop ends when u==v. At that point, the number of songs that have been placed is 7. The loop invariants give (since u and v are equal, use variable v in your answers): - The Taylor Swift songs are in A [.. - The Kool \& the Gang songs are in A[ . - All other songs are in A [ l. Efficiency What is the running time of playList? (a) (1) (b) (logn) (c) (n2) (d) (nlogn) (e) (n)