ADV DATA STRUCTURE PROBLEM

can you give the solution for a,b,c, and d separately?

There are lots of solutions on Chegg for this, but none of them have separate answers. Please don't copy and paste. Thank you

(a) Hamiltonian-Cycle problem is the problem that takes a graph as input and asks whether there is a simple cycle in G that visits each vertex of G exactly once and then return to its starting vertex. Such a cycle is called a Hamiltonian cycle of G. Describe a nondeterministic polynomial time algorithm for this problem. (b) The 3-Partition problem is defined as follows. Given a finite set A of 3m elements, a bound B ? Z. (a positive integer) and a size s(a) ? Z' for each element a ? A such that s(a) satisfies the following inequalities: B/4 ? s(a) ? B/2 and such that Can A be partitioned into m disjoint sets Si, S2, .., Sm such that, for 1 s ism, S(a aeS Describe a nondeterministic polynomial time algorithm for this problem. (c) How would you go about proving that the above two problems are indeed NP- Complete? (d) If Professor Weise arrives at describing a deterministic polynomial algorithm for any of the above problems, what conclusions would you draw? Justify your