ZuoTi.Pro
Question

CSC231 Discrete Structures Algorithms Attached to this assignment as a separate document is the C++ code for a program that d
unsigned int Palindrome Example::stringLength (const char *sl) { int count = 0; 34 for (; 51 [count] != 0x0000; count++); 35

Attached to this assignment as a separate document is the C++ code for a program that determines if a given string is a palindrome or not. A palindrome is a word that is spelled the same backward or forward. "bob" is an example of a palindrome. The program is sometimes a talking point during lecture, and may not fully adhere to the many bobisms I've been telling you about. In fact, it may not entirely work but that wasn't its purpose Review the document and answer the following question Compare and contract the complexity of the for loop on line 34 and while loop one lines 62-67. Then, determine the complexity of the entire ispalindrome (char*) function that begins on line 52. Type you answer in the space provided below.
engineering   Computer-Science   
0 0
Add a comment Improve this question Transcribed image text
Next > < Previous
Sort answers by oldest

Homework Answers

Answer #1

Line 34 loop->

for count = 1 to the end of string (null character)

if string length is n, then complexity of this loop is O(n)

loop at line 62->

bos is pointer to start of string (assume it index 0 for simplicity)

eos is pointer to end of string (assume it index length-1 for simplicity)

In the worst case, while loop execute till bos<=eos

and in each iteration, bos increases by 1 and eos decreases by 1 which is as traversing string faster by 2 times

Complexity = O(length) for this loop

isPalindrome call stringLength which is O(n) and then line 62 while loop which is also O(n)

complexity = O(n) +O(n) = O(n)

0 0
Add a comment
Know the answer?
Add Answer to:
Attached to this assignment as a separate document is the C++ code for a program that...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions

  • I keep getting an error code in my C++ program. It says "[Error] 'strlen' was not...

    I keep getting an error code in my C++ program. It says "[Error] 'strlen' was not declared in this scope" in my main.cpp. Here are my codes. main.cpp #include <iostream> #include <string> #include "functions.h" using namespace std; //definition of the main function. //takes arguments from the command-line. int main(int argc, char *argv[]) { //Determine if you have enough arguments. //If not, output a usage message and exit program if (argc<2 || (argc == 2 && argv[1][0] == '-')) { //call...

  • Can anyone help me fix this program to make sure use stack and use STL library...

    Can anyone help me fix this program to make sure use stack and use STL library to check the name1 and name2 is palindrome. Thank you stackPalindrome.h #ifndef_STACK_PALINDROME_H #define_STACK_PALINDROME_H template <class StackPalindrome> class StackPalindrome { public:    virtual bool isEmpty() const = 0;    virtual bool push(const ItemType& newEntry) = 0;    virtual bool pop() = 0;    virtual ItemType peek() const = 0; }; #endif stack.cpp #include<iostream> #include<string> #include<new> #include "stackPalindrome.h" using namespace std; template <class ItemType> class OurStack...

  • ***************Fix code recursive function #include <iostream> #include <cctype> #include <string> using namespace std; void printUsageInfo(string executableName)...

    ***************Fix code recursive function #include <iostream> #include <cctype> #include <string> using namespace std; void printUsageInfo(string executableName) { cout << "Usage: " << executableName << " [-c] [-s] string ... " << endl; cout << " -c: turn on case sensitivity" << endl; cout << " -s: turn off ignoring spaces" << endl; exit(1); //prints program usage message in case no strings were found at command line } string tolower(string str) { for(unsigned int i = 0; i < str.length(); i++)...

  • 1 of 1 15 points) Palindrome Detector. A palindrome is a phrase that reads the Pi...

    1 of 1 15 points) Palindrome Detector. A palindrome is a phrase that reads the Pi same ronwards as it does backwards. For example, "a man, a plan, a canal, Panama is a palindrome. Write a program that uses a stack to check for palindromes in each line of a text file. Try your program on the example text file "palindromes txt".Your program should output the palindromes that it finds in the document. For example: FindPalindromes( palindromes.txt") will display "a...

  • Please use Visual Studio! Let me know if you need anything else <3 #include <stdio.h> #include...

    Please use Visual Studio! Let me know if you need anything else <3 #include <stdio.h> #include <string.h> #pragma warning(disable : 4996) // compiler directive for Visual Studio only // Read before you start: // You are given a partially complete program. Complete the functions in order for this program to work successfully. // All instructions are given above the required functions, please read them and follow them carefully. // You shoud not modify the function return types or parameters. //...

  • Please read the problem carefully and answer the 2 questions below code: /***************************************************************** * Program: palindrome.c...

    Please read the problem carefully and answer the 2 questions below code: /***************************************************************** * Program: palindrome.c * * Purpose: implements a recursive function for determining *   if a string is a palindrome * * Authors: Steven R. Vegdahl, Tammy VanDeGrift, Martin Cenek * *****************************************************************/ #include #include #include /***************************************************************** * is_palindrome - determines whether a string of characters is a palindrome * * calling sequence: *    result = is_palindrome(str, first_index, last_index) * * parameters - *    str - the string to test *    first_index -...

  • Assignment 1 In this assignment you will be writing a tool to help you play the...

    Assignment 1 In this assignment you will be writing a tool to help you play the word puzzle game AlphaBear. In the game, certain letters must be used at each round or else they will turn into rocks! Therefore, we want to create a tool that you can provide with a list of letters you MUST use and a list of available letters and the program returns a list of all the words that contain required letters and only contain...

  • I need help fixing my code.   My output should be the following. Hello, world! : false...

    I need help fixing my code.   My output should be the following. Hello, world! : false A dog, a panic in a pagoda : true A dog, a plan, a canal, pagoda : true Aman, a plan, a canal--Panama! : true civic : true If I had a hi-fi : true Do geese see God? : true Madam, I’m Adam. : true Madam, in Eden, I’m Adam. : true Neil, a trap! Sid is part alien! : true Never odd...

  • Write a program that uses a recursive function to determine whether a string is a character-unit...

    Write a program that uses a recursive function to determine whether a string is a character-unit palindrome. Moreover, the options for doing case sensitive comparisons and not ignoring spaces are indicated with flags. For example "A nut for a jar of tuna" is a palindrome if spaces are ignored and not otherwise. "Step on no pets" is a palindrome whether spaces are ignored or not, but is not a palindrome if it is case sensitive. Background Palindromes are character sequences...

  • I need help programming this program in C. 1.) Write a program that reads a message,...

    I need help programming this program in C. 1.) Write a program that reads a message, then checks whether it's a palindrome (the letters in the message are the same from left to right as from right to left), example is shown below: Enter a message: He lived as a devil, eh? Palindrome Enter a message: Madam, I am Adam. Not a Palindrome 2.) Ignore all characters that aren't letters. Use integer variables to keep track of positions in the...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT