dee complete please help

Complexity Theory

(a) Defifine the set of Boolean expressions 2CNF and the language 2SAT over them.

(b) For a Boolean expression in 2CNF, let G() be the directed graph with vertices

the variables of and their negation, and with edges (a, b) if, and only if, there

is a clause (a b) or (b a) in . Note that an edge (a, b) is in G() if, and

only if, so is the edge

Prove that a Boolean expression in 2CNF is unsatisfifiable if, and only if, there

is a variable x in such that there are paths from x to x and from x to x in

G(). [Hint: Recall that the proposition (P Q) is equivalently the implication

(P Q).] [12 marks]

(c) Argue as to whether or not 2SAT is in NL, in P, and in NP. Your answer may

use the fact that NL is closed under complementation. [6 marks]

4CST1.2021.6.5

4

Complexity Theory

(a) For a complexity class C, let co-C = { L | L C } and say that C is closed under

complementation whenever C = co-C.

Argue as to whether the following statements are true, false, or unknown.

(i) All deterministic time complexity classes are closed under complementation.

[3 marks]

(ii) All non-deterministic time complexity classes are closed under

complementation. [3 marks]

(b) For a mapping f : on an alphabet and a language L , defifine

f[L] = { f\ (w) | w L } where f\ (a1 an) = f(a1) f(an).

Prove that L NP implies f[L] NP. [4 marks]

(c) Consider the following decision problem.

Q: Given natural numbers m and n in N, and bits a

(k)

i,j

and bk in

{0, 1} for 1 k m and 1 i, j n, determine whether the system

of equations P 1i,jn a

(k)

i,j

xi xj = bk (1 k m) with unknowns

x1, . . . , xn has a solution in arithmetic modulo 2.

(i) Prove that Q is in NP. [3 marks]

(ii) By means of a polynomial-time reduction from the problem 3CNF, or

otherwise, prove that Q is NP-hard. [Hint: Note, for instance, that x = y

in the Boolean algebra {0, 1} if, and only if, xx + yy = 1 in arithmetic

modulo 2.] [7 marks]

You may use standard results provided that you state them clearly.

5CST1.2021.6.6

5

Computation Theory

(a) For each n, e N, let

(n)

e

denote the partial function Nn* N computed by the

register machine with index e using registers R1, . . . , Rn to store the n arguments

and register R0 to store the result, if any.

Explain why for each m, n N there is a totally defifined register machine

computable function Sm,n : N 1+m N with the property that for all (e, ~x)

N 1+m and ~y Nn

(n

)

S

m,n

(e,~x)(~y)

(m+n)

e

(~x, ~y) (1)

where denotes Kleene equivalence: for all z N, the left-hand side is defifined

and equal to z if and only if the right-hand side is defifined and equal to z.

Your explanation should make clear what assumptions you are making about

the relationship between numbers and register machine programs. [10 marks]

(b) Let f : N 1+m+n* N be a register machine computable partial function of 1+m+n

arguments for some m, n N.

(i) Why is the partial function f : N 1+m+n* N satisfying for all (z, ~x, ~y)

N 1+m+n

f(z, ~x, ~y) f(S1+m,n(z, z, ~x), ~x, ~y) (2)

register machine computable? [3 marks]

(ii) By considering S1+m,n(e, e, ~x) where e is an index for the partial function

f in part (b)(i), prove that there is a totally-defifined register machine

computable function fifix f : Nm N with the property that for all ~x Nm

and ~y Nn

(n)

fifix

f(~x)(~y) f(fifix f(~x), ~x, ~y) (3)

[7 marks]

6CST1.2021.6.7

6

Computation Theory

A set A equipped with a binary operation @ : A A A is a combinatory algebra

if there are elements K, S A satisfying for all a, b, c A

@(@(K, a), b) = a

(1)

@(@(@(S, a), b), c) = @(@(a, c), @(b, c)) (2)

(a) Show that there is a binary operation on the set of equivalence classes of closed

-terms for the equivalence relation of -conversion that makes it a combinatory

