CS251 – Data Structures and Algorithms Fall 2021 Homework 5

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

  

 

CS251 – Data Structures and Algorithms Fall 2021

1

Homework 5

 

Instructions:

Type your answers to the following questions and submit them in a single PDF file on Gradescope by the

due date and time listed above. Put each question on a separate page and assign pages accordingly

when you submit. You should give justification for all your answers, even if the question does not

explicitly say so.

Important:

• From the syllabus: “Figures, diagrams, and complex mathematical notations can be handwritten

and included in the PDF as an image, but illegible solutions will receive no credit. Note that the

definitions of "complex" and "illegible" are at the grader's discretion, so it is in your best interest

to type your solutions whenever possible.” All images and diagrams must be placed in a vertical

layout and with a clean background. A picture with smudges, blots, or lazy handwriting will receive

no credit. We will not accept regrade requests if an image or diagram does not have a bare

minimum of professional presentation.

• Homework assignments in Gradescope without correct page selection will be graded with 0 even if

the answers are correct. We will not give partial credits in such a case either.

• Individual homework assignments reschedule due to a valid reason (e.g., medical, military, grief)

should be requested through the Office of the Dean of Students. You need to send your request

with anticipation. We will not consider requests made after the respective deadline. We will not

grant extensions beyond 11/10/2021 due to academic calendar.

• Check the syllabus for additional information on late days, extensions, grading, and regrade

requests.

On academic dishonesty:

Although you are allowed to discuss these problems with other people, your work must be entirely your

own. It is considered academic dishonesty to read anyone else’s solution to any of these problems,

share your solution with another student, or post questions/answers on the Internet. We will report all

academic dishonesty incidents to the Office of Student Rights and Responsibilities without exception.

More information on this matter is in the syllabus.

Problem 1 (10 points):

Show the Brute-Force pattern matching algorithm on the following two patterns for the same text and

give the total number of compares that are necessary in each case.

T = where_there_is_a_will_there_is_a_way

P = a_way

CS251 – Data Structures and Algorithms Fall 2021

2

Problem 2 (10 points):

Show the KMP pattern matching algorithm on the following pattern and text and give the total number

of compares that are necessary. Be sure to show the failure function.

T = sqraaaqrrrsqsqsqrsq

P = sqrsq

Problem 3 (20 points):

a) Is the above FA Deterministic?

b) Does the FA accept or reject the following strings?

• aabba

• ababab

• bbbaa

• babaa

• baaabb

• bababa

• abababbaaabbbabababa

• ab

• bbb

• bbaaab

c) What are the two smallest strings which can be accepted by the FA?

CS251 – Data Structures and Algorithms Fall 2021

3

d) From part (b), and the state transition diagram of the FA, generalize the type of input string

recognized by the FA.

Problem 4 (10 points):

Kate wants to send a message to Mike. Since the message is confidential, she wants to encode the

message and then send the encoded message to Mike. Mike also receives a “key” (code) from Kate so

he can decode the received encoded-message. Assume that the message Kate sent has the following

characters appearing with their corresponding frequencies, as shown in the table. Construct a Huffman

Tree for the given data in the table and show the final Huffman code for each character. Note- when

assigning codes in the tree, make sure to assign the left child as 0 and right child as 1. Also, calculate the

average number of bits needed to encode a character (use appropriate units).

A 0.4

B 0.2

C 0.05

D 0.15

_ 0.2

Problem 5 (20 points):

Consider the following regular expressions (space characters added for readability only):

• (ab)* (ba)* | (aa*)

• (((ab) | (aab))* a*)*

• ((a* b* a*)* b)*

• ((ba) | b)* | ((bb) | a)*

a) Give a non-trivial string (i.e., the empty string 𝜖𝜖) accepted by all four regular expressions. If not

possible, explain formally why it is not possible.

b) For each regular expression, give a string only recognized by such regular expression and not by the

other three. If not possible, explain formally why it is not possible.

CS251 – Data Structures and Algorithms Fall 2021

4

Problem 6 (15 points):

a) For each of the following sets of strings, construct a Standard Trie. Add the dollar sign at the end of

each word to allow word to be prefixes of other words in the same set.

• {feet, feat, fiction, feature, farther, fashion, fathom, father, feast, feather}

• {let, lettuce, letter, lexicon, recur, radius, reflex}

• {sneak, pause, cover, react, taunt}

 

b) Convert each of the Standard Tries you constructed on the previous question into a Compressed

Trie.

Problem 7 (15 points):

a) Construct a Suffix Trie from the following string: bibbidibobbidi$

CS251 – Data Structures and Algorithms Fall 2021

5

b) Given the following Suffix Trie, state whether each string below occurs in the source string, and if so,

how many times it occurs.

• TAG

• AGT

• CG

• A

• GTAC

c) What is the longest substring in the Suffix Trie above that appears more than once?

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of