solve the recurrence relations for a discrete numeric function

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Question 1

Find the generating functions for the following sequences;

(a) 3, 0, 8, 1, 0, 1/7, 100, …                                                                                  [3]

(b) 4,4,4,4,4, …                                                                                                     [3]

(c) Write the generating function in (b) above in its closed form.                      [4]

Question 2

(a) Explain the meaning of asymptotic behaviour.                                              [2]

(b) Let 𝑎 and 𝑏 be discrete numeric functions defined by;

                       ar=2r

                       br=r+r2

(i) Plot the linear graphs for ar and br. [6]

(ii) Determine which numeric function here asymptotically dominates.              [2]

Question 3

(a) Distinguish between a terminal and a non-terminal symbol.                          [2]

(b) Using examples explain what type-0 and type-1 grammar are.                      [2]

(c) Solve the recurrence relations for a discrete numeric function defined such that;

              𝑎𝑛+1 = 4𝑎𝑛 − 2, and has 𝑎0 = 1

(i) Complete the sequence by finding the a1, a2, a3, and a4 terms of the function.                 [4]

(ii) Write the corresponding generating function for the numeric function in (i).                     [2]

Question 4

A counter is a finite state machines that counts from 00, 01, 10, 11 and start all over again on

consecutive inputs of clock signal = 1. The counter does not change its state when the clock signal

= 0. You are required to model the count described here using:

(a) State transition table                                                                  [5]

(b) State transition diagram                                                            [5]

Question 5   

Determine the generating function for the discrete numeric function 𝒂𝒓 where,

𝒂𝒓 = { 2 𝑟 , 𝑖𝑓 𝑟 𝑖𝑠 𝑒𝑣𝑒𝑛 −2 𝑟 − 2𝑟, 𝑖𝑓 𝑟 𝑖𝑠 𝑜𝑑d                               [10]

Attachments:

Related Questions

. The fundamental operations of create, read, update, and delete (CRUD) in either Python or Java

CS 340 Milestone One Guidelines and Rubric  Overview: For this assignment, you will implement the fundamental operations of create, read, update,

. 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

Retail Transaction Programming Project  Project Requirements:  Develop a program to emulate a purchase transaction at a retail store. This

. The following program contains five errors. Identify the errors and fix them

7COM1028   Secure Systems Programming   Referral Coursework: Secure

. Accepts the following from a user: Item Name Item Quantity Item Price Allows the user to create a file to store the sales receipt contents

Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip

. The final project will encompass developing a web service using a software stack and implementing an industry-standard interface. Regardless of whether you choose to pursue application development goals as a pure developer or as a software engineer

CS 340 Final Project Guidelines and Rubric  Overview The final project will encompass developing a web service using a software stack and impleme