algebra. [5 marks]

(b) Show that every combinatory algebra A contains an element I satisfying

@(I, a) = a

(3)

for all a A. [Hint: what does (2) tell us when a = b = K?] [2 marks]

(c) For an arbitrary combinatory algebra A, let A[x] denote the set of expressions

given by the grammar

e ::= x | p aq | (ee)

where x is some fifixed symbol not in A and a ranges over the elements of A.

Given e A[x] and a A, let e[x := a] denote the element of A resulting from

interpreting occurrences of x in e by a, interpreting the expressions of the form

p a0 q by a0 and interpreting expressions of the form (ee0 ) using @.

(i) Give the clauses in a defifinition of e[x := a] by recursion on the structure of

e. [2 marks]

(ii) For each e A[x] show how to defifine an element xe A with the property

that

@(xe, a) = e[x := a] (7)

for all a A. [6 marks]

(d) Recall the usual encoding of Booleans in -calculus. Using Part (c)(ii), show

that in any combinatory algebra A there are elements True, False A and a

function If : A A A satisfying

@(If (a, b), True) = a

(11)

@(If (a, b), False) = b

(12)

for all a, b A

[5 marks]

7CST1.2021.6.8

7

Data Science

(a) Let xt be the number of new COVID infections on date t. We anticipate

approximately exponential growth or decay, xt+1 (1 + )xt , and we would

like to estimate from a dataset (x1, . . . , xT ).

(i) Find the maximum likelihood estimator for for the model

Xt+1 Poisson

Utilizing the data gave for the situation study, would you be able to assemble a Context graph, Level 0 Data Flow Diagram, and an ERD utilizing any outlining programming.

The 2020 Covid pandemic has affected numerous enterprises across the globe and Australia's organic product picking industry is no exemption. Natural product send out contributes fundamentally to Australia's exchange. Most natural products are by and large transitory and consequently natural product picking is something that should be done brilliantly and with care. In spite of the fact that Australia's organic product picking industry faces a few issues, one of them is absence of adequate labor. This issue, among many, has exasperated as of late because of COVID 19. To help the ranchers and the natural product picking industry, Zaf Soft, an Australian Information System supplier association has concocted an online arrangement that would assist with fruiting ranchers pick organic product well on schedule. The CEO of Zaf Soft, Rabee James has chosen to send off a site donesloching.com. The thought is basic, innovative and in particular it adds financial worth. donesloching.com would permit Australian ranchers and organic product pickers to enroll on this site. While ranchers can enlist separately, the site additionally permits bunch enrollment for organic product pickers. Natural product pickers are common individuals dwelling in Australia who wish to add to organic product picking. These individuals frequently wish to work/procure compensation or on occasion be essential for the organic product picking process for relaxation as it were. The enlistment cycle for the ranchers is basic. Ranchers give their contact subtleties, ranch address and above all; their business charge subtleties. This is went with a picture ID that is likewise given as a feature of the enlistment interaction. The organic product pickers give a lot of comparative subtleties in the event that they wish to do natural product picking for procuring an everyday, month to month or a time-based compensation. For this situation they additionally give bank subtleties while enlisting. As opposed to this, in the event that the natural product picker wishes to enroll for recreation just, bank subtleties and expense subtleties are not needed by the framework. Natural product picker's gathering enrollments is just conceivable assuming that the enlistment is for relaxation as it were. The site permits the natural product pickers to choose and plan their visits for natural product picking for a specific ranch; seven days ahead of time. Each mentioned plan is supported by the rancher and afterward the natural product pickers get endorsement warning by means of email or potentially as portable instant message (as solicitation by the natural product picker). Visits to the homestead without rancher's endorsement are not permitted and not upheld by the framework and the mentioned plan is auto declined in no less than multi week from the mentioned date if in any case not supported by the rancher. While mentioning for a timetable, the natural product pickers give subtleties of the fruit(s) that they need to pick. This is to guarantee the executives of wages, time, instrument and assets expected to play out the work action. Compensation differ with time, weight of organic product picked and the kind of organic product. The compensation is chosen according to the rancher's circumspection and is given by the rancher at the hour of enlistment. If there should be an occurrence of organic product pickers who are picking for recreation just, subtleties of organic product or organic products that they wish to pick is additionally significant on the grounds that this guarantees general and using time productively at the rancher's end. The framework likewise permits 'giving' also. With this usefulness, the ranchers conclude how much organic product they would gift (concerning weight, as a rate or proportion) to the natural product picker(s) who wish to just pick organic product for relaxation. This data is likewise given by the rancher at the hour of enlistment and comparable measure of organic product is given as gift by the rancher, on the homestead, to the natural product pickers, in view of how much natural product has been picked. The giving system likewise permits ranchers to make a job of gift administrator. The job of the gift administrator is simply to help the rancher. The gift supervisor is just liable for distributing gifts (natural product) according to the data given by the rancher at the hour of enrollment. The framework, subsequently, monitors how much natural product was talented and how much was picked. For the organic product pickers who are picking to acquire compensation, the data for example 'how much natural product is picked?', is significant for wage the executives reason. donesloching.com permits organic product pickers to drop their visits. It additionally permits, crossing out of enrollment for the two ranchers and organic product pickers. Essentially, the site permits both the gatherings to make changes to their enrollment as and when required. The site upholds a total entrance for the ranchers and the natural product picker.

