Computer Science 171 Introduction to Computer Programming

Dr. Stephen Bloch office 112 Alumnæ Hall phone 877-4483

                    email sbloch@adelphi.edu
            Web page http://www.adelphi.edu/sbloch/
     Class Web page http://www.adelphi.edu/sbloch/class/171/

office hours TBA

August 31, 1999

1 Subject Matter — Overview

Computers do many of the same things people do, only faster, more accurately, and without getting bored. Accordingly, the task of programming a computer is essentially the task of figuring out exactly how you would solve a particular problem, and then explaining it to the computer. Unfortunately, computers are literal-minded and completely devoid of intuition, so your explanation must be much more precise and unambiguous than if you were explaining things to a human being. This course, therefore, is about how to analyze a problem, figure out precisely and unambiguously how to solve it, and present this explanation to a computer.

2 Who Should Take This Course

If you’re a computer science major, you must take this course as early as possible, preferably in your first semester at Adelphi. If you’re a computer science minor, you must take this course in your first two years at Adelphi. If you’re majoring in mathematics, pre-engineering, or perhaps some other fields, you must take this course at some point. If you’re curious about how computers work, what programming is like, and how programmers think, this is a good course to take. If you have no interest in writing significant programs of your own, but simply want to use Web browsers and search engines, spreadsheets, databases, word processors, etc. and perhaps write your own Web pages, you should take CSC 170 instead.

3 Prerequisites

This course has no prerequisites. Students are not expected to know how to program, use, or even turn on a computer. However, students who have done some programming in a different language may still benefit from the course; consult the professor.

4 Subject Matter — More Details

4.1 “Good” Programs

What distinguises a “good program” from a “bad program”? Obviously, a good program has to work correctly and reliably — a difficult goal in itself, as we’ll see. But this is far from enough. In practice, very few programs are written once, used for a while, and discarded: much more often, a program is used until the need for it changes, the program is modified to handle the new requirements, the modified program is used for a while, and the cycle repeats. Thus a “good program” must be not only correct the first time around, but structured in such a way that it can easily be modified to accomodate likely changes in requirements. The implications of this fact will follow you throughout your years as a computer science student and your career as a computer professional; we’ll only scratch the surface this semester.

4.2 Kinds of Knowledge

An introductory programming course is in some sense an almost impossible task. In one semester, you’ll be asked to learn several different kinds of knowledge:

1. How to use the computers and the software on them

2. The grammar, punctuation, and vocabulary of a programming language

3. How to analyze a problem and design a program to solve it, so that the program is both correct and easy to write, read, modify, and repair

4. How to plan your time, and what sequence of steps to go through, in designing, writing, testing and debugging a program

5. Application-specific knowledge (e.g. to write a program that draws geometric shapes on the screen, you have to know something about geometry.)

It is easy for a student (or a professor or a textbook author, for that matter) to get caught up in the details of the first two at the expense of the rest. I urge you not to fall into this trap, because the specific kinds of computers and software, and to some extent the language, you learn this semester will almost certainly be obsolete by the time you leave Adelphi. The much more interesting and lasting knowledge is at levels 3, 4, and 5 (and I’ll try to minimize the time we spend on level 5 because it’s not specific to computer science). In short, although all five kinds of knowledge are necessary in order to write a good program, I’ll try to concentrate on levels 3 and 4.

4.3 Language and design recipes

Last year, I taught this course in the Java programming language, and found that we spent far too much of our time on level-1 and level-2 knowledge, with not enough time left for levels 3 and 4. So this year we’re going to start in the Scheme language, which has simpler rules of grammar, punctuation, and vocabulary and is easier to use. Once we’ve mastered many of the fundamental concepts and techniques of programming, we’ll switch to Java for the second semester. Other teachers doing this have found that students switching from Scheme to another language soon write better in that other language than do those who started in it.

We’ll pay a lot of attention to design patterns, which are step-by-step “recipes” for getting from a vague English-language description of a problem to a working computer program. Last year’s students tended to skip the recipes when they were in a hurry, and invariably found themselves wasting more time as a result. To prevent this, you will be graded on, among other things, how well and thoroughly you use the recipes.

4.4 Knowing your Tools

If you wanted to learn carpentry, you would start by studying the characteristics and capabilities of each of the common tools carpenters use, so you use the right tool at the right time for things that it does well. In programming, although you have editors, compilers, etc. to help, your main tool is your mind; accordingly, it makes sense to study the characteristics and capabilities of your mind. Indeed, it can be studied and measured just as scientifically as a bouncing ball in Physics class. By the end of the semester, you should have a much better idea (backed up with hard numbers) of how you work as a programmer, and hence the ability to accurately estimate how long you will need to complete a specified programming task. This allows you to plan ahead and complete assignments on time — an invaluable skill for a professional programmer!

5 Texts

I’m using two different textbooks for this course. For levels 1, 2, 3, and part of 4, we’ll use How to Design Programs, by Felleisen, Findler, Flatt, and Krishnamurthi (who also wrote the programming platform we’ll use, DrScheme). This book is due to be printed “any day now” by MIT Press, but it’s already available on the Web at

http://www.cs.rice.edu/CS/PLT/Teaching/Lectures/Released/curriculum/. Some of

the later chapters are still being written, but they should be complete by the time we get to them.

For more level-4 knowledge, we’ll use Introduction to the Personal Software Process, by Watts Humphrey (Addison-Wesley 1997, ISBN 0-201-54809-7). This book discusses how to keep track of problems you encounter in programming, so as to prevent them in the future, and how to manage your time so as to finish programming assignments before they’re due. (The easiest way to fail my class is to fail to turn in homework assignments!)

You’ll need to read an average of about 50 pages a week. You are responsible for everything in the reading assignments, whether or not I discuss it in a lecture. You are also responsible for checking my class Web page at least once a week or so; I often post assignments, corrections to assignments, solutions to assignments, etc. there.

6 Grading

I expect to give approximately ten programming assignments — roughly one a week, due the following week. Most assignments are to be turned in by email, and will be considered late if the time stamp on the email is after midnight on the assigned due date. Assignments turned in up to a day late lose 30% credit; those up to two days late lose 60% credit; and beyond that, they’ll lose 90% credit (i.e. the best grade you can hope for is 10%.)

We’ll also have a two-hour final exam on December 16 or 20 (depending on which section you’re in), weighted the same as a programming assignment: that is, if there are 9 programming assignments, each of them will be worth 10% of your semester grade, and the final exam will also be worth 10%. The final exam must be taken at the scheduled time, unless arranged in advance or prevented by a documented medical or family emergency. If you have three or more exams scheduled on the same date, or a religious holiday that conflicts with an exam or assignment due date, please notify me in writing within the first two weeks of the semester in order to receive due consideration. Exams not taken without one of the above excuses will be recorded with a grade of 0.

7 Ethics

Most homework assignments in this course involve writing, testing, and debugging a program. For most of these assignments, you are to work in teams of two students (switching teams from one assignment to the next); for other assignments, I may ask you to work individually.

It’s hard to define what constitutes “cheating” in this sort of course. Students are encouraged to help one another with level-1 and level-2 difficulties (“how do I save this file?”, “what’s the syntax for define-struct?”, etc.), regardless of whether they’re on the same team, but designing, coding, testing, and debugging should be done by team members. It’s remarkably easy for a professor to notice when three different teams have turned in nearlyidentical programs; if that happens, I’ll grade it once and divide the credit among the three, so the best any of them can hope for is 33%.

All work on the final exam must be entirely the work of the one person whose name is at the top of the page. If I have evidence that one student copied from another on an exam, both students will be penalized; see above.

8 Schedule

Section 1 of this class meets every Tuesday and Thursday from 1:40 to 2:55 PM in Science 227; the final exam is Thursday, Dec. 16, from 1:00–3:00 PM.

Section 2 meets every Monday and Wednesday from 2:25 to 3:40 PM in Science 227; the final exam is Monday, Dec. 20, from 3:30–5:30 PM. Section 3 meets every Tuesday and Thursday from 9:25 to 10:40 AM in Science 227; the final exam is Thursday, Dec. 16, from 10:30 AM–12:30 PM.

All dates in the following schedule are tentative, except those fixed by the University; if some topic listed here as taking one lecture in fact takes two lectures to cover adequately, or vice versa, the schedule will shift.

In the column marked “Reading”, the letters “HtDP” precede section numbers in How to Design Programs, while the letters “PSP” precede section numbers in the Humphrey textbook on the Personal Software Process.

I expect you to have read the reading assignments (usually about 25 pages per lecture) before the lecture that deals with that topic. This way I can concentrate my time on answering questions and clarifying subtle or difficult points in the textbook, rather than on reading the textbook to you, which will bore both of us. Please read ahead!

When I say “read” above, I mean an active process, involving not only the textbook but pencil, scratch paper, and a notebook for writing down key points. Finally, and perhaps most importantly, you’ll need a computer for trying out the new ideas you find in your reading. Just as you cannot learn about cooking or driving a car just by reading about it, you cannot learn about programming just by reading about it. In short, every time you read about a new programming idea, try it! The How to Design Programs textbook contains lots of exercises, which you are encouraged to do as you come to them in the text, whether assigned as homework or not.

8.1 Schedule for Sections 1 and 3

Date(s) Assignment  Reading  Lecture Subject

