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 i th letter in the j th entry of string TAM and the j th letter in the i th 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 algorithm, called Sort_TAM, which sorts the  letters in the array TAMUK in a way that all T’s appear first, followed by all A’s, and  followed by all M’s. The algorithm Sort_TAM should have one parameter: The array  TAMUK. Also, your solution is correct only if the following four constraints are satisfied:  - 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 javascript programming language and a UI interface

C++ Programming: From Problem Analysis to Program Design
8th Edition
ISBN:9781337102087
Author:D. S. Malik
Publisher:D. S. Malik
Chapter15: Recursion
Section: Chapter Questions
Problem 8SA
icon
Related questions
Question

 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 i
th letter in the j
th entry of string TAM and the j
th letter in the i
th 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 algorithm, called Sort_TAM, which sorts the 
letters in the array TAMUK in a way that all T’s appear first, followed by all A’s, and 
followed by all M’s. The algorithm Sort_TAM should have one parameter: The array 
TAMUK. Also, your solution is correct only if the following four constraints are satisfied: 
- 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 javascript programming language and a UI interface

 

Problem Statement: Consider an input string TÂM 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 jh entry of string TAM and the jth letter in the ih 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 algorithm, called Sort_TAM, which sorts the
letters in the array TAMUK in a way that all T's appear first, followed by all A's, and
followed by all M’s. The algorithm Sort_TAM should have one parameter: The array
TAMUK. Also, your solution is correct only if the following four constraints are satisfied:
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 programming language.
Transcribed Image Text:Problem Statement: Consider an input string TÂM 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 jh entry of string TAM and the jth letter in the ih 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 algorithm, called Sort_TAM, which sorts the letters in the array TAMUK in a way that all T's appear first, followed by all A's, and followed by all M’s. The algorithm Sort_TAM should have one parameter: The array TAMUK. Also, your solution is correct only if the following four constraints are satisfied: 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 programming language.
Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 4 steps with 2 images

Blurred answer
Knowledge Booster
Fibonacci algorithm
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
Similar questions
  • SEE MORE QUESTIONS
Recommended textbooks for you
C++ Programming: From Problem Analysis to Program…
C++ Programming: From Problem Analysis to Program…
Computer Science
ISBN:
9781337102087
Author:
D. S. Malik
Publisher:
Cengage Learning
C++ for Engineers and Scientists
C++ for Engineers and Scientists
Computer Science
ISBN:
9781133187844
Author:
Bronson, Gary J.
Publisher:
Course Technology Ptr