Please list all the three methods we discussed to solve recurrence.

    Why we usually use worst-case running time to represent the time complexity of an algorithm rather than using the average-case-running time?

Consider the following LP instance What can you said about the Dual LP?

Given a graph G=(V,E) and integers and , we say that a subset S of its vertices is (, )-balanced if (1) The size of S is . (2) There are at most edges in E with both endpoints in S. Consider the Balanced Subgraph Problem: Input: a graph G=(V,E) and positive integers . Output: a subset S of the vertices such that S is (, )-balanced, or report NO otherwise. Show that the Balanced Subgraph Problem is NP-complete.  

The K-almost SAT problem takes as input a boolean formula in conjunctive normal form with n variables and m clauses, an integer , and outputs an assignment of the variables such that exactly  clauses evaluate to true, or returns NO otherwise. Show that K-almost SAT is NP-complete.

Standard disclaimer: your solution should use the algorithms from class (DFS, Explore, BFS, Dijkstra’s, Bellman-Ford, Floyd-Warshall, SCC, Kruskal’s, Prim’s, Ford-Fulkerson, Edmonds-Karp, and 2-SAT) as a black box subroutine for your algorithm. If you attempt to modify one of these algorithms you will not receive full credit, even if it is correct. Make sure to explain your algorithm in words (no pseudocode!), explain the correctness of your design, and state and analyze its running time. Faster—and correct—solutions are worth more credit. You are given a directed, weighted graph G=(V,E) with exactly one edge, e=(uv), satisfying  w(e)

Let  be the set of all n-roots of unity, where n is a power of 2. You square all the elements in , delete duplicates if needed, and get a new set .  The elements in are

You are given a network  and a valid flow f. You are told that the flow along an edge satisfies f(e)=c(e). Which of the following is True? Select the most accurate answer.

Please define the term Inference?

Conversations and interview method of recording can be used for assessing the child’s language, cognitive, and social-emotional development.