## CPSC 120:

Principles of Computer Science

Department of Mathematics and Computer Science Hobart and William Smith Colleges Fall, 2002. Instructor: David J. Eck (eck@hws.edu) Monday, Wednesday, 12:20 -- 1:15. Room Lansing 300. Friday, 12:20 -- 1:15. Room Gulick 208. Course Handout: http://math.hws.edu/eck/courses/cpsc120_f02.html

## Information

- Tests with answers: First Test Second Test Third Test
- Information sheet for: First Test Second Test Third Test Final Exam
- Web page from last year's course
- Information about your Linux account

## Lab Worksheets

- Lab 1, September 6: Data Representations (and Web Pages)
- Lab 2, September 13: Logic Circuits
- Lab 3, September 20: The xComputer Model Computer
- Lab 4, September 27: More about Web Pages, plus some Linux
- Lab 5, October 11: xTurtle Basics
- Lab 6, October 18: Thinking about Programs
- Lab 7, October 25: A Simple WebLog wih PHP
- Lab 8, November 1: Subroutines and Recursion
- Lab 9, November 8: Two-Dimensional Graphics with xModels
- Lab 10, November 15: Adding the Third Dimension to xModels
- Lab 11, November 22: Three-D Graphics with Blender
- Lab 12, December 6: Turing Machines
- Lab 13, December 13: Artificial Intelligence

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 Fall term of 2002.

## First Week: September 2, 4, and 6

The reading for this week is Chapter 1 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.

Before you come to lab on Friday, youmustknow your user name and password for the HWS Windows network. If you have forgotten this information, you should go to the computer center in Williams Hall for help.Here is a list of some of the important terms and ideas from 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 logic gate counting in binary subroutine ASCII code loop byte machine language pixel high-level language digitization compiler

## Second Week: September 9, 11, and 13

This week we will be talking about "complex hardware." The relevant material from the textbook includes Section 1.2 (which you should already have read) and Chapter 2, pages 29 to 48 (that is, from the beginning of the chapter through Subsection 2.2.2). The lab and classes for this week will also briefly discuss ALU circuits and memory circuits, which are covered later in Chapter 2. However, we will not cover them in detail.

Here is a list of new terms and ideas for this week:

Boolean Algebra AND, OR, and NOT logic in English sentences logic circuits building a circuit from a boolean algebra expression finding the boolean algebra expression for a circuit building a circuit from an input/output table addition of binary numbers k-bit adder circuit memory circuit feedback loop one-bit memory register

## Third Week: September 16, 18, and 20

The lab this week will be about the "model computer" that is covered in Chapter 3 of the text. You should read the following material from Chapter 3: pages 67--71 (ending with the paragraph that starts "A black box understanding"), pages 73--82 (subsections 3.1.2 and 3.1.3), and pages 94--95 (subsection 3.3.1). You might also want to review Section 1.3 in Chapter 1. In class and lab, you will also learn something about the machine language for xComputer and about Control Circuits.

Here is a list of terms and ideas for the week:

Main memory Registers in xComputer: RAM AC, IR, PC, ADDR, COUNT, X, Y location in memory address of a location ML instructions for xComputer: address wires ADD, ADD-C, SUB, SUB-C, load-data-into-memory wire LOD, LOD-C, STO, INC, DEC, control wires in general JMP, JMZ, JMN, HLT ALU Clock (that drives the computer) assembly language Fetch-and-execute cycle labels in assembly language Control Circuit Black Box

## Fourth Week: September 23, 25, and 27

There is a

testthis Wednesday, September 25, in class. An information sheet about the test will be given out in class on Monday, and we will spend Monday reviewing, finishing up our discussion of xComputer, and discussing Friday's lab. There is no reading for this week. We will skip Chapter 4 and come back to it later in the term, so the next reading will be Chapter 5.

## Fifth Week: September 30, October 2 and 4

We will not have a lab this week. Instead, we will meet on Friday in our regular classroom to view the video

Giant Brains.The reading for the week is Chapter 5. This chapter covers a variety of topics related to "real computers." The first section is on on the history of computing, the second deals with how complete computer systems operate, and the third looks briefly at some of the social implications of computers. Here are some terms, people, and ideas for this week:electronic, general-purpose, stored-program computers Ada Lovelace microprocessor Charles Babbage integrated circuit the Analytic Engine command-line interface the Jacquard Loom graphical user interface the Enigma machine memory-mapped I/O code-breaking in World War II interrupts Alan Turing interrupt handler the ENIAC bus "human computers" expansion slot John Mauchly operating system J. Presper Eckert device driver John von Neumann application program von Neumann machine ROM (read-only memory) universal machine booting a computer information age cyberspace de-skilling computers and privacy issues

