Question 1:

Using Backus-Naur notation, a grammatically correct sentence can be generated using the

following rules:

1. hsentencei → hnoun phraseihverb phrasei

2. hnoun phrasei → harticleihnouni

3. hverb phrasei → hverbihnoun phrasei

(a) Represent these rules as a parse tree.

(b) Following these rules, generate all possible sentences with harticlei → the, hnouni →

cow|grass, and hverbi → ate.

(c) All sentences in (b) should have correct syntax. Which of these sentences also has the

correct semantics?

Question 2:

Use the theorems on graphs and trees to help you with this question.

(a) Either draw a tree with 5 vertices and total degree 10, or explain why no such graph

exists.

(b) Either draw a connected graph that has a circuit, 7 vertices, and 6 edges; or explain why

no such graph exists.

(c) Either draw a graph that is circuit-free, has 7 vertices, and 4 edges; or explain why no

such graph exists.

1

(d) A connected graph has 11 vertices and 10 edges. Does it have a vertex of degree 1?

Question 3:

Apply insertion sort (from Tutorial 6) to sort the list 4, 15, 36, 30, 3, 9.

(a) How does the algorithm know when the list is sorted?

(b) What is the maximum number of comparisons required for a list of six numbers?

(c) How many comparisons did you actually require for the given list?

Question 4:

Use the definition of Θ-notation (but not the general theorem on polynomial orders) to show

that:

(a)

x

2 + 25x + 4,

is Θ(x

2

). Show your reasoning.

(b)

1

2

x

3 − 50x − 12,

is O(x

3

). Show your reasoning.

Question 5:

(a) Use mathematical induction to prove that log2 n ≤ n for all integers n ≥ 1.

(b) O, Ω, and Θ notations are also used for functions defined on the set of non-negative

integers (i.e., sequences). Use the result in part (a) to show that

3n + log2 n,

is Θ(n). Show your reasoning