Problem Statement: Consider an input string TAM of letters ‘A’, ‘M’, and ‘T’. This string, which is given by the user, ends with ‘#’. It should be stored in a table (or array), called TAMUK. The number of each of these letters is unknown. We have a function, called SWAP(TAM,i,j), which places the ith letter in the jth entry of string TAM and the jth letter in the ith entry of TAM. Note that SWAP(TAM,i,j) is defined for all integers i and j between 0 and length(TAM)–1, where length(TAM) is the number of letters of TAM.
Problem Statement: Consider an input string TAM of letters ‘A’, ‘M’, and ‘T’. This string, which is given by the user, ends with ‘#’. It should be stored in a table (or array), called TAMUK. The number of each of these letters is unknown. We have a function, called SWAP(TAM,i,j), which places the ith letter in the jth entry of string TAM and the jth letter in the ith entry of TAM. Note that SWAP(TAM,i,j) is defined for all integers i and j between 0 and length(TAM)–1, where length(TAM) is the number of letters of TAM.
1. Using our algorithmic language, write an
- Constraint 1: Each letter (‘A’, ‘M’, or ‘T’) is evaluated only once.
- Constraint 2: The function SWAP(TAM,i,j) is used only when it is necessary.
- Constraint 3: No extra space can be used by the algorithm Sort_TAM. In other words,only the array TAMUK can be used to sort the ‘A’, ‘M’, or ‘T’.
- Constraint 4: You cannot count the number of each letter ‘A’, ‘M’, or ‘T’.
2. Show that the algorithm Sort_TAM is correct using an informal proof (i.e., discussion).
3. Give a program corresponding to Sort_TAM using your favorite
Want to solve this program using "R" programming
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
