## A few computer science questions reviewed

Elaborate on the merits of specific tournaments or have general theoretical discussion here.
rajk
Lulu
Posts: 23
Joined: Thu Oct 25, 2012 10:55 pm
Location: California
Contact:

### A few computer science questions reviewed

A few criticisms of questions in the very small part of computer science I know
about.

In general, I think the problem is that writers tend to be imprecise or like to
reword theorems/statements, but often introduce critical errors while doing so.
Also, if the writer does not know too much about a subject and is just reading
Wikipedia, there's great potential for adding non uniquely identifying or
misleading clues. In fact, almost any time I looked up a tossup with non
uniquely identifying clues, all the lines were sourced from Wikipedia, which
isn't bad necessarily, but can sometimes lead to bad questions.

My other complaint is that in a lot of tossups, it's just a bunch of statements
of theorems one after the other with no connection or sense of "big picture" or
philosophical importance. Why is the busy beaver important at all? It's not
clear from the tossup I later mention. But perhaps this isn't possible given
the format.

ACF Nationals

=================

ACF Nationals 2015 Round 16 Question 8
Question: A value named for this scenario is defined as the sum over all inputs
p of "two raised to the negative of the absolute value of the length of p" and
is an example of a Martin-Lof random sequence. The proof of the principal
theorem resulting from this scenario relies on constructing a model whose two
inputs are another model of the same type as well a string, then having that
first model output the opposite of the second model; afterwards it is shown
that there is a contradiction if both models are the same. A reduction of this
scenario is used to prove that computing a non-trivial partial function is
impossible, a result known as Rice's theorem. Chaitin's constant gives the
probability that a program successfully resolves this scenario. The
insolvability of the Post correspondence problem relies on reducing it to this
other problem. For 10 points, name this undecidable decision problem which asks
if a Turing Machine will stop for a given input.

ANSWER: halting problem
1) You can't really prove anything by reducing PCP to halting problem.
The question meant to say "..relies on reducing this problem to PCP".
Common mistake but it makes the clue completely wrong.

2) Acceptance problem for Turing machines (rather than halting) is usually
reduced to PCP, though they are closely related. Acceptance problem should
probably just be an alternate answer.

=================

ACF Nationals 2016 Round Michigan B Question 2
ANSWER: Busy beaver function

1) The statement that BB(5) = 4098 is incorrect, this is just a lower bound

2) In general this tossup doesn't talk about why the Busy Beaver is
computationally or philosophically important, it just lists a bunch of big
numbers. But maybe it's hard to motivate it while still being uniquely
identifying.

=================

ACF Nationals 2014 Round Michigan Bonus 4
ANSWER: Post correspondence problem

1) This is a really bad description of the PCP, and I don't think it can be
considered remotely correct even given generous interpretation.

=================

ACF Nationals 2011 Round Yale Tossup 14
ANSWER: DFAs

1) "A set of symbols...in the language" is not unique to DFAs at all, that's
basically the definition of the language of any machine

2) The pumping lemma doesn't state that DFAs can't recognize nonregular
languages. Rather, regular languages are defined as languages that can be
recognized by DFAs.

3) "These objects can be defined with a finite alphabet, a set of states, and a
transition function...". This is also true for PDAs, deterministic PDAs, LBAs,
Turing machines, whatever. Not unique at all.

4) The tossup should most likely accept or at least prompt on NFAs since a
large part of the clues involve constructions that use NFAs.

=================

Chicago Open

=================

Chicago Open 2010 Round 3 Question 2
ANSWER: interactive proof

1) Completeness and soundness are bounded by 2/3 and 1/3 respectively, usually,
not 1/3 and 2/3 like the question says.

2) The question implies AM[poly(n)] = AM[2], which is still an open problem).
It is true however that AM[k] = AM[2] for constant k. Problem is that
"Arthur-Merlin protocol" doesn't really clearly correspond to any of AM, MA,
AM[k], or AM[poly(n)].

3) Many interactive proofs don't involve any sort of committing as the question
implies, but zero-knowledge proofs do due to Goldwasser,
Sipser et al. - maybe this is what the author meant. However note that
their construction involves commitment schemes, and I think all
committment schemes assume that one-way functions exist, which is not known
to be the case, so it doesn't really make sense to make such a blanket statement.

4) The prover is not usually probabilistic, since he has infinite power (or in
some cases, limited to PSPACE), he can just simulate randomness. In fact, many
constructions of IP model the prover as a function instead of a Turing machine.

5) In interactive proofs, the verifier is never dishonest. However the verifier
could be dishonest in zero knowledge proofs.

6) Shamir seems pretty early given the difficulty of the following clues.

=================

Chicago Open 2016 Round 11a Mukherstein Question 14
ANSWER: oracle machines

