Date: Tue, 26 Nov 1996 18:41:10 GMT Server: NCSA/1.5.1 Last-modified: Tue, 23 Apr 1996 04:16:24 GMT Content-type: text/html Content-length: 15869 CS 60: Principles of Computer Science URL http://www.cs.hmc.edu/~keller/cs60s96.html (Link to INDEX page).

Harvey Mudd College, Spring 1996

Computer Science 60

Principles of Computer Science

Home Page and Reference Card

Course Personnel

Room 102 Beckman is where the X terminals connected to our machine muddcs are. To find it, leave the back of the lecture hall (Galileo Edwards) turn right, then another right down the long corridor. Proceed to the new section of the building, then turn right. 102 is the second door on the right.

To get to my office, go back to the long corridor and keep going to the end. Go right, then upstairs (you will then be in the Olin building), then go left, then left again, to the southeast corner of Olin. My office is 242, which is inside of 240. 240 is always open during business hours. My door is usually closed to filter out noise, but don't hesitate to knock.

Catalog Description

Introduction to principles of computer science. Algorithms, complexity analysis, data structuring, data and procedural abstraction, grammars, correctness, logic principles, processor organization, operating system concepts, programming languages, basic automata theory, and theoretical limitations.

Course Goals

To learn and apply basic principles of computer science, including software construction, hardware organization, and limitations of computers.

Text

Robert M. Keller, Principles of Computing, January 1996. Available by one-time special order for $29 (cost of reproduction) and it is strongly recommended that you buy a copy. The entire book is also on-line in Microsoft word on KATO, the Mac server, in the folder KATO.HOME/Department Homes/CS/CS 60/. It will be thus viewable from Macs on the local network. I will see about getting a PC version as well. However, it is still recommended that you purchase the book (rather than, say getting someone's old version) because: (1) The book has been revised substantially since the last course offering. (2) The book is large (750 pages), and reading it all on the screen is apt to be tiresome and inconvenient. (3) The book can be taken into the exams, whereas a Mac cannot be.

Course Assumptions

Students should have had a first course in computing at the college level (e.g. CS5). Prior experience in C or C++ is preferred although not essential. Others have made it through starting with just a knowledge of Pascal. You should know about procedures, arrays, and types at a minimum; if you are unfamiliar with these, please take CS5 or CS50 first.

"Lectures"

The word "lecture" below is used very loosely. I expect that the lecture periods will include some explanation, but will be more like a multilogue (set of dialogues). You are expected to attend, ask questions, and provide comments.

Threads

There are essentially three interwoven "threads" in the course: The book, the problems, and the lectures. I try to keep them "in synch" with one another, but active participation in all three threads is required. Volume-wise, the book covers more material than can be discussed in the lecture. The lecture will cover some things not in the book. Staying attune to what is going on in lecture will help you focus on the areas in the book that are important as far as exam emphasis. The problems exercise some, but not all, of the things discussed in the book and lecture.

Resources

The course is planned to be interactive throughout. We are eager to prevent programming difficulties from consuming extraordinary time, so please ask when you get stuck with such difficulties. It is much more efficient to start early on each assignment so that you give yourself enough time to cope with the numerous contingencies which inevitably materialize. You can get help on-line by emailing to cs60help@muddcs which goes to the graders/tutors and to me. I don't enable 'talk' because it is too slow, but I check email often. When you email a message, it will typically be answered to the entire class with parts of your message embedded. If you do not want it to be attributed to you, please so indicate in your message.

By carrying problem solutions through to computer implementation, you are showing that you understand the issues, principles, and techniques. I will explain to you how to work any problem, to any level of detail, if you ask. However, you must do so with a sufficient time margin. Telling me at the eleventh hour that you just aren't getting and therefore want to drop the course is not availing yourself of the substantial help available.

You are also welcome to submit email or a note card with any question you'd like to have answered or any point you would like addressed before or after class, or leave it in my mailbox in 240 Olin. Of course you are encouraged to ask such questions in class as well. There are many tools available on the computer itself. Use the 'man' feature of UNIX to find what you need and to explore. (The command

man command gives information on a specific command; The command man -k topic lists commands relating to a specific topic.) You can also use the 'info' reader in GNU Emacs for certain library, language, and editor specifics. In emacs type escape-X info Helpful information, examples, on-line copies of assignments, etc. will be kept in various subdirectories of the directory /cs/cs60 on machine muddcs. There is a web page for rex documentation. Finally, the "corner store" maxim applies: If you can't find what you want, ask for it.

Grading

There will be approximately eight assignments entailing programming. Programming assignments help drive home key working concepts and principles. After the first couple of assignments, where the rex language (one you have not likely seen) is used, the language used will mostly be C++. C++ is used due to its position as an emergent industry standard and its ability to reflect both low-level computer structure and at the same time provide high-level data and object abstractions. There will may be one assignment in assembly-language programming, using a simulated computer, the ISC. As prior exposure to C++ varies across the class, I will hold one or more special evening sessions for C++ if you so request.

Is this a "Programming Course"?

Although much of the course entails programming, we consider exposure to computer science ideas to be the important part. The intent of the programming assignments is to drive home these key ideas. I am willing to devote as much of each class period as is needed (nominally 15 minutes) to more detailed examples of programming techniques and for specific programming questions and answers. If this does not appear useful on a given day, the time will be used for other purposes.

