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 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, whichis given by the user, ends with #'. It should be stored in a table (or array), called TAMUK. Thenumber of each of these letters is unknown. We have a function, called SWAP(TAM,i.j), whichplaces the ith letter in the jh entry of string TAM and the jth letter in the ih entry of TAM. Note thatSWAP(TAM,i.j) is defined for all integers i and j between 0 and length(TAM)–1, wherelength(TAM) is the number of letters of TAM.1. Using our algorithmic language, write an algorithm, called Sort_TAM, which sorts theletters in the array TAMUK in a way that all T's appear first, followed by all A's, andfollowed by all M’s. The algorithm Sort_TAM should have one parameter: The arrayTAMUK. 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.

ALGORITHM:- Sort_TAM (TAMUK[]) start = 0, mid = 0, end = length(TAMUK) - 1 while mid <= end if TAMUK[mid] = 'T' swap(TAM, start, mid) start = start + 1 mid = mid + 1 else if TAMUK[mid] = 'A' mid = mid + 1 else swap(TAM, mid, end) end = end - 1 2. Proof: We are always placing 'T' at the starting position by using start pointer, 'A' at middle position bu using mid pointer and 'M' at the end position by using end pointer. So this will work because this is what we need to do: Place all T at starting, A at middle and M at the end.CODE:- #include<bits/stdc++.h>using namespace std; void swap(char TAMUK[], int i,int j){ char c = TAMUK[i]; TAMUK[i] = TAMUK[j]; TAMUK[j] = c;} void Sort_TAM (char TAMUK[]){ int start = 0, mid = 0, end = strlen(TAMUK) - 1; while(mid <= end) { if(TAMUK[mid] == 'T') { swap(TAMUK, start, mid); start++; mid++; } else if(TAMUK[mid] == 'A') { mid++; } else { swap(TAMUK, mid, end); end--; } }} int main(){ char TAMUK[] = "ATMTATMATMATMATM"; Sort_TAM(TAMUK); cout<<TAMUK;}OUTPUT:-

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

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

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.

Expert Solution

Trending now

This is a popular solution!

Step by step

Solved in 4 steps with 2 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

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.