CPSC 120: Principles of Computer Science


   Department of Mathematics and Computer Science
   Hobart and William Smith Colleges

   Spring, 2002.

   Instructor:  David J. Eck  (eck@hws.edu)

   Monday, Wednesday, 9:05 -- 10:00.
   Room Lansing 300.
   
   Friday, 9:05 -- 10:00.
   Room Gulick 208.

   Course Handout:  http://math.hws.edu/eck/courses/cpsc120_s02.html

Information

Lab Worksheets

Labs and assignments for CS 120, and possibly other information about the
course, will be posted on this page as the course is taught
during the Spring term of 2002.

End of Term and Final Exam

Monday, April 29 is the last day of class. The final exam will take place on the following Monday, May 6, at 7:00. An information sheet is available with full information about the final and about my office hours during this period.

Enjoy the summer!

Fourteenth Week: April 22, 24, and 26

The final topic for the course is Artificial Intelligence. This will be less technical and more philosophical than other sections of the course. The reading consists of a handout, "Computing Machinery and Intelligence" by Alan Turing, together with Chapter 12 of the text. You should read the handout before class on Monday so that we will be able to discuss it in class. Read Chapter 12 before Wednesday's class. Some of the ideas that you should be familiar with include: 

     The Turning Test, called the "Imitation Game" in the handout
     Some of the "Contrary Views" from the handout, and Turing's responses:
        The Theological Objection, The Mathematical Objection, 
        The Argument from Consciousness, Lady Lovelace's Objection,
        The Argument from Informality of Behavior
     Symbolic Artificial Intelligence:
        Physical Symbol System Hypothesis
        Problem solving
        Heuristics
        Microworlds
        Natural-language processing
        Machine Translation
        Expert systems
        Knowledge representation
     Philosophical issues in AI:
        Godel's Theorem and the limits of logic (Turing's Mathematical Objection)
        Searl's Chinese Room argument
        The problem of consciousness and the danger of solipsism
     New approaches to Artificial Intelligence and Artificial Life:
        Neural nets
        Genetic algorithm

Thirteenth Week: April 15, 17, and 19

There is a test this week on Wednesday, April 17. An information sheet is available.

The reading for the week is the remainder of Chapter 11, dealing with three-dimensional graphics and realistic images. However, this material is not on the test. The lab on Friday will cover three-dimensional images and animations in xModels. Some important ideas from the reading include:

         rotation about an axis in three dimensions
         scaling and translation in three dimensions
         projection of a three-dimensional image onto a two-dimensional surface
         wireframe model
         attributes
         specular reflection and diffuse reflection
         texture mapping
         lighting and light sources
         ambient light
         hidden surface removal
         high quality graphics: ray tracing and radiosity

Twelfth Week: April 8, 10, and 12

The reading for the week is Chapter 11, through the end of Subsection 11.1.2. We will spend Monday finishing up some loose ends from Chapter 7 and Web site programming before moving onto Chapter 11 on Wednesday. The lab this week will be about two-dimensional computer graphics. The reading is about the geometrical side of computer graphics. Here are some of the things you should learn about in the reading:

          computer graphics
          painting programs
          drawing programs
          geometric modeling
          rendering
          hierarchical models (building complex scenes from simple shapes)
          polygons
          geometric transformations
          translation
          scaling
          rotation
          scaling and rotation about a point other than the origin
          computer animation

Remember that there is a test coming up on Wednesday of next week, April 17.

Eleventh Week: April 1, 3, and 5

The reading for the week is the lab handout for Lab 10. This lab introduces another programming language, PHP, which is used to program interactive Web sites. You should read the handout early and plan in advance what you will do in the lab on Friday.

On Monday, I will finish up Chapter 7 and look at BNF (which was introduced in Chapter 6) as an example of recursion. On Wednesday, we will talk about PHP. There is no new reading from the textbook this week.

Tenth Week: March 25, 27, and 29

This week, we will be working on Chapter 7 (Subroutines and Recursion). You should not worry about the "gritty details" in Section 7.1.2. Here are the ideas that you should be familiar with:

         defining subroutines
         SUB ... END SUB
         dummy parameter
         actual parameter
         modules
         interface and implementation
         software life cycle
         top-down design
         bottom-up design
         recursion
         recrusive subroutines
         drawing recursive pictures
         implementing subroutines
         activation record
         stack (of activation records)

Ninth Week: March 18, 20, and 22

There is a test on Wednesday of this week.

For this week's reading, you should finish Chapter 6. Note, however, that Section 6.3 is not part of the material that you should know for the test. New terms and ideas in Section 6.3 include:

          precondition
          postcondition
          processes and states
          3N+1 problem
          software engineering (see p. 174)

Eighth Week: March 4, 6, and 8

On Monday, we will discuss the video that was shown on Friday. We will also discuss Section 5.3, which is about computers and society. The new reading for the Week is Chapter 6, Sections 6.1 and 6.2, and the lab on Friday will be on the material from Chapter 6.

Next week is Spring break. There is a test coming up on March 20, the Wednesday after Spring break. It will cover Chapter 4, Chapter 5, Sections 1 and 2 of Chapter 6, and material from 6, and 7 and from the "Giant Brains" video.

Important terms and ideas from Sections 6.1 and 6.2:

         programming            declaring variables
         syntax                 assignment statement
         semantics              input/output
         variables              control structure
         subroutines            loops and branches
         parameters             BNF (Backus-Naur Form)
         turtle graphics
         
         from the xTurtle programming language:
            DECLARE, LOOP, EXIT, and IF statements
            the assignment operator, :=
            expressions such as  x*(x+1)  and  sqrt(distance)
            forward, turn, back, face, moveTo,
            PenUp, PenDown, TellUser, AskUser

Seventh Week: February 25 and 27; March 1

There is no lab this week.
We will meet in our regular classroom
to view the video, "Giant Brains"

The reading for this week is Chapter 5, but I will spend most of Monday talking about the Halting Problem (Section 4.3). I do not plan to lecture on Section 5.1, but you should read it. The lecture on Wednesday will cover Section 5.2, and I hope to have some class discussion on Wednesday or Monday about the issues raised in Section 5.3. The video that you will see on Friday will cover some of the same history that appears in Section 5.1. On the next test, there might be questions about the video (hopefully ones that you can answer after one attentive viewing).

Your report for Lab 6 is supposed to be due on Wednesday. However, you can turn it in on Friday if you prefer, with no penalty.

Important terms, ideas, events, and people in Chapter 5 include:

         Charles Babbage
         Analytical Engine
         Ada Lovelace
         Jacquard Loom
         Computers in World War II
         Enigma Machine, codes, and code-breaking
         Eckert and Mauchly
         ENIAC
         von Neumann machine
         General-purpose, electronic, stored-program computers
         Integrated circuit
         Microprocessor
         Operating system
         Memory-mapped I/O
         Interrupts
         Interrupt handlers
         Bus
         Device driver
         Configuration of a computer at start-up
         Information Age
         Cyberspace
         De-skilling
         Computer privacy issues
         Computer databases

Sixth Week: February 18, 20, and 22

You should read Chapter 4. We will finish this chapter this week, and the lab on Friday will be about Turing Machines, which are covered in Section 4.2.

Note that my solutions to the first test are available on line.

Here are some important terms and ideas from Chapter 4:

         computational universality
         eqivalence of different kinds of computers
         simulation of one computer by another
         the Church-Turing thesis
         Turing machines
         tape, cells, states, and symbols of a Turing machine
         how a Turing machine computes
         describing a Turing machine with a table of rules
         universal Turing machine
         code number of a Turing machine
         unsolvable problems
         the Halting problem
         philosophical implications of all this

Fifth Week: February 11, 13, and 15

