Discrete Structures (DS) Semester 3 (Revised Course) (3 Hours) May 2009

Discrete Structures (DS) Semester 3 (Revised Course) (3 Hours) May 2009
VR-3330 [Total Marks : 60]
N.B:	(1)	Question no.1 is compulsory.
	(2)	Attempt any four questions out of remaining six questions.
	(3)	Assumptions made should be clearly stated.
	(4)	Figures to the right indicate full marks.
	(5)
1.	(a)	Prove that A x(B ∩ C) = (A x B) ∩ (A x C).	04
	(b)	Prove there is no rational number p/q whose square is 2.	04
	(c)	Show than n3+2n is divisible by 3 for all n > 1.	06
	(d)	Among the integers 1 and 300,      (i) How many of them are divisible by 3,5 or 7 and are not divisible by 3 nor by           by 5 nor by 7?      (ii) How many of them are divisible by 3 but not 5 nor by 7?	06
2.	(a)	Prove that if any 14 integers from 1 to 25 are chosen, than one of them is a multiple of another	04
	(b)	Solve the recurrence relation dn = 2dn-1- dn-2 with initial conditions d1=1.5 and d2 = 3.	04
	(c)	Let A = Z, the set of integers and let R be the relation less than. Is R Transitive?	06
	(d)	Negate the statement. For all real numbers x, if x> 3 then x2>9.	06
3.	(a)	Let A = {a, b, c, d, e}and       R = { (a,a), (a,b), (b,c), (c,e), (c,d), (d,e) } Compute (i) R2 and R∞.	06
	(b)	Let A = { 1, 2, 3, 4 } and let R = { (1,2), (2,3), (3,4), (2,1) } Find Transitive Closure of R using Warshall's algorithms.	06
	(c)	Explain the Equivalence Class with an Example.	04
	(d)	Explain with an Example dual of the poset.	04
4.	(a)	Show that in bounded is distributive lattice, if a complement exists. it is unique.	06
	(b)	Determine whether the following posets are boolean algebras. Just your answers      (i) A = { 1, 2, 3, 6} with divisibility.      (ii) D20 : divisors of 20 with "divisibility".	06
	(c)	Explain primitive Recursive Function. Every primitive recursive function is a total function, justify.	04
	(d)	(i)  Is every Eulerian graph as Hamiltonian? (ii)  is every Hamiltonian graph an Eulerian ?       Justify with the necessary graph.	04
5.	(a)	So that if set A has 3 elements, than we can find 8 relations on A that all have the same symmetric closure.	06
	(b)	Draw the Hasse diagram of the poset A = { 2, 3, 6, 12, 24, 36, 72 } Under the relation of divisibilty. is this poset a lattice? justify.	06
	(c)	Let A = { 0, -1, 1} and B = { 0, 1}, Let f : A → B where f(a) = | a |. Is f onto?	04
	(d)	State and prove right or left cancellation property for a group.	04
6.	(a)	Prove that every field is an integral domain.	06
	(b)	Consider the chains of divisors of 4 and 9 i.e.,L1= {1, 2, 4} And L2= {1, 3, 9}. Find partial ordering relationsof division on L1 and L2. Draw lattice of L1 x L2.	04
	(c)	Explain the linear recurrence relations with constant co-efficeints.	04
	(d)	Explain the types of generating function with an example.	04

7.	(a)	Consider the (3, 5) froup encoding function e : B3 → B5 defined by --     e (000) = 00000   e (100) = 10011 e (001) = 00110   e (101) = 10101 e (010) = 01001   e (110) = 11010 e (011) = 01111   e (111) = 11100 Decode the following words relative to a maximum likelihood decoding function-      (i) 11001     (ii) 01010     (iii) 00111	06
	(b)	Let G be the set of all nonzero real numbers and let     a * b = ab / 2. Show that (G, *) is an Abelian group.	06
	(c)	Let m = 2, n = 5 and   H = 1 1 0 0 1 1 1 0 0 0 1 0 0 0 1 Determine the group code B2 → B2	04
	(d)	Explain congruence relation with an example.	04

B.E. (IT), Multimedia Systems (MS) [Elective], Semester 7, May2009

B.E. (IT), Multimedia Systems (MS) [Elective]

Semester 7, May2009

Con. 2839-09

(Revised Course)

VR-4188

(3 Hours)

[Total Mark : 100]

N. B. : (1) Question no 1 is compulsory.

(2) Solve any four questions from the remaining six questions.

(3) Assume suitable data wherever required.

1. One of the most important application using both technologies network and multimedia is distance learning. You are appointed as a consultant to design the system. For such an application. --- (20 Marks)
(a) Specify the hardware and software requirements for the same, if this application is to be used in distributed environment.

(b) Design its workflow and hence design the entire multimedia system.

2. (a) Draw and explain the workstation based architecture for multimedia systems. Also specify the hardware and software expected at each layer (if any) considering an example. --- (10 Marks)
(b) Explain MPEG in detail.--- (10 Marks)

3. (a) Draw a neat labelled diagram for a flat bed scanner. Explain scanning mechanism and CCD used in scanning operation. --- (10 Marks)
(b) Explain RIFF with respect to various kinds of chunk and give pseudo code for .WAV and .AVI for RIFF. --- (10 Marks)

4. (a) Explain audio/video streaming and the role of RTP, RTSP, RSVP, and RTCP in streaming. --- (10 Marks)
(b) Explain voice recording system in detail. --- (10 Marks)

5. (a) You are appointed as a consultant to develop an implementation strategy for an automated tourist system that helps its customers to plan this tours. The system has agencies that provide services like air, railway luxury, economics, planing of tour, hotels, services etc. For such a system – Design the multimedia authorising system and also specify the multimedia data base schema for the same. --- (10 Marks)
(b) Explain WORM read/write operation in detail. --- (10 Marks)

6. (a) Explain hypermedia messaging with a suitable example. --- (10 Marks)
(b) Explain different scheduling and policing mechanism in multimedia networking. --- (10 Marks)

7. Write short notes on any two: --- (20Marks)
(a) Design considering related to virtual reality.

(b) Multimedia architecture and telecommunication considerations.

(c) Storage and retrieval technology.

Also see Multimedia systems question papers for December 2011

Data Structure & Algorithms (Information Technology Sem III) JUNE 2010

Data Structure & Algorithms Information Technology   Sem III
June 2010	AN-2569
(3 Hours)	[Total Mrks : 100]
N.B: 1)  Question No. 1 is compulsory
2) Attempt any four questions from remaining SIX questions.
1. a) Write a program to implement a STACK ADT using Linked list.	10
b) Explin Huffman coding and construct huffman code for the following	10
"JAVA DATA STRUCTURES"
2. a) Construct the binary tree for the inorderd and post traversal sequence given below  `                 In oreder : "INFORMATION                   Post Order: "INOFMAINOTR"	10
b) Write and explain Radix sort algorithm with suitable example.	10
3. a) Write an algorithm for merge sort and comment on its complexity.	10
b) Calculate and draw the minimum cost spanning tree using Kruskal's algoritham for the          following graph.	10
4.  a)  Explain how interface and packages are created and accessed with their syntax.	10
b)  Write any pattern Matching Algoritham and explain it with suitable example.	10
5.  a) Write a program to implement queue using array.	10
b)  Write a program to search an element in an array using binary search technique.	10
6.  a)  Write algorithm for heap sort and explain Ascending heap with suitable example.	10
b)  Hash the following in a table of size 11. Use any two collision resolution technique              99     67     41     0     17     2     98     20     94     27	10
7.  a)  Write short note on any four of the following:-	20
i)  AVL Trees           ii)  Red and Black Trees          iii)  Asymptotic Notation          iv)  Recursion          v)  Graph traversal technique         vi)  Abstract data type.

Also see Data structure & algorithms question papers for May 2009

SE (IT) Semester III Data Structure & Algorithms May 2009.

S.E. (IT) Sem 3rd

Data Structure & Algorithms (May 2009)

Con. 2996-09.

VR-3393

(3 Hours)

[Total Mark 100]

N. B.:- (1) Question No. 1 is compulsory.
(2) Answer any four out of remaining six questions.
(3) All Programs are to be written in JAVA only.
1. (a) What is Recursion? Give disadvantage of recursion. Write a programme to implement Tower of Hanoi.--10 Marks
(b) Explain Asympotic Notations (0, Ω,.θ) and write the properties of asymptotic notations.--5 Marks
(c) Explain packages and how do we hide classes using packages.--5 Marks
2. (a) Write a program to implement Quick sort and comment on its complexity.--10 Marks
(b) Write an algorithm for binary search method with example.--6 Marks
(c) Explain vectors with at least five methods.--4 Marks
3. (a) Write a program to implement Circular queue using array.--10 Marks
(b) Explain Huffman Algorithm. Construct Huffman tree for “MALAYALAM” with its optimal code.--10 Marks
4. (a) Write an algorithm to traverse a graph using – (with example)-- 10 Marks

1. Breath First Search
2. Depth First search

(b) Implement the function to delete a node from Binary Search Tree.--10 Marks
(Consider all possible cases.)

5. (a) Draw the minimum cost spanning tree using Kruskal’s algorithm. Also find its cost with all intermediate steps.--10 marks

(b) Write a program to implement STACK using Linked List.--10 marks
6. (a) Explain in brief--10 marks

1. Ascending heap
2. Desending heap

Write a program to implement heap sort.
(b) What is hashing? Explain Hashing methods and collision avoiding techniques.--10 marks
7. Write short notes on any four of the following with example.--20Marks
(a) AVL Tress
(b) B- Tress
(c) Shortest Path Algorithm.
(d) Pattern matching.
(e) Comparison of sorting Algorithms.
(f) Expression and realization of ADT’s in JAVA.

Also see Data structure & algorithms question papers for December-2010