题目内容

Given a MAX 3-SAT formula $\Phi$ with k clauses, we show that the expected number of clauses satisfied by a random assignment is 7k/8. Consider a random assignment for formula $\Phi \wedge \bar{\Phi}$, the expected number of clauses satisfied is _____.

A. 7k/16
B. 7k/8
C. 7k/4
D. 7k/2

查看答案

搜索结果不匹配？点我反馈

更多问题

There are 8 statements and we have no knowledge about them. We randomly guess them true or false. So the possibility that we correctly guess 6 statement is _____.

A. 1/256
B. 9/256
C. 37/256
D. 93/256

查看答案

Given the same 3 men and 3 women as exercise 1. Which of the following misrepresentation can make Grace obtain better partner for herself in the returned matching?

A. Grace lies "I prefer David to Jack"
B. Grace lies "I prefer Jack to Bob"
C. Grace lies "I prefer David to Bob"

查看答案

Gale-Shapley algorithm finds______.

A. a perfect matching without stability
B. possible different assignments among all executions
C. the man-optimal assignment which is a stable matching

查看答案

Given the same 3 men and 3 women as exercise 1. Which one is the result of Gale-Shapley algorithm?

A. Bob-Grace, Jack-Anna, David-Alice
Bob-Alice, Jack-Grace, David-Anna
C. Bob-Anna, Jack-Grace, David-Alice

查看答案

Given a MAX 3-SAT formula $\Phi$ with k clauses, we show that the expected number of clauses satisfied by a random assignment is 7k/8. Consider a random assignment for formula $\Phi \wedge \bar{\Phi}$, the expected number of clauses satisfied is _____.

A. 7k/16 B. 7k/8 C. 7k/4 D. 7k/2

There are 8 statements and we have no knowledge about them. We randomly guess them true or false. So the possibility that we correctly guess 6 statement is _____.

Given the same 3 men and 3 women as exercise 1. Which of the following misrepresentation can make Grace obtain better partner for herself in the returned matching?

Gale-Shapley algorithm finds______.

Given the same 3 men and 3 women as exercise 1. Which one is the result of Gale-Shapley algorithm?

A. 7k/16
B. 7k/8
C. 7k/4
D. 7k/2