Gordon College, Fall 2010

Irvin J. Levy
Professor of Chemistry and Computer Science
Office Hours:
MWF, 8:00-9:00am
T, 11:00-12:30pm
R, 8:00-9:30am; or by appointment
al go rithm /al-guh-rith-uhm/ -noun
a set of rules for solving a problem in a finite number of steps, as for finding the greatest common divisor
ma chine /muh-sheen/ -noun
an apparatus consisting of interrelated parts with separate functions, used in the performance of some kind of work


In its most general form, computer science is the study of algorithms and machines that perform them. Interestingly, computer science is a discipline that is both well-known and broadly misunderstood. To many, computer science refers to the acquisition of certain skills for using a computer. In other words, some think of learning to use a spreadsheet program, a word processor, or a web browser as "computer science." The term causes others to imagine people sitting in somewhat darkened rooms typing endless lines of cryptic code into a keyboard to create a remarkable new computer program. Some imagine engineers developing massive robots or amazingly small microcomputers embedded into other devices. Still others hear the term and envision anarchistic hackers roller-blading with laptop computers equipped to bring the world to its knees. In truth, all of these notions have something to do with "computer science" but none of them is sufficient to represent the richness of the topic.

In this course, you will be challenged to develop a clearer understanding of the term "computer science". You will see that computer science has much to do with practical applications such as the development of a new robotic vacuum cleaner, but it is also a philosophically interesting pursuit with mathematically elegant underpinnings. You will learn how to get work done with a computer, as well as how a computer works. You will understand how to use a computer, but also ways in that computers are sometimes manipulated to "use" us. Through reading and discussion you will begin to examine the evolution of our "digital society" and how it affects our lives and how it might affect us differently in the future.


While no formal prerequisite coursework is required before attending this course, it is important for all students to be aware that this class has components that require mathematical reasoning, logical reasoning and abstract reasoning. Consequently, students with weak ability in one or more of these areas are strongly encouraged to discuss this with the professor during the first week of classes to determine whether the course is suitable for their needs.

Course Texts and Materials


Course expectations

A. Lecture and Reading

Reading from the course texts will be assigned on a regular basis. All assignments must be read prior to the class in which the material will be discussed since the lecture will assume this degree of familiarity with the topic. Class sessions will include a discussion and amplification of the material from the text and the presentation of further examples and supplementary material. You should not necessarily expect to grasp everything presented in the text when you first read it; however, you should note areas that are unclear to you and be prepared to raise questions about them in class. If you read the material only after its lecture, you will not be able to participate effectively during the lecture and you are likely to feel as though lecture is only for note-taking rather than the intended learning experience.

All students are expected to attend lecture regularly and are responsible for all material covered during class. In the event of an unavoidable absence, it is the student's responsibility to learn of any material or assignments from the missed class.

B. Homework

Numerous homework problems will be assigned to help you clarify important concepts; however, normally homework will not be collected and will not directly affect your final course grade. Homework does, of course, affect the grade in that it is unlikely that the course content can be mastered without significant practice. Self-evaluation of homework will be possible through the use of posted solutions. You are encouraged to contact the professor either during office hours, by email or during appropriate times in lecture if questions relating to homework problems arise. Students are encouraged to work in groups to solve homework problems unless otherwise directed by the professor.

C. Quizzes

Since this course is of a technical nature and since the complexity of the material builds from topic to topic, it is essential that you stay up to date with the reading and homework from the course. In order to motivate you to continually interact with the material, numerous quizzes will be given throughout the semester. These quizzes will normally cover material from the previous several classes and normally will require no more than 10 minutes for completion. All quizzes will be announced no later than the lecture prior to the quiz date. Quizzes are closed-book, closed-note unless previously announced to the contrary. Make-up quizzes will not be administered under any circumstances; however, the two lowest quiz scores will be discarded when determining the final quiz grade.

D. Opportunities

Two times during the course you will receive the opportunity to solve problems during an entire class session. The opportunities will be administered on the dates listed in the course schedule. The second opportunity will be cumulative; however, it will emphasize material from the latter portion of the course. Each opportunity will assume familiarity with material from the text, from lecture, from homework problems and from laboratory work. Opportunities will be open book (course texts only) and open notes. Use of a computer will not be allowed.

E. Laboratory

Additional significant practice will come from a series of laboratory assignments. Laboratory work will typically be completed by partners. It is important that both partners in a team are fully aware of all material presented in the laboratory since all students will be responsible for any information presented in the laboratory. Often a pre-laboratory reading assignment will be given. It is essential that all pre-laboratory assignments be completed before arriving in lab. The time in lab is very limited; thus, sufficient preparation is important. Each laboratory will be evaluated on a Credit/No Credit basis. The final laboratory grade will be determined by summing the number of laboratory credits and dividing by the number of available credits. The material covered in the laboratory may be further evaluated either via Quiz or Opportunity.

In the event that a student is absent during a laboratory period, the student is responsible to complete the assignment, with a one-half credit penalty, no later than the beginning of the next laboratory period. After this final due date the assignment will not be accepted for credit; however, it may be completed without credit in order for the student to master the material.

A significant long-term laboratory project will be assigned during the course. In this project, a team of students will program a simple robot to perform various tasks. At the end of the course a competition will be as the culmination of the robot programming assignment. You should plan to spend significant amounts of time working on this project outside the scheduled laboratory hours.

IMPORTANT NOTE: Students who fail to receive credit for three or more laboratories will have final course grades reduced by one letter grade for each missing laboratory after the second. This penalty is in addition to the lowered laboratory grade.


The final score will be computed from a weighted average, as follows:

25%    Quizzes/Homework (drop two low scores)
25%    Opportunity #1
25%    Opportunity #2
25%    Laboratory

Miscellaneous Information

Make-up examinations will be allowed only if the absence is previously cleared with the instructor or in the event of an emergency. In the case of illness, a written excuse from the health center is required. In the case of a personal emergency, a note from the Center for Student Development is required.

Make-up quizzes are not administered under any circumstances.

Gordon College is committed to assisting students with documented disabilities (see Academic Catalog Appendix C, for documentation guidelines). A student with a disability who may need academic accommodations should follow this procedure:

1. Meet with a staff person from the Academic Support Center (Jenks 412 X4746) to:

a. make sure documentation of your disability is on file in the ASC,
b. discuss the accommodations for which you are eligible,
c. discuss the procedures for obtaining the accommodations, and
d. obtain a Faculty Notification Form.
2. Deliver a Faculty Notification Form to each course professor within the first full week of the semester; at that time make an appointment to discuss your needs with each professor.

Failure to register in time with your professor and the ASC may compromise our ability to provide the accommodations. Questions or disputes about accommodations should be immediately referred to the Academic Support Center. (See also Grievance Procedures in Student Handbook.)

Supplementary materials

NOTE: This list will expand during the semester. Check back frequently.

Tentative Lecture Outline



Aug 25 - What is Computer Science?               

         Homework for next class:
             Reading (see above): 
                 Essay: For a While, The Luddites Had a Smashing Success

Aug 27 - What is a computer?

         Homework for next class:
            Read text, Chapter 1.1 - 1.3
            Homework problems: p.34, #1.1, 1.13 and either 1.3 or 1.7
            Essay: Five Things We Need To Know About Technological Change



Aug 30 - Algorithm Discovery and Design - Attributes of an Algorithm

         Homework for next class:
            Text, Chapter 1.4, 2.1 - 2.2
            Essay (handout): On The Nature of Computing
            Explore homework problem 1.8
Sep 1 - Algorithms in Depth; m-digit addition

         QUIZ #1 on reading and homework
         Homework for next class:
            Essay: A Place for Hype
            Construct an algorithm to compute the n-th Fibonacci number

Sep 3 - Describing Algorithms via Pseudocode
         Fibonacci numbers

         Handout: Technology Inventory


Sep 6 -  Labor Day

Sep 8 -  Describing non-arithmetic algorithms
         TSP and Sort

         Homework for next class:
             Develop an algorithm for bubble sort as demonstrated in class today
             Bubble sort explorations:
                 Sort the following lists showing new list after each pass
                  Count number of comparisons made for the complete sort of each list
                  Plot list size vs. # of comparisons
                        4 7 12 14 2
                        4 7 12 14 2 5 8 19 11 1
                        4 7 12 14 2 5 8 19 11 1 3 16 42 32 99
Sep 10 - "QUIZ #2" - Technology Inventory collected
         Searching and Sorting; The Efficiency of Algorithms
         Constant, Logarithmic, Linear, Polynomial, and Exponential
             Binary Search
         Homework for next class:
             Search the web for best algorthim explanation of bubble sort
             Text, skim Chapter 3
             Supplemental, Essay - The Beauty of Simplicity



Sep 13   - Sorted List Management
          Insertion into sorted list
          Linear search, binary search and algorithmic efficiency
          Towards a Θ(1) search
Sep 15  - Discussion of formal code for bubblesort
          Introduction to formal algorithm description - Karel the Robot
          QUIZ #3 on reading and homework

          Homework for next class:
             Supplemental, Essay - Software Wars

Sep 17  - Karel the Robot programming

          Problems discussed: 
              Search and Retrieve
          Homework for next class:
              Karel the Robot handout

Sep 20  - Stepwise Refinement of Complex Problems

          Homework for next class:
             Text, Chapter 4, pages 130-151

