Q10: Language of DFA

Question #10: What is the language of the DFA below?

 

Options:

1. All string having even number of 0’s
2. (1*01*01*)*
3. All strings which end with 1 + empty string
4. Both options 1 and 2

Solution: The above DFA accepts strings of  even number of 0’s, making option 1 the only correct answer. Note that option 2 is incorrect because it doesn’t include the string (1)* which is included in the DFA.

Q9: Context Free Grammar

Question #9: What does the following grammar represent?

Options:

1. All strings which start with 0 and end with 1.
2. All strings whose only first and last symbol is same.
3. All strings that reads the same forward and backward.
4. All strings of 0 and 1.

 

Solution:

First three rules are the basis and 4^th and 5^th rule can form any string by appending same symbol before and after the string. These strings are known as palindrome strings. Hence, the correct answer is option 3.

Q8: Interval Scheduling: An alternative approach

This question is in continuation of previous question of interval scheduling. Please visit Question #7 before attempting this question.

Question #8: Consider a different greedy approach to solve the same problem of finding a subset of maximum size of non-overlapping intervals. This greedy algorithm selects shorter requests first and adds it to the solution if it doesn’t overlap with the existing jobs. The algorithm finally stops until we reach the highest interval job. Which of the following option is correct?

Options:

1. This algorithm produces optimal set as more number of shorter requests can be covered in a given time as compared to longer ones.
2. This algorithm will produce optimal set only if a good mix of shorter and longer requests exists.
3. This algorithm doesn’t produce optimal set in cases when all requests have same size.
4. We can design some counter examples to prove that this algorithm doesn’t work in all cases, even if requests have varying size.

Solution:

Consider the following counter example.

The above mentioned algorithm selects 1 smaller request instead of 2 bigger ones. Hence, this algorithm is not optimal.

Q7: Interval Scheduling Problem

There’s a set of n requests, where each request i represents an interval of time starting and finishing time. A subset of these requests is compatible, if there is no overlap, as only one request can be handled at a given time. The goal is to select a subset of maximum size for scheduling. For example, the figure below has a total of 11 requests and a maximum of 4 requests from it can be scheduled without any conflicts.

Question #7: Consider a greedy solution to the above described interval scheduling problem:

At any time, select the job which is going to start the earliest. Eliminate all the conflicting jobs, and of the remaining ones, again select the job which is going to start the earliest & so on.

Options:

1. This algorithm produces the optimal set in the above example only.
2. This algorithm produces the optimal set always because it is the most intuitive way to solve the problem.
3. This algorithm will produce optimal set always because it always chooses the first job and then next best possible choice, hence it always selects the maximum number of jobs.
4. This algorithm may not produce optimal set in every case.

Solution: Consider the following example where this algorithm fails.

Since we have at least one counter-example, this algorithm is not optimal. Hence, the correct answer is option 4.

Q6: Is the system deadlocked?

Question #6: Consider the following situation with processes named A to G and resources named R to W:

1. Process A holds R and wants S.

2. Process B holds nothing but wants T.

3. Process C holds nothing but wants S.

4. Process D holds U and wants S and T.

5. Process E holds T and wants V.

6. Process F holds W and wants S.

7. Process G holds V and wants U.

Is this system deadlocked?

Options:

A)   No, all processes can go ahead and finish the job eventually.

B)   Yes, since there is a cycle in resource allocation graph.

C)   There may be a deadlock, can’t say deterministically.

D)   There is a race condition but deadlock may or may not be there.

Solution: Let’s model the above scenario in the form of resource allocation graph. Let square blocks represent resources and circled blocks represent processes.

For example, A holds R is represented by an arrow from R to A. A wants S is represented by an arrow from A to S. Since there is a cycle of resource hold and want, there is a deadlock in the system. Hence, the correct answer is B.

Q5: Translation Look-aside Buffer

Question #5: Which of the following statements is false regarding Paging and Translation Look-aside Buffer (TLB)?

A)     Paging requires at least two memory accesses (one to fetch the correct virtual to physical address translation & second to do the actual load/store at the memory location in the instruction).

B)     To speed up the first memory access (translation phase), hardware support in the form of MMU and TLB is added.

C)     TLB is just a hardware cache for popular virtual to physical address translations.

D)     TLB replaces the need to go to page table and thus we don’t need to store page tables for address translation anymore.

 

Solution: TLB doesn’t replace page tables. Each translation is first checked in TLB, if found it is resolved faster. If it is not found, then page tables need to be searched. Size of TLB is very small and it only contains a few of the popular translations, full information is in the page tables. Hence the correct option is D.

Q4: The big O notation

The asymptotic notation big-O is defined as follows, where a function f(n) is called the big-O of g(n) if there exists some positive constants c & n₀ such that:

This is called the asymptotic upper bound.

Question #4: What are the least positive values of c and n₀ for function f(n) = 3n² + 2 and g(n) = n² based on the above definition?

1. C = 3, n₀ = 2
2. C = 3, n₀ = sqrt(2)
3. C = 4, n₀ = 2
4. C = 4, n₀ = sqrt(2)

Solution: We want, 3n² + 2 < = c n²   for all n > n₀

For the above equation to be true, c cannot be lesser than 4 since otherwise LHS won’t ever be lesser than RHS. Putting c = 4, n₀ can be derived to be sqrt(2). Following picture shows the two curves (3n² + 2 and 4n²) . After n = sqrt(2), the graph of 4n² always remains above 3n² + 2.

 

Hence option 4 is the correct one.

Q3: A Marble Toy

Above figure represents a marble-rolling toy. A marble is dropped at A or B. There are three levers in this figure, let’s say x1, x2 and x3 from left to right. Whenever a marble encounters a lever, it causes the lever to reverse after the marble passes, so the next marble will take the opposite branch. Model this toy as a finite automaton. Let the inputs A and B represent the input into which the marble is dropped. Let acceptance correspond to the marble exiting at D; non-acceptance represents a marble exiting at C.

Question #3(a): Let’s say the initial state of the levers be ‘L’, ‘L’ and ‘L’ as shown in figure. As an example, suppose the input marble is through A, it will go to C and the state of levers will become “RLL”. What will be state of the levers after input “ABA”?

1. LLR

2. RRR

3. RRL

4. LLL

Question #3(b): Let’s say the initial state of the levers be “LLL”, where will the final marble go (in C or D) after input marbles through “ABA”?

1. C

2. D

3. Can’t say

4. None of the above.

Solution 1: After first input through A, the state of levers will be “RLL”. After another marble through B, the state will be “RRR”. After another marble through A, the state will be “LLR” as this marble will pass through both x1 and x2. Hence the first option is the correct choice.

Solution 2: The first marble will go to C as per the direction of liver and the state of the livers will become “RLL”. The second marble entering through B will also go to C as per the direction of levers and state of the levers will become “RRR”. The third marble entering through A will then go to D. Hence the second option is the correct choice.

Q2: Shortest Remaining Time First

An operating system uses Shortest Remaining Time first (SRT) process scheduling algorithm. Consider the arrival times & execution times for the following processes:

Process            Execution time            Arrival time

P1                           20                            0

P2                           25                           15

P3                           10                           30

P4                           15                           45

 

Question #2: What is the total waiting time for process P2?

• 5
• 0
• 10
• 15

 

Solution: Following will be the timeline based on the SRT algorithm.

|—-P1—-|—-P1—-|—-P2—-|—-P3—-|—-P2—-|—-P2—-|—-P4—-|

0            15           20            30            40           45            55           70

P2 entered into the system at 15 and finished off at 55. The total time it stayed in the system is 55-15 = 40 and its execution time is 25. Hence, it waited for a total of 40-25 = 15 time units. Hence option 4th is the correct one.

Q1: Twisted Peterson’s Algorithm

Question #1: The following code is the realization of Peterson’s algorithm for mutual exclusion except that the lines 12 & 13 (assignment statements) have been exchanged. Does the code below still solves the critical section problem?

#define FALSE  0
#define TRUE   1
#define N  2                          /* number of processes */

int turn;                             /* whose turn is it? */
int interested[N];                    /* all values initially 0 (FALSE) */

void enter_region (int process)       /* process is 0 or 1 */
{
    int other;                        /* number of the other process */
    other = 1 - process;              /* the opposite of process */
    turn = process;                   /* set flag */
    interested[process] = TRUE;       /* show that you are interested */

    while (turn == process &&
           interested[other] == TRUE);
}

void leave_region(int process)        /* process leaving */
{
    interested[process] = FALSE;      /* indicate departure from critical region */
}

 

Options:

1. No, there is no mutual exclusion.
2. Yes, it solves the problem.
3. No, as there can be a deadlock.
4. No, there can be a process outside its critical region which blocks another process entering into critical region.

 

Solution: It looks like as if assignment statements don’t make any difference, but they do. Let’s consider the following sequence:

• Process 0 sets the variable turn as 0.
• Context switch occurs
• Process 1 sets interested[1] as TRUE & sets turn to 1.
• Process 1 then checks the while condition. It will enter into the critical section because interested[0] is still FALSE.
• Context switch happens again
• Process 0 sets the interested[0] as TRUE and checks the while condition.

Now, even Process 0 will enter into its critical section since turn is set to 1! Hence, there is no mutual exclusion if the above sequence of events happen. So the correct answer is option 1.