Give an asymptotic upper bound

Assignment Help Engineering Mathematics
Reference no: EM132136341

Assignment -

1. Let (T, ∧, ∨,', 0, 1) be a Boolean Algebra.

Define ∗ : T × T → T and o : T × T → T as follows:

x ∗ y := (x ∨ y)' x o y := (x ∧ y)'

(a) Show, using the laws of Boolean Algebra, how to define x ∗ y using only x, y, o and parentheses.

(b) Show, using the laws of Boolean Algebra, how to define x o y using only x, y, ∗ and parentheses.

Define R ⊆ T × T as follows: (x, y) ∈ R if, and only if, (x ∧ y) ∨ (x' ∧ y') = 1

(c) Show, using the laws of Boolean Algebra, that R is an equivalence relation. Hint: You may want to use the observation that if A = B = 1 then A ∧ B ∧ C = A ∧ B implies C = 1 (why?)

2. Let P F denote the set of well-formed propositional formulas made up of propositional variables, T, ⊥, and the connectives ¬, ∧, and ∨. Recall from Quiz 7 the definitions of dual and flip as functions from PF to PF:

  • dual(p) = p
  • flip(p) = ¬p
  • dual(T) = ⊥; dual(⊥) = T
  • flip(T) = T; flip(⊥) = ⊥
  • dual(¬φ) = ¬dual(φ)
  • flip(¬φ) = ¬flip(φ)
  • dual(φ ∧ ψ) = dual(φ) ∨ dual(ψ)
  • flip(φ ∧ ψ) = flip(φ) ∧ flip(ψ)
  • dual(φ ∨ ψ) = dual(φ) ∧ dual(ψ)
  • flip(φ ∨ ψ) = flip(φ) ∨ flip(ψ)

 (a) For the formula φ = p ∨ (q ∧ ¬r):

(i) What is dual(φ)?

(ii) What is flip(φ)?

(b) Prove that for all φ ∈ PF: flip(φ) is logically equivalent to ¬dual(φ).

3. Let P(n) be the proposition that: for all k, with 1 ≤ k ≤ n,


(a) Prove that P(n) holds for all n ≥ 1. (Note: it is possible to do this without using induction)

We can compute 1858_figure2.pngfrom the formula given in lectures, however this can often require computing unnecessarily large numbers. For example,1543_figure3.png= 253338471349988640 which can be expressed as a 64-bit integer, but 100! is larger than a 512-bit integer. We can, however, make use of the equation above to compute 1858_figure2.pngmore efficiently. Here are two algorithms for doing this:


Let trec(n, k) be the running time for chooseRec(n, k), and let titer(n) be the running time for chooseIter(n, k). Let Trec(n) = max0≤k≤n trec(n, k) and Titer(n) = max0≤k≤n titer(n, k) (so Trec(n) ≥ trec(n, k) for all k, and likewise for Titer(n)).

(b) Give an asymptotic upper bound for Trec(n). Justify your answer.

(c) Give an asymptotic upper bound for Titer(n). Justify your answer.

Reference no: EM132136341

Derive the formula of time period of simple pendulum

Calculate the time period of simple pendulum having length 100m and g=10m/sec2. Draw the PV graph of isothermal process. Write the formula of Lorentz force and write unit of f

Find the eigen values and eigen vectors of the matrix

All parts for this question are compulsory a) Find the 5th derivative of exx3. b) Find the stationary point of f(x,y) = 5x2 + 10y2 + 12xy - 4x - 6y + 1 c) If u= x2-y2 + sin yz

Find the average number of items sold in june

Plot the graph of y = x3- 2 in the range -10 ≤ x ≤ 10 Name the axes and add a title. Where PV= Present Value, P=Payment per period, r=interest rate and n=number of years. Writ

Prove that h is orthogonal

Consider the matrix H = I -hhT, where h is a column vector in M.n and I is the properly sized identity matrix. Prove that H is orthogonal, provided that h T h = 1. This matr

How do the coefficient estimates from the usual rule

These are the results of running 5-fold cross-validation on each of the ridge and lasso models, and using the usual rule (min) or the one-standard-error rule (1se) to select

Find the core and the least core

Here, wi ≥ 0 are called weights and q > 0 is called a quota. Take q = 1/2 Σi ε N wi . Suppose that there is one large group with two-fifths of the votes and two equal-sized g

Analyze the problems the author uses the concept of duality

In one of the papers (to be cited along with solutions) published in Operations Research journal, the author considers the following problem and its LP model: To analyze the

What is the standard deviation of the project npv

Consolidated Oilfield plc is interested in exploring for oil near the west coast of Australia. The Australian government is prepared to grant an exploration license to the



10/9/2018 10:33:25 PM

Note: In your assignment, how you arrived at your solution is as important (if not more so) than the solution itself and will be assessed accordingly. There may be more than one way to find a solution, and your approach should contain enough detail to justify its correctness. Lecture content can be assumed to be common knowledge.


10/9/2018 10:33:20 PM

Advice on how to do the assignment - All submitted work must be done individually without consulting someone else’s solutions in accordance with the University’s “Academic Dishonesty and Plagiarism” policies. Assignments are to be submitted via WebCMS (or give) as a single pdf (max size 2Mb). In Linux, the following command pdfjoin --outfile output.pdf input1.pdf input2.pdf ... can be used to combine multiple pdf files. The command convert -density 150x150 -compress jpeg input.pdf output.pdf can be used to reduce the filesize of a pdf (change 150 to reduce/improve quality/filesize). Please ensure your files are legible before submitting.


10/9/2018 10:33:15 PM

Be careful with giving multiple or alternative answers. If you give multiple answers, then we will give you marks only for ”your worst answer”, as this indicates how well you understood the question. Some of the questions are very easy (with the help of the lecture notes or book). You can use the material presented in the lecture or book (without proving it). You do not need to write more than necessary (see comment above). When giving answers to questions, we always would like you to prove/explain/motivate your answers. If you use further resources (books, scientific papers, the internet,...) to formulate your answers, then add references to your sources.

Write a Review

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd