http:^^www.cs.indiana.edu^classes^s251^home.html

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

Date: Wed, 20 Nov 1996 22:32:35 GMT
Server: Apache/1.0.3
Content-type: text/html
Content-length: 15327
Last-modified: Fri, 03 May 1996 19:28:53 GMT

<TITLE>C251 Course Description</TITLE>

<H2>S251 -- Foundations of Digital Computing (3 cr)</H2>

<IMAGE ALIGN=top SRC="img/new_tiny.gif">

<UL>
<LI> <!WA0><a href="http://www.cs.indiana.edu/classes/s251/grades/grades.txt"> <b> Grades </b> </a> have been posted.
<LI> <!WA1><a href="http://www.cs.indiana.edu/classes/s251/exam/e2a.txt"> Solutions </a>
     to the questions on the final examination have been posted.
</UL>

<H3>Contents</H3>
<UL>
<LI> <!WA2><A HREF="http://www.cs.indiana.edu/classes/s251/img/students.html"><B> Directory </B> of current S251 students</A>
<LI> <!WA3><A HREF="#general">General information</A>
<LI> <!WA4><A HREF="#textbook">Textbook</A>
<LI> <!WA5><A HREF="#description">Course description</A>
<LI> <!WA6><A HREF="#syllabus">Syllabus and supplementary material</A>
     <UL>
     <LI> <!WA7><A Href="#problemassignments"> Problem presentations
     <LI> <!WA8><A Href="#homework"> Homework
     </UL>
<LI> <!WA9><A HREF="#grading">Grading and gradebooks</A>
<LI> <!WA10><A HREF="#communication">Communication</A>
<LI> <!WA11><A HREF="#evaluation">Course evaluations</A>
<LI> <!WA12><A HREF="#policies">Policies</A>
</UL>
<A NAME="general"><H3>General Information</H3></A>

This is CSCI S251, Section 2126, Second Semester 1995-96.

<H3> Instructors </H3>

<table>
<td rowspan=3>
 <!WA13><A HREF="http://www.cs.indiana.edu/usr/local/www/foto/sjohnson.gif">
 <IMAGE
  ALIGN=top
  SRC="http://www.cs.indiana.edu/picons/db/users/edu/indiana/sjohnson/face.gif"
  photo</image></A>
<td>
 <!WA14><A HREF="http://www.cs.indiana.edu/hyplan/sjohnson.html">
 <B> Steven D. Johnson</B></A>, Associate Professor 
<tr>
<td>
 <!WA15><A HREF="mailto:[e-mail]"><EM>
    [e-mail]</EM></A>
<tr>
<td> Office hours:
     Tue. and Thu. 2:30-3:30pm in Lindley 330F, or by arrangement
<tr>
<td rowspan=3>
 <IMAGE ALIGN=top SRC="img/Newkirk.little.gif" </image>
<td>
 <!WA16><A HREF="http://www.cs.indiana.edu/hyplan/jnewkir.html">
 <B>Jim Newkirk</B></A>, Associate Instructor
<tr>
<td> <!WA17><A HREF="mailto:[e-mail]"><EM>[e-mail]</EM></A>
<tr>
<td> Office hours:
     Wed. 1:00-3:00pm (tentative) in Lindley 330I, or by arrangement
</table>

<H3> Meetings </H3>

<DL PACKED>
<DT> Lectures: TR 1:00-2:15pm in Balentine Hall, Room 335 (BH335).
<DT> Demonstrations: Lindley Hall, Room 115 (LH115) during lecture periods,
     as announced.
<DT> Discussion: W 7:15-9:15pm in Lindley Hall, Room 102 (LH102).
     <em> No regular meetings. </em>
     This time is scheduled for reviews, examinations, and possible
     discussions.
</DL>

<H3>Prerequisites</H3>
C211, M215, and as a prerequisite or corequisite C212.
This is the "honors" version of C251 and participants must be enrolled as
Honors Division  students.  It is assumed that you have taken C211 here
at Indiana, and so are familiar with the Scheme programming language.
The particular skills needed are the ability to program in a symbolic
programming language and the experience of programming with recursion.

<A NAME="textbook"><H3>Textbook</H3></A>

We will use the textbook <I>Logic and Discrete Mathematics</I> by
Winfried Karl Grassmann and Jean-Paul Tremblay (Prentice-Hall, 1996).
At this time the text book is on order; it has not arrived at the book stores
yet.

<A NAME="description"><H3>Course Description</H3></A>

The mathematical foundations of computer science differ somewhat from
from those of the physical and social sciences.  The study of computation
has two main branches, performance and meaning.  In formalizing
performance we focus on combinatorics and statistics, whose foundations
are included in "traditional" mathemematics.  In formalizing meaning
we draw more heavily on logic, both as a way to express ideas about programs
and as a discipline for describing what computers are and what they do.

<P>
Computation takes place in a discrete <em> digital </em> domain where all
phenomena ultimately reduce to binary <b>1</b>s and <b>0</b>s.
To explore this universe we need different mathematical tools than are
used by physicists and chemists.  We use <em> induction </em> far more
often than differentiation or integration, for example, and will see
numerous styles of inductive reasoning in this course.  We will also
explore discrete mathematical structures, trees and other graphs, that
are prevalent in computing.

<P>
The main goal of the course is to improve each participant's ability
to conduct a rigorous mathematical argument, that is, to do proofs.
One reason (not the only one) we look at logic in this course is for the
purpose of evaluating proof narratives.  A central idea of this course
is that "doing a proof" and "programming" are pretty much the same activities.
The better you are at proving, the better programmer you will be.
More important, the better computer scientist you will become.

<P>
I plan to follow the text book, except for Chapters 4 (Prolog),
8 (Specification in Z), and 12 (Relational Database Systems).  I may
have to skip more chapters, depending on our progress through the material.
I may also introduce some topics from later chapters as we go along.
There are a few topics not in the text that we may look at, again, if there
is time.  In any event, I will cover all the material of a core 251 course.

<A NAME="syllabus"><H3>Syllabus and supplementary material </H3></A>

One or two weeks will be devoted to each of the chapters listed below.
Supplementary material is (or will be) included below the chapter listing in
some cases. This is an <EM>evolving syallabus</EM>, which will grow as
the course develops.  Check it weekly for new additions to the supplementary
material.

<UL>
<LI> Chapter 1: Propositional Logic (2 weeks)
 <UL>
 <LI> <!WA18><A HREF="http://www.cs.indiana.edu/classes/s251/hw/probs.ch1.txt"><B>problem assignments</B></A>
 <LI> <!WA19><A HREF="http://www.cs.indiana.edu/classes/s251/pgm/tt.ss">pgm/tt.ss</A>, a truth table generator in Scheme.
 <LI> <!WA20><A HREF="http://www.cs.indiana.edu/classes/s251/pgm/sets.ss">pgm/sets.ss</A>, set operations in Scheme.
 <LI> <!WA21><A HREF="http://www.cs.indiana.edu/classes/s251/pgm/dnf.ss">pgm/dnf.ss</A>, a DNF generator
 <LI> Notes from meetings:
      <UL>
      <LI> <!WA22><A HREF="http://www.cs.indiana.edu/classes/s251/lec/1">1st</A> January 9
      <LI> <!WA23><A HREF="http://www.cs.indiana.edu/classes/s251/lec/2">2nd</A> January 11
      <LI> <!WA24><A HREF="http://www.cs.indiana.edu/classes/s251/lec/3">3rd</A> January 16
      <LI> <!WA25><A HREF="http://www.cs.indiana.edu/classes/s251/lec/4">4th</A> January 18
      <LI> <!WA26><A HREF="http://www.cs.indiana.edu/classes/s251/lec/5">5th</A> January 23
      <LI> <!WA27><A HREF="http://www.cs.indiana.edu/classes/s251/lec/6">6th</A> January 25
      </UL>
 <LI> <!WA28><A HREF="http://www.cs.indiana.edu/classes/s251/suppl/parse-1.ps"> Parsing Example (ps)</a>:
 <LI> <!WA29><A href="http://www.cs.indiana.edu/classes/s251/suppl/PFdiagrams.ps"> Proof Diagrams (ps)</A>
 </UL>
<LI> Chapter 2 (and maybe 11): Predicate Calculus (2 weeks)
 <UL>
 <LI> <A NAME="problemassignments">
      <!WA30><A HREF="http://www.cs.indiana.edu/classes/s251/hw/probs.ch2.txt"><B>problem assignments</B></A></A>
 <LI> Notes from meetings:
      <UL>
      <LI> <!WA31><A HREF="http://www.cs.indiana.edu/classes/s251/lec/7">7th</A> January 30
      <LI> <!WA32><A HREF="http://www.cs.indiana.edu/classes/s251/lec/8">8th</A> February 1
      <LI> <!WA33><A HREF="http://www.cs.indiana.edu/classes/s251/lec/9-10">9th and 10th</A> February 6 and 8
      <LI> <!WA34><A HREF="http://www.cs.indiana.edu/classes/s251/lec/11">11th</A> February 12
      <LI> <!WA35><A HREF="http://www.cs.indiana.edu/classes/s251/lec/12">12th</A> February 14
      </UL>
 <LI> <!WA36><A HREF="http://www.cs.indiana.edu/classes/s251/pgm/u.ss">pgm/u.ss</A>, a <em>unification</em> algorithm.
 <LI> <!WA37><a href="http://www.cs.indiana.edu/classes/s251/exam/e1-handout.ps"> Summary sheet </a>, laws of boolean
      algebra, propositional logic, equational logic, and predicate logic.
 </UL>
<LI> Chapter 3:  Induction and Recursion (4 weeks)
  <UL>
  <LI> Skim Sections 3.2 and 3.5
  <LI> Notes from meetings:
      <UL>
      <LI> <!WA38><A HREF="http://www.cs.indiana.edu/classes/s251/lec/13-15"> 13, 14, 15 </a> February 20 through March 5