ALGORITHMS TO MACHINES
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

Purpose

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.

Prerequisites

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

Required

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.

Evaluation

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

------------------------------------------------------------------------------

WEEK #1

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

-------------------------------------------------------------------------------

WEEK #2

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

WEEK #3

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
                    Lists:
                        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
             Max/Min
             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

-------------------------------------------------------------------------------

WEEK #4

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
              Harvester
             
          Homework for next class:
              Karel the Robot handout
             
-------------------------------------------------------------------------------
   
WEEK #5

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

-------------------------------------------------------------------------------

WEEK #6
                       
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
             Parity
             Majority
             Not-equal
             
         HOMEWORK ON BINARY COLLECTED ("Quiz #4")
         Reading for next class:
              Supplemental, Essay The Internet? Bah! (published in 1995)
                            Essay Tim Berners-Lee calls for free internet worldwide (published in 2010)

-------------------------------------------------------------------------------

WEEK #7
         
Oct 4 - Logic, Switches, Gates, then Circuits
         "Building" logic from switches
         Circuits to Expressions
         Simplifying circuits
             Parity
             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
             Flip-flops
             Multiplexers
             Decoders
         Putting it all together...
    
Oct 8  - OPPORTUNITY #1 
         Open notes (and book, if you must)
         Bring completed essay
    
-------------------------------------------------------------------------------

WEEK #8

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

         Reading: 
             Text, Chapter 8
             Supplemental, Essay, Privacy, Legislation, and Surveillance Software
 
Oct 15 - QUAD FINALS, NO CLASSES

-------------------------------------------------------------------------------

WEEK #9

Oct 18 - Introduction to Lego Mindstorms Programming

         Reading:
             Supplemental, Essay, Bloggers Against Torture

Oct 20 - Metalanguages - Using Language to Describe a Language

         Reading:
             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

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

          Reading:
             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

         Reading:
             Supplemental, Essay, Why Spyware Poses Multiple Threats to Security

Nov 5  - Java programming continues

         Reading:
             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
         Reading: 
             Text, Chapter 15

         Supplementary reading (see above):
             Human and Machine Dignity

Nov 17 - Unauthorized Access (video) 
         Reading:
             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

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

Dec 3  - continued

-------------------------------------------------------------------------------

WEEK #16

Dec 6  - MEET WITH ROBOT PROGRAMMING TEAM TO PREPARE FOR LAB

Dec 8  - Discussion of topics for Opportunity #2

-------------------------------------------------------------------------------

FINAL EXAMINATION PERIOD

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

=============================================================


Tentative Laboratory Outline


Aug 26 : NO LAB TODAY
       
-------------------------------------------------------------------------------

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

Sep 9  : NO LAB TODAY 
          
          TECHNOLOGY INVENTORY DAY
          FOLLOW INSTRUCTIONS PROVIDED IN CLASS
          
-------------------------------------------------------------------------------

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 DecentFilms.com
            2001: A Space God-esy, Mark Midbon
            See professor for: 
                "Creation Machines, Stanley Kubrick's View of Computers in 2001"

-------------------------------------------------------------------------------

Nov 25 : THANKSGIVING!

-------------------------------------------------------------------------------

Dec 2  : LMR project continues

-------------------------------------------------------------------------------

Dec 9  : LMR project exhibition & competition