The organic product picker's entrance permits them to see their past and impending exercises/schedules. They can likewise see subtleties of their record. For each visit to the homestead, they can add remarks, encounters and memory photos. Rancher's entry likewise permits them to see their past, current and impending homestead reservations. The ranchers can perceive how much natural product was gathered by each natural product pickers and what was gifted or paid to them. They can see nitty gritty remarks and encounters of each natural product picker for each booking. The rancher's entryway additionally permits them to choose photos of the natural product picking action for the site's photograph display. Just the photos that the organic products pickers permit to share can be shared by the ranchers. At last, the site additionally permits the ranchers to produce day to day, week after week and month to month reports to get quantitative understanding into entire organic product picking movement and the fruit(s) picked. Rabee James, the CEO of Zaf Soft, is sure that this site would be an enormous achievement. Zaf Soft designs to acquire from ranchers. Extremely negligible membership charges are charged from the ranchers at the hour of enrollment. donesloching.com permits month to month and yearly memberships. The membership charges are chosen by the administration of Zaf Soft and can be added to the framework by means of the administrator entry. The overseer is mindful of dealing with the general site's smooth working, information reinforcement, recuperation and up gradation.

18.3 For WEP, information integrity and statistics confidentiality are carried out using the RC4 stream encryption set of rules. The transmitter of an MPDU performs the subsequent steps, called encapsulation: 1. The transmitter selects an initial vector (IV) price. 2. The IV price is concatenated with the WEP key shared by transmitter and receiver to form the seed, or key input, to RC4. 3. A 32-bit cyclic redundancy take a look at (CRC) is computed over all the bits of the MAC information subject and appended to the facts field. The CRC is a not unusual blunders-detection code used in records link control protocols. In this example, the CRC serves as a integrity take a look at price (ICV). 4. The result of step three is encrypted using RC4 to form the ciphertext block. 5. The plaintext IV is prepended to the ciphertext block to shape the encapsulated MPDU for transmission. A. Draw a block diagram that illustrates the encapsulation manner. B. Describe the steps at the receiver give up to get better the plaintext and carry out the integrity check. C. Draw a block diagram that illustrates part b.

