## Description

## PART A – The Linked Bag, 20 points

Please implement class LinkedBag focusing on method removeAllOccurrences. This method removes all occurrences of

the given entries from a bag. Our program’s output must be identical to the following same output:

## PART B – Stack, 15 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 car is a palindrome. So is A man, a

plan, a canal: Panama. More about palindromes:

http://www.palindromelist.net/. We ignore spaces

P E R F O R M A N C E T R A C K E R

ASMT GRADE YOUR GRADE

ZOOM 05

01 20

02-PREPARATION 25

02 75

03 75

TOTAL 200

A: 90-100% B: 80-89% C: 70-79% D: 60-69% F: 0-60%

The course grader provides feedback to your assignments

on iLearn.

=== LINKED BAG 220 JAVA ==========================================================

[+] Creating a CSC220 LinkedBag…

[+] Adding…. these items to the bag: A _ _ G Bb A _ u n o A o d Bb A A l l

[>] The bag now contains 18 string(s): l l A A Bb d o A o n u _ A Bb G _ _ A

[+] Creating… a 2D test array with the below contents:

A A A A A A

B A Bb B Bb B

C B _ A

n u l l

[+] Removing 2D test array items from the bag…

[-] Converting 2D array to 1D…

[-] Removing duplicates in 1D array…

[>] The final 1D array now contains: A B Bb C _ n u l

[-] Removing the final 1D array items from the bag…

[>] The bag now contains 4 string(s): G o o d

=== LINKED BAG 220 JAVA ==========================================================

[>>] 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!

and punctuations. Please do not worry about ellipsis, n-dash, and m-dash, and case. Please see

https://simple.wikipedia.org/wiki/Punctuation .

## PART C – Recursion, 15 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 the

same manner as the sample run does:

## PART D – Recursion, 10 points

Please add code to the provided code to complete a recursive program that determines and

prints the nth 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, 15 points

1. Show how you count the number of operations (not only basic

operations) required by the algorithm to the right, 5 points:

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, 5 points:

Although Loop A is O(n) and Loop B is O(n2), 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.

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

Please submit both our code and our discussion.

Happy Coding!

int i, n = 5, sum = 5;

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

sum *= n + i * 7 + 37;

}

// 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;

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

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

1 4 6 4 1

Enter a row of Pascal’s Triangle: 6

1 6 15 20 15 6 1

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!

// Loop C

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

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

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

sum = sum + k;