Harvey Mudd College
Computer Science 60
Principles of Computer Science
Overview/Syllabus, Spring 2002
What Is This Course About?
This course is designed to introduce you to the basic principles
of computer science.
You willll have a chance to use several different programming
languages including a functional
programming language (rex), an object-oriented language (Java),
a logic programming language (Prolog),
and assembly language (ISCAL). Why so many languages? The goal is
that, once you've taken CS 60, you
will be able to program in ANY language! (perhaps with the help of
a manual). After all, in 10 years, you will probably still need to
solicit the help of computers to solve problems, but the languages
in vogue today may well have gone the way of cobol, pascal, or fortran
(with apologies to any lingering fortran boosters).
By covering the foundations of data structures, algorithms, complexity
analysis, computability theory, logic principles, and computer architecture,
CS 60 will sharpen your language-independent skills.
These are the principles that will remain constant, even as Windows, MacOS,
Linux, etc., undergo their annual facelifts for years to come.
General Information
Instructors:
Section One (MW 2:45-4:00, Beckman 126)
Instructor:
Robert Keller
Office: Olin 1249
Phone: x18483 (909-621-8483)
E-mail: keller@cs.hmc.edu
Official Office Hours:TTh 2-4
Feel free to visit anytime, but you may wish to check my schedule first for likely availability.
Section Uno (TTh 2:45-4:00, Galileo Pryne)
Instructor:
Zachary Dodds
Office: Olin 1265
Phone: x78990 (909-607-8990)
E-mail: dodds@cs.hmc.edu
Official Office Hours: MW 4:00-5:00
Real Office Hours: Anytime
Course Homepage: http://www.cs.hmc.edu/courses/2002/spring/cs60/index.html
Help via e-mail:
For short questions related to homework, mail cs60help@cs.hmc.edu. For more
extensive help, please see a tutor or one of the instructors in
person. Help with the systems (turing, etc.) is available
from
help@cs.hmc.edu.
Asking CS-savvy friends and neighbors may be even more efficient.
Texts
- Computer Science: Abstraction to Implementation
(pseudo-title Computer Science for Smart People)
by
Robert M. Keller.
This is the primary textbook for the course.
This book is available for purchase from Ms. Joyce Greene
in the Computer Science Department Office, Olin 1240.
You may also use the text free of charge
online but it should not be printed at the expense of your college.
- [Optional] A book of your choice that covers the fundamentals of
Java. All the information you need is on line, so this
is only if you like reference books. I use some of the links from the
reference page.
All conduct in this course should be conducted in accordance with the Harvey
Mudd Honor Code.
To avoid confusion, the Harvey Mudd honor code has
been made very explicit with
regards to the computer science department and its computing systems.
Those details are in the
Computer Science Academic Honesty Policy.
You are expected to have on a file in the CS Department office a copy of
this document signed by you to indicate that you understand the policy.
Tentative Lecture Schedule
This list constitutes the basic topics of CS60; they
will be the focus of the lectures, assignments, and exams
for the course.
- Lecture 1 - Is computer science more than programming?
- If the answer isn't yes, this will be a short course.
- If it is yes, what else is there?
- Imperative Programming (Java)
- Functional Programming (Rex)
- Logical Programming (Prolog)
- Hey, isn't this all programming?
- How programming languages work
- Categorizing problems' difficulty
- Representing Information: Lists
- Implementing computers with logic and circuits
- Factorial, logs, binary numbers
- Lecture 2 - Lists in rex
- Recursive data structures
- Using recursion effectively to write functions
- Recursion, recursion, recursion!
- Open lists
- Trees and graphs as lists and their operations
- The no-side-effects paradigm
- Base Case (phew!)
- Assignment 0
- Warming up with Unix and Rex, the king of programming languages
- Lecture 3 - Recursion: putting the function in functional programming
- First-class objects
- Function composition
- Higher-order functions: some common examples
- Anonymous functions
- Rewrite rules as function definition
- Rewrite rules as computation in general!
- Lecture 4 - Higher-order functions
- Predicates as special functions
- Functions as special predicates
- More general entities: relations
- Functional decomposition of problems
- Assignment 1
- Tyrannosaurus Rex! -- lots o' rex programs (each only 1 line
long!)
- Lecture 5 - Techniques for implementing Rex functions
- Accumulators
- Recursion; tail recursion
- Tree search: BFS, DFS
- Lecture 6 - Advanced functional programming
- Guards: equational, conditional
- Laziness
- Infinite lists
- Currying
- Types
- Assignment 2
- Larger projects using Rex: Unicalc
- -- aka --
- Seven days to spaceship-saving software
- Lecture 7 - Object-oriented programming
- Java syntax review
- List implementation
- Open lists vs. closed lists: nature or nurture?
- References and pointers
- Lecture 8 - More Data Structures (Rex and Java)
- Stacks/Queues and variants
- Deep vs. shallow equality
- Virtual memory
- More references and pointers
- Assignment 3
- From rex to java: java's easier, right ? RIGHT ?
- Building an open list class
- Lecture 9 - Recursion in Java and Data structures
- Tail recursion
- Implementing recursion
- Open vs. closed lists
- Kinds of closed lists: stacks, queues
- Lecture 10 - Search
- Graphs, DAGs
- Breadth-first search
- Depth-first search
- McCarthy's transformation
- Assignment 4
- A bit of searching
- Recursion in Java: porting from rex
- Building a Java Queue
- Lecture 11 - The Object Oriented Paradigm: Inheritance
- Classes and objects
- Static vs. Nonstatic
- Interfaces
- Object state and methods for making transitions
- Mutability
- appropriate uses of class derivation: "is a" not "part of"
- Lecture 12 - Inheritance and overriding functions
- Dynamic dispatch
- Message metaphor; upcasting vs downcasting
- Polymorphism and container classes
- The java built-in hierarchy
- Virtual functions
- Applets
- The java GUI hierarchy
- Assignment 5
- Java search: building a mouse
- Implementing inheritence: the Deque
- Lecture 13 - Event-driven programming
- Graphics syntax and AWT
- Event listeners
- Event handling
- Double buffering
- Interfaces revisited
- Lecture 14 - Additional Java programming
- 2d arrays; matrices
- Breadth-first search, depth-first search
- using Deques
- Assignment 6
- Writing a full-fledged applet
- Lecture 15 - Implementation of programming languages
- Grammars as a specification tool for languages
- Inductive definitions
- More general notion of "language"
- General proof by induction
- Expression trees
- Precedence and associativity: tighter-binding functions
are closer further from the root
- Assignment 7
- EXAM (3/13 or 3/14)
- SPRING BREAK (3/15 - 3/24)
- Lecture 16 - Parsing of expressions + propositional logic
- Grammar generates; parser tests for membership
- Compilation steps: tokenize, parse, translate
- Parsing and recursive descent
- Propositional logic primitives: and, or, not, ...
- Lecture 17 - Propositional Logic in Java
- the
Expr class
- Abstract base classes
- more on parsing and recursive descent
- Assignment 8
- A logical parser in Java
- Using an inheritance hierarchy to distribute
an application's work.
- Lecture 18 - Do computers think logically?
- Propositional Logic revisited
- Boolean algebra
- Combinational functions
- Encoding sets in binary
- Two-term operators
- Completeness of nor
- Tautologies, satisfiability
- Lecture 19 - Manipulating and analyzing logical functions
- Minterm reduction
- Shannon expansions
- SOP == DNF representation
- Karnaugh maps
- Computing circuits
- "Don't cares" bits; LED example
- Assignment 9
- Solving SAT
- Extra credit for polynomial-time algorithms
- Lecture 20 - Predicate logic
- Variables representing individuals
- Quantifiers
- Graphs as binary relations -- equivalent to predicates
- DeMorgan's laws for quantifiers and simplifying expressions
- Representing problems as contraints: Prolog
- Lecture 21 - Programming in Logic
- Prolog and its syntax
- Computes variables within predicates
- Answering database queries
- Closed-world assumption and assumed quantifiers
- Examples: geneology, puzzle-like problems
- Solving problems without work!
- Assignment 10
- worksheet on Karnaugh maps
- Programs in prolog, e.g., restaurant-query example and
puzzle-solving examples.
- Lecture 22 - Prolog in earnest
- logical programming: how it works
- backtracking
- representing problems as sets of constraints
- Lecture 23 - Is this program correct?
- Program correctness: proving vs. debugging
- Program specification: states and transitions
- Assertions
- Loop invariants
- Proofs of correctness; assertion proofs
- examples
- Assignment 11
- prolog puzzles
- worksheet on program correctness
- Lecture 24 - Analyzing algorithms
- Sorting
- Program (profiler) vs. computational complexity
- Other possibilities: memory complexity
- Dependence on input size
- Counting steps: loops and recursion
- Writing and unrolling recurrences
- Growth rate and big-O definition
- Lecture 25 - Sorting and models of computation
- Comparison sorting is N*logN
- DFA and NFA
- P vs. NP
- Assignment 12
- worksheet on running time analysis
- coding: sorting in rex, java, and prolog
- Lecture 26 - Models for computers
- DFA NFA and regular expressions
- More generally, what languages are accepted by what machines
- Turing machines
- The halting problem
- which is a better model for a computer: FSM or TM ?
- Implementing finite state machines in logic
- Lecture 27 - More models for computers
- Implementing finite state machines in logic
- Clocks, flip-flops -- the whole machine!
- ISCAL
- Wrap-up
- Assignment 13
- JFLAP: building FSMs and TMs
- some more review of rex, java, and prolog
- Extra Credit Assignment
- Final Exam