Consider the subsequent threats to Web security and describe how every is countered by using a particular characteristic of TLS. A. Brute-Force Cryptanalytic Attack: An exhaustive seek of the important thing area for a traditional encryption algorithm. B. Known Plaintext Dictionary Attack: Many messages will contain predictable plaintext, along with the HTTP GET command. An attacker constructs a dictionary containing each viable encryption of the regarded-plaintext message. When an encrypted message is intercepted, the attacker takes the component containing the encrypted known plaintext and appears up the ciphertext within the dictionary. The ciphertext must in shape towards an entry that changed into encrypted with the equal secret key. If there are several suits, every of those can be tried in opposition to the whole ciphertextual content to determine the right one. This assault is especially effective in opposition to small key sizes (e.G., forty-bit keys). C. Replay Attack: Earlier TLS handshake messages are replayed. D. Man-in-the-Middle Attack: An attacker interposes during key change, performing as the patron to the server and as the server to the patron. E. Password Sniffing: Passwords in HTTP or other application visitors are eavesdropped. F. IP Spoofing: Uses cast IP addresses to idiot a bunch into accepting bogus data.

import java.util.Arrays, pubiic dlass Arraystackc|> Implements Stack!ntertacex>Private ll stack// Array of stack entries private int toplndex;/7 Index of top entry private static final int DEFAULT-CAPACITY = 50;/ Construct a stack with DEFAULT_CAPACITY public ArrayStack0 this (DEFALULTCAPACIT Y) > // end default constructor/ Construct a stack with the given initialCapacity * /* Throw StackException if initialCapacity0 public ArrayStack(int initialCapacity) // add stataments> // end constructor public void push(T newEntry) // add stataments // end push/* Throw StackException if stack is empty publicT peek) // add stataments return null; > // end peek Throw StackException if stack is empty / publicT pop0 // add stataments return null;/ end pop public boolean empty) // add stataments return false; // end empty public int size0 / add stataments return 0;> // end size public void clear) // add stataments 1// end dlear /toString) returns a list of data in Stack, separate them with" public String toString0 // add stataments return nul; // double the size of array using Arrays.copyof 0 private void doubleArray0 // add stataments // end doubleArray public interface Stacklntertace T> /Gets the current number of data in this stack @return the integer number of entries currently in the stack public int size); Adds a new data to the top of this stack. @param aData an object to be added to the stack/ public void push (T aData); Removes and returns this stack's top data. @return the object at the top of the stack @throw StackException if the stack is empty* public T pop); / Retrieves this stack's top data. @return either the data at the top of the stack athrow StackException if the stack is empty public T peek); Detects whether this stack is empty @return true if the stack is empty / public boolean empty) Removes all data from this stack public void clear) // end MyStackinterface O th in

Correct Tower application to move the disks from the pin on the left to the pin on the right. Hint: draw the motion of th disks for a small set "say three" and walk your way through the recursion. #include using namespace std; void towers(int,char,char,char); int main) int num; cout << "Number of disks: cin >> num; cout << "Sequences begin here ; towers(num, 'A', 'B! "C"); return 0 void towers(int num, char frompeg, char topeg.char auxpe ifnum == 1) cout << "Move disk 1 from" << frompeg <<" to peg" a topeg << endl; return; towers(num - 1, frompeg, auxpeg, topeg): cout << "Move disk" << num << "from peg" << frompe towers(num 1, auxpeg, topeg, frompeg): "to peg" << topeg << endl;

