ASSIGNMENT-02 Solution

PART B – Stack, 10 points

Please add code to the provided code. Our program tests whether an input string is a palindrome. Our program output must be identical to this sample output.

A palindrome is a string of characters (a word, phrase, or sentence) that is the same regardless of whether we read it forward or backward. For example, Race

• Enter a string (or a ! to exit): Csc [+] Yes. “Csc” IS a palindrome!

• Enter a string: CSC 220 – Data Structures

[-] No. “CSC 220 – Data Structure” is NOT a palindrome!

[>>] Enter a string: Ah, Satan sees Natasha!

• Yes. “Ah, Satan sees Natasha!” IS a palindrome! [>>] Enter a string: Amy, must I jujitsu my ma?

• Yes. “Amy, must I jujitsu my ma?” IS a palindrome! [>>] Enter a string: A man, a plan, a canal: Panama.

• Yes. “A man, a plan, a canal: Panama.” IS a palindrome! [>>] Enter a string: Are Mac ‘n’ Oliver evil on camera?

• Yes. “Are Mac ‘n’ Oliver evil on camera?” IS a palindrome! [>>] Enter a string: !

[<<] Thank you!

Updated: 3/14/2020 4:50 PM

PART C – Recursion, 10 points

In the language of an alien race, all words take the form of Blurbs. A Blurb is a Whoozit followed by one or more Whatzits. A Whoozit is the character ‘x’ followed by zero or more ‘y’s. A Whatzit is a ‘q’ followed by either a ‘z’ or a ‘d’, followed by a Whoozit. Please add code to the provided code to complete a recursive program that generates random Blurbs in this alien language. Our program must behave in a same manner as the sample run does:

PART D – Recursion, 5 points

Enter a number of blurbs: 7

Blurb #1: xyyyqdxyyyyyyyqdxyy

Blurb #2: xqdxyqzxyyyyyqzx

Blurb #3: xyqdxyyyy

Blurb #4: xqzxqzx

Blurb #5: xyqdxyyyyyy

Blurb #6: xyqdxqzxqzxqzxqdxyyyy

Blurb #7: xqzx

Please add code to the provided code to complete a recursive program that determines and prints the n^th row of Pascal’s Triangle (as shown on the left). Each interior value is the sum of the two values above it. Our program output must be identical to the sample out. Hint: use an array to store the values on each line.

PART E – The Efficiency of Algorithms, 10 points

1. Show how you count the number of operations (not only basic operations) required by the algorithm to the right, 4 points:

Enter a row of Pascal’s Triangle: 0 1

Enter a row of Pascal’s Triangle: 1 1 1

Enter a row of Pascal’s Triangle: 2 1 2 1

Enter a row of Pascal’s Triangle: 4 14641

Enter a row of Pascal’s Triangle: 6 1615201561

Enter a row of Pascal’s Triangle: 11

1 11 55 165 330 462 462 330 165 55 11 1 Enter a row of Pascal’s Triangle: ! Adiós!

int i, n = 5, sum = 5;

for (i = 5; i < 3 * n; i++) { sum *= n + i * 7 + 37;

}

It is OK to do this part on a sheet of paper then snapshot it. Please include the screenshot in our assignment report. Microsoft Office Lens, Adobe Scan, and Google Lens are good phone applications for this purpose.

Coding is recommended but not required. Please make sure our handwriting is readable to our grader.

2. Consider Loop A and Loop B in the box to the right, 4 points:

Although Loop A is O(n) and Loop B is O(n²), Loop B can be faster than Loop A for small values of n. Design and code a creative experiment to find a value of n for which Loop B is faster.

Please submit both our code and our discussion.

2. Repeat question E.2 but use Loop C in place of Loop B, 2 points:

Please submit both our code and our discussion.

Happy Coding!

// Loop A

for (i = 1; i <= n; i++)

for (j = 1; j <= 10000; j++)

sum = sum + j;

// Loop B

for (i = 1; i <= n; i++)

for (j = 1; j <= n; j++)

sum = sum + j;

// Loop C

for (i = 1; i <= n; i++)

for (j = 1; j <= n; j++)

for (k = 1; k <= n; k++)

sum = sum + k;