The course described on this page ended May 7, 2001

I will be teaching CPSC 120 again in the Spring of 2002.

--David Eck

I will be teaching CPSC 120 again in the Spring of 2002.

--David Eck

## CPSC 120:

Principles of Computer Science

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

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 2001.

## Links to lab worksheets:

First lab, January 26:Applets, Data Representation, and HTMLSecond lab, February 2:The lab is xLogicCircuits Lab 1, from the Java Web Page for The Most Complex Machine. However, you should only do Exercises number 1, 3, 4, 6, and 9. For the exercises that ask you to construct a circuit, turn in a drawing of your circuit.Third lab, February 9:This week's lab is xComputer Lab 1. For your lab report, you should turn in Exercises 2, 3, 4, 7, and 8. (Because of the test next Wednesday, you can turn in the lab report on Friday of next week instead of Wednesday.)Fourth lab, February 16:Introduction to Web Page Authoring.Fifth lab, February 23:The lab will be about Turing Machines. See the Lab 5 information page for more information.Sixth lab, March 2:The lab is xTurtle Lab 1. For your lab report, you should do exercises 1, 4, 5, 6, 7, and 9. If you want, you can also do exercise 10 for a little bit of extra credit.Seventh lab, March 9:The lab is xTurtle Lab 2. For your lab report, you should do exercises 1, 5, 6, 7, and 9.Eighth lab, March 23:More about Web Pages.Ninth lab, March 30:Today's lab is xTurtle Lab 3, on subroutines and recursion. Your lab report will consist of the following exercises from this lab: 1, 3, 6, 8, and 10.PLEASE NOTE:On April 6, we will not have a lab. Instead, we meet in our regular classroom to view a videotape, "Giant Brains".Tenth Lab, April 13:The lab is xSortLab: Sorting and the Analysis of Algorithms. For your lab report, you should do problems 4, 6, 7, 8, and 10.Eleventh Lab, April 20:The lab is xModels Lab 1. For the lab report, do Exercises 1, 2, 6, 8, and 10. For exercise 10, show me the result of your efforts at lab next Friday, April 27.Twelfth Lab, April 27:The lab is xModels Lab 2. For the lab report, do Exercises 1, 3, 5, and 6.Thirteenth Lab, May 4:The final lab for the course is a short look at two aspects of artificial intelligence: Machine Translation and the Genetic Algorithm. You will turn in your work for this lab at the end of the lab.

## Final Exam: May 7

The final exam for this course is on Monday, May 7, at 1:30 PM, in our regular classroom. The exam is cumulative. You should review the lists of terms and ideas that are given on this Web page for each week of the term. However, the exam will

notcover: the assembly language of xComputer, analysis of algorithms, BNF, or the "Giant Brains" video. You can expect the exam to include a summary essay question on structured complexity.

## Fourteenth Week: April 30; May 2 and 4

In the final week of the term, we will discuss Chapter 12, which deals with artificial intelligence. The lab on Friday will also be about artificial intelligence. For this lab, instead of doing a lab report, you will turn in your answers to two questions at the end of the lab. These questions will count for 14 points, and you will probably get the full 14 points as long as you take the questions seriously. Unless you have a really, really good excuse, you must be at the lab to get credit.

You should read Chapter 12. Here is a list of terms that you should know from this chapter:

Artificial Intelligence (AI) Turing Test cognition physical symbol system hypothesis microworld knowledge representation natural language: language as a symbol system arguments against AI: limits of logic argument Chinese room argument the problem of consciousness expert system emergence artificial life neural net genetic algorithm

## Thirteenth Week: April 23, 25, and 27

The reading for the week is Chapter 11: Computer Graphics. The lab for this week is a

xModels Lab 2, which covers three-dimensional graphics. Here are some terms and ideas that you should know from the reading: computer graphics "painting" programs vs. "drawing" or "modeling" programs computer animation geometric modeling polygons hierarchical models with complex objects (DEFINE in xModels) rendering geometric transformations: scaling, rotation, and tranlation rotations in 3D (about x-, y-, or z-axis) projection from 3D onto a 2D screen wireframe model attributes, such as color diffuse reflection and specular reflection texture maps ray tracing radiosity

## Twelfth Week: April 16, 18, and 20

We will finish up Section 9.3 on Monday, and possibly start talking about Chapter 11, if there is time. The lab for Friday will be xModels Lab 1. It is loosely based on Section 11.1, but is mostly self-contained. I will hand out a copy in class. It is important for you to read the lab before coming to class on Friday.

On Wednesday, there is a test. It covers everything that we have done since the previous test. Of course, you will also have to remember the basic material on xTurtle that was covered on the previous test. The test covers all of Chapter 7; Sections 5.1, 8.1, and 9.3; and Labs 9 and 10. Some of the main topics on the test are:

Subroutines and parameters Writing and using subroutines in xTurtle Recursion Interpreting recursive subroutines in xTurtle Activation records and the stack of activation records. The early history of computing The "Giant Brains" video The idea of "abstraction" in programming languages Analysis of algorithmsSee also the lists of terms given below for the previous three weeks. I will not ask you about the P=NP problem, and I will not ask you to write a recursive subroutine. However, I will probably give you a recursive subroutine and ask you to show the picture that it produces.

## Eleventh Week: April 9, 11, and 13

The reading for this week is Chapter 8, Section 1 and Chapter 9, Section 3. (I encourage you to read the other sections in these chapters, but they will not be covered in class or on the test.) The lab this week will be xSortLab: Sorting and the Analysis of Algorithms, which is based on Section 9.3. Here are some terms and ideas for this week:

abstraction: control abstraction, procedural abstraction, data abstraction data structures FORTRAN, Algol, COBOL, Basic, Pascal, C, C++, Java algorithm analysis of algorithms "Big-Oh" notation O(n), O(n^{2}), and O(n*log(n)) algorithms worst-case running time average-case running time time complexity classes, such as TIME(n) sorting sorting algorithms (from the lab): bubble sort, insertion sort, and merge sort the P=NP problem

Reminder: There is a test next week, on Wednesday, April 18.

## Tenth Week: April 2, 4, and 6

Lab 9 is due in class. Exercise 10 is optional. It will count for extra credit if you do it.

This week, we are departing from the original schedule as given the course handout. Instead of trying to cover JavaScript, I have decided to talk about Section 7.4 on Monday and then to spend some time on Section 5.1 on Wednesday. The material in Section 5.1 is on the history of computing, and we will follow this up on Friday with a video that covers some of the same subjects. In lecture, I might add in some material on the history of programming languages from Section 8.1, even though we will not cover that section formally. There will be no lab on Friday. There will be a few short questions about this video on the next test.

You should read Section 7.4 and Section 5.1. Here is a list of important terms and ideas from this reading:

activation record return address stack of activation records how recursion is implement using the stack Charles Babbage Ada Augusta, Countess of Lovelace the Analytical Engine the Jacquard loom general purpose, electronic, stored-program computers Colossus and the Enigma machine Alan Turing the ENIAC John Mauchly and J. Presper Eckert John von Neumann von Neumann machine mechanical relays, vacuum tubes, and transistors integrated circuit microprocessor

## Ninth Week: March 26, 28, and 30

This week, we will cover Chapter 7, sections 1 to 3, on subroutines and recursion. We will not cover Section 7.4 in this course. [

This was changed as of Week Ten.] The lab will be xTurtle Lab 3. Here are some important terms and idea from Chapter 7:creating subroutines with SUB ... END SUB subroutines as black boxes calling subroutines parameters in subroutine declarations dummy parameters actual parameters local variable global variable modules and modular program design software life cycle: specification coding maintenance top-down design bottom-up design recursion recursive subroutines Koch curve randomness in recursion

## Eighth Week: March 19, 21, and 23

There is a test this week on Wednesday, March 21. It will cover Chapters 4 and 6, as well as Labs 4, 5, 6, and 7. The lists of terms for Chapters 4 and 6, which you can find below on this page, should be helpful in reviewing for the test. We might begin Chapter 7 on Monday, but it will not be on the test.

The lab this week will continue your introduction to HTML and Web-page authoring.

## Seventh Week: March 5, 7, and 9

This week, we will complete Chapter 6. Your lab report for last week's lab is due on Friday. The lab this week will be xTurtle Lab 2. I will hand out a copy of the lab in class on Wednesday. Please read it before coming to lab.

Here are some important terms and ideas from Chapter 6 and from the labs:

programming xTurtle software engineering turtle graphics syntax DECLARE statement semantics := names used in programs built-in xTurtle subroutines: variables forward(x), back(x), built-in subroutines turn(d), face(d), subroutine call statement red, blue, ..., parameters rgb(x,y,z), hsb(x,y,z), assignment statements TellUser("string"), declaring variables AskUser("string", variable), loops circle(r), exiting a loop PenUp, PenDown, decisions moveTo(x,y), move(dx,dy) BNF (Backus-Naur Form) random, randomInt(N) process expressions with +,-,*,/ precondition conditions with =, <, >, and, ... postcondition IF... END IF statement nested statements using OR IF in an if statement comments (in a program) LOOP... END LOOP 3N+1 sequence EXIT IF <condition>Next week is Spring Break. Please remember that there is a test coming up on the Wednesday after Spring break. It will cover Chapters 4 and 6. It might also have a question about HTML and Web pages, which were covered in the fourth lab.

## Sixth Week: February 26 and 28; March 2

The reading from the textbook for this week and next is Chapter 6. The labs for both weeks will be based on this material. The lab for this Friday is xTurtle Lab 1. The lab report is due next Friday, and from now on, lab reports will always be due at the next lab, on the following Friday.

## Fifth Week: February 19, 21, and 23

