Mathematics > QUESTIONS & ANSWERS > Questions and Answers > University of Illinois, Urbana Champaign - ECE 374Ahw5-sol CS/ECE 374A Homew (All)

Questions and Answers > University of Illinois, Urbana Champaign - ECE 374Ahw5-sol CS/ECE 374A Homework 5 Solutions Spring 2018.

Document Content and Description Below

It’s almost time to show off your flippin’ sweet dancing skills! Tomorrow is the big dance contest you’ve been training for your entire life, except for that summer you spent with your uncle i... n Alaska hunting wolverines. You’ve obtained an advance copy of the list of n songs that the judges will play during the contest, in chronological order. For each integer k, if you dance to the kth song on the schedule, you will be awarded exactly Score[k] points, but then you will be physically unable to dance for the next Wait[k] songs (that is, you cannot dance to songs k + 1 through k + Wait[k]). Describe and analyze an efficient algorithm to compute the maximum total score you can achieve. The input to your sweet algorithm is the pair of arrays Score[1.. n] and Wait[1 .. n] Suppose you are given a NFA M = (f0,1g,Q, s, A,δ) and a binary string w 2 f0,1g∗. Describe and analyze an algorithm to determine whether M accepts w. Report the running time of your algorithm as a function of k (the number of states in M) and n (the length of the input string w) Describe and analyze an efficient algorithm to find the smallest number of palindromes that make up a given input string. For example, given the input string BUBBASEESABANANA, your algorithm should return the integer 3. [Show More]

Last updated: 2 years ago

Preview 1 out of 7 pages

Buy Now

Instant download

We Accept: