CIS 38 | Fall 2004

CIS 38: Theoretical Computer Science
Fall 2004

Announcements

If you are interested in internships or other kinds of employment (relating to computer science), please check out the CUNY Institute for Software Design and Development's new Career Center on the web at http://career.cisdd.org. This is a free service that matches current CUNY students with potential employers. To participate, you simply upload your resume information and go through a 10-15 interview at the Institute (at the CUNY Graduate Center in midtown). They very much want to have a lot of CUNY students participating, and they're also very eager to help you out with resume-writing and interviewing skills. Please check it out and email with any questions.

Dec 11 OK, no homework from Chapter 7. But it will be on the final! I suggest you review problems 7.4, 7.5, 7.6. (I'll probably give you a couple more reivew problems before the exam...)
If you're interested in extra credit, you can take a look at chapter 5, and do exercises 5.6 and 5.7. Turn them in at the final (note that chapter 5 will NOT be on the final, but there are some very important ideas there nonethless.
I posted approximate current grades (sorted by student id). I don't have a couple folks' IDs, so check with me if you're one of them that isn't there. These grades are ROUGH and may not have much to do with your final grade in the class. It's just a rough sense of whether you're passing or not, basically!

Nov 30 Solutions for HW problems from Chs 3 and 4 are here (it's a MSWord document).

Nov 22 Exam Review questions: 3.5, 3.8, 3.13, 3.14, 4.4, 4.5, 4.12.
Turn in the three problems from Chapter 4 as homework.
And enjoy the holiday.

Nov 13 I can't remember if we made an official decision in class last week: let's postpone the exam until the Wednesday after Thanksgiving. It will cover chapters 3 and 4. We will probably start talking about Chapter 5 this week, but that material will not be on the exam.
OK, so on the 17th you'll turn in the problems listed below, along with 4.2, 4.3, 4.16

Nov 7 I don't think lecture this week went that great, so I'm not going to assign homework to be due on the 10th. But there will be a slightly larger homework due on the 17th, and it will start with these problems:

3.1c
3.5
3.7
3.8c
3.14a

Oct 31 Sorry for the late posting: homwework this week is 2.18cd and 2.19. The Pumping Lemma problems require a little thought to get s right, but they're not too bad. To do 2.19 properly requires a little mathematical induction -- do your best.
For extra credit, prove that the language {0^m 1^n | m != n} is not regular.
(And most of you owe me the homework that was due last week; don't forget it!)

Oct 22 I've graded the exams; the average is 68, which I'm actually quite pleased with -- in general it went better than I hoped it would. Feel free to email me for your grade (if you're in the high 60s that's a B-, with other grades roughly following from there). But I will not discuss specifics of your exam over email.
Homework due 10/27 is 2.5bde, 2.11, 2.15 (union only), 2.18a. For extra credit, 2.26.

Oct 18 (I nearly wrote "Dec 18". Don't I wish.) Anyway, the solutions link below is now updated to include HW5 and (kinda) HW2. Yee-ha.

Oct 16 Recent news on the exam: there will be no questions about PDAs, though there may be questions about CFGs.
(Remember, it's this coming Wednesday the 20th, from 6:20 to 8:00. Lecture will happen at 8:00, and your attendance is required.)

Oct 9 I've posted solutions to Homeworks 3 and 4. Solutions to 2 coming fairly soon.

Oct 7 Homework due Oct 13: 2.1c, 2.3bcfgjkm [part c should read "Give THREE..."], 2.4adf, 2.9, 2.14.

Oct 5 At long last, there is a mailing list available for our class. To subscribe, send an email to majordomo@sci.brooklyn.cuny.edu with body
subscribe cis38_dexter
To send a message to the list, send it to cis38_dexter@sci.brooklyn.cuny.edu

Oct 30 Homework 4, due Oct 6:
Use the Pumping Lemma to show that each of the following languages is nonregular:

The language of all strings over {0,1} that contain the same number of 0's and 1's (that is, 0101, 0011, 1001, 010110, etc. are all in the language).
The language containing all strings of the form 0^{i^2} for i >= 0 (that is, all sequences of i^2 -- "i squared" -- 0's).
The language of all strings over {0, 1} that are palindromes; that is, they are equal to their own reverse. So 0, 1, 00, 0110110110, 01110, etc. are all in the language.
For extra credit, prove the following: if L = L₁ union L₂, L is nonregular, and L₁ is regular, then L₂ is nonregular. (Hint: you do not need to use the pumping lemma...)

Sept 22 Homework 3, due Sept 29, is 1.9, 1.12b, 1.13abei, 1.15bdf, 1.16a

Sept 15 Homework 2, due Sept 22, is 1.4dhik and 1.5abd. Note that some of these address topics we haven't completely discussed in class. I think the books' explanation should be sufficient, but email if you have questions. I hope to finish Chapter 1 at the next lecture, so we'll be moving a little more quickly...!

Sept 4 The first exciting homework assignment, due at the beginning of class on Wednesday, is:
0.3 0.7, 0.11, 1.1, 1.3
Your answers may be typed or handwritten as you prefer.

Sept 1 Welcome to CIS 38. See the "Documents & Resources" page for the course syllabus and any other documents that may turn out to be useful for this course.

Dec 11	OK, no homework from Chapter 7. But it will be on the final! I suggest you review problems 7.4, 7.5, 7.6. (I'll probably give you a couple more reivew problems before the exam...) If you're interested in extra credit, you can take a look at chapter 5, and do exercises 5.6 and 5.7. Turn them in at the final (note that chapter 5 will NOT be on the final, but there are some very important ideas there nonethless. I posted approximate current grades (sorted by student id). I don't have a couple folks' IDs, so check with me if you're one of them that isn't there. These grades are ROUGH and may not have much to do with your final grade in the class. It's just a rough sense of whether you're passing or not, basically!
Nov 30	Solutions for HW problems from Chs 3 and 4 are here (it's a MSWord document).
Nov 22	Exam Review questions: 3.5, 3.8, 3.13, 3.14, 4.4, 4.5, 4.12. Turn in the three problems from Chapter 4 as homework. And enjoy the holiday.
Nov 13	I can't remember if we made an official decision in class last week: let's postpone the exam until the Wednesday after Thanksgiving. It will cover chapters 3 and 4. We will probably start talking about Chapter 5 this week, but that material will not be on the exam. OK, so on the 17th you'll turn in the problems listed below, along with 4.2, 4.3, 4.16
Nov 7	I don't think lecture this week went that great, so I'm not going to assign homework to be due on the 10th. But there will be a slightly larger homework due on the 17th, and it will start with these problems: 3.1c 3.5 3.7 3.8c 3.14a
Oct 31	Sorry for the late posting: homwework this week is 2.18cd and 2.19. The Pumping Lemma problems require a little thought to get s right, but they're not too bad. To do 2.19 properly requires a little mathematical induction -- do your best. For extra credit, prove that the language {0^m 1^n \| m != n} is not regular. (And most of you owe me the homework that was due last week; don't forget it!)
Oct 22	I've graded the exams; the average is 68, which I'm actually quite pleased with -- in general it went better than I hoped it would. Feel free to email me for your grade (if you're in the high 60s that's a B-, with other grades roughly following from there). But I will not discuss specifics of your exam over email. Homework due 10/27 is 2.5bde, 2.11, 2.15 (union only), 2.18a. For extra credit, 2.26.
Oct 18	(I nearly wrote "Dec 18". Don't I wish.) Anyway, the solutions link below is now updated to include HW5 and (kinda) HW2. Yee-ha.
Oct 16	Recent news on the exam: there will be no questions about PDAs, though there may be questions about CFGs. (Remember, it's this coming Wednesday the 20th, from 6:20 to 8:00. Lecture will happen at 8:00, and your attendance is required.)
Oct 9	I've posted solutions to Homeworks 3 and 4. Solutions to 2 coming fairly soon.
Oct 7	Homework due Oct 13: 2.1c, 2.3bcfgjkm [part c should read "Give THREE..."], 2.4adf, 2.9, 2.14.
Oct 5	At long last, there is a mailing list available for our class. To subscribe, send an email to `majordomo@sci.brooklyn.cuny.edu` with body `subscribe cis38_dexter` To send a message to the list, send it to `cis38_dexter@sci.brooklyn.cuny.edu`
Oct 30	Homework 4, due Oct 6: Use the Pumping Lemma to show that each of the following languages is nonregular: The language of all strings over {0,1} that contain the same number of 0's and 1's (that is, 0101, 0011, 1001, 010110, etc. are all in the language). The language containing all strings of the form 0^{i^2} for i >= 0 (that is, all sequences of i^2 -- "i squared" -- 0's). The language of all strings over {0, 1} that are palindromes; that is, they are equal to their own reverse. So 0, 1, 00, 0110110110, 01110, etc. are all in the language. For extra credit, prove the following: if L = L₁ union L₂, L is nonregular, and L₁ is regular, then L₂ is nonregular. (Hint: you do not need to use the pumping lemma...)
Sept 22	Homework 3, due Sept 29, is 1.9, 1.12b, 1.13abei, 1.15bdf, 1.16a
Sept 15	Homework 2, due Sept 22, is 1.4dhik and 1.5abd. Note that some of these address topics we haven't completely discussed in class. I think the books' explanation should be sufficient, but email if you have questions. I hope to finish Chapter 1 at the next lecture, so we'll be moving a little more quickly...!
Sept 4	The first exciting homework assignment, due at the beginning of class on Wednesday, is: 0.3 0.7, 0.11, 1.1, 1.3 Your answers may be typed or handwritten as you prefer.
Sept 1	Welcome to CIS 38. See the "Documents & Resources" page for the course syllabus and any other documents that may turn out to be useful for this course.