A bus arrives every 20 minutes to a bus stop, beginning at 6

Report

Report an issue

Name

Email

Message

Submit

Cancel

PGCET CSE Exam (Karnataka) 2011 click here to view all questions

A bus arrives every 20 minutes to a bus stop, beginning at 6-40 AM and continuing till 8-40 AM. A passenger, not knowing the schedule, randomly arrives between 7 AM and 7-30 AM. What is the probability that he weiits for more than 5 minutes for the bus ?

A1/6

B1/4

C3/4

D5/6

No answer description available for this question. Let us discuss.

View Answer

Discuss

The proposition p ^ ( ~ p V q ) is

Report

Report an issue

Name

Email

Message

Submit

Cancel

PGCET CSE Exam (Karnataka) 2011 click here to view all questions

The proposition p ^ ( ~ p V q ) is

Aa tautology

Ba contradiction

Clogically equivalent to p ^ q

Dlogically equivalent to q

Nithin K ? Dec 7 '2016 at 21:52

Answer: logically equivalent to p ^ q

Explanation:

p^(~pV q)
According to distributive law it is equivalent to,
(p^~p)V (p^q)
0V (p^q)
p^q
so, it is logically equivalent to p ^ q.

View Answer

Discuss

Match the methodology of List-A with the application of List

Report

Report an issue

Name

Email

Message

Submit

Cancel

PGCET CSE Exam (Karnataka) 2011 click here to view all questions

Match the methodology of List-A with the application of List-B :

Aa->III b->I c->IV d->II

Ba->IV b->III c->II d->I

Ca->III b->IV c->I d->II

Da->III b->II c->I d->IV

Nithin K ? Dec 7 '2016 at 21:43

Answer : a->III b->I c->IV d->II

Explanation:

A “greedy algorithm” is optimization problem is one in which you want to find, not just a solution, but the best solution
Example: Finding MST using Kruskal’s algorithm (min-weight spanning tree)

A DFS algorithm is used to find strongly connected component.

A dynamic programming algorithm remembers past results and uses them to find new results example:Floyd–Warshall algorithm (All Pair Shortest path algorithm)

A divide and conquer algorithm consists of two parts:
Divide the problem into smaller subproblems of the same type, and solve these subproblems recursively
Combine the solutions to the subproblems into a solution to the original problem
Example: quicksort

View Answer

Discuss

Given two problems X and Y, Y is NP complete and X reduces

Report

Report an issue

Name

Email

Message

Submit

Cancel

PGCET CSE Exam (Karnataka) 2011 click here to view all questions

Given two problems X and Y, Y is NP complete and X reduces to Y in polynomial time. Which of the following is a valid statement ?

AX is NP hard

BX is NP complete

CX is an NP, but not necessarily NP complete

DIf X can be solved in polynomial time, so also can Y.

Nithin K ? Dec 7 '2016 at 21:38

Answer : X is NP complete

Explanation:

A decision problem C is NP-complete if:
i.) C is in NP, and
ii.) Every problem in NP is reducible to C in polynomial time.

C can be shown to be in NP by demonstrating that a candidate solution to C can be verified in polynomial time.

Note that a problem satisfying condition 2 is said to be NP-hard, whether or not it satisfies condition 1.
Reference:https://en.wikipedia.org/wiki/NP-completeness

View Answer

Discuss

Look at the following grammar

Report

Report an issue

Name

Email

Message

Submit

Cancel

PGCET CSE Exam (Karnataka) 2011 click here to view all questions

Look at the following grammar :

It generates strings of terminals that have

Aequal number of a`s and b`s

Bequal number of a`s and b`s

Ceven number of a`s and even number of b`s

Dodd number of a`s and even number of b`s.

No answer description available for this question. Let us discuss.

View Answer

Discuss

What does the machine shown in the figure do

Report

Report an issue

Name

Email

Message

Submit

Cancel

PGCET CSE Exam (Karnataka) 2011 click here to view all questions

What does the machine shown in the figure do ?

AComplements a given bit pattern

BFinds 2`s complement of a given pattern

CIncrements the given pattern by 1

DChanges the sign bit.

No answer description available for this question. Let us discuss.

View Answer

Discuss

The grammar S -> aSa | bS | c is

Report

Report an issue

Name

Email

Message

Submit

Cancel

PGCET CSE Exam (Karnataka) 2011 click here to view all questions

The grammar S -> aSa | bS | c is

ALL ( 1 ) but not LR ( 1 )

BLR ( 1 ) but not LL ( 1 )

CBoth LL ( 1 ) and LR ( 1 )

Dneither LL ( 1 ) nor LR ( 1 ).

Nithin K ? Dec 7 '2016 at 20:38

Answer : Both LL ( 1 ) and LR ( 1 )

Explanation:

First(aSa) = a
First(bS) = b
First(c) = c
All are mutually disjoint i.e no common terminal between them, the given grammar is LL(1).
As the grammar is LL(1) so it will also be LR(1) as LR parsers are more powerful then LL(1) parsers. and all LL(1) grammar are also LR(1)
So option C is correct.

Below are more details.

A grammar is LL(1) if it is possible to choose the next production by looking at only the next token in the input string.
Formally, grammar G is LL(1) if and only if
For all productions A ? a1 | a2 | ... | an,
First(ai) n First(aj) = Ø, 1 = i,j = n, i ? j.
For every non-terminal A such that First(A) contains e,
First(A) n Follow(A) = Ø

View Answer

Discuss