ITTCTUae siOStrEattiP using namespace std; struct ListNode{ float value; ListNodenext; ListNode *head; class LinkedList { public: int insertNode(float num); void deleteNode(float num); void destroyList0; void displayList0: LinkedList(void) {head = NULL) -LinkedList(void) (destroylist0 int LinkedList:insertNode(float num) struct ListNode *newNode, *nodePtr = head, *prevNodePtr = NULL: newNode = new ListNode; if(newNode = = NULL) {

Question 2) Use Point class to define another class called Rectangle which has only two data members of type Point named UpperLeftPoint and BottomRightPoint a. Define two constructors one is default and one is initializer b. Define member functions named getLength of rectangle c. Define member functions named get Width of rectangle d. Define member functions named getArea of rectangle. Note, the values of the functions are calculated based on the two points of the rectangle e. Define member functions named isLarger(Rectangle &R2), that compares the original object with R2 based on area, and t bool isOverlapped(Rectangle &R2) that returns true if original g. Define member functions named Print0, that prints the returns true if its area is larger, or false otherwise object is Overlapped with R2 object and false otherwise r in the previous two questions and note the following: Make sure to validate the input in the Implement the functions described setters If an invalid value is provided, an appropriate error message should be shown

#include #include #include using namespace std // Implementation of the ParkedCar Class // This class should simulate a parked car class ParkedCar I/Private data members private: string make string model; string color string licenseNumber; int numberOfMinutes; public: // default constructor ParkedCar0 make = " model-= ,

//constructor ParkedCar(string cMake, string cModel, string cColor, string cLicenseNum, int cNumMinParked) make cMake; model = cModel; color = CColor; licenseNumber = cLicenseNum; numberOfMinutes = cNumMinParked; //Setters void ParkedCar::setmake(string amake) make amake; void Parked Car::setmodel(string amodel) model = amodel; void ParkedCar:setcolor(string acolor) Color acolor

The abstract syntax of commands in a simple parallel programming language P is given by C ::= skip 2 where ie, be and X range over the syntactic categories of integer expressions, boolean expressions and program variables, respectively. The intended behaviour of C1 k C2 is that C1 and C2 are executed in parallel until they have both terminated. Hence atomic execution steps from C1 and C2 may be arbitrarily interleaved. The other command forms behave as usual. (a) Give a small-step transition semantics for P which derives statements of the form hC, Si hC 0 , S0 i, where S and S 0 are states. You may assume that rules for the evaluation of expressions have already been given. Comment briefly on your choice of what constitutes an atomic execution step. [9 marks] (b) The binary relation on commands is defined by C1 C2 S, S0 . hC1, Si hskip, S0 i hC2, Si hskip, S0 i. Show that is not a congruence. [5 marks] (c) Assuming that S(X) = S(Y ) = 0, describe the set of possible execution traces which are derivable in your semantics starting from the configuration hC, Si, where C is (X := 1) k (while X = 0 do Y := Y + 1). Why might one argue that this does not accurately reflect the behaviour of a reasonable implementation of the language? [6 marks]

This question concerns lexical grammars. (a) Tree Adjoining Grammars contain two types of elementary tree. (i) What are these trees called? [1 mark] (ii) If one were building a grammar for English which aspects of language do the two tree types model? [2 marks] (b) Provide a Tree Adjoining Grammar that can parse the string: students enjoy easy exams [5 marks] (c) Show how a parse for this string is constructed. Explain the operations. [5 marks] (d) Provide a Categorial Grammar that can parse the same sentence. [4 marks] (e) When children learn their first language they usually acquire nouns before verbs before modifiers. They also usually produce single word strings before moving on to longer strings. With reference to Tree Adjoining Grammars and/or Categorial Grammars propose some hypotheses for this. Justify your proposals.

A birdsong is composed of a sequence of these elements as follows: c c d c c e c c d c c d c c e (a) (i) Using byte pair encoding induce a context-free grammar for this sequence of birdsong. Show your workings and state what you have decided to do in the case of a tie. [6 marks] (ii) Draw the derivation tree that parses the birdsong using your induced grammar. [1 mark] (iii) What are the shortcomings of this method of grammar induction for natural languages? [3 marks] (b) Assuming that c, d and e are the only melodic elements available in the birdsong, and that the excerpt we are given is probabilistically representative of the birdsong in the wild, what is the average information produced per element? Provide relevant equations. [3 marks] (c) In Part (b) we assumed a 1st-order model of the birdsong. What assumption does this make about the sequence of elements? [1 mark] (d) Consider a 2nd-order model of the birdsong and calculate the conditional entropy. Provide relevant equations. [4 marks] (e) How can we calculate the entropy rate of birdsong? Provide relevant equations

Consider expressions represented using the following ML datatype: datatype exp = Var of string | Neg of exp | Divide of exp * exp (a) Using at least one union, define a type or types in the C language for conveniently storing such expressions. [5 marks] (b) Give efficient C code that checks whether two structures represent identical expressions. (Do not consider whether they might evaluate to the same result.) Explain how much of the input expressions is explored when they differ. [4 marks] (c) Given that a lot of expressions are to be rapidly generated and discarded, what considerations apply to storage management? Define and discuss at least 3 different approaches to storage management. [5 marks] (d) The substitution operation for an expression replaces all occurrences of one variable with another variable. Given that sub-expression trees are commonly shared over numerous expressions, explain a problem that could arise in the substitution operation. Explain the details of a solution to the problem by giving code or otherwise. [6 mark

(a) Derive an expression for the gradient Ei(w) wj for weight wj in an output node when Ei(w) is the error for the ith example Ei(w) = 1 2 (yi h(w; xi))2 , h(w; xi) is the output of the complete network for the ith example, and (a) = a. You need only derive the expression for the output node. [3 marks] (b) Derive an expression for the gradient Ei(w) wj for weight wj in an output node when (a) = 1/(1 + exp(a)) and the error for the ith example is Ei(w) = yi log h(w; xi) + (1 yi) log(1 h(w; xi)). You may use the fact that d(a)/da = (a)(1 (a)). You need only derive the expression for the output node. [7 marks] (c) In the standard backpropagation algorithm the central quantity of interest for each node N is = Ei(w)/a. It is proposed that, instead of using nodes in the form presented above, we introduce functions i and construct multilayer networks from nodes that compute z = (a) where

and the functions i are fixed, having no further parameters. A multilayer perceptron is constructed from nodes of this kind. Give a detailed, general derivation of the formula for computing for a non-output node N in this network, assuming you know the values of for the nodes connected to the output of N. [10 marks

The standard linear regression model uses a hypothesis

h(x, w, b) = wT x + b

to fifit m examples ((x1, y1), . . . ,(xm, ym)) by minimizing the error

(yi h(xi, w, b))2 .

(a) Derive a gradient descent algorithm for training the linear regression model

described. [5 marks]

(b) In the application of interest, you believe that it is desirable to train such that

the learned parameters have ||w|| ' 1. Suggest a modifification to E(w, b) that

facilitates this, and derive the corresponding gradient descent training algorithm.

[5 marks]

(c) Describe the components of a general heuristic search problem. [4 marks]

(d) You are faced with a heuristic search problem, but the heuristics you have so far

developed are less effffective than desired. Suggest two ways in which supervised

machine learning might be used to develop a better heuristic, mentioning if

necessary any corresponding disadvantages of using the approach. You may

assume that a collection of problems to be solved by the heuristic search is

available. [6 marks]

2CST1.2021.6.3

2

Artifificial Intelligence

A Boolean satisfifiability problem has four variables, x1, x2, x3 and x4. A literal l

can be a variable or its negation, denoted l. The formula of interest, in conjunctive

normal form (CNF), is

f = (x2 x3) (x2 x3) (x1 x2 x4).

(1)

The aim is to fifind assignments to the variables such that f is true under the usual rules

for Boolean operations. This question addresses the use of more general constraint

satisfaction to solve this problem.

(a) Give a general description of a constraint satisfaction problem (CSP).

[3 marks]

(b) Explain how a Boolean satisfifiability problem in CNF form and with n variables

can be converted to a CSP, also having n variables and having a suitable

constraint for each clause. Illustrate your answer using the 4-variable formula f

in (1). [3 marks]

(c) Explain, again using a constraint corresponding to a clause from (1), how general

constraints can be converted to binary constraints. Provide a graph illustrating

the problem from (1) after it has been converted to a CSP with only binary

constraints. [4 marks]

(d) Explain, how forward checking works in the context of a general CSP. How does

this benefifit a CSP solver? [3 marks]

(e) Using the CSP equivalent you developed for (1), with only binary constraints,

demonstrate how forward checking works using the sequence of assignments

x1 = F, x2 = F, x4 = T. [5 marks]

(f ) How would you expect the solution obtained when applying forward checking to

be affffected if constraints were allowed to propagate more widely?