Miscellaneous 01

01. ______ is process of extracting previously not known valid and actionable information from large data to make crucial business and strategic decisions.                     [Paper III December 2012]

(A) Data Management

(B) Data base

(C) Data Mining

(D) Meta Data

02. Data Warehouse provides                                             [Paper III June 2012]

(A) Transaction Responsiveness

(B) Storage, Functionality Responsiveness to queries

(C) Demand and Supply Responsiveness

(D) None of the above

03. An example of a dictionary-based coding technique is      [Paper III December 2012]

(A) Run-length coding

(B) Huffman coding

(C) Predictive coding

(D) LZW coding

SOLUTIONS

1. C

2. B

A data warehouse is a database used for reporting and data analysis. It is a central repository of data which is created by integrating data from one or more disparate sources. Data warehouses store current as well as historical data and are used for creating trending reports for senior management reporting such as annual and quarterly comparisons.

The data stored in the warehouse are uploaded from the operational systems (such as marketing, sales etc.,). The data may pass through an operational data store for additional operations before they are used in the DW for reporting.

3. D
Run-length Coding is a very simple form of data compression in which runs of data (that is, sequences in which the same data value occurs in many consecutive data elements) are stored as a single data value and count, rather than as the original run.
Huffman coding is an entropy encoding algorithm used for lossless data compression. The term refers to the use of a variable-length code table for encoding a source symbol.
Predictive coding is a tool used mostly in audio signal processing and speech processing for representing the spectral envelope of a digital signal of speech in compressed form, using the information of a linear predictive model.
Lempel–Ziv–Welch (LZW) is a universal lossless data compression algorithm. A high level view of the encoding algorithm is shown here:

1. Initialize the dictionary to contain all strings of length one.
2. Find the longest string W in the dictionary that matches the current input.
3. Emit the dictionary index for W to output and remove W from the input.
4. Add W followed by the next symbol in the input to the dictionary.
5. Go to Step 2.

A dictionary is initialized to contain the single-character strings corresponding to all the possible input characters (and nothing else except the clear and stop codes if they're being used). The algorithm works by scanning through the input string for successively longer substrings until it finds one that is not in the dictionary

Graph Theory 01

1. The time complexities of some standard graph algorithms are given. Match each algorithm with its time complexity? (n and m are no. of nodes and edges respectively) [Paper III December 2012]

a. Bellman Ford algorithm                  1. O (m log n)

b. Kruskals algorithm                         2. O (n3)

c. Floyd Warshall algorithm               3. O(mn)

d. Topological sorting                        4. O(n + m)

Codes:

a          b          c          d

(A)       3          1          2          4

(B)       2          4          3          1

(C)       3          4          1          2

(D)       2          1          3          4

2. Two graphs A and B are shown below: Which one of the following statement is true? 

[Paper III December 2012]

(A) Both A and B are planar.

(B) Neither A nor B is planar.

(C) A is planar and B is not.

(D) B is planar and A is not.

3. Maximum number of edges in a n Node undirected graph without self loop is:  

[Paper II December 2011]

(A) n²                             (B) n(n – 1)

(C) n(n + 1)                    (D) n(n – 1)/2

4. Consider a weighted undirected graph with positive edge weights and let (u, v) be an edge in the graph. It is known that the shortest path from source vertex s to u has weight 53 and shortest path from s to v has weight 65. Which statement is always true?              [Paper III June 2012]

(A) Weight (u, v)  12              (B) Weight (u, v) = 12

(C) Weight (u, v) ≥ 12            (D) Weight (u, v) > 12

5. G1 and G2 are two graphs as shown:                 [Paper III June 2012]

(A) Both G1 and G2 are planar graphs.

(B) Both G1 and G2 are not planar graphs.

(C) G1 is planar and G2 is not planar graph.

(D) G1 is not planar and G2 is planar graph.

6. The number of colours required to properly colour the vertices of every planer graph is          [Paper II June 2012]

(A) 2                (B) 3

(C) 4                (D) 5

SOLUTIONS

1. A

• The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. Bellman–Ford runs in O(|V|·|E|) time, where |V| and |E| are the number of vertices and edges respectively.
• Kruskal's algorithm is a greedy algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. Where E is the number of edges in the graph and V is the number of vertices, Kruskal's algorithm can be shown to run in O(E log E) time, or equivalently, O(E log V) time.
• Floyd–Warshall algorithm (also known as Floyd's algorithm, Roy–Warshall algorithm, Roy–Floyd algorithm, or the WFI algorithm) is a graph analysis algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles, see below) and also for finding transitive closure of a relation R. the complexity of the algorithm is O(n3).
• A topological sort of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. The usual algorithms for topological sorting have running time linear in the number of nodes plus the number of edges O(|V| + |E|).

2. A

A planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. The given graphs can be redrawn as shown below:

3. D

If you have n nodes, and each node has an edge with n-1 other nodes. However, n(n-1) is double-counting because if two nodes are each connected with the other then that needs to be counted as a single edge. So maximum number of edges is n(n-1)/2.

4. C

The difference in weights to u and v from source is 12. The shortest path to v may or may not include the edge (u, v). Suppose it is included, then the weight(u,v) = 12. And if it is not included, that means there is a path of less weight from u to v, i.e weight(u,v) > 12

5. B

6. C
The Four Color Theorem asserts that every planar graph - and therefore every "map" on the plane or sphere - no matter how large or complex, is 4-colorable

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: x_{n + 1}= x²_n+ 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 z_n+1 = z_n² + 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 z_n 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.

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)

16. Consider 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.

Data Structures 02

11. Which one of the following binary search tree is optimal, if probabilities of successful search and unsuccessful search are same?                 [Paper III June 2012]

12. The strategy used to reduce the number of tree branches and the number of static evaluations applied in case of a game tree is                                 [Paper III June 2012]

(A) Minmax strategy

(B) Alpha-beta pruning strategy

(C) Constraint satisfaction strategy

(D) Static max strategy

13. The postfix expression AB + CD – * can be evaluated using a

[Paper II June 2012]

(A) stack                     (B) tree

(C) queue                    (D) linked list

14. The post order traversal of a binary tree is DEBFCA. Find out the preorder traversal.

[Paper II June 2012]

(A) ABFCDE

(B) ADBFEC

(C) ABDECF

(D) None of the above

15. A binary search tree is a binary tree:    [Paper II June 2012]

(A) All items in the left subtree are less than root

(B) All items in the right subtree are greater than or equal to the root

(C) Each subtree is itself a binary search tree

(D) All of the above

16. Leaves of which of the following trees are at the same level?

[Paper II June 2012]

(A) Binary tree                      (B) B-tree

(C) AVL-tree                        (D) Expression tree

17. A / B+ tree index is to be built on the name attribute of the relation STUDENT. Assume that all students names are of length 8 bytes, disk block are of size 512 bytes and index pointers are of size 4 bytes. Given this scenario what would be the best choice of the degree (i.e. the number of pointers per node) of the B+ tree?            [Paper II June 2012]

(A) 16             (B) 42

(C) 43             (D) 44

18. The Inorder traversal of the tree will yield a sorted listing of elements of tree in

[Paper II June 2012]

(A) Binary tree

(B) Binary search tree

(C) Heaps

(D) None of the above

19. Which of the following data structure is linear type?          [Paper II June 2012]

(A) Strings

(B) Lists

(C) Queues

(D) All of the above

20. To represent hierarchical relationship between elements, which data structure is suitable? 
[Paper II June 2012]

(A) Dequeue             (B) Priority

(C) Tree                    (D) All of the above

SOLUTIONS

11. D

This tree is optimal because the distance to the leaf nodes is minimum.

12. B

Minimax is a decision rule used in decision theory, game theory for minimizing the possible loss for a worst case (maximum loss) scenario. Originally formulated for two-player zero-sum game theory, covering both the cases where players take alternate moves and those where they make simultaneous moves, it has also been extended to more complex games and to general decision making in the presence of uncertainty.

Alpha-beta pruning is a procedure to reduce the amount of computation and searching during minimax. It seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly for machine playing of two-player games (Tic-tac-toe, Chess, Go, etc.). It stops completely evaluating a move when at least one possibility has been found that proves the move to be worse than a previously examined move. 

13. A

14.

15. D

16. B
A B-tree is a tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree is a generalization of a binary search tree in that a node can have more than two children. A B-tree is kept balanced by requiring that all leaf nodes be at the same depth.
An AVL tree is a self-balancing binary search tree in which the heights of the two child subtrees of any node differ by at most one.
An expression tree is a specific application of a binary tree to evaluate certain expressions. 

17.

18. B

19. D

20. C

Operating Systems 02

11. The maximum amount of information that is available in one portion of the disk access arm for a removal disk pack (without further movement of the arm with multiple heads) [Paper II December 2011]

(A) a plate of data

(B) a cylinder of data

(C) a track of data

(D) a block of data

12. Which of the following is scheme to deal with deadlock?      [Paper III June 2012]

(A) Time out

(B) Time in

(C) Both (A) & (B)

(D) None of the above

13. A computer system supports 32 bit virtual address as well as 32 bit physical addresses. Since the virtual address space is of same size as that of physical address space, if we want to get rid of virtual memory, which one of the following is true?                                              [Paper III June 2012]

(A) Efficient implementation of multi-user support is no longer possible.

(B) The processor cache can be made more efficient.

(C) Hardware support for memory management is not needed.

(D) CPU scheduling can be made more efficient.

14. A user level process in Unix traps the signal sent on a Ctrl + C input and has a signal handling routine that saves appropriate files before terminating the process. When a Ctrl + C input is given to this process, what is the mode in which the signal handling routine executes?              [Paper III June 2012]

(A) User mode

(B) Kernel mode

(C) Superuser mode

(D) Privileged mode

15. Consider the methods used by processes P1 and P2 for accessing their critical sections. The initial values of shared Boolean variables S1 and S2 are randomly assigned, 

          P1                                             P2

while (S1 = = S2);                  while (S1 = = S2);

critical section                         critical section

S1 = S2;                                 S1 = S2;
Which one of the following statements describes the properties achieved?        [Paper III June 2012]

(A) Mutual exclusion but not progress

(B) Progress but not mutual exclusion

(C) Neither mutual exclusion nor progress

(D) Both mutual exclusion and progress

16. What is the meaning of ‘Hibernate’ in Windows XP/Windows 7? [Paper III June 2012]

(A) Restart the computers in safe mode.

(B) Restart the computers in normal mode.

(C) Shutdown the computer terminating all the running applications.

(D) Shutdown the computer without closing the running applications.

17. Which one of the following options is not a shell in UNIX system?  [Paper III June 2012]

(A) Bourne Shell

(B) C Shell

(C) Net Shell

(D) Korn Shell

18. What deletes the entire file except the file structure?                     [Paper II June 2012]

(A) ERASE                 (B) DELETE

(C) ZAP                      (D) PACK

19. Which command is the fastest among the following?                     [Paper II June 2012]

(A) COPY TO <NEW FILE>

(B) COPY STRUCTURE TO <NEW FILE>

(C) COPY FILE <FILE 1> <FILE 2>

(D) COPY TO MFILE-DAT DELIMITED

20. In round robin CPU scheduling as time quantum is increased the average turn-around-time            [Paper II June 2012]

(A) increases

(B) decreases

(C) remains constant

(D) varies irregularly

SOLUTIONS

11. B

Data is read from disk by positioning the arm on the correct track and then rotating the disk to read data in the track. Same tracks in different plates form a cylinder. So data can be read from a cylinder without further moving the arm provided it has multiple heads for reading.

Disk showing track and cylinder

12. A

One of the for necessary conditions required for deadlock to occur is hold-and-wait. This can be avoided by adding time-out for the resource or the process. That is a process waiting for more than a fixed amount of time should stop waiting and release all the resources acquired by that. Or any resource that is held by a process for more than a fixed amount of time should be released.

13. A

14. ?

15. C
As both S1 and S2 are assigned random values initially, both can be same, in which case both processes wait indefinitely without entering critical section. Even if S1 != S2 initially, when one process executes the critical section and exits S1 is equated to S2, Neither process P1 or P2 can enter critical section after this. So there is no progress.
Now considering mutual exclusion, when S1 !=S2, suppose P1 enters critical section and is executing it, at the same time P2 checks for the values of S1 and S2, finds they are same and enters the critical section. So there is no mutual exclusion also. This can be solved by modifying the code as 

          P1                                             P2

while (S1 = = S2);                  while (S1 = = S2);

S1 = S2;                                 S1 = S2 = true;

critical section                         critical section

S1 = !S2;                                S1 = !S2; 

Here both processes P1 and P2 sets S1=S2 before entering the critical section, so no other process can enter. So Mutual exclusion is attained, Also once the execution of critical section is over, the process makes S1!=S2, so that any waiting process can enter.

16. D

17. C

The shell provides you with an interface to the UNIX system. It gathers input from you and executes programs based on that input. When a program finishes executing, it displays that program's output.A shell is an environment in which we can run our commands, programs, and shell scripts.

In UNIX there are two major types of shells:

• The Bourne shell. If you are using a Bourne-type shell, the default prompt is the $ character.
• The C shell. If you are using a C-type shell, the default prompt is the % character.

There are again various subcategories for Bourne Shell which are listed as follows:

• Bourne shell (sh)
• Korn shell (ksh)
• Bourne Again shell (bash)
• POSIX shell (sh)

The different C-type shells follow:

• C shell (csh)
• TENEX/TOPS C shell (tcsh)

18. C
PACK: Shrinks file into one small (compressed) file so that it does not take as much space up.
ZAP: Removes all records from a table, leaving just the table structure.
ERASE/DELETE is a command used to remove files from your computer's hard drive or other writeable media.

19. ?

20. B
The round-robin scheduling algorithm is designed especially for time-sharing systems. It is similar to FCFS scheduling, but pre-emption is added to switch between processes. A small unit of time, called a time quantum or time slice, is defined. When a process finishes the time quantum it is switched and the next process in queue is taken for execution.
Turnaround Time is the time elapsed from when process is submitted to when it is completed. It includes execution time and waiting time and switching time between processes.
When the time quantum is increased, the no. of times the process is switched decreases reducing the switching time between processes. So Average turn around time gets reduced