The first test of the term will be in class on Wednesday, February 13. It will cover all the material that we have done in the first four labs and from Chapters 1, 2, and 3 of the textbook. (For more information, see the information sheet.)

We will begin Chapter 4 on Monday, after reviewing for the test. We will continue with this chapter next week, and you will probably want to put off reading it until after the test. The lab this week will be a continuation of Web page design, which you started in Lab 1. This lab will be independent of the textbook.

Because of the test on Wednesday, you can turn in your lab report for Lab 4 on Friday.

Fourth Week: February 4, 6, and 8

This week, we will complete our exploration of the question, "How can a machine be made to follow instructions and execute programs?" by looking at a complete simulated model computer, xComputer. This model computer is covered in Chapter 3 of the textbook. I encourage you to read the whole chapter, but you are not responsible for the following material:

You will find a reasonable outline of a lot of the material that you do need to know in xComputer Lab 1. (This is the lab that you will be working on this Friday.)

Here are some of the terms and ideas that you need to know:

         clock (that makes a computer run)
         Control Circuit
         RAM (random access memory)
         location in RAM
         address of a location in RAM
         specific registers in xComputer:  ADDR, IR, PC, COUNT, AC
         fetch-and-execute cycle
         control wires
         how the clock and Count Register drive the steps of the
              fetch-and-execute cycle
         how the Control circuit works
         specific assembly language instructions:
              ADD, ADD-C, SUB, SUB-C, LOD, LOD-C, STO, INC, DEC, JMP, JMZ, JMN, HLT
         assembly language and its relationship to machine language
         labels in an assembly language program

There is a test next week, on Wednesday, February 13.

Third Week: January 28 and 30; February 1

The reading for this week is Chapter 2, Sections 2 and 3. However, you are not responsible for the internal details of the half-adder, full-adder, subtraction circuit, ALU, or one-bit memory circuit. You should know what these circuits do. You do not need to understand subtraction, as discussed in Subsection 2.2.3 or multiplication and division, as discussed in Subsection 2.2.4.

Here are some things you should know:

          Using circuits to compute with binary numbers
          Addition of binary numbers
          One-bit (or "full") adder circuit: two inputs, Carry-in, Sum, and Carry-out
          Building a multi-bit adder from several one-bit adders
          ALU (arithmetic-logic unit)
          Control wire
          Feedback loop
          Memory circuit
          One-bit memory: Data-in, Data-out, and Load-data wires
          Register

Second Week: January 21, 23, and 25

You should finish reading Chapter 1, and you should read Section 1 of Chapter 2. You are not responsible for memorizing the rules of Boolean algebra from Subsection 2.1.4. When you read a chapter from the textbook, you should also read the questions at the end of the chapter and look at the answers at the back of the book (starting on page 375).

Important terms and ideas from the reading include:

         Central Processing Unit        Main Memory
         program                        fetch-and-execute cycle
         machine language               high-level language
         transistor                     logic gates
         AND, OR, and NOT               propositional logic
         logic formulas                 logic circuits
         relating formulas to circuits
         building a circuit from an Input/Output table
         Boolean algebra

First Week: January 16 and 18

The reading for this week is Chapter 1, Sections 1 and 2, of the textbook. You should also make sure to read the course handout. Your written homework for the week is the lab report for the first lab. This is due in class next Wednesday, January 23.

Remember that every Friday, we will meet in the computer lab in Gulick 208. Lab worksheets will generally be posted and linked to this page in advance of the lab, so you will have time to read through the worksheet before coming to class. You should do this if you want to use your time in class effectively.

Here is a list of some of the important terms and ideas from Sections 1 and 2 of Chapter 1. You should make sure that you are familiar with these terms, and you should ask questions about the ones you don't understand:

         complexity                   structured complexity
         computation                  computer program
         symbols                      CPU
         mechanical manipulation      computer memory
         bit                          transistor
         binary (base-two) numbers
         counting in binary
         ASCII code
         byte
         pixel
         digitization