assignments
due Tue Sep 10
Assignment 0
- Plunge into Chapter 0 of Sipser. Read and understand as much as you can.
- In class we'll go over the main ideas and any bits you found especially sticky.
- ADDED SEP 6th:
- Start Chapter 1; as much as you can manage of Section 1.1.
due Thu Sep 12
Assignment 1
- Problems 0.3 ("Is the set..."), 0.7 ("For each part..."), 0.10 ("Find the error in the following proof that 2=1..."), 0.12 ("Show that every graph...") from Sipser (2nd ed.) and 0.13 (Ramsey's Theorem). For the last one, can you do better than \( 1/2 log_2 n \) (in general or for small \(n\)?
- Show that 1.2 + 2.3 + 3.4 + ... + n(n+1) = n(n+1)(n+2)/3 for all positive integers n (where "." denotes multiplication)
- Continue with Chapter 1 reading (details TBD in class on Tuesday).
due Thu Sep 19
Assignment 2
- Finish reading chapter 1.
- 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 26
Assignment 3
- From Sipser (2nd Ed.): 1.29b, 1.43, 1.54, 1.55c,e,f, 1.57.
due Thu Oct 3
Assignment 4
- Read about parsing. (I have a long list of possible sources at parsing - take your pick and explore and/or google the key words.)
- Answer the following questions :
- What is the difference between "top down" and "bottom up" parsing? Explain with a specific example. (In other words, pick a context free grammar, perhaps from the reading, pick a sentence that it can create, and parse it by hand using both a top-down and bottom-up approach.)
- What is "recursive descent"? What are its advantages and disadvantages?
- What is "LR" parsing, and what does it have to do with Bison? What are its advantages and disadvantages?
- Pick (at least) one of the software tools listed above. Install it, get one of the demos in the documentation running, and try to write a tiny example of your own, using (for example) a grammar for a calculator, with sentences like "1 + 2 * 4". Describe your experience, and be ready for some show-and-tell in class.
due Thu Oct 10
Assignment 5
- From Sipser (2nd Ed.): 2.9, 2.10, 2.21, 2.31, 2.33.
due Thu Oct 17
Assignment 6
- Finish reading chapter 3 if you haven't already
- Implement and test Sipser (2nd edition) example 3.7 on page 143 (a machine that decides 0**(2**n)) with vtm. See the vtm notes from Tuesday's class for how to use vtm (on cs.marlboro.edu or csmarlboro.org).
- Design and implement a turing machine that recognizes the language \(a^nb^nc^n\), and show that it works, again using vtm. (We started this in class on Tuesday).
due Thu Oct 24
Assignment 7
- From Sipser: 3.8b, 3.12, 3.15.
- Either Sipser 3.19 or do something more with vtm.
due Thu Oct 31
Assignment 8
- From Sipser: 4.3, 4.6, 4.10, 4.18.
due Thu Nov 7
Assignment 9
- Read Chapter 5.
- From Sipser: 5.16, 5.23
- Give an example in the spirt of the recursion theorem of a program in a real programming language that prints itself out.
due Thu Nov 14
Assignment 10
- Read Chapter 6.
- From Sipser:
- 6.2 (Show that any infinite...)
- 6.23 (Show that the set of incompressible strings is undecidable).
- Google, read, and about "Chaitin's constant". Describe how you might go about trying to compute some of it.
- Describe how you might go about determining \( d_{python}((10)^n) \) , as defined on pg 238 of Sipser, where the notation \( (10)^3 \) means the string 101010. Can you make a case for any specific values of this function?
- Write a program that solves at least some instances of the PCP (Post Correspondance Problem, the dominos from chapter 5).
due Thu Nov 21
Assignment 11
- (This may be turned in the Tuesday after the break if need be.)
- Read chapter 7 on time complexity, P and NP.
- Choose a class NP problem. Implement a computer program that solves it, and show with numerical experiments that the run time is slower than polynomial.
- Demonstrate with a numerical experiment that a solution to that NP problem can be verified in polynomial time.
- 7.5 : Is the given formula satisfiable? (This is quick.)
- 7.9 : Show that TRIANGLE (does a given undirected graph contain one) is in P. (Also quick.)
- 7.26 : flip cards (A thought problem.)
- Read about minesweeper, and check one of its logic gates.
due Tue Dec 10
presentations
- present a "complexity zoo" example or topic
due Mon Dec 16
final take-home exam
- out Tue Dec 10; due Mon Dec 16
- exam (pdf)
semester grade
- a place for Jim & Matt to give feedback and a grade
