Head TA Joves has been working on a problem . He correctly proved the following two statements: (1) There exists a verifier for that runs in polynomial time.  (2) Every algorithm that solves the problem runs in time greater or equal to , where n is the input size. Which of the following can we conclude from Joves’ work?

We call a graph G an IceCream of size K if G has exactly K+3 vertices, K of which form a clique, and the other three vertices together with exactly two vertices of the clique form a cycle. The picture shows an ice cream graph of size 4 and 5, respectively. Consider the IceCream problem: Input: a graph G=(V,E) and an integer K>3. Output: a subset of K+3 vertices such that the induced subgraph is an IceCream of size K, and reports NO if such subset does not exist. Show that the IceCream problem is NP-complete.  

Recall that the K-SAT problem takes as input a boolean formula in conjunctive normal form such that each clause has at most K literals, and outputs a true assignment, or report when such assignment does not exist. Head TA Emily claims the following: “It is known that for every pair of integers a,b>1, there is a reduction from a-SAT to b-SAT”.

You should read all material with the same degree of intensity.

You know clearly what you want to do, but it doesn’t fit within a single existing major at your choice of college. What should you do? Click all actions that you could realistically take.

Before answering the questions on a test, you should read the instructions and skim through the entire test.

There are a number of ways you can prepare for a test. Click all that apply.

Once you’ve registered for your courses, the first thing you should do to make sure you were successful is to

What are the benefits of taking notes while reading an assignment? Click all that apply.

What techniques can you follow to reduce any test anxiety you may experience? Click all that apply.