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 C251 Course Description

S251 -- Foundations of Digital Computing (3 cr)

Contents

General Information

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

Instructors

Steven D. Johnson, Associate Professor
sjohnson@cs.indiana.edu
Office hours: Tue. and Thu. 2:30-3:30pm in Lindley 330F, or by arrangement
Jim Newkirk, Associate Instructor
jnewkir@cs.indiana.edu
Office hours: Wed. 1:00-3:00pm (tentative) in Lindley 330I, or by arrangement

Meetings

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

Prerequisites

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.

Textbook

We will use the textbook Logic and Discrete Mathematics 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.

Course Description

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.

Computation takes place in a discrete digital domain where all phenomena ultimately reduce to binary 1s and 0s. To explore this universe we need different mathematical tools than are used by physicists and chemists. We use induction 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.

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.

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.

Syllabus and supplementary material

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 evolving syallabus, which will grow as the course develops. Check it weekly for new additions to the supplementary material.

Homework assignments

In studying the textbook material, you should work enough exercises and problems in the text to ensure that you understand the material. Since many of the discussions in class will derive from these exercises, we should be certain that at least one individual has worked through every one of them, so every problem has assigned to it one or two students who are expected to be able to present the problem at a class meeting. These assignments are maintained in the s251 newsgroup. Most homeworks will not be graded for credit; the purpose of these assignments is to guide participants in preparing for the presentation of material in the class, and to show the kinds of problems that will be asked on examinations. Challenges are homework assignments that are offered for credit. These will be clearly indicated when posted.

In this course, you are welcome to discuss assignments, presentations, and challenges with other students. Do not assume this is true in all your courses! Teamwork in doing assignments is good as long as each member of the team contributes, and fully understands the assignment. If you are working with a group, please indicate it on your homework papers. If someone has given you a lot of help, acknowledge them; you will not be penalized and they will get the thanks they deserve.

Grading and gradebooks

The gradebook will be posted on this home page and updated regularly. The listing of evaluation criteria shown below is tentative. For this honors class I would like to place greater emphasis on interation and participation than on formal examinations and assignments. However, the form of participation is something I would like to discuss at the first meeting of the class. Also, since I am required to enter a grade for each participant at the end of the semester, some objective performance comparison will be necessary.