Comments for Exam 1

CSc 75010: Theoretical Computer Science
Graduate Center, City University of New York
Fall 2002


Grading

The exam was graded in the same style as the comprehensive exam in June.  Each question was worth 20 points.  The overal score was the sum of the best five question scores.  You can not score over 100%.

Regrading:

If you would like your exam regraded, please attach a note on the front of the exam.  Your note should explain which questions you would like regraded and why.  Please use complete sentences.  Do not write on the exam itself.  If you do so, your exam will not be considered.  You must turn the exam in for regrading by Friday, 25 October.

Scores:

After each exam was graded, the average of the different exams were calculated.  The scores were than normalized to make up for any differences in difficulty between the different versions of exams.  The average across all exams is 93 with standard deviation 7.

Version:
 Average:
 Standard Deviation:
 To Calculate your score:
Blue
 95
 5
 raw score
Green
 92
 11.5
 min(raw score+3, 100)
Pink
97
 4
 raw score
Yellow
 90
 6.8
 min(raw score+5, 100)



Comments

When taking the exam in June, each question must be answered on a separate piece of paper (actually, separate "blue book").

Question 1:  Define basic terms.

Most everyone had no problems providing the simple definitions required.  A similar question to this has appeared frequently on the exam offered in June.  See for example, June 2002, #2.  On the June exam, this question is considered easy, so, mistakes on this are graded harshly.  The same was done for this exam.

Question 2:  Find error in proof of 2=1.

This comes straight from the homework.  You needed to state the reason the proof failed (dividing by 0 is not allowed) to get full credit.

Question 3:  Build 2 NFAs.

While each version of the exam had different questions, they were all variations on a theme.  Part a) was recognize the language of all words that contains a fixed substring (i.e. "yellow").  Part b) was slightly harder and asked the string begin or end with a fixed substring (i.e. "hi" or "bye") and satisfy some condition about length.  Partial credit was given for NFAs that recognized part, but not all, of the language.  All and all, everyone did well on this question.

Question 4:  Prove closure under a regular operator.

This is straight from the lecture notes or book.  The most common mistakes were notational-- writing down a machine M but not saying how it related to the question (did it recognize the original language? was it the machine you were trying to build?)-- and proving that some other operator was regular instead of the one on your version of the exam.  If the idea was there but muddled by notation, only 5 points were deducted.

Question 5:  Prove a language is not regular.

When using the Pumping Lemma, you cannot choose the length of the y given by the Pumping Lemma for a given string.  The lemma is weaker, it only says that some y exists that satisfies the conditions of the lemma for each string s longer than the pumping length.  1/2 the points were deducted for choosing a fixed y, instead of considering all the possibilities that it could be.

The blue exam asked to show that the complement of {0^n1^n  | n >= 0} is not regular.  Half of the points were awarded if you only showed the language (and not it's complement) is regular.  This question can be approached in a number of ways.  The easiest would be to show the language is not regular, and then note that the class of regular languages is closed under complementation. You could also look at the language in two parts: those words that have more 0's than 1's and those that have more 1's than 0's.  Or, you can do this directly using the Pumping Lemma by choosing 0^p1^{p+p!} and pumping with (1+p!/j) where j is the length of y.

The pink exam asked similar question to the blue and can be solved in the same way.

The yellow exam asked about the language ADD from the homework.  Most mistakes were forgetting that "=" is just another symbol in the language.  If you choose s = "1^p = 1^p + 0", then the rest follows as before.

Question 6:  Give CFGs

This was the question most likely to be skipped.  All of these are from the book and homework.  Part a) for each version was a simple CFG, and part b) more complicated.  The most common mistake was to draw DFA's instead of writing out grammars.