UNIVERSITY AT BUFFALO - STATE UNIVERSITY OF NEW YORK
The Department of Computer Science & Engineering

CSE 111 : GREAT IDEAS IN COMPUTER SCIENCE Fall 2004

SYLLABUS

The themes of the course are algorithmic problem solving and the nature of computation. You will gain an appreciation for some of the most interesting and significant results of computer science, as well as its intellectual and social significance. The course has both a mathematical and laboratory component. Topics include some or all of: representation of information, algorithm design, introduction to structured programming, numerical computation, computability, and artificial intelligence.

This course is designed to help satisfy the General Education requirements for both the UB/SUNY Requirements in Mathematical Sciences and Knowledge Area Requirements in Mathematical Skills.

• There are no prerequisites, since CSE 111 is designed for students with no previous background in computing.

• If you have had some experience in programming a computer (e.g., a high-school course in Basic, Pascal, C, C++, Java, etc.),
  or if you would eventually like to take more advanced courses in computer science,
  
  then you should take CSE 113 (Introduction to Computer Programming I)
                                     or CSE 115 (Introduction to Computer Science for Majors I)
  
  instead of CSE 111.
  • Either of CSE 113 or CSE 115 is the prerequisite for all further computer-science courses, as well as the computer-science and computer-engineering majors.
  • Students who successfully complete CSE 111 can certainly take CSE 113 or CSE 115 in the future.

• In short, CSE 111 is NOT for students who want to "learn about computers" WITHOUT programming (because we will be doing some programming in this course).
• It is also NOT for students who want to be computer-science or computer-engineering majors or who really want to learn how to program computers (because we will only be doing a little programming and not learning all there is to know about programming).

• If you want to learn about computers without programming, take CSE 101 (Computers: A General Introduction).
• If you want to learn how to program, take either CSE 113 or CSE 115.
• If you want to learn about algorithmic problem solving and the other great ideas of computer science (or if you just want to satisfy the math requirements without taking a "math" course (:-), then do take CSE 111.

STAFF:

Professor:
Dr. William J. Rapaport, 214 Bell Hall, 645-3180 x 112, rapaport@cse.buffalo.edu
Office Hours: Tuesdays, 2:00-2:50 p.m.; Fridays, 1:00-1:50 p.m.; or by appointment.

Teaching Assistants:

• Mr. Sripathi ("Raj") Guruprasannaraj, Bell 329, 645-5084 x 15, sg47@cse.buffalo.edu
  Office Hours: Mondays, 2:00-2:50 p.m.; Tuesdays, 3:30-4:30 p.m.; or by appointment.

• Mr. Denis Mindolin, Bell 329 645-PHONE, mindolin@buffalo.edu
  Office Hours: Mondays, 10:30-11:30 a.m.; Wednesdays, 1:30-2:30 p.m.; or by appointment.

• Ms. Lopamudra ("Lopa") Mukherjee, Trailer B, Desk 11, 645-3772, lm37@cse.buffalo.edu
  Office Hours: Mondays, 9:00-9:50 a.m.; Wednesdays, 11:00-11:50 a.m.; or by appointment.

  Note: Trailers A and B are between Furnas Hall & Ketter Hall.

1. Hillis, Daniel (1998), The Pattern on the Stone: The Simple Ideas that Make Computers Work (New York: Basic Books).

2. Pattis, Richard E.; Roberts, Jim; & Stehlik, Mark (1995), Karel the Robot: A Gentle Introduction to the Art of Programming, Second Edition (New York: John Wiley & Sons).

IMPORTANT DATES & TENTATIVE SCHEDULE:

Note: I have adjusted some of the information below to reflect what we actually did in class, rather than on what I had hoped to do:-)

