1.a. Find the smallest number of people you need to choose at random so that the probability that at least two of them were both born on April 1 exceeds ½. Assume number of days in year as 366 days.

1.b. Show that each of these conditional statements is a tautology by using truth tables : $(p \wedge q) \rightarrow p$ $p \rightarrow(p \vee q)$

2.a. A club has 25 members : (i) How many ways are there to choose four members of the club to serve on an executive committee ? (ii) How many ways are there to choose a president, vice president, secretary, and treasurer of the club, where no person can hold more than one office ?

2.b. There are 2504 computer science students at a school. Of these, 1876 have taken a course in Java, 999 have taken a course in Linux, and 345 have taken a course in C. Further, 876 have taken courses in both Java and Linux, 231 have taken courses in both Linux and C, and 290 have taken courses in both Java and C. If 189 of these students have taken courses in Linux, Java, and C, how many of these 2504 students have not taken a course in any of these three programming languages?

3.a. Draw the graph and its equivalent Hasse diagram for divisibility on the set : {1, 2, 3, 6, 12, 24, 36, 48}.

3.b. State the theorems for presence of Euler path and circuit in a graph. Justify whether the graphs contain the following properties. If yes, write the path and circuit : (i) Euler path (ii) Euler circuit (iii) Hamiltonian path (iv) Hamiltonian circuit.

4.a. Use Warshall’s algorithm to find transitive closure of the following relation on the set {1, 2, 3, 4}, R = {(1, 2), (1, 3), (1, 4,), (2, 3), (2, 4), (3, 4)}

4.b. Find minimum cut set and value of vertex connectivity of the following graphs.

5.a. 000 people enter a chess tournament. Use a rooted tree model of the tournament to determine how many games must be played to determine a champion, if a player is eliminated after one loss and games are played until only one entrant has not lost. (Assume there are no ties.)

5.b. How many edges does a full binary tree with 1000 internal vertices have ?

6.a. Represent the expressions (x + xy) + (x/y) and x + ((xy + x)/y) using binary trees. Write these expressions in : (i) prefix notation (ii) postfix notation (iii) infix notation.

6.b. Use Huffman coding to encode these symbols with given frequencies : a : 0.20, b : 0.10, c : 0.15, d : 0.25, e : 0.30. What is the average number of bits required to encode a character?

7.a. What is abelian group ? Show that $\left(Z_{6},+\right)$ is an Abelian Group?

7.b. Find the hamming distance between code words of : C = {(0000), (0101), (1011), (0111)} Rewrite the message by adding even parity check bit and odd parity check bit.

8.a. Let R = and * = binary operation, so that for a and b in R, a * b is overall angular rotation corresponding to successive rotations by a and then by b. Show that (R, *) is a Group.

8.b. Let G = {even, odd} and binary operation be defined as :