2 Sept HW1 Administrivia, survey, accounts, passwords,

email, Web, using the lab

7 Sept HW1 due HtDP through 2.2, Using DrScheme & stepper; arithmetic expressions,

PSP 1 data types, variables, defining functions

9 Sept HW2 HtDP 2.3–2.7, Errors and debugging; design recipe;

PSP 11.1–11.3 pair programming; program development cycle

13 Sept Deadline to add classes 14 Sept HtDP 3, PSP 12 Conditionals, defect tracking and removal 16 Sept HW2 due; HW3 HtDP 4, PSP 13 Symbols and code review 21 Sept HtDP 5 Compound data and design recipes for them;

iterative refinement

23 Sept HW3 due; HW4 PSP 14 Code review checklists 24 Sept Deadline to drop classes 28 Sept HtDP 6–I1 Mixed data, design recipes for them 30 Sept HW4 due; HW5 HtDP 8 Lists and design recipes for them 5 Oct HtDP 9, PSP 2 List processing; time management 7 Oct HW5 due; HW6 HtDP 10 Natural numbers and recursion on them 12 Oct HtDP 11–I2, PSP 3 Examples; time tracking 14 Oct HW6 due; HW7 HtDP 13 More recursive data structures 19 Oct I’m at a conference; sub or no class

21 Oct  HtDP 14  More recursive data structures
26 Oct  HtDP 15–16  Iterative refinement and multiple complex data

28 Oct HW7 due; HW8 HtDP I3, PSP 5 Code estimation 2 Nov HtDP 18 Abstracting designs 4 Nov HtDP 19, I4, PSP 6 Programs as data 5 Nov Deadline to withdraw from classes 9 Nov HtDP 20–21 Using abstractions 11 Nov HW8 due; HW9 HtDP 23–24 Generative recursion

pp. 16 Nov  HtDP 25  More on recursion
18 Nov  HtDP 27–28  Accumulative recursion

23 Nov HW9 due; HW10 HtDP 29–31 More on accumulators 25 Nov Thanksgiving break — no classes 30 Nov HW10 due; HW11 HtDP 32 History and State 2 Dec HtDP 33 Modifying compound data 7 Dec Catch up and review 9 Dec HW11 due Catch up and review for final exam 16 Dec 10:30 AM – 12:30 PM, final exam for section 3 16 Dec 1:00 – 3:00 PM, final exam for section 1

8.2 Schedule for Section 2

Date(s) Assignment  Reading  Lecture Subject

1 Sept HW1 Administrivia, survey, accounts, passwords,

email, Web, using the lab

6 Sept Labor Day — no classes 8 Sept HW1 due HtDP Preface–2.2, Using DrScheme & stepper; arithmetic expressions,

PSP 1 data types, variables, defining functions

13 Sept Deadline to add classes

HW2 HtDP 2.3–2.7, Errors and debugging; design recipe;

PSP 11.1–11.3 pair programming; program development cycle

15 Sept HtDP 3, PSP 12 Conditionals, defect tracking and removal 20 Sept Yom Kippur — no classes 22 Sept HW2 due; HW3 HtDP 4, PSP 13 Symbols and code review 24 Sept Deadline to drop classes 27 Sept HtDP 5 Compound data and design recipes for them;

iterative refinement

29 Sept HW3 due; HW4 PSP 14 Code review checklists 4 Oct HtDP 6–I1 Mixed data, design recipes for them 6 Oct HW4 due; HW5 HtDP 8 Lists and design recipes for them 11 Oct HtDP 9, PSP 2 List processing; time management 13 Oct HW5 due; HW6 HtDP 10 Natural numbers and recursion on them 18 Oct I’m at a conference; sub or no class 20 Oct HtDP 11–I2, PSP 3 Examples; time tracking 25 Oct HW6 due; HW7 HtDP 13 More recursive data structures

27 Oct  HtDP 14  More recursive data structures
1 Nov  HtDP 15–16  Iterative refinement and multiple complex data
3 Nov HW8  HtDP I3, PSP 5  Code estimation

5 Nov Deadline to withdraw from classes 8 Nov HW7 due HtDP 18 Abstracting designs 10 Nov HtDP 19, I4, PSP 6 Programs as data 15 Nov HtDP 20–21 Using abstractions 17 Nov HW8 due; HW9 HtDP 23–24 Generative recursion

22 Nov  HtDP 25  More on recursion
24 Nov  HtDP 27–28  Accumulative recursion

29 Nov HW9 due; HW10 HtDP 29–31 More on accumulators

1 Dec  HtDP 32  History and State
6 Dec  HtDP 33  Modifying compound data

8 Dec Catch up and review 13 Dec HW10 due Catch up and review for final exam 20 Dec 3:30 – 5:30 PM, final exam for section 2