DAY	MONTH	DATE	TOPIC	READING
M	Aug	30	Introduction	Hillis, pp. vii-xi, 1-6
W	Sep	1	Introduction: What is computer science? What is an algorithm?	Hillis, pp. 6-16
F		3	What is a computer? 4 Great Ideas of CS Great Idea I: Binary Representation	Hillis, pp. 16-28
M		6	Labor Day: NO CLASS
W		8	Binary Numerals	Hillis, pp. 28-38
F		10	Binary arithmetic;	Hillis, pp. 39-50
W		15	Binary representation of sound; Physical interpretation of binary codes	Do the first 2 pages of: either Waner & Costenoble 2001: [Page 1] [Page 2] or Wintergerst & Zschornak 2001: [Page 1] [Page 2]
F		17	Physical interp'n of bin. codes (cont'd); Binary rep'n of meaning: Propositional logic	Read 1 or more of the links on Propositional and Boolean Logic
M		20	Propositional logic: Truth tables	"Turing Machines" [PDF]
W		22	Truth tables (cont'd); Do we really only compute with numbers?	no new reading
F		24	Great Idea II: Turing Machines (at last!)	no new reading, but continue studying the TM article assigned on Sep 20.
W	Oct	13	Review for Midterm Exam
F		15	***** MIDTERM EXAM *****
M		18	Great Idea III: Boehm & Jacopini's Theorem	Karel, pp. 1-11 (§§1.1-2.4.1)
W		20	Review of Midterm Exam	Karel, pp. 11-24 (§§2.4.2-2.7)
F		22	Last R date Karel the Robot (algorithmic problem solving)	Karel, pp. 25-34 (§§3.1-3.6)
M		25	Karel (cont'd)	Karel, pp. 34-43 (§§3.7-3.8.1)
W		27	Karel (cont'd)	Karel, pp. 43-53 (§§3.8.2-3.8.3.4)
F		29	Karel (cont'd)	Karel, pp. 53-63 (§§3.9-3.11)
M	Nov	1	Karel (cont'd)	Karel, pp. 65-74 (§§4.1-4.3)
W		3	Karel (cont'd)	Karel, pp. 74-81 (§§4.4-4.7)
F		5	Karel (cont'd)	Karel, pp. 81-91 (§§4.8-4.10)
M		8	Karel (cont'd)	Karel, pp. 93-100 (§§5.1-5.2)
W		10	Karel (cont'd)	Karel, pp. 100-111 (§§5.3-5.4)
F		12	Karel (cont'd)	Karel, pp. 112-120 (§§5.5-5.7)
M		15	Karel (cont'd)	Karel, pp. 121-127 (§§5.7-5.8)
W		17	Karel (cont'd)	Karel, pp. 128-139 (§5.9)
F		19	Karel (cont'd)	Karel, pp. 141-145 (§6.1)
M		22	Karel (cont'd)	Karel, pp. 145-151 (§§6.2-6.3)
W		24	Thanksgiving: NO CLASS
F		26	Thanksgiving: NO CLASS
M		29	Karel (concluded)	Hillis, Ch. 4: TMs & beyond
W	Dec	1	What can't be computed: the Halting Problem	Hillis, Ch. 5: algorithms vs. heuristics
F		3	Karel the Robot as a Turing machine	Hillis, Ch. 6: coding
M		6	Can cognition be computed? Artificial Intelligence	Hillis, Ch. 7: parallel computation
W		8	Artificial Intelligence (cont'd)	Hillis, Ch. 8: AI
F		10	Last Class: SUMMARY	Hillis, Ch. 9: computers & brains
Sat		11	Reading Day
Sun		12	Reading Day
M		13	Exam Week Begins
F		17	*** Final Exam *** 3:30-6:30 p.m. Knox 104
M		20	Exam Week Ends

• "Teachers open the door, but you must enter by yourself." -- Chinese Proverb
  "You can lead a horse to water, but you can't make him drink." -- American Proverb

• The readings from the Hillis book (it's not a textbook, but a book aimed at a general audience) may not always exactly match our lectures, but they will supplement them.

• We will follow the Karel text fairly closely (this one is a textbook, complete with exercises).

• I will give more specific reading assignments in class.

• For advice on how to slowly and actively read (a computer science text), see "How to Read (a Computer Science Text)".

1. You will be expected to attend all lectures and labs (attendance will be taken in labs and will count towards your final grade), and to complete all readings and assignments on time. There will be regular homework assignments, a midterm exam, and a final exam (during exam week). Taking both the exams is a necessary condition for passing the course.

2. Homeworks:
   1. All homeworks will be announced in lecture. Therefore, be sure to get a classmate's phone number or email address (for instance, 1 or 2 people sitting next to you in class, whoever they are!), so that you will not miss assignments in the unlikely even that you miss a class.

   2. HW assignments will be of two types:
      1. Some will be of the "paper-and-pencil" variety, to be done at home.

      2. Others will be lab exercises that will involve you in designing algorithms, cod ing them in a programming language, and running, testing, and debugging the programs on the PCs. Lab exercises will normally be done in the labs or public sites on your own time, though some of them may be done in your lab section, and you will have to do the preliminary design of them at home. The programs you will be asked to write will be relatively short and will be chosen to illustrate particular techniques or issues.

      3. You can use your own laptop for much of the work; most of the software is freely downloadable from the Web. Besides your lab, PCs are available in Baldy 210, UGL, SEL, Lockwood, and perhaps elsewhere. (For many applications, you can also use UBUnix machines directly, if you know how.) For a complete listing of public sites, see the "CIT Public Computing" webpage.

   3. The purposes of homeworks are:
      • to give you hands-on experience with relatively small problems and to give you hands-on experience in designing, coding, testing, debugging, and documenting programs
      • to give you practice in applying the concepts covered in the course
      • to give you a chance to assess the level of your understanding

   4. There will be approximately 1 HW each week. Some of them may be time-consuming (but fun, I hope!). You should plan to spend at least an hour or two each week at the computer.

   5. Late Policy:

      Due dates will be announced in lecture when the homework is assigned. HWs will be collected at the start of lecture on the due date. This is so that the homework can be discussed in the class period when it is due.

      If they are turned in after the start of lecture, your grade will be discounted by one full letter grade (e.g., A becomes B, A- becomes B-, etc.).

      If they are turned in after the start of the next lecture, your grade will be discounted by two full letter grades (e.g., A becomes C, A- becomes C-, etc.).

      If you turn in a HW after the start of the class after that, your grade will be discounted by three full letter grades (e.g., A becomes D, etc.).

      No HWs will be accepted after that.

   6. Put your full name, date, and your lab (L1, L2, etc.) at the top right-hand side of each page, and secure all pages with a staple in the top left-hand corner.

   7. Note: The lowest homework grade will be dropped; you should assume that you will fail to turn in one homework (oversleep, get stuck in traffic, etc.)--that's the one that will be dropped. If you know now that you will regularly be late, see me to make alternative arrangements for turning in your work. Your graded HW will be returned in lab. Occasional extra assignments or quizzes from lab can be used to replace low HW grades, at your TA's discretion.

3. There will be other assignments and quizzes in labs.

4. Email list:

   You will automatically be placed on an email list (a "listserv") for the course. If you do not normally read email at the email address that UB has as your official address, please either do so for this course, or else have your mail forwarded. I will use this list as my main means of communicating with you out of class, and you can use it to communicate with the rest of us.

   You may send questions and comments that are of general interest to the entire class using the listserv: Just send them to:

   cse111-fa04-list@listserv.buffalo.edu

   You can also send email just to me, at:

   rapaport@cse.buffalo.edu

   In any case, be sure to fill in the subject line, beginning with "CSE 111:" so that my mailer doesn't think it's spam.

   If you send email to me that I deem to be of general interest, I will feel free to remail it anonymously to the email list along with my reply unless you explicitly tell me otherwise.

   I will archive the emails at http://www.cse.buffalo.edu/~rapaport/111F04/email.txt.

5. Just as you cannot expect to learn how to drive a car by reading about it or by watching other people do it, the same holds true for doing computer science. Do your work on time--this is one course you simply cannot cram for at the last minute, so don't even try! I cannot stress this strongly enough. Homeworks and lab exercises may be fairly time-consuming, so please consider your other commitments, and plan your time accordingly.

6. You should notify Prof. Rapaport within the first two weeks of class if you have a disability which would make it difficult to carry out course work as outlined (requiring note-takers, readers, extended test time, etc.).

For further information on my philosophy of grading, see my web document on "Grading Principles"

Incompletes:

For more information on Incomplete policies, see the web page, "Incompletes".

ACADEMIC INTEGRITY:

CLASSROOM DISRUPTIONS:
In large classes (such as this), students have been known to be disruptive, either to the instructor or to fellow students. The university's policies on this topic, both how the instructor should respond and how students should behave, may be found in the document "Obstruction or Disruption in the Classroom - Policies". (Also here.)