Comprehensive Exam for PhD CS Important FAQ

“Comprehensive Exam for Ph.D. CS Important FAQ ” is the bundle of important questions asked in a comprehensive exam of a university.

Adv. Theory of Automata – Comprehensive Exam for Ph.D. CS

Regular expression for
Begin and end with the same symbol
Don’t contain substring “aa”
Draw FSA for the above two problems
PDA for {a2n bn | n is a natural number}
Prove that all recursively enumerable languages are countable
Reduction from Accepts null to the halting problem

Fault tolerance – Comprehensive Exam for Ph.D. CS

Difference between backward and forward fault tolerance
Difference between NCP and RtB
Difference between design, data and temporal diversity
How NVP is inferior to RtB, how NVP-TB-AC improves NVP
Explain the working of SCOP
Algorithm:
Exercise 2.2 – 5
Exercise 2.3 – 4
Exercise 2.4 – b, c, d, e
Prove that n2/2 + n = Q(n2) -or similar to it
R(N) = R(N-1) + R(N-2)
Convert this algorithm into O(N) time complexity and O(1) space complexity

Semantic Computing – Comprehensive Exam for Ph.D. CS

True False
XML is a subtree in RDF
XQuery is used to query RDF
Restriction can be imposed by deleting attributes and elements from parent RDFS
Etc.
Whether the XML document complies with XML schema
(Answer was Header tag is missing, the end tag is addition)
Man 1 and Man 2 are the father of Girl 1. This sentence is semantically incorrect. How semantic model helps us to make such a statement impossible.
XQuery statement was given like the following
$ item = item/@num
$product
$price
we are asked to interpret its working
SPARQL program is given like following
Name 1, name 2, fofsa, etc.
And
UNION author, title, etc.
We are asked to draw a tree and interprets its working

Data Mining – Comprehensive Exam for Ph.D. CS

Difference between prediction and classification
Feature selection criteria (Indian author’s paper)
Convert 200, 400, 800, 1000, 2000, 2200 to min-max (0 – 100)
Make 2 bins for equal width from the above dataset
Make 2 bins for equal frequency from an above dataset

Describe the decision tree algorithm
Find fist split of decision tree for the following dataset

A B Class
1 0 C1
0 1 C2
1 0 C2
0 0 C1
1 0 C2
0 1 C2
1 1 C1
0 0 C2
1 1 C2
1 1 C1

8.What is entropy how it is used in classification

Software Testing – Comprehensive Exam for Ph.D. CS

Test cases for SBVT, WBVT, RSBVT
Program pseudocode is given
Minimum Test cases for
Condition Coverage
Condition – decision coverage
MCDC (it was difficult)
Transition coverage is stronger than state coverage? How?
Difference between All path coverage, Prime path coverage, and decision coverage
Explain Bottom-up and top-down approach