ALCCS

**NOTE: **

· **Question 1 is compulsory and
carries 28 marks. Answer any FOUR questions from the rest. Marks are indicated against each question.**

· **Parts of a question should be
answered at the same place.**

**Q.1 **a.** **Prove that in a connected graph of “n” vertices, the number
of vertices of odd degree will always be even.

** **b.** **In how many different ways can
6 people be seated in a committee room with 7 chairs?

c. Is the statement ‘If p then q’ with given p
and q, false or true?

p:
Ravana was the king of Ayodhya

q:
Mandodari was Ravana’s wife

d. Simplify the logical expression

e. State and prove the Euler formula to detect
the planarity of a graph.

f. What is the difference between a Relation and
a Function? What is an Equivalence Relation?

g.
What kind of strings is accepted by the
following automaton? Explain how. **(7
**** 4)**

**1**

**0**

**Q.2 **a.** **If P, Q and R are three atomic variables,
obtain the principal disjunctive normal form for (P→ (QΛR)) V
(~P→ (QVR))

b. How many bytes are required to encode n bits
of data when n equals 5, 500 and 3000 respectively? **(9+9)**

**Q.3** a. Show
that the maximum number of vertices in a binary tree of height h is 2^{h+1 }–
1.

** **

b. On a set S = {1,2,3,4,5}, find the equivalence
relation on S, which generate the partition { {1,2}, {3}, {4,5} }. Draw the
graph of the relation. **(9+9)**

** **

**Q.4 **a. Using
Dijkstra’s algorithm find a shortest path between ‘a’ and ‘z’ in the weighted
graph shown below

** **

b. Translate the infix expression

To reverse polish expression. **(9+9)**

**Q.5** a. Show
that the language

** **

is not a finite state
language.

b. Define Boolean algebra. Prove that the power
set of any set will form a Boolean algebra. **(9+9)**

**Q.6** a. What is a lattice? Which of the following
graphs are lattices? State reasons for your claim.

(a) (b)
(c)

b. Prove that if (A, ≤) has a least
element, then (A, ≤) has a unique least element. **(8+10)**

**Q.7** a. Write
the Preorder, Inorder and Postorder tree traversal algorithm.

b. For the given graph, find the minimal spanning
tree using Prim’s algorithm. **(10+8)**