Monday, July 29, 2013

Computer Graphics 01

1. The aspect ratio of an image is defined as         [Paper III December 2012]
(A) The ratio of width to its height measured in unit length.
(B) The ratio of height to width measured in number of pixels.
(C) The ratio of depth to width measured in unit length.
(D) The ratio of width to depth measured in number of pixels.

2. The Mandelbrot set used for the construction of beautiful images is based on the following transformation: xn + 1= x2n+ z    Here,                        [Paper III December 2012]
(A) Both x & z are real numbers.
(B) Both x & z are complex numbers.
(C) x is real & z is complex.
(D) x is complex & z is real.

3. In an image compression system 16384 bits are used to represent 256 × 256 image with 256 gray levels. What is the compression ratio for this system? [Paper III June 2012]
(A) 1 (B) 2
(C) 4 (D) 8

4. If the pixels of an image are shuffled then the parameter that may change is
[Paper III June 2012]
(A) Histogram (B) Mean
(C) Entropy (D) Covariance

5. The quantiser in an image-compression system is a      [Paper III June 2012]
(A) lossy element which exploits the psychovisual redundancy
(B) lossless element which exploits the psychovisual redundancy
(C) lossy element which exploits the statistical redundancy
(D) lossless element which exploits the statistical redundancy

6. The perspective projection matrix, on the view plane z = d where the centre of projection is the origin (0, 0, 0) shall be [Paper III June 2012]

7. If a and b are the end points of a line, then which one of the following is true?   [Paper III June 2012]
(A) If both end points are left, right, above or below the window, the line is invisible.
(B) If both end points are left, right, above or below the window, the line is completely visible.
(C) If both end points are left, right, above or below the window, the line is trivially visible.
(D) If both end points are left, right, above or below the window, the line is trivially invisible.

8. Halftoning is defined as                      [Paper III June 2012]
(A) a technique to obtain increased visual resolution using multiple intensity levels.
(B) a technique for using minimum number of intensity levels to obtain increased visual resolution.
(C) a technique to obtain increased visual resolution using maximum number of intensity levels.
(D) a technique for using appropriate number intensity levels to obtain increased visual resolution.




SOLUTIONS

1. A

2. B
The Mandelbrot set is the set of values of c in the complex plane for which the orbit of 0 under iteration of the complex quadratic polynomial zn+1 = zn2 + c remains bounded. That is, a complex number c is part of the Mandelbrot set if, when starting with z0 = 0 and applying the iteration repeatedly, the absolute value of zn remains bounded however large n gets.

3.

4.

5. A
Quantization, involved in image processing, is a lossy compression technique achieved by compressing a range of values to a single quantum value. When the number of discrete symbols in a given stream is reduced, the stream becomes more compressible. For example, reducing the number of colours required to represent a digital image makes it possible to reduce its file size.

  • Color quantization reduces the number of colors used in an image.
  • Frequency quantization: The human eye is fairly good at seeing small differences in brightness over a relatively large area, but not so good at distinguishing the exact strength of a high frequency (rapidly varying) brightness variation. This fact allows one to reduce the amount of information required by ignoring the high frequency components. This is done by simply dividing each component in the frequency domain by a constant for that component, and then rounding to the nearest integer.

6.

7. A

8.
Halftone is the reprographic technique that simulates continuous tone imagery through the use of dots, varying either in size, in shape or in spacing. "Halftone" can also be used to refer specifically to the image that is produced by this process.
Most photographs, paintings, or similar pictorial works reproduced in books, magazines and newspapers are printed as halftones. In a halftone, the continuous tones of the picture being reproduced are broken into a series of equally spaced dots of varying size, printed with only one color of ink. The outcome exploits an optical illusion: the tiny halftone dots are blended into smooth tones by the human eye.

Saturday, July 27, 2013

Theory of Computation and Compiler Design 02

11. The equivalent grammar corresponding to the grammar  G : S → aA, A → BB, B → aBb | ϵ is                                                                                                 [Paper III June 2012]
(A) S →  aA,     A →  BB,     B →  aBb
(B) S → a | aA,    A → BB,     B → aBb | ab
(C) S → a | aA,    A → BB | B,     B → aBb
(D) S → a | aA,    A → BB | B,     B → aBb | ab

12. Consider the regular expression (a + b) (a + b) … (a + b) (n-times). The minimum number of states in finite automaton that recognizes the language represented by this regular expression contains                                                                      [Paper III June 2012]
(A) n states                  (B) n + 1 states
(C) n + 2 states            (D) 2n states

13. The following CFG S → aB | bA, A → a | as | bAA, B → b | bs | aBB  
generates strings of terminals that have                        [Paper III June 2012]
(A) odd number of a’s and odd number of b’s
(B) even number of a’s and even number of b’s
(C) equal number of a’s and b’s
(D) not equal number of a’s and b’s

14. The regular expression for the following DFA is      [Paper III June 2012]
(A) ab*(b + aa*b)*           (B) a*b(b + aa*b)*
(C) a*b(b* + aa*b)           (D) a*b(b * + aa*b)*

15. Match the following:                      [Paper III June 2012]
(i) Regular Grammar                           (a) Pushdown automaton
(ii) Context free Grammar                   (b) Linear bounded automaton
(iii) Unrestricted Grammar                  (c) Deterministic finite automaton
(iv) Context Sensitive Grammar          (d) Turing machine
(i)         (ii)        (iii)       (iv)
(A)       (c)        (a)        (b)       (d)
(B)       (c)        (a)        (d)       (b)
(C)       (c)        (b)        (a)       (d)
(D)       (c)        (b)        (d)       (a)

16Consider the following statements:           [Paper II June 2012]
I. Recursive languages are closed under complementation.
II. Recursively enumerable languages are closed under union.
III. Recursively enumerable languages are closed under complementation.
Which of the above statements are true?
(A) I only                    (B) I and II

(C) I and III                (D) II and III



SOLUTIONS
11. D
Strings that are legal according to the given grammar is a, aab, aabab etc
Out of the options the grammar that can produce all these strings is D
Option B seems to be correct in first look, but fails to produce  aab.

12.

13.

14. D

15. B
Grammar Type
Language
machine
Type 0
Recurssively Enumerable/ Un restricted/ Phase structured/ Semithus
Turing Machine
Type 1
Context Sensitive
Linear Bounded Automata
Type 2
Context Free
Pushdown Automata
Type 3
Regular
Finite Automata

16. B
Recursively enumerable languages are closed under the following operations:
  • Kleene star L*
  • concatenation of L and P
  • union of L and P
  • intersection L and P.
Recursive languages are closed under the following operations:
  • Kleene star L*
  • Concatenation L and P
  • Union L and P
  • Intersection L and P
  • Complement of L
  • Set difference L - P
So only Statements I and II are true.