HW 4

pdf

School

University of California, Davis *

*We aren’t endorsed by this school

Course

122B

Subject

Computer Science

Date

Feb 20, 2024

Type

pdf

Pages

Uploaded by ConstableDiscoveryRedPanda31

Assignment 4 Setareh Rafatirad ECS 122B Winter 2021

Problem 1 (20 points) a) (10 pts) Modify the Binary Search method provided in Lecture 9, slide 20 so it returns all occurrences of a pattern. b) (10 pts) Provide an example for part (a) and show how your solution works on the example (think of a text T and a pattern that repeatedly occurs in T. Your algorithm should return a range of indexes where the corresponding suffix(s) start with the pattern). Answer [Fill in here] Problem 2 (20 points) a) (10 pts) Given a text T = never - ever - say - never - again $ , create BWT(T) and show your complete work. Explain which approach you used to create BWT(T). b) (10 pts) Reverse BWT(T) and show your complete work. Show all the steps and explain your approach. Answer [Fill in here] Problem 3 (20 points) a) (10 pts) What is the Brute force running time for creating BWT (i.e., BWT via BWM)? b) (10 pts) Show that BWT[i] = T[SA[i] - 1], where T is the input string, BWT[i] is the character at position i in the BWT string for T, and SA[i] is 1

the i th entry in the suffix array for T. Answer [Fill in here] Problem 4 (20 points) In randomized selection, assume the expected value of randomly choosing a number in the middle 50% percentile is 2. a) (10 pts) Analyze the randomized selection given that the expected value of getting a number in the middle 50% percentile is 3. b) (10 pts) Analyze given that your expected value of getting a number in the middle 60% is a . Where a is some constant. Answer [Fill in here] Problem 5 (20 points) Run the randomized selection by hand algorithm to find 4 th smallest term in the String S. S = { 2,3,6,5,5,21,8,13,11,20,4,1 } note: Use a random number generator to determine the pivot point P https://www.random.org/ Answer [Fill in here] 2

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

Related Documents

Asg3-ethereum-sep21 (1).docx

Review_CNNs_solution.pdf

HW3a.knit.pdf

FCS 240 Assignment 1 - Winter 24.docx

Recommended textbooks for you

C++ Programming: From Problem Analysis to Program...

Computer Science

ISBN:9781337102087

Author:D. S. Malik

Publisher:Cengage Learning

Systems Architecture

Computer Science

ISBN:9781305080195

Author:Stephen D. Burd

Publisher:Cengage Learning

COMPREHENSIVE MICROSOFT OFFICE 365 EXCE

Computer Science

ISBN:9780357392676

Author:FREUND, Steven

Publisher:CENGAGE L

C++ for Engineers and Scientists

Computer Science

ISBN:9781133187844

Author:Bronson, Gary J.

Publisher:Course Technology Ptr

SEE MORE TEXTBOOKS

Recommended textbooks for you

C++ Programming: From Problem Analysis to Program...
Computer Science
ISBN:9781337102087
Author:D. S. Malik
Publisher:Cengage Learning
Systems Architecture
Computer Science
ISBN:9781305080195
Author:Stephen D. Burd
Publisher:Cengage Learning
COMPREHENSIVE MICROSOFT OFFICE 365 EXCE
Computer Science
ISBN:9780357392676
Author:FREUND, Steven
Publisher:CENGAGE L
C++ for Engineers and Scientists
Computer Science
ISBN:9781133187844
Author:Bronson, Gary J.
Publisher:Course Technology Ptr