Lectures: Tuesdays and Thursdays - 3:00-4:15 pm - Doolan Hall 219
Instructor: Philip Dorin - Doolan 102 - (310) 338-2832 - philip.dorin@lmu.edu
Secretary: Jacqi Davis - Doolan 101 - (310) 338-7351 - JaDavis@lmu.edu
Labs Manager: Andres Buritica - Doolan 104 - (310) 338-8100 - andres.buritica@lmu.edu
Laboratory Assistants: Doolan 114 (aka the Keck Lab). The Keck Lab is open variously from eight to twelve hours per day. (By the second week of the semester) you will find a schedule posted on the door. If the lab is open, there will be a lab assistant on duty.
The goal is to become familiar with some of the great ideas that have arisen from the science of computation, including algorithms, data structures, languages, efficiency, complexity, computability, numbers, codes, cryptography, artificial intelligence, human intelligence, and, of course, the machines themselves, to name but a few.
Lectures will be heavily sprinkled with puzzles, each of which is designed to motivate a topic du jour.
None.
There is no required book for this course. Many of the readings are available on the Web; several others will be distributed in class.
Expect, roughly, a new homework assignment each week; a mid-term exam (Thursday, October 22); and a final exam (2 pm, Tuesday, December 15). Among other things (and if time permits), you will be asked to:
try to solve lots of puzzles;
sketch some algorithms and make some small JavaScript programs;
read some famous papers that have to do with computation and cognition;
program a robot (the Lego Mindstorms NXT) or an avatar (in Second Life);
fool around with Google Docs and Wikipedia;
maintain a small website (well, really just the content)!
In evaluating the quality of your work, I will take into consideration your total course effort, including homework, midterm exam, and final exam, with emphasis on the exams.
Grades will be awarded as follows: for superior work, A; for good work, B; for satisfactory work, C; for poor work, D; for failing work, F. At the discretion of the instructor, these may be raised by a + or lowered by a -.
Regarding academic honesty and integrity, students are referred to the LMU Bulletin 2008-2010, specifically, the section dealing with the university's honor code and process.
Kindly turn off the ringer on your cell phone before class begins.
Music players, laptops, netbooks, etc., should not be used during class.
The contents of this syllabus are subject to change as necessary. You should periodically monitor this website to keep abreast of any changes, as well as posted homework assignments, hints, solutions, etc.
Introduction (the course is about some of the great ideas from computer science)... goal (how to think like a computer scientist)... modus operandi (puzzles). [9/1]
A greedy algorithm for making change with American-style coins... definition of algorithm. [9/3]
Making change with arbitrary type of coins... brute-force search... combinatorial explosion... how to determine whether greed will work (the one-point theorem). [9/8]
A brief history of computing- part I: to 1950. [9/10]
Map coloring... brute-force search... combinatorial explosion... backtracking. [9/15]
Distributing homework papers... performance of linear vs. binary search. [9/17]
Finite state machines... river-crossing puzzles... pouring puzzles. [9/22]
FSM's as models for cognition. [9/24]
a FSM solution to Sun-Tzu's puzzle... a proof that FSM's are not very powerful. [9/29]
A visit to the lab... creating a rudimentary web site. [10/1]
The command-line interface... remote copy (scp) and login (ssh). [10/6]
Introduction to programming... Java vs. JavaScript... some small programs. [10/8]
Another visit to the lab... a script for making change. [10/13]
More about JavaScript... discrete simulation... clock puzzles solved. [10/15]
Midterm review... exponential-time algorithms vs. intrinsically difficult (aka intractable) problems... PARTITION (special case of SUBSET SUM). [10/20]
Midterm exam. [10/22]
Digression: Statistical studies of baseball and thoroughbred racing. PRIMALITY has recently be shown to be tractable. [10/27]
SATISFIABILITY... CLIQUE... TRAVELING SALESMAN... NP-completeness. [10/29]
Greatest Common Divisors: Brute force vs. Euclid's algorithm. [11/3]
Number systems... counting on your fingers... unary vs. binary vs. ternary vs. decimal... converting among number systems. [11/5]
Algorithms for arithmetic in decimal and binary number systems... Russian Peasant Multiplication. [11/10]
Sets... comparing the sizes of sets... powersets... countably-infinite sets. [11/12]
Cantor's theorem... unsolvable problems... HALTING is not decidable... a poem after Dr. Seuss. [11/17]
W3C markup validation... the Internet... packet-switching... traceroute and ping... a YouTube video. [11/19]
[11/24]
[12/1]
[12/3]
[12/8]
[12/10]
Final exam. [12/15]
A ten-country map coloring puzzle (distributed in class). [9/10]
The Eight Queens puzzle (assigned during class). [9/17]
Two puzzles: (1) a river-crossing puzzle; (2) a pouring puzzle (assigned during class). [9/22]
Some historical articles and some problems about brute-force search. [9/29]
At the end of class, I asked you to complete the machine diagram for the river-crossing puzzle, but... never mind! I neglected to mention one aspect of the design that you need to know; I'll distribute a full solution on 9/24.
Sun-Tzu's puzzle. [9/29]
Read Daniel Dennett's Where Am I? [10/1]
More reading and some questions about finite-state machines. [10/13]
Two clock puzzles (assigned in class). [10/15]
Examine, and then run, this GeneralClockSolver script. You can copy/paste it into a JavaScript runner; or you can embed it in a new web page (using script tags); or you can embed a link to it from a new web page (again, using script tags); or, just navigate to GeneralClockSolver.html.
Some simple scripts and some readings on machine intelligence. [10/22]
Binary vs. decimal arithmetic. [11/10]
One more script, some questions about SUBSET SUM, and some more readings. [11/12]
Last revision: 10:40 on 19 November 2009