The reading for this week is Chapter 4 (but we will probably carry over the material from Chapter 4 into the beginning of next week). The lab on Friday will be xTuringMachine Lab. For the lab report, you will only do Exercises 1, 2, 4, 5, 9 and 11 from this lab.

Important terms and ideas from Chapter 4 include:

Simulation Turing Machines: Translation tape of a Turing machine Interpreter cells on a tape Computational Universality symbols on a tape Church-Turing Thesis states of a Turing machine The Halting Problem halt state Unsolvable problems rules for a Turing machine how a Turing machine computes constructing Turing machines

## Fourth Week: February 12, 14, and 16

The main event this week is the

testwhich will take place in class on Wednesday. The test covers all the material that we did from Chapters 1, 2, and 3 and in the labs. The lists of important terms that are given on this page each week are a good starting point for studying for the test.We will finish up Chapter 3 on Monday and do a bit of review. In spite of what the tentative syllabus says, I do not plan on starting Chapter 4 until next week. I do hope to take some class time to talk about real computer systems. (If you want to know more about this, you can read Chapter 5, Section 2, but this is not required reading.) The important terms that you should learn about from this discussion include:

interrupt device driver operating systemThese terms will

notbe on the test on Wednesday.The lab for this week will be about creating a web page. (We will finally do the stuff that we had to leave out of Lab 1 because of network problems.)

## Third Week: February 5, 7, and 9

The reading for the week is Chapter 3, Sections 1 and 3. (You can also read the introductory paragraphs on pages 67 and 68.) Section 2 has a lot of technical detail, which we will skip. However, you will learn about some of the machine language instructions for xComputer. Here are some important ideas and terms for this week:

CPU (Central Processing Unit) Important registers in xComputer: Main Memory Accumulator, Instruction Register, RAM (Random Access Memory) Program Counter, Count Register, location (in memory) Address Register address (of a location) Important instructions in xComputer: Clock (that drives the computer) ADD, ADD-C, SUB, SUB-C, LOD, LOD-C, Control Circuit STO, INC, DEC, JMP, JMZ, JMN, HLT Control wire Fetch-and-execute cycle Steps in the fetch-and-execute-cycle black box interface vs. implementation Black-Box PrincipleThe lab this week will be xComputer Lab 1. From this lab, you will only turn in exercises 2, 3, 4, 7, and 8. (Note that the xComputer applet will do the mechanical part of Exercise 2 for you!).

Don't forget that the first test in the course is coming up on Wednesday of next week. The lists of terms that I give each week can help you figure out what you should concentrate on. You can see some old test and quizzes (with answers) from previous terms on the home page for the textbook we are using: http://math.hws.edu/TMCM.html. Look at the bottom of the page. (The course number there, CPSC 100, is the old number for this course.) Please keep in mind that in previous terms, I covered Chapters 2 and 3 in a bit more detail than I am this term.

## Second Week: January 29 and 31, and February 2

Your first lab report is due in class on Wednesday of this week. Remember that because of the network problems, you only need to do Exercises 1 though 4. We will return to the topic of making Web pages in the fourth lab.

The lab for this week is xLogicCircuits Lab 1, as noted at the top of this page. Please note that for the lab report that is due next week, you will only do Exercises 1, 3, 4, 6, and 9 from that lab.

The reading for the week is Chapter 2 of The Most Complex Machine, up to page 48. I will not ask you to read the remainder of Chapter 2, but I will cover some aspects of that material briefly in class, including the definitions of ALU, memory, and register. Here are some important terms for this week:

logic operations: AND, OR, NOT propostions logic gates: AND, OR, and NOT gates true/false; on/off; one/zero logic circuits relation between propostions and logic circuits Boolean algebra input/output tables how to build a circuit to compute an input/output table addition of binary numbers half-adder circuit full-adder circuit k-bit adder circuit ---------- Not in Reading: ------------- arithmetic-logic unit (ALU) feedback loops in circuits memory circuit k-bit register

## First Week: January 22, 24, and 26

The reading for this week is

Chapter 1from the textbook. I will also be handing out a short excerpt from an electronic newsletter by Phil Agre. You should read this before Wednesday's class and be prepared to discuss it.This class meets each Friday in Gulick 208 for a lab. You can read the worksheet for that lab ahead of time if you want. You should do all the exercises from this worksheet. Turn in a lab report with your answers to exercises 1 through 4 next Wednesday in class. Remember that you can work with someone in lab, if you want. If you do, you and your partner have the option of turning in a single lab report or separate lab reports. However, everyone in the class has to do Exercises 5 and 6. I will grade these exercises by looking at your Web page on line. These exercises should also be done by class time next Wednesday.

Here are some of the most important terms that you need to be familiar with from Chapter 1 of the text:

mechanical manipulation of symbols transistor bit central processing unit binary number fetch-and-execute cycle base two machine language byte loops and decisions ASCII code jump instruction Unicode subroutine pixel high-level language digitization compiler structured complexity