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 HTML
- Second 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 not cover: 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
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 algorithms
See 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(n2), 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 test which 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 system
These terms will not be 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 Principle
The 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 1 from 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