1) I could be wrong but I don't think the prononuciation of languages with
oracle machines L^A as "L-A" is standard (at least my professor says "L to the
A"). Might trip up a few people who intepret it as L(A).

=================G

ACF Regionals

=================

ACF Regionals 2015 Round VCU A + Dorman HS Question 17
Question: The cycle rank, or loop complexity, of a directed graph is related to
a quantity for these things according to a theorem devised by Eggan. These
things can be converted to an NFA by constructing partial NFAs and putting them
together with an epsilon transition, as is done by Thompson's construction
algorithm. Like a namesake type of language, these things were developed and
formalized by Stephen Kleene, who defined concatenation, union, and his
namesake star for them. A backreference in these things can be created using
parentheses. The asterisk quantifier is used to match the previous group or
character zero or more times in Perl's system for them. For 10 points, identify
these notations used for pattern matching that describe a set of strings,
so-called "expressions".

ANSWER: regular expressions [or regexp; or regular sets; or rational
expressions; or regular languages; accept just regular after "expressions" is
read; prompt on "patterns"]
1) Concatenation, union, and Kleene star apply to languages in general, not
just regular languages.

2) Backreferences are impossible in "real" regular expressions. Maybe "A
backreference in a generalization of one of these things" would be more
appropriate.

=================

ACF Regionals 2015 Round xEMERGENCY EXTRASx Question 3
Question: Langston's ant and turmites are two-dimensional analogues of these
constructs. Recursively enumerable languages are equivalent to the class of
languages recognized by these constructs. The universal variant of these
constructs can simulate every possible one of these constructs. Attaching one
of these to an "oracle" can make it stronger, and a busy beaver is a specific
variant of these constructs that executes the maximum number of steps. Lambda
calculus is equivalent in power to these constructs according to a hypothesis
named after Alonzo Church and these devices' namesake. For 10 points, name
these theoretical devices with a head that can read, write, and move upon an
infinite length of tape.

ANSWER: Turing machines
1) Church-Turing thesis states that all algorithms computable in general (for
example, by a human) can be computed by Turing machines. Equivalence between
lambda calculus and Turing machines has been proved.

=================

ACF Regionals 2012 Round MIT A Question 2
ANSWER: NP

1) Again, it's not really clear what "Arthur Merlin" proof refers to.

=================

Lederberg 2014

All great, at least on the stuff I know.

-The compilers tossup was pretty easy, GHC and LLVM on second line.
-Java, I thought autoboxing was pretty basic stuff beginners learn
-Stable marriage is worded somewhat confusingly.
-Post question is good.
-Cryptographic keys tossup seems very easy compared to for example, planar
graphs or permutations.

=================

Avogadro 2016

All great, at least on the stuff I know.

1) Lawson's flip algorithm seems early mention, since the projection later
mentioned is used to prove the correctness of Lawson flip.

2) File question is good, but the "one of these things following a greater than
sign" probably confused some people. Maybe "the name of one of these things"
would be better. I think more people would be familiar with the 3 UNIX
permissions octals than the specific ext3/ext4 implementations.

3) "hacking" xkcd clue is nice

=================

George Oppen Round 15 Question TB Bonus
ANSWER: Boolean satisfiability

1) The answerline accepts 2-SAT as an alternate answer, which is incorrect
since 2-SAT is known to be in P and even NL.

=================

MUT 2012 Round 3 Question 18
ANSWER: P

1) The bonus lead in says that we are sure P!=PSPACE. However, this is an
open question.

=================

For fun,

ACF Nationals 2004 Round Rutgers Question 23

1) QSAT is not the typical name for the canonical PSPACE-complete problem, it's
called TQBF by almost everyone but one specific textbook, that isn't a major
one. Further, the description of TQBF is incorrect, because "satisfiability of
first-order logical expressions" is undecidable in general. In TQBF, variables
are quantified over the set {0, 1}.

2) Graph non-isomorphism is in PSPACE, sure, but any reasonable person would
say it's in co-NP, since it is way more specific than PSPACE.

3) P also trivially includes L, though I believe P=L is still open. NL, P, and
NP could also reasonably be proper subsets of Sigma2, PH, #P, EXP, NEXP, some
circuit classes, whatever.

=================

Also, why are there so many clues on Chaitin's constant? Fuck Chaitin's
constant.
Last edited by rajk on Sat Oct 01, 2016 5:03 pm, edited 4 times in total.
Bala
UC Berkeley, 2018
Cody
2008-09 Male Athlete of the Year
Posts: 2776
Joined: Sun Nov 15, 2009 12:57 am
Location: Richmond

### Re: A few computer science questions reviewed

rajk wrote:ACF Regionals 2015 Round VCU A + Dorman HS Question 17
Question: The cycle rank, or loop complexity, of a directed graph is related to
a quantity for these things according to a theorem devised by Eggan. These
things can be converted to an NFA by constructing partial NFAs and putting them
together with an epsilon transition, as is done by Thompson's construction
algorithm. Like a namesake type of language, these things were developed and
formalized by Stephen Kleene, who defined concatenation, union, and his
namesake star for them. A backreference in these things can be created using
parentheses. The asterisk quantifier is used to match the previous group or
character zero or more times in Perl's system for them. For 10 points, identify
these notations used for pattern matching that describe a set of strings,
so-called "expressions".

