Register

Jest Exam

324 views
0 votes
0 votes
A tournament is a directed graph in which there is exactly one directed edge between
every pair of vertices. Let Tn be a tournament on n vertices.
(a) Use induction to prove the following statement:
Tn has a directed hamiltonian path (a directed path that visits all vertices).
(b) Describe an algorithm that finds a directed hamiltonian path in a given tourna-
ment. Do not write whole programs; pseudocode, or a simple description of the
steps in the algorithm, will suffice. What is the worst case time complexity of
your algorithm?
User Avatar

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
0 answers
2
sahadebmandal asked Jan 17, 2019
227 views
jest Exam
function mu(a,b:integer) returns integer; var i,y: integer; begin ---------P---------- i = 0; y = 0; while (i < a) do begin --------Q------------ y := y + b ; i = i + 1 end return y end Write a condition P such that the program terminates, and a condition Q which is true whenever program execution reaches the place marked Q above.
function mu(a,b:integer) returns integer;var i,y: integer;begin -P i = 0; y = 0;while (i < a) dobegin Q y := y + b ;i = i + 1endreturn yendWrite a condition P suc...
User Avatar
1 votes
1 votes
1 answer
3
sripo asked Feb 15, 2019
426 views
Jest Exam sample question-3
How many subsets of even cardinality does an n-element set have ? Justify answer. Please give a proof if possible.This is part of subjective JEST paper.
How many subsets of even cardinality does an n-element set have ? Justify answer.Please give a proof if possible.This is part of subjective JEST paper.
User Avatar
0 votes
0 votes
0 answers
4
sahadebmandal asked Jan 17, 2019
306 views
jest Exam
function AP(x,y: integer) returns integer; if x = 0 then return y+1 else if y = 0 then return AP(x-1,1) else return AP(x-1, AP(x,y-1)) (a) Show that on all nonnegative arguments x and y, the function AP terminates. (b) Show that for any x, AP(x, y) > y.
function AP(x,y: integer) returns integer;if x = 0 then return y+1else if y = 0 then return AP(x-1,1)else return AP(x-1, AP(x,y-1))(a) Show that on all nonnegative argume...
User Avatar
Link Copied!