Question

In: Math

A palindrome is a string whose reversal is identical to the string. For example, 110010011 is...

A palindrome is a string whose reversal is identical to the string. For example, 110010011 is a palindrome. So are BOB and KAYAK. How many bit strings of length ?? are palindromes? Explain your solution clearly.

Solutions

Expert Solution

Here we need to consider two cases.

Case 1: If n is odd. Then leaving middle digit we can divide the string in to parts each having digits (n-1) / 2.

Let us consider first half that have (n-1)/2 digits. Each of these (n-1)/2 digit can be filled in 2 ways either from 1 or 0. So possible number of ways of filling first half of string is

Now, second half can be filled only way by reversing the digit of first half. Middle digit can be filled in 2 ways. So possible number of strings that are palindrome is

Case 2: If n is even. Then we can divide the string in to parts each having digits (n) / 2.

Let us consider first half that have (n)/2 digits. Each of these (n)/2 digit can be filled in 2 ways either from 1 or 0. So possible number of ways of filling first half of string is

Now, second half can be filled only way by reversing the digit of first half.So possible number of strings that are palindrome is


Related Solutions

A palindrome is a string that reads the same forward and backward, for example, radar, toot,...
A palindrome is a string that reads the same forward and backward, for example, radar, toot, and madam. Your task is to construct a python algorithm to receive as input a string of characters and check whether it is a palindrome using a stack and a queue. Your ADTs contains the following methods: Queue Queue() – constructor enqueue(e) – enqueue an element dequeue(e) – dequeue an element len() – returns the number of elements in the queue Stack Stack() -...
(Palindrome integer) Write the methods with the following headers // Return the reversal of an integer,...
(Palindrome integer) Write the methods with the following headers // Return the reversal of an integer, i.e., reverse(456) returns 654 public static int reverse(int number) // Return true if number is a palindrome public static boolean isPalindrome(int number) Use the reverse method to implement isPalindrome. A number is a palindrome if its reversal is the same as itself. Write a test program that prompts the user to enter an integer and reports whether the integer is a palindrome. Here is...
PLEASE DO IN JAVA 4.15 Palindrome A palindrome is a string that is the same spelled...
PLEASE DO IN JAVA 4.15 Palindrome A palindrome is a string that is the same spelled forward as it is spelled backward. So, "abcba" is a palindrome, as are "eye" and "madam". This program takes as input from the user, a string and outputs whether the string is a palindrome. (1) Modify the given program to use a loop to output the string one character at a time. (1 pt) Example output for word = radar: Word Entered: radar r...
Write a recursive method to determine if a String is a palindrome. Create a String array...
Write a recursive method to determine if a String is a palindrome. Create a String array with several test cases and test your method. Write a recursive method to determine if a String is a palindrome. Create a String array with several test cases and test your method. In Java
C++: A palindrome is a string that is the same backward as it is forward. For...
C++: A palindrome is a string that is the same backward as it is forward. For example, “tot” and “otto” are rather short palindromes. Write a program that lets a user enter a string and that passes to a bool function a reference to the string. The function should return true if the string is a palindrome and false otherwise. When you do the judgment, capitalization, spaces, and punctuation should be neglected, that is, “Madam, I’m Adam” should test as...
Question 3. A string p = p1…pn is a palindrome if it spells the same string...
Question 3. A string p = p1…pn is a palindrome if it spells the same string when read backward, that is pi = pn+1 –i for 1≤ i ≤ n. Design an efficient algorithm for finding all palindromes (of all lengths) in a text. (The pseudo code the algorithm should be provided) (40 points)
In C++: This is the problem: [(1)] A palindrome is a string that reads the same...
In C++: This is the problem: [(1)] A palindrome is a string that reads the same forwards as backwards. Using only a fixed number of stacks and queues, the stack and queue ADT functions, and a fixed number of int and char variables, write an algorithm to determine if a string is a palindrome. Assume that the string is read from standard input one character at a time. The algorithm should output true or false as appropriate [(2)] Let Q...
A palindrome is a string of characters (a word, phrase, or sentence) that is the same...
A palindrome is a string of characters (a word, phrase, or sentence) that is the same regardless of whether you read it forward or backward – assuming that you ignore spaces, punctuation and case. For example, Race car is a palindrome. So is A man, a plan, a canal: Panama. 1. Describe how you could use a stack to test whether a string is a palindrome. 2. Describe how you could use a queue to test whether a string is...
I wrote this program to check a string is palindrome or not. but in both cases,...
I wrote this program to check a string is palindrome or not. but in both cases, it gives me palindrome. could someone help me with this program? it has an error I couldn't find. when I run the code and give a string, in both cases it gives me palindrome. for example if I give Pop it says it is a palindrome but if I give Salima, it also says palindrome. #include<string> #include <iostream> using namespace std; class PString:public string...
IN JAVA - [(1)] A palindrome is a string that reads the same forwards as backwards....
IN JAVA - [(1)] A palindrome is a string that reads the same forwards as backwards. Using only a fixed number of stacks and queues, the stack and queue ADT functions, and a fixed number of int and char variables, write an algorithm to determine if a string is a palindrome. Assume that the string is read from standard input one character at a time. The algorithm should output true or false as appropriate [(2)] Let Q be a non-empty...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT