COMPUTER GRAPHICS MODEL PAPER

First question is compulsory.
Answer any FOUR from the remaining questions.
All questions carry equal marks.
Write all bits of the first question at one place.

1. (a) Give some applications of graphics.
(b) Explain display file compilation.
(c) Describe Raster scan systems.
(d) Write the characteristics of a good graphics package.

2. (a) Describe the simple DDA line drawing algorithms.
(b) Describe Bresenhams circle generation algorithm.

3. (a) Suppose we know a point (x', y') and the fact that it was transformed from an unknown point (x,y) by a known matrix Q. Describe a mechanism for finding the original point (x, y). 'Is this mechanism useful in graphics? Explain.
(b) Describe various methods of scan conversion of polygons.

4. (a) Describe edge listing algorithm for scan converting a polygon.
(b) Discuss modifications to the Display file structure that would handle appending to segments.

5. (a) Write operations on segments with illustration.
(b) Write 3D transmissions for translation, scaling, rotation.

6. (a) How can scan conversion ideas be used to cross hatch a polygon with lines as in the following figure?
(b) Explain various co ordinate systems in 3D viewing.

7. (a) Describe procedure for drawing Bezier curve.
(b) Explain B spline methods.

8. (a) Explain different types of parallel projections.
(b) Describe bas ic principles of designing a graphic package.

MCA IInd YEAR MODEL PAPERS

THEORY OF COMPUTATION

First Question is Compulsory

Answer any four from the remaining

Answer all parts of any Question at one place.

Time: 3 Hrs.
Max. Marks: 100

1. a). Let Σ={a,b}. Write regular expression for the set of all strings in Σ* with no more than three a’s.
b). State the mathematical definition of DFA.
c). Define Context Free grammar.
d). What is configuration of a Turing machine?
e). When do we say that a function is Turing – computable.
f). When do we say that a function is Primitive recursive?
g). State post correspondence problem.
h). Define the class NP.
i). Define the concept of validity in prepositional calculus.
j). Construct truth tables for the following formula : (A ↔ (B ↔ A))

2. a). Prove that, for every non deterministic finite automation there is an equivalent deterministic finite automation.
b). Construct DFA equivalent to non-deterministic automata given below :
-----DIAGRAM-----

3. a). Show that the class of Languages accepted by pushdown automata is exactly the class of context-free languages.
b). Construct context free Grammar that generate the language
{wcw^R ⌈ wε {a, b}*}

4. a). Describe the Turing Machine which shifts a string w containing no blanks to one cell to the left.
b). Construct a Turing Machine that accepts the Languages a^* ba^*b.

5. a). Describe the method of Godelization
b). Show that the function f(n) = n! is primitive recursive

6. a). What is halting problem? Explain
b). Show that any finite set is Turing-decidable

7. a). Let L b an NP-complete language. Then P=NP if and only if L ε P.
b). Show that Travelling salesman problem is NP-complete.

8. a). Show that the following formula of prepositional calculus is a Tautology.
(( P→Q) →R))→((P→Q) →(P→R))
b). Describe resolution in Predicate calculus.