Honor Code Standard

Read this carefully: Although discussion of problems with others is encouraged, programming in CS60 emphasizes individual learning rather than group projects. We observe the following Standard: "You may discuss the assignment with other students. You may not share (= give or receive) written work of any kind, inside or outside the course". Elaboration: In the case of programming assignments, we consider email, computer files, fragments of files, and printed output to be "written work". In developing code for a programming assignment, you can discuss ideas with others, but discussion of ideas must not involve wholesale examination or transcription of the actual working code of others, with the exception that you may use any code explicitly provided by the instructor. Definitely forbidden is a form of collaboration wherein two or more students split up an assignment, then transcribe each others' contributions, sometimes changing names of variables, comments, formatting, etc. If this occurs, a failing grade is issued automatically. If the help you get from another is significant, you should acknowledge it on your submission. You do not lose credit for this. If you have any doubts about whether a form of interaction constitutes a violation of this standard, please consult with me prior to continuing.

Grading Weights

The programming assignments will constitute 50% of the grade. The mid-term examination will count 15% and the final 25%. Class attendance, participation, random quizzes, etc. will account for the remaining 10%. Various "practice problems" will be indicated. In particular, you should be able to work most ** ("two dot") problem in the notes relating to material covered in lecture. These do not need to be submitted, but the exams will consist largely of problems of a similar level, along with some perhaps a little easier or harder. Exams are open book and emphasize conceptual understanding, rather than memorization of fine details.

Late Assignment Policy

Submissions are done by emailing source code to the grader, cs60grad@muddcs, which also establishes the time of submission. The due dates on assignments should be noted carefully. The work of an assignment should be conducted in the week or weeks before, not on the last day when there is no space for the necessary thinking. There is an automatic, fixed, one-day grace period on all assignments. In other words, if the due date states day N, then the assignment must be turned in before midnight on day N+1 to receive any credit. After midnight on day N+1 work you spend on the problem is for you own edification only (which is not to say that it isn't worth doing or required; you just don't get points for it then). It is best to plan to get the assignments in on the stated due date.

CS 60 Topic Outline

The lectures will roughly follow this outline. The progression is at the rate of about two of the numbered topics below per week. I should say that this is what I would like to do. Depending on background, some of the topics expand to longer than allocated, with the result that other topics get jettisoned or fall off the end. Please keep up on the reading without it being explicitly assigned. The notes generally expand on the lectures and discussions. But the lectures may also expand on the notes or introduce new material. More often than not, several threads will be interwoven in the lectures over a period of time, in part to emphasize the commonality of concepts from different vantage points. Brackets below indicate where chapters in the notes start with respect to the concepts that follow. The outline does not mention every topic. The actual lectures determine points of emphasis.

  1. [Computing by the Rules] Computation problems and models of computation. States and transitions. List notation. Functional specifications. Computation by rewriting.

  2. Heterogeneous lists and trees. Mutual recursion. Anonymous functions.

  3. Assignment-based programs. McCarthy's transformation. Turing machines.

  4. [Computing on Demand] C++ review, the Polya library (translating rex to C++)

  5. RAM model, linear addressing principle, arrays, pointers, L-values and R-values.

  6. [Computing Grammatically] Inductive definitions, grammars, syntax.

  7. Parsing. Evaluation. S expressions.

  8. [Structural Computing] Data structuring. Dynamic storage allocation. Open- vs. Closed-list models

  9. [Computing Objectively] Object-orientation and data abstraction. C++ objects. Inheritance.

  10. [Computing Logically] Proposition logic and applications. Gate realizations. Minterm expansion. Boole/Shannon expansion.

  11. Logic simplification. Hypercubes. Karnaugh maps. "Don't care" situations.

  12. Predicate logic. Programming in logic. Backtracking.

  13. Program specification, correctness, and verification.

  14. Mid-term examination. (Date of Midterm: Wed. Mar. 6, during class period).

  15. [Complexity of computing] Runtime measures. Profiling. Growth-rate comparisons. Upper bounds. "O" notation. Examples from sorting: Heapsort, merge sort, radix sort.

  16. Complexity (continued). Empirical measurements. Set abstraction examples. Bit-vectors, tries.

  17. [Computing graphically] Directed graphs. Graph representations, depth- and breadth-first search.

  18. Weighted graphs. Shortest paths. Traveling salesman problem.

  19. [Finite-State Computing] Finite-state machines. Sequential logic design.

  20. Regular expressions and finite-state machines.

  21. Computer components. Registers, buses, multiplexors, etc.

  22. [Computing with the Store] Stored-program computer structure.

  23. Assembly language.

  24. [Computing physically] Physical bases for computation.

  25. [Computing in Parallel] Parallel computation.

  26. [Limitations of Computing] Finite-state limitations. Lower bounds. Incomputability. Intractability and NP-completeness. The glitch phenomenon.

  27. Comprehensive final exam (Date of Final: Fri. May 10, 2-5 p.m.).

How to email assignments:

Use the following scheme only: elm -saN cs60grad@muddcs.cs.hmc.edu < your-code where N is the assignment number and your-code is a file containing your code. Do not, under any circumstances, mail using PINE. This MIME encodes the file and we can't use it easily.