## Sixth Week: October 7, 9, and 11

We will begin Chapter 6 this week. You should read Chapter 6, pages 173 to 191. This includes the first two sections of the chapter. This is the first of several weeks that will be devoted to programming. We will be using a fairly simple high-level programming called "xTurtle." Important terms from the reading include:

turtle graphics LOOP statement in xTurtle syntax IF statement in xTurtle semantics BNF built-in subroutine subroutine call statement xTurtle commands: parameter forward, back, turn, face, variable moveTo, move, penUp, penDown, DECLARE statement TellUser, AskUser, assignment statement heading, xCoord, yCoord

## Seventh Week: October 16 and 18

There is no class on Monday, on account of Fall break. Remember that there is a test coming up on Wednesday of next week, October 23.

You should finish reading Chapter 6. Here are some of the important new ideas in Section 6.3:

precondition postcondition state process software engineering nested statement

## Eighth Week: October 21, 23, and 25

There is a

teston Wednesday, October 23. An information sheet about the test is available. We will spend Monday finishing up Chapter 6 and preparing for the test. The lab on Friday will be our final lab related to Web pages.

## Ninth Week: October 28 and 30; November 1

You should read Chapter 7, "Subroutines and Recursion". We will definitely cover Sections 7.1 and 7.3 this week, except for Subsection 7.1.2 which is not required except for the definition of local variable. We might also cover Section 7.2. Here is a list of some of the terms and ideas you should be familiar with from Sections 7.1, 7.2, and 7.3:

subroutine module subroutine declaration black box using SUB...END SUB implementation and interface dummy parameter software life cycle actual parameter top-down design local variable bottom-up design recursion software engineering recursive subroutine coding Koch curve randomness in recursion

## Tenth Week: November 4, 6, and 8

On Monday, I will finish up Section 7.2. We will then be moving on to Chapter 11, Computer Graphics. We will be concentrating on two-dimensional graphics this week. You should read the first part of Chapter 11, pages 321 to 328. Here are some important ideas from this reading and from this week's lab:

computer graphics animation painting programs drawing program rendering geometric modeling transformations scaling, rotation, and translation coordinate system origin scene description language frames of an animation key frame animation object definitions in xModels

## Eleventh Week: November 11, 13, and 15

We will finish Chapter 11 this week. The reading is the remainder of that chapter, pages 328 to 342. Here are some of the terms you should know from this week's reading and lab:

xyz-coordinate system on 3D space rotations in three dimensions axis of rotation projection from 3D to 2D wireframe model specular reflection and diffuse reflection color texture bump map light sources ambient light hidden surface ray tracing and radiosity lathing extrusion translations in 3D scaling in 3D rotation about the x-axis, the y-axis, and the z-axisReminder: There is a test coming up next week.

## Twelfth and Thirteenth Weeks: November 18, 20, 22, and 25

There is a

teston Wednesday, November 20. An information sheet is available about this test. On Friday, we will have another lab on 3D graphics -- this time using Blender. Next Monday, we should start on Chapter 4, and the remainder of the term will be spent on Chapters 4 and 12.There is no class on Wednesday, November 27 or Friday, November 29 because of the Thanksgiving holiday.

## Fourteenth Week: December 2, 4, and 6

We will finish up Chapter 4 this week, concentrating on Turing machines on Monday and on the halting problem on Wednesday. Note that we will not cover Subsection 4.2.3 (universal Turing machines). Important terms and ideas from Chapter 4 include:

Computational Universality equivalence of all computers simulation Church-Turing thesis Turing machines: tape, cells, symbols, blank cell, states, halt state, how a Turing machne computes, table of rules, how to use a Turing machine to compute a function unsolvable problems the Halting Problem implications of the unsolvability of the Halting Problem

## Wrapping up the course: December 9, 11, 13, and 19

For the last week of the course, we will be looking at Artificial Intelligence. The reading for the week is Chapter 12 of the text. We will have our final lab on Friday. The lab report for this lab will be your answers to two questions that you will turn in

at the end of lab.The final exam will be given in our regular classroom at 7:00 PM on Thursday, December 19. It will be cumulative but will concentrate on the material that we have covered since the third test. Essay questions will be probably be based more on class discussion than on the readings from the test.Here are some important terms from Chapter 12:

artificial intelligence Turing test physical symbol system hypothesis heuristic natural language processing machine translation expert system knowledge representation common sense arguments for and against AI Godel's Theorem and the limits of logic embodied intelligence the Chinese room the problem of consciousness solipcism neural nets emergence artificial life genetic algorithm