Sep 22  - The Building Blocks, Binary Numbers, Boolean Logic and Gates
          Binary representation of integers, signed integers and real numbers

          Homework for next class:
             Text, Chapter 4, continued
          Optional (link to extra lecture notes
Sep 24  - Numeric codes, continued.

          Homework for next class:
             Supplemental, Essay: National ID


Sep 27 - Binary representation of characters, images and sound
         Compression Algorithms
             Lossless Variable Length Encoding:
             The Huffman Code
         Reading for next class:
             Supplemental, Essay - How Deep Can You Probe?
Sep 29 - Boolean logic and switches
         AND/OR/NOT and all that stuff
         Symbolic logic
         Logic expressions in truth tables
         Homework on Binary assigned.  Due on Friday. Counts as a quiz.

Oct 1 - Boolean Logic Expressions
         Logic Expressions ---> Truth Tables
         Equality of logic expressions
         Simplfying expressions
         Truth Tables ---> Logic expressions
         Reading for next class:
              Supplemental, Essay The Internet? Bah! (published in 1995)
                            Essay Tim Berners-Lee calls for free internet worldwide (published in 2010)


Oct 4 - Logic, Switches, Gates, then Circuits
         "Building" logic from switches
         Circuits to Expressions
         Simplifying circuits
             Half Adder
             Full Adder

         Opportunity #1 Essay Questions distributed

         Homework for next class:
             Supplemental, Essay, Is Google Making Us Stupid? 
Oct 6  - Circuits that remember, Circuits for choosing
         Putting it all together...
Oct 8  - OPPORTUNITY #1 
         Open notes (and book, if you must)
         Bring completed essay


Oct 11 - Introduction to Assembly Language
         Machine codes, Multiplexers
Oct 13 - Introduction to High-level Language Programming

             Text, Chapter 8
             Supplemental, Essay, Privacy, Legislation, and Surveillance Software



Oct 18 - Introduction to Lego Mindstorms Programming

             Supplemental, Essay, Bloggers Against Torture

Oct 20 - Metalanguages - Using Language to Describe a Language

             Supplemental, Essay, Piracy, Computer Crime, and IS Misuse at the University
Oct 22 - Introduction to Java

WEEK #10

Oct 25 - Java Programming In A Nutshell

             Supplemental, Essay, The Coming Robot Army
Oct 27 - Java Programming In A Nutshell

             Supplemental, Essay, False Reporting on the Internet and the Spread of Rumors

Oct 29 - Java Programming In A Nutshell


WEEK #11

Nov 1  - Java programming continues

Nov 3  - Java programming continues

             Supplemental, Essay, Why Spyware Poses Multiple Threats to Security

Nov 5  - Java programming continues

             Supplemental, Essay, China's Computer Wasteland
WEEK #12

Nov 8 - Java and Programming Language Translation

Nov 10 - Reading:
             Supplemental, Essay, In Korea, A Boot Camp for Web Obsession

Nov 12 - Reading:
             Supplemental, Essay, Google and the Wisdom of Clouds

WEEK #13

Mov 15 - Social Impact of Computing
             Text, Chapter 15

         Supplementary reading (see above):
             Human and Machine Dignity

Nov 17 - Unauthorized Access (video) 
             Supplemental, Essay, The Virus Underground
             Supplemental, Essay, A Nascent Robotics Culture
Nov 19 - Artificial Intelligence
         Choose one of the following essays to read:
             A. Why People Think Computers Can't, Marvin Minsky, AI Magazine, Fall 1982

             B. Robots, After AllHans Moravec, Communications of the ACM, October 2003

WEEK #14
Nov 22 - Artificial Intelligence, continued
        Choose one of the following audio/visual presentations:
             A. Interview with Dr. Anne Foerst on Science and Being: Speaking of Faith American Public Radio, September 23, 2004
                Main page, then click the "Listen" link
             B. Convocation lecture by Dr, Rosalind Picard, "Toward Machines That Can Deny Their Maker", March 26, 2004
                Click for the video - On campus only
Nov 24 - Thanksgiving break

Nov 26 - Thanksgiving break


WEEK #15

Nov 29 - Artificial Intelligence discussion

             Text, Chapter 14  
Dec 1  - Models of Computation
         Reading: Chapter 11

Dec 3  - continued


WEEK #16


Dec 8  - Discussion of topics for Opportunity #2



Monday, Dec 13, 10:30 am - 12:30 pm, OPPORTUNITY #2


Tentative Laboratory Outline


Sep 2 : History of Computing
         The Machine That Changed The World

Sep 9  : NO LAB TODAY 

Sep 16 :  Experimental measurement of time order of algorithms
         Sorting, Factoring (with related cryptography example)

         Sorting lab tools
         Factoring lab tools


Sep 23 : Implementation of algorithms -- Karel the Robot Handout


Sep 30 : Logic in the Sandbox: Introduction to Circuit Sandbox digital simulator    
         Lab Report from previous week is due


Oct 7 : Design of Circuits: From Function to Logic
         Given desired behavior, design and test circuits with Circuit Sandbox

Oct 14 : QUAD BREAK, No lab.


Oct 21 : Introduction to LMR Programming
         Random Walk to goal; measurement of time performance


Oct 28 : Control Structures and Sensors in LMR programming

         LMR project assigned

             2010: Folsom Prison Blues
             2009: Suppertime
             2008: Keep On The Sunny Side
             2007: Walk The Line

Nov 4  : LMR project continues


Nov 11 : LMR project continues


Nov 18 : 2001: A Space Odyssey
         Optional supplements: 
            HAL's Legacy online

            2001, A Space Odyssey, Internet Resource Archive

            Review from
            2001: A Space God-esy, Mark Midbon
            See professor for: 
                "Creation Machines, Stanley Kubrick's View of Computers in 2001"




Dec 2  : LMR project continues


Dec 9  : LMR project exhibition & competition