http:^^www.deas.harvard.edu^cs^academics^courses^cs121^cs121.html

This data set contains WWW-pages collected from computer science departments of various universities

Date: Wed, 20 Nov 1996 22:24:53 GMT
Server: NCSA/1.5
Content-type: text/html
Last-modified: Mon, 11 Nov 1996 15:20:21 GMT
Content-length: 6694

<a name="top">
<title>CS121: Introduction to Formal Systems and Computation</title>
</a>

<h1>CS121: Introduction to Formal Systems and Computation</h1>

<i>Computer Science 121 is an undergraduate course introducing
automata, formal languages, computability, uncomputability, 
computational complexity, and NP-completeness.  The theme of the course is 
reasoning about formal systems.
This page provides access to on-line course materials.</i><p>

<h2>Table of Contents</h2>

<i>
<ul>
<li><!WA0><a href="#general">General Information</a>
<li><!WA1><a href="#announcements">Announcements</a>
<li><!WA2><a href="#problemsets">Problem Sets</a>
<li><!WA3><a href="#errata">Errata in text</a>
</ul>
</i>

<hr>

<!WA4><a name="general" href="#general"><h2>General Information:</h2></a>

<ul> 

<li><!WA5><a href="http://www.deas.harvard.edu/cs/academics/courses/cs121/summary.html">Course summary</a>
<li><!WA6><a href="http://www.deas.harvard.edu/cs/academics/courses/cs121/admin.html">Administative Details</a>
    <ul>
    <li><!WA7><a href="http://www.deas.harvard.edu/cs/academics/courses/cs121/admin.html#meeting">Meeting Information</a>
    <li><!WA8><a href="http://www.deas.harvard.edu/cs/academics/courses/cs121/admin.html#staff">Instructional Staff</a>
    <li><!WA9><a href="http://www.deas.harvard.edu/cs/academics/courses/cs121/admin.html#email">Email Access</a>
    <li><!WA10><a href="http://www.deas.harvard.edu/cs/academics/courses/cs121/admin.html#office">Office Hours</a>
    <li><!WA11><a href="http://www.deas.harvard.edu/cs/academics/courses/cs121/admin.html#prereq">Prerequisites</a>
    <li><!WA12><a href="http://www.deas.harvard.edu/cs/academics/courses/cs121/admin.html#prob-sets">Course Work</a>
    <li><!WA13><a href="http://www.deas.harvard.edu/cs/academics/courses/cs121/admin.html#sections">Sections</a>
    <li><!WA14><a href="http://www.deas.harvard.edu/cs/academics/courses/cs121/admin.html#computer">Computer Issues</a>
    <li><!WA15><a href="http://www.deas.harvard.edu/cs/academics/courses/cs121/admin.html#texts">Texts</a>
    <li><!WA16><a href="http://www.deas.harvard.edu/cs/academics/courses/cs121/admin.html#handouts">Handouts</a>
    </ul>
<li><!WA17><a href="http://www.deas.harvard.edu/cs/academics/courses/cs121/files/syllabus.ps">Syllabus</a>

</ul>

<!WA18><a name="announcements" href="#announcements"><h2>Announcements:
</h2></a>

<ul>

<li>Sat Sep 07 16:14:00 1996: 
<strong>Please Purchase Text</strong><br>
The text book is available in the Science Center stockroom (in the basement).
<p>
<li>Mon Sep 16 13:44:00 1996:
<strong>Sign up for sections</strong><br>
Possible section times are Sun at 7:00, Mon at 1:00, 2:00, 3:00,
4:00, 7:00, 8:00.  Please sign up for all sections which you can
<it>possibly</it> attend, not just the most convenient time.
Instructions for signing up for section are available 
<!WA19><a href="http://icg.harvard.edu/section/student.html">here</a>.<p>
<li>Wed Sep 18 12:45:18 1996:
<strong>Problem section this Friday</strong><br>
There will be an optional problem section this Friday in Aiken 
G-23 from 2pm to 4pm.  The topic will be "How to do Proofs".<p>
<li>Wed Sep 18 12:54:44 1996:
<strong>Old handouts</strong><br>
The handouts distributed during Tuesday's lecture are available in
University Hall 4.  Each day's lecture notes (and any other applicable
handouts) will be made available there shortly after the conclusion
of lecture.<p>
<li>Thu Sep 19 18:00:00 1996:
<strong>Lecture Hall change</strong><br>
Starting on Tue Sep 24, lectures will be in the Boylston Hall
Auditorium.  Boylston Hall is in the yard next to Widener.<p>
<li>Fri Sep 20 15:15:00 1996:
<strong>Regular Sections</strong><br>
If you signed up for section before 14:00 on Fri, Sep 20, you should
have been assigned to a section.  If you didn't receive automatic
notification of your section assignment, please look
<!WA20><a href="http://www.deas.harvard.edu/cs/academics/courses/cs121/files/students-in-sections.txt">here</a>.
<p>
<li>Fri Sep 20 15:15:00 1996:
<strong>Additional Section</strong><br>
There will be a section at 4:00 on Tue, Sep 24 in Aiken G23.
Please try to attend this section if you can't attend your regular
Sunday or Monday section because of the holiday.<p>
<li>Sun Sep 22 13:23:00 1996:
<strong>Correction to Problem Set 0</strong><br>
Problem 4b of PS0 should be corrected to read
<pre>"Is the overlap relation reflexive?  If so, prove it.  If not, 
provide a counterexample."</pre><br>
The formal definition of overlap originally expected is in fact 
reflexive.  However, there exists an alternate definition of this relation, 
equally reasonable, but different in some minor details, which is not 
reflexive.  Your answer to 4b should be consistent with your definition, 
as should your justification of that answer.<p>
<li>Tue Sep 24 12:58:13 1996:
<strong>Proof section repeated this Friday</strong><br>
The problem section on "How to do Proofs" which was held last Friday
will be repeated this Friday from 2-4pm in Aiken G-23. <p>
<li>Sat Sep 28 15:32:18 1996:
<strong>Sunday evening section relocated</strong><br>
Ben's Sunday 7:00-8:00 section will be held from now on in Science
Center B-09.
<li>Tue Oct 15 12:59:49 1996:
<strong>Sunday review section for hour exam</strong><br>
There will be a special section Sunday October 20 from 1:00PM to
3:00PM in Science Center 111 to help review for the hour exam.
<p>
</ul>