ANSWER: regular expressions [or regexp; or regular sets; or rational
expressions; or regular languages; accept just regular after "expressions" is
read; prompt on "patterns"]
1) Concatenation, union, and Kleene star apply to languages in general, not
just regular languages.

2) Backreferences are impossible in "real" regular expressions. Maybe "A
backreference in a generalization of one of these things" would be more
appropriate.
A number of your other critiques look fine. But, I will comment on this critique because I helped VCU edit this question before it went in and the critiques to this question are very, very wrong in the tact they take.

1) There is no other thing which fits the partial clue: has a namesake type of language + formalized by Kleene (like the type of language). There is no other thing that fits the full clue, which expands on it to give you information about the Kleene star and other operations that were specifically defined by Kleene. To make the (obvious) claim that the mentioned operations also apply to other languages is to miss the forest for the trees: there's a whole lot of sentence before that point that makes things unique. Plus, the clue 100% implicitly rules out a type of language as an answer in that sentence, and the clue you point out refers directly to the answerline.

2) If every assumption and caveat in science questions were spelled out, there would be no room for actual clues. Quizbowl is much better for not including information not necessary to clearly convey what the answer is given a clue that someone knows. If you know what backreferences are, you will not be confused and you will get this question (especially given that Perl's RE system is most commonly called just regular expressions, unless you're discussing grep with someone).
Cody Voight (he/him), VCU ‘14. I wrote lots of science and am an electrical engineer.
VCU Tournament Director ‘13-‘17. HSAPQ President ‘15-‘16. ACF Treasurer ‘19-‘20. ACF Nats ‘21 TD.
Hero of Socialist Quizbowl Labor (NSC ‘14). “esteemed colleague” of Snap Wexley, ca. 2016. Stats Hero (Nats ‘16).
Quizbowl at VCU
Ike
Auron
Posts: 1047
Joined: Sat Jul 26, 2008 5:01 pm
Contact:

### Re: A few computer science questions reviewed

I disagree with a lot of these critiques, and I really don't see the point of this thread. Quizbowl is rife with simplifications, and thats OK and by design. I don't know what the original poster's intention here is, but at least one of these critiques, and maybe more, are made just "for fun." Well, no one likes seeing critiques of their own work just "for fun."

Here's what I mean: I'm the one who made the error of 4,098 being a lower bound. I apologize for making this error, but i cannot see how this can possibly affect game play. But did that cause a player to neg, or is the OP just going through stuff in the past to catalogue a list of inaccuracies? I suspect it's the latter more than the former.

I'll say this, these questions aren't written by people who have that much theory of computation background, so expecting them to fit perfectly to OP's sensibilities and be error free is unrealistic, especially since there aren't any theory specialists writing tons of qb questions. Not gonna lie - I don't have enough real knowledge about IP to grasp the points OP made, and I imagine that almost no one else who is reading this does either. So if there is some general advice other than "don't make mistakes," by all means give it, but I don't think this advice here is useful to future writers.
Ike
UIUC 13
rajk
Lulu
Posts: 23
Joined: Thu Oct 25, 2012 10:55 pm
Location: California
Contact:

### Re: A few computer science questions reviewed

@Cody - I agree with your points.

@Ike - I'd like to hear which ones you disagree with, if you have time. Most of these to me, seem to be factual inaccuracies rather than stylistic choices.
is the OP just going through stuff in the past to catalogue a list of inaccuracies?
Yes, this was the task posed to me.
I don't know what the original poster's intention here is,
I had noticed some errors in questions while looking up answerlines that I had learned about in class, and was surprised by how many there were, and wasn't sure if it was known to the community that there were these errors.
So if there is some general advice other than "don't make mistakes," by all means give it, but I don't think this advice here is useful to future writers.
This is hard. I've never really written any questions, so I don't really have useful advice. My view is that it's almost impossible to write an error-free technical question at the ACF Nats/CO level without actually understanding all the clues, since there's such a great chance for minor changes to introduce errors. It isn't really possible to give advice on how to make clues uniquely identifying, since that generally requires a large amount of domain knowledge to begin with. But here are a few ideas.
• If using a clue from a source, try not to change any technical wording significantly. "Reducing to" and "reducing from" are entirely different but sound very similar.
• Wikipedia often has confusing writing, so make sure you know what a particular sentence in Wikipedia is referring to before using the sentence as a clue. For example, Wikipedia says "For any constant k ≥ 2, the class AM[k] is equal to AM[2]." And maybe someone assumed that AM stood for Arthur-Merlin protocol in general. So it's reasonable to assume that any Arthur Merlin protocol would only take 2 rounds, but this is incorrect, since the quoted sentence only referred to AM[k] for constant k (as opposed to the number of rounds being dependent on the size of the input).
• Double check facts, don't rely on memory, even if you do know about the subject. This prevents silly errors like saying 2-SAT is NP-complete.
I'd be interested in hearing how computer science writers in the community write good questions. For example, the bonus in 2015 ACF Nationals about complexity classes/IP/GI was excellent. Did the writer already know about interactive proofs prior to writing the question?
Bala
UC Berkeley, 2018