## 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

Tests and answers: First Test Second Test Third TestInformation sheet for: First Test Second Test Third Test Final Exam- About your Linux account
- Web page from last year's course

## Lab Worksheets

Lab 1, January 18:Data Representation, Linux, and Web PagesLab 2, January 25:Logic Circuits, Part 1. (This lab starts with xLogicCircuits Lab 1: Logic Circuits, but the exercises you have to do are at the end of Logic Circuits, Part 1.)Lab 3, February 1:Logic Circuits, Part 2. (This lab uses xLogicCircuits Lab 2: Memory Circuits.)Lab 4, February 8:The xComputer Model Computer. (This lab uses xComputer Lab 1: Introduction to xComputer.)Lab 5, February 15:More About Web Pages.Lab 6, February 22:Turing Machines. (This lab uses xTuringMachine Lab.)Lab 7, March 8:The lab is xTurtleLab 1. You should only do Exercises 3, 5, 6, 7, 9, and 11 from this lab. You can save the programs in your homework directory, or you can turn in handwritten programs or printouts of programs.Lab 8, March 22:The lab is xTurtleLab 2. You should only do Exercises 1, 5, 6, 9, 10 and 11 from this lab. You can save the programs in your homework directory, or you can turn in handwritten programs or printouts of programs.Lab 9, March 29:The lab is xTurtleLab 3. You should only do Exercises 1, 3, 4, 7, 8, and 9 from this lab. Exercises 3 and 4 should be turned in together asoneprogram.Lab 10, April 5:Introduction to Web Site Programming with PHP.Lab 11, April 12:The lab is xModels Lab 1. Do Exercises 2, 4, 6, 8, and 10 from this lab. The programs for exercises 1, 6, and 10mustbe saved in your homework directory. (Note that you should also do Exercise 1 and use it as a basis for exercise 2.)Lab 12, April 19:The lab is xModels Lab 2. Do Exercises 3, 6, 7, 9, and 10 from this lab. The programs for exercises 3, 6, 7, and 9mustbe saved in your homework directory.Lab 13, April 26:Genetic Algorithm / Machine Translation. This final lab of the term will be turned in at the end of the lab period.

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

noton 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 animationRemember 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

notresponsible for the following material:

- Pages 71--73 on the implementation of RAM.
- Section 3.2 on the implementation of individual assembly language instructions.
- Pages 92 and 93 on the internal construction of the Control Circuit.
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 programThere 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

notresponsible for the internal details of thehalf-adder, full-adder, subtraction circuit, ALU, or one-bit memory circuit.You should know what these circuits do. You donotneed 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

notresponsible 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