(5/5)

cpts515 Midterm Exam

Do in Python using pyEDA package . You may find installation instructions at https://pyeda.readthedocs.io/en/latest/install.html

Understand how CTL formulas are interpreted on a graph.

- 0.Let
*G*be a graph over 32 nodes (namely, node 0, · , node 31). For all

0 ≤ *i**,**j** *≤31, there is an edge from node *i** *to node *j** *if·f (*i** *+ 3)%32 = *j*%32

or (*i** *+ 8)%32 = *j*%32. (% is the modular operator in C; e.g., 35% 32=3.) A node *i** *is even if *i** *is an even number. A node *i** *is prime if *i** *is a prime number.

In particular, we define [even] as the set {0 *, *2 *, *4 ·*,*6·*…*· *.*30} and [prime]

as the set { 3*, *5*, *7*, *11*, *13*, *17*, *19*, *23*, *29*, *31} . We use *R** *to denote the set of all edges in *G*.

- (20%, graded on correctness and efficiency) (write-up) Let
*p*be a CTL formula while [*p*] is the set of nodes in*G*that satisfy*p*.- Please design afix-point iteration algorithm that computes [
*EF**p*] (the set of nodes in*G*that satisfy*EF**p*from*R*and [*p*]). - Please design afix-point iteration algorithm thatcomputes [
*EGp*](theset of nodes in*G*that satisfy*EGp*from*R*and [*p*]).

- Please design afix-point iteration algorithm that computes [

You may first study the algorithms for [*AGp*] and [*AF p*].

- (50%, graded on correctness and If you use explicit graph search such as DFS, you receive 0.) (coding in Python) Every finite set can be coded as a BDD. Please write a Python program to compute [
*EG*(even∧*EF*prime)] (the set of nodes that satisfy the formula*EG*( even∧*EF*prime).), and verify

your answer by checking

node 5 satisfies *EG*(even∧ *EF *prime) and node 6 doesn’t satisfy *EG*(even∧ *EF *prime).

(Important: your code shall first encode *R*, [even], [prime] in BDDs using pyEDA and then using methods provided with the package, implement the iteration algorithms provided in 3 symbolically in BDD using methods in the package. Many students’ find methods *BDD. compose* () and *BDD. smoothing* () are quite useful in the package.)

*L*of DNA strands, where each strand is simply a string on alphabet {*A, T, C, G}*(that is, a strand is a sequence of nucleotides, each of which is chosen from four nitrogen-containing nucleobases.). One may use a deterministic finite automaton (DFA)1*M*

(which itself is a graph) to *model *the set *L*; i.e L ⊆ *L*(*M *). That is, each

strand *w** *in *L*, there is a walk in *M *(from the initial state to an accepting state) such that the symbols sequentially collected on the transitions on the walk form exactly the *w*. Clearly, many many different *M *can be used to model *L** *(e.g., *M *can be ridiculously simple with only one state and accepting every word on the alphabet.). Consequently, one need come up with a metric *Q*(*M**, L*), which is a real number, to characterize the “precision” on using the given *M *to model *L*. When this is done, one can argue, for two given DFAs *M*1 and *M*2 which both model the given *L*, which model is more precise. Now, you need write a mini-paper (of 1 or 2 or more pages) in figuring out ways to define *Q*(*M**, L*) and to design algorithms to compute *Q*(*M**, L*).23

1I assume that you know finite automata theory, which is covered in wsu undergaduate required course cpts317.

2Important: I am not interested in how to create a model *M *from the given *L*. Instead, I am interested in, when *M *and *L *are given, how to measure the precision.

3More important: *L*(*M *) or the language accepted by the given model *M *is most likely to be an infinite language. But the given set *L *is always finite. The case that *L*(*M *) is finite is trivial and don’t spend a minute on it.

(5/5)

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

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. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

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

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