• Final exam scores and course grades posted to Compass.
• Some HW and links removed from site.

• Old practice exams for the final: FA09 mock midterm 2,FA09 midterm 2, SP10 mock final (solutions). As before, the subject matter and problem types might differ from our exam!

• Just a reminder: If you are willing to posting anonymous course feedback, please use the following link: Feedback. Thanks.

• Thanks to collective bargaining, you are allowed 4 sheets of paper as a cheetsheet for the final exam. (Same guidelines as for midterm 2; 8 sides of paper total)

• Final Exam is Friday Aug 05 from 1pm to 3pm (only 2 hours). It will be held in the 9am lecture room 1109 SC, with overflow in 1111 SC. Review will be held during the Thursday 9am slot.
• Last week office hours (as always, in the basement of Siebel):
  • Tue: 4-5pm Charles
  • Wed: 2-5pm Lucas
  • Thu: 10:30-noon, 2-5pm Lucas
• No lecture 2pm Wed Aug 03. Lucas is not planning on holding this lecture and will be holding office hours instead. (Though we reserve the right to reinstate this lecture if the need arises.)
• ICES (course review) forms will be handed out on Thursday during the review session. Please attend!
• You are allowed 3 sheets of paper as a cheetsheet for the final exam. (Same guidelines as for midterm 2; 6 sides of paper total)

• HW5 posted to the Lectures page

• Posted Midterm 2 solutions.
• Thanks to marathon grading, Midterm 2 scores will be posted to Compass soon.

  A list of the exam scores follows with a rough idea of letter grades. This is meant to give you an idea how you are doing relative to the rest of the class. The grade borders approximately follow the following guidelines (computed without outliers): B-/C+ cutoff is at the mean, and a std.dev. is one full letter grade away from that. e.g. A-/B+ is mean plus a std.dev., and C+/C is mean minus a third of a std.dev.

  • Mean (±stdev) = 43.19 (±14.78)

    A+
    A	63
    A-	61.5 60.5 60.5 59 58.5
    B+	57.5 57.5 56 54
    B	52.5 51.5 51.5 50.5 50.5 49
    B-	47
    C+	42 38.5
    C	38 37 35
    C-	30 30 28.5
    D+	24
    D	19.5 18.5
    D-	17 17
    F

  Chart formatting and grading formula copied from the admirably clear presentation of CS473.

• Posted solutions to the unrecognizable practice problems.

• There was a typo in the unrecognizable practice problems. A corrected version has been posted.
• Posted a short guide to reductions which gives a brief outline for reduction proofs.
• As stated in lecture, you can bring a cheatsheet to the midterm: two 8.5x11" sheets of paper with anything written / printed on both sides (4 sides in total). Otherwise, the exam is closed notes/books/etc.
• In case anyone looks at it again in the future, we modified HW4 "Problem Hierarchy" so that it has explicit encoding for the input. Alternate interpretions will not affect your grading.
• Two more practice problems: show the complement of REGULAR is unrecognizable and the Tape Monitor problem (HW4 in-class) is decidable.

• Practice problems have been posted for midterm 2: Fa 2011 Midterm 2, unrecognizable practice problems. More practice can be found in the HWs from previous semesters (Sp11 site, Fa10 site).

• Midterm Exam 2 is next Tuesday July 26 during lecture (normally a PSS). Lucas will be around the basement and available to answer questions for the majority of Monday (guaranteed to be there: 10:30-11:30am, 3:30-5:30pm). Charles will hold Monday office hours from 11:30-1:30am.
• There will be a 2pm lecture on Monday covering material that is not on the exam.
• Rice's theorem proof has been posted.

• The 2pm lecture today ran over by 5 minutes. The recording cut off the last minute or so, but it will be repeated at the start of next lecture.

• HW4 posted to the Lectures page

2011-July-14:

• It was mentioned in discussion that the proof that a language is not regular using the pumping lemma can be thought of as a game between you and an opponent. A description of this approach is available here.

2011-July-13:

• A change has been made to the second language of the "Closure properties to prove nonregularity" problem in HW3. Now, #0(w)+#1(w) = k² instead of 2^k. Please note this change when attempting to solve the problem (HW3).
• Lucas posted another regular closure property to the newsgroup (inverse homomoprhism). It can be complicated, but might help if you're trying to delete parts of strings.

2011-July-12:

• Midterm 1 solutions are posted.

2011-July-09:

• Starting at HW3, there will be a short answer Comprehension problem on each HW. The answers will not be covered during the problem solving sessions and cannot be resubmitted, so they are marked as In-Class-Submit. This is great for exam short answer practice!
• Added a collection of linked files at the top of the Lectures page.

2011-July-09:

• Lecture 14 did not record, so there are typed notes posted here.
• There was a small (but important) typo in the lecture 13 about the definition of a suffix class. See correction.

2011-July-07:

• HW2 resubmit deadline pushed back to Monday July 11.
• Midterm 1 scores are posted to Compass.

  A list of the exam scores follows with a rough idea of letter grades. This is meant to give you an idea how you are doing relative to the rest of the class. The grade borders approximately follow the following guidelines (computed without outliers): B-/C+ cutoff is at the mean, and a std.dev. is one full letter grade away from that. e.g. A-/B+ is mean plus a std.dev., and C+/C is mean minus a third of a std.dev.

  • Mean (±stdev) = 43.15 (±12.02)

    A+	71
    A	64 62 62
    A-	59 59 57 56
    B+	54.5
    B	48.5 48.5 48
    B-	47 44 43.5
    C+	43 42.5 42 41
    C	36.5
    C-	34.5 34.5 34 32 32 31.5
    D+	31 31 30.5
    D	23.5
    D-	22
    F

  Chart formatting and grading formula copied from the admirably clear presentation of CS473.

2011-July-05:

• Midterm 1 practice exams: Spring 2011 midterm 1 and the exams listed at Fall 2010. Caution: they may cover some different/additional material!

2011-June-29:

• Midterm Exam 1 is next Wednesday July 06 during 9am lecture. Lucas will hold office hours after lecture on Tuesday, and Charles will hold his usual office hours at Tue 4pm
• Lecture 14 video posted as a asx file instead of the usual stream. It can be played in applications such as browsers (depending on addons), Windows media players, and VLC. (Sorry, there were more technical issues that Lucas doesn't understand yet.)

2011-June-28:

• Lecture 10 video posted late due to techinical issues. The first 15-20 minutes are missing, so there are lecture notes available to cover the gaps.

2011-June-24:

• HW2 posted to the Lectures page

2011-June-23:

• Modified the resubmit policy to reflect the "good faith effort" requirement. (Lucas mentioned this in class during the first week, but it was missing from the text.) You can only resubmit problems if you tried to complete them the first time!

2011-June-22:

• During today's 2pm lecture, the audio quality was off for unknown reasons. If you cannot understand something, email Lucas (ltcook2) and he'll translate for you. We're looking into the problem now...
• Dropboxes available in the basement for HW dropoff. Either lecture or dropbox submission is fine. Remember, submission deadline is the start of class (9:00 AM)!

2011-June-20:

• Typos involving the cent symbol fixed in the HW1 pdf (as mentioned in lecture).

2011-June-19:

• HW1 posted to the Lectures page.
• All office hours have been moved to the open area with the tables in the basement of Siebel. This is directly across from the CSIL labs, and one floor below the tables at Bevande.

2011-June-17:

• Students are allowed to work in groups of 2 and submit one copy of the HW. This is now a bit clearer in the policies.

2011-June-15:

• HW0 actually posted to the Lectures page, thanks to incompetence with technology.

2011-June-14:

• HW0 is now posted to the Lectures page.
• Course site is up. Please read the details above (especially the homework guidelines and course policies).

Course Summary

Objectives

• To learn the basic mathematical concepts and models which form part of the core of computer science.
• To gain experience in abstract mathematical reasoning and writing of mathematical proofs.
• To develop skills necessary for survival in CS 473.

Topics

• Finite automata, regular languages, and regular grammars
• Deterministic and nondeterministic computations on various automata
• Context free grammars, languages, and pushdown-automata
• Turing machines, Church's thesis, and undecidable problems

Prerequisites

The prerequisites for this course are CS 125 (or ECE 190), CS 173 (or MATH 213), and CS 225, or similar course experience.

Website adapted from previous semesters of CS 373 at Illinois. Thanks to Agha & Viswanathan Fall 2010 and LaValle Spring 2011. Some styling also borrowed from past CS 473 pages.