<!WA21><a name="problemsets" href="#problemsets"><h2>Problem Sets:</h2></a>

Problem set policies can be found <!WA22><a href="http://www.deas.harvard.edu/cs/academics/courses/cs121/admin.html#prob-sets">here</a>.

<ul> 

<li><!WA23><a href="http://www.deas.harvard.edu/cs/academics/courses/cs121/files/ProblemSets/ps0.ps">Problem Set 0</a>: 
      Induction Relations, etc. Optional but recommended.<br>
  <i>Distributed:</i> Tuesday, September 17.
  <ul><li><!WA24><a href="http://www.deas.harvard.edu/cs/academics/courses/cs121/files/ProblemSets/soln0.ps">Solutions</a></ul>
<li><!WA25><a href="http://www.deas.harvard.edu/cs/academics/courses/cs121/files/ProblemSets/ps1.ps">Problem Set 1</a>: 
      Regular expressions, Finite automata, and Algorithms.<br>
  <i>Distributed:</i> Tuesday, September 24.
  <ul><li><!WA26><a href="http://www.deas.harvard.edu/cs/academics/courses/cs121/files/ProblemSets/soln1.ps">Solutions</a></ul>
<li><!WA27><a href="http://www.deas.harvard.edu/cs/academics/courses/cs121/files/ProblemSets/ps2.ps">Problem Set 2</a>: 
      Equivalence of regular expressions, finite automata; Closure properties.
  <i>Distributed:</i> Tuesday, October 1.
  <ul><li><!WA28><a href="http://www.deas.harvard.edu/cs/academics/courses/cs121/files/ProblemSets/soln2.ps">Solutions</a></ul>
<li><!WA29><a href="http://www.deas.harvard.edu/cs/academics/courses/cs121/files/ProblemSets/ps3revised.ps">Problem Set 3</a>: 
      Non-regular languages, Pumping theorems, Automata minimization.
  <i>Distributed:</i> Tuesday, October 8.  <i>Revised:</i> Thursday,
October 10.
  <ul><li><!WA30><a href="http://www.deas.harvard.edu/cs/academics/courses/cs121/files/ProblemSets/soln3.ps">Solutions</a></ul>
<li><!WA31><a href="http://www.deas.harvard.edu/cs/academics/courses/cs121/files/ProblemSets/ps4.ps">Problem Set 4</a>: 
      Context free grammars, Pushdown automata.<br>
  <i>Distributed:</i> Tuesday, October 22.
  <ul><li><!WA32><a href="http://www.deas.harvard.edu/cs/academics/courses/cs121/files/ProblemSets/soln4.ps">Solutions</a></ul>
<li><!WA33><a href="http://www.deas.harvard.edu/cs/academics/courses/cs121/files/ProblemSets/ps5.ps">Problem Set 5</a>: 
      Closure Properties, Pumping Theorem, DPDAs, Parsing.<br>
  <i>Distributed:</i> Tuesday, October 29.
  <ul><li><!WA34><a href="http://www.deas.harvard.edu/cs/academics/courses/cs121/files/ProblemSets/soln5.ps">Solutions</a></ul>
<li><!WA35><a href="http://www.deas.harvard.edu/cs/academics/courses/cs121/files/ProblemSets/ps6.ps">Problem Set 6</a>: 
      Top down parsing, intro to Turing Machines.<br>
  <i>Distributed:</i> Tuesday, November 5.
  <ul><li><!WA36><a href="http://www.deas.harvard.edu/cs/academics/courses/cs121/files/ProblemSets/soln6.ps">Solutions</a></ul>
</ul>

<!WA37><a name="errata" href="#errata"><h2>Errata in text:</h2></a>
Please send any errors that you find in the text, and any proposed fixes to
the errors to 
<i><!WA38><A HREF=mailto:[e-mail]>[e-mail]</A></i>.
 <P>
The official fixes for the text are archived 
<!WA39><a href="http://www.deas.harvard.edu/cs/academics/courses/cs121/files/errata.ps">here</a>.
 <P>
<address>[e-mail]</address>