Any idea on how to do question 1a?

W_0 and W_2 are given. W_1 should be 4.

I've gone ahead and figured out W_3 = 43 and W_4 = 142, but these two could be wrong. Hen issays that it cannot contain AA, BA, or CA, it means that if n = 3, then permutations such as AAA, BAA, or ACA are not allowed, but ABC and ABD are allowed.

CS/MATH111 ASSIGNMENT 3Problem 1:LetWnbe the number of strings of lengthnformed from lettersA,B,C, andDthat do notcontain a substringAA,BAorCA. For example, forn= 2, all the strings with this property areAB,AC,AD,BB,BC,BD,CB,CC,CD,DA,DB,DC,DDand thusW2= 13. (Note thatW0= 1, because the empty string satisfies the condition.)(a) Derive a recurrence relation for the numbersWn. Justify it.(b) Find the formula for the numbersWnby solving this recurrence. Show your work.Problem 2:Solve the following recurrence equation:fn= 13fn-2+ 12fn-3+ 2n+ 1f0= 0f1= 1f2= 1Show your work (all steps: the associated homogeneous equation, the characteristic polynomial and its roots,the general solution of the homogeneous equation, computing a particular solution, the general solution ofthe non-homogeneous equation, using the initial conditions to compute the final solution.)Problem 3:Solve the following recurrence equation:tn=tn-1+ 2tn-2+ 3nt0= 0t1= 4Show your work (all steps: the associated homogeneous equation, the characteristic polynomial and its roots,the general solution of the homogeneous equation, computing a particular solution, the general solution ofthe non-homogeneous equation, using the initial conditions to compute the final solution.)1

• 1495856311-Homework 3 prompt.pdf

ComputerScienceExpert

(11)

Status NEW Posted 27 May 2017 03:05 AM My Price 8.00

-----------

Attachments

file 1495856313-Solutions file 2.docx preview (51 words )

H-----------ell-----------o S-----------ir/-----------Mad-----------am ----------- Th-----------ank----------- yo-----------u f-----------or -----------you-----------r i-----------nte-----------res-----------t a-----------nd -----------buy-----------ing----------- my----------- po-----------ste-----------d s-----------olu-----------tio-----------n. -----------Ple-----------ase----------- pi-----------ng -----------me -----------on -----------cha-----------t I----------- am----------- on-----------lin-----------e o-----------r i-----------nbo-----------x m-----------e a----------- me-----------ssa-----------ge -----------I w-----------ill----------- be----------- qu-----------ick-----------ly -----------onl-----------ine----------- an-----------d g-----------ive----------- yo-----------u e-----------xac-----------t f-----------ile----------- an-----------d t-----------he -----------sam-----------e f-----------ile----------- is----------- al-----------so -----------sen-----------t t-----------o y-----------our----------- em-----------ail----------- th-----------at -----------is -----------reg-----------ist-----------ere-----------d o-----------n -----------THI-----------S W-----------EBS-----------ITE-----------. ----------- Th-----------ank----------- yo-----------u -----------

Not Rated(0)

• Buy Answer