assignments
due Tue Sep 6
Assignment 0
- Plunge into Chapter 0 of Sipser. Read and understand as much as you can.
- In class Thu we'll go over the main ideas and any bits you found especially sticky.
- Then start Chapter 1 : as much as you can manage of Section 1.1.
due Thu Sep 8
Assignment 1
- Problems 0.3 ("Is the set..."), 0.7 ("For each part..."), 0.11 (The one about horses), 0.12 ("Show that every graph...") and 0.13 (Ramsey's Theorem) from Sipser (2nd ed.). For the last one, can you do better than \( 1/2 \log_2 n \) (in general or for specific small \(n\) )?
- Show that \( 1 \cdot 2 + 2 \cdot 3 + 3 \cdot 4 + ... + n(n+1) = n(n+1)(n+2)/3 \) for all positive integers n (where "\(\cdot\)" denotes multiplication)
- Continue with Chapter 1 reading, as discussed in class.
due Thu Sep 15
Assignment 2
- Finish reading chapter 1 for Tuesday.
- Do Sipser 1.14 ("Show that if M is a DFA that...") and 1.16 ("Use the construction given in Theorem 1.39 to ...").
- Read about regex's as used by programmers, from e.g. http://docs.python.org/2/howto/regex.html , http://regex.learncodethehardway.org/book/ , and/or http://docs.python.org/2/library/re.html .
- Explain which parts of the regex programming syntax are consistent with the math definition of a regular expression, which aren't, and why.
- Give and test regexes that match simple versions of either (a) a valid email address, or (b) a valid URL. You'll need to decide on your own what "simple" means, and do a bit of digging to decide what characters are allowed where. (Please don't just google this; see what you can come up with. I'm saying 'simple' because the complete rules can get pretty messy.)
For at least one of these DFA's
(a) {0,1} with even number of ones OR multiple of three of zeros
(b) {0,1} with even number of ones AND multiple of three of zeros
(c) {0,1} with a 1 in every odd position in the string
(d) The language matched by the regex 0*1*00*
do the following two coding exercises :
- Create a *.fa file using Jim's simulator at http://cs.marlboro.edu/tools/finite_automata/fa.cgi (Once it does what you want, copy/paste the text into a file on your computer, and submit it as part of your homework. Then reset the _sample machine so the next person isn't starting from yours.)
- Write some code in a language of your choice (e.g. Python) to simulate it yourself, including running some test cases and printing out the result.
due Thu Sep 29
Assignment 3
From Sipser (2nd Ed.): 1.43 (on DROP-OUT), 1.53 (on ADD), 2.9 (Give a context-free grammar...), 2.10 (Give an informal description...) , 2.21 (Let \(\Sigma\)...).
due Thu Oct 6
Assignment 4
E → E , E | id ( E ) | ( E ) | [ E ] | id
If an approach won't work, adjust the grammar in a way that it can.
- From Sipser (2nd Ed.): 2.31 (palindromes), 2.33 (\(\{a^ib^j:i=jk\}\)), 2.35 (Chomsky normal form).
due Thu Oct 13
Assignment 5
- Using the yvtm (yaml virtual turing machine) spec as described at virtual turing machine, implement and test a turing machine simulator. You can use a language of your choice ... but python might be a simple choice. The YAML format has library support in most popular languages, so reading in the file shouldn't be a lot of work.
- Using your machine (or my older vtm which is running on csmarlboro.org, or a classmate' implementation, or mine if you're really stuck - and if so, ask) write Turing machine programs in the *.yvtm form for at least two of the following three machines :
- recognize the language \( a^nb^nc^n \)
- addition base 2, i.e. 101 + 111 = 1100
- recognize strings of 0's and 1's which have an even number of 0's and either a multiple of 3 or a multiple of 5 number of 1's.
- From Sipser: 3.4 (definition of enumerator), 3.11 (doubly infinite tape).
due Thu Oct 20
Assignment 6
- Find the error in this proof.
- From Sipser: 3.8b (implementation level TM), 3.12 (left reset), 3.15 (closure of decidable languages), 3.19 (infinite recognisable languages).
due Thu Oct 27
Assignment 7
- Explore the topic of where humans fit into our hierarchy of computability, if anywhere. In other words, can a machine be a person (conscious, sentient, etc) and if so, what sort of machine would be required? Is "being human" turing computable?
- See this page of questions and resources to get started.
- Summarize the various arguments pro and con and make a reasoned argument for your position on this question.
due Thu Nov 3
Assignment 8
- Sipser: 5.3 (Find a match), 5.19 (Silly PCP), 5.21 (AMBIG_CFG), 5.31 (Collatz).
due Thu Nov 10
Assignment 9
- Translate the sentence "Every prime is expressible as the sum of two square numbers" into precise language for math statements given in Section 6.2. Is it a member of \( \mathcal{Th}(\mathbb{N}, + , \times) \)?
- Sipser: 6.6 (Describe two Turing machines...), 6.13 (Integers mod m), 6.25 (Show that for any \(c\)...)
due Thu Nov 17
Assignment 10
- Programming problem discussed in class:
- Choose a classic P problem. Implement a computer program in a language of your choice that solves it for various n, and show that the runtime is a polynomial.
- Do the same for a classic NP problem, but this time show that the runtime is exponential.
- Finally, demonstrate that a solution to that NP problem can be verified by a program that runs in polynomial time.
- Sipser 7.26 (You are given a box...)
due Mon Dec 12
Final
term grade
- A place for Matt & Jim's comments
