CS200: Computer Science, Spring 2004
Course Objective. The goal of this course is to teach students with no prior experience in computing to think like computer scientists.
The course is designed to enable students to appreciate, use and understand ideas at the core of computer science. This course covers ideas that will be useful and interesting to students, whether or not they major in computer science.
Course Description. In the past hundred years, computer science has changed the world more than any other field. Without nuclear Physicists, World War II may have lasted longer, but without computer scientists the other side may have won. Without computer science, humans would not have walked on the Moon, modern medicine would not exist, and Wal-Mart would be a small store in Arkansas.
But this course is not about the pragmatic impact of computer science; it is about something even more fundamental: how computer science changes the ways we think, solve problems and understand the world. Despite its name, computer science has very little to do with the beige boxes we call computers, and it is far from being a science. It has more in common with music and mathematics than it does with science or engineering. At its core, computer science is the study of imperative knowledge. Whereas mathematics is all about declarative knowledge ("what is"), computer science is all about "how to" knowledge.
Computer science is the study of how to describe and predict properties of information processes. Most of what we know about describing information processes stems from three simple ideas:
Although these ideas are simple, they have profound implications that it takes many years to fully appreciate.
- You can define things in terms of themselves (recursive definitions).
- You can treat procedures and data as one and the same (first class procedures).
- When you give something a name, it becomes more useful (abstraction).
The kinds of properties we want to predict about information processes include whether or not there is a procedure that can always solve a given problem (computability), and how much time and space will be required to solve a given problem (complexity).
Expected Background: This course is open to students with no prior background in computer science or programming, but appropriate and challenging for experienced CS majors also. The only background we assume is:
- Language: reasonable proficiency in reading and writing English
- Math: understanding of whole numbers and addition, subtraction, multiplication, divison and exponentiation.
- Logic: familiarity with logicial and and or and not.
- Computer Literacy: ability to use email and browse the web.
Meetings: Mondays, Wednesdays and Fridays at 2:00-2:50 pm in MEC 341.
Books: There are two required books for this course:
We will not cover all of either book, but will cover most of Chapters 14 of SICP and most of Part I of GEB. There will also be a few additional readings.
- Structure and Interpretation of Computer Programs ("Wizard Book"), by Harold Abelson and Gerald Jay Sussman with Julie Sussman (referred to as SICP) [MIT Press] [Amazon]
- Gödel, Escher, Bach: An Eternal Golden Braid, by Douglas R. Hofstadter (referred to as GEB) [Amazon]
Web page: http://www.cs.virginia.edu/cs200. This page is updated often and students are expected to visit it regularly (almost every day). All lectures, notes and assignments for the course will be posted on the web site.
AssignmentsProblem Sets. There will be eight problem sets that involve both written questions and programming problems. Some problem sets will be done by small groups of students. For almost all students, doing the problem sets will be the best way to learn the course material.
The expected problem set due dates and topics (which are subject to change) are:
- Problem Set 1: Problem Solving (Art), due Wednesday, 21 January
- Problem Set 2: Programming with Procedures (Politics), due Monday, 2 February
- Problem Set 3: Programming with Data (Biology), due Wednesday, 11 February
- Problem Set 4: Review (Cryptography), due Monday, 16 February
- Problem Set 5: Programming with State (Economics), due Wednesday, 3 March
- Problem Set 6: Programming with Objects (Narrative), due Friday, 19 March
- Problem Set 7: Interpreting Languages (Physics), due Monday, 29 March
- Problem Set 8: Review (Dynamic Web Sites), due Monday, 26 April
Exams. There will be two exams during the semester and a final. All exams will be open book and open notes. All exams will be take-home unless I have any reason to believe there are any untrustworthy students in this class.
- Exam 1: out Friday, 20 February; due Monday, 23 February
- Exam 2: out Friday, 2 April; due Monday, 5 April
- Final: out Monday, 26 April; due Friday, 30 April
Collaboration PolicyYour fellow students are your best resource. Except on Exams which are done individually, students are encouraged to discuss readings and assignments in study groups. Some assignments may have a specific collaboration policy, which should be explained clearly on the assignment. If this is ever unclear, ask to make sure before proceeding.
Students are also encouraged to consult outside sources, including human experts. Always list the resources you used (students, outside experts, papers, web sites) on your submission. The only resource you may not use are CS200 problem sets from previous semesters. It is to your advantage for the course staff to be able to reuse effective assignments from previous semesters, and important that we can trust you to no abuse those materials.
All students are required to sign the course pledge, which applies to the entire course.
StaffCoach: David Evans
email@example.com phone x2-2218 (office), (434) 293-9688 (home) office Olsson, 236A office hours Wednesday after class - 4pm; Thursdays, 4-5pm; email to arrange other times.
Sarah Bergkuist (firstname.lastname@example.org)
Andrew Connors (email@example.com)
Patrick Rooney (firstname.lastname@example.org)
Katie Winstanley (email@example.com)
All the assistant coaches are undergraduate students who took CS200 (Sarah, Andrew and Patrick took it last year; Katie took it two years ago, and was an assistant coach last year).
The assistant coaches will be available in Small Hall to answer questions and help with problem sets during these times:
Note that the staffed lab hours are spread throughout the week. Lab hours the night before problem sets are due tend to be crowded, and ACs will not be able to provide as much help then. It is to your advantage to start assignments early, and take advantage of the staffed lab hours throught the week. The ACs should be very helpful to you during their posted lab hours, but please do not expect them to help you outside of those times. They have their own work to do too!
- Sundays: 4-5:30pm (Andrew), 5:30-7pm (Patrick)
- Mondays: 7-8:30pm (Katie)
- Tuesdays: 5-6:30pm (Andrew), 6:30-8pm (Sarah)
- Wednesdays: 7-8:30pm (Katie)
- Thursdays: 7-8:30pm (Patrick)
- Fridays: 3-4:30pm (Sarah)
Email: Send mail to firstname.lastname@example.org to reach the whole course staff.
EvaluationAll students who put an honest effort into all the assignments and convince me they have learned to think like a computer scientist by the end of the course will receive an A as a final grade.
For students who do not succeed in convincing me they can think like a computer scientist, grades will be based on approximately the following weighting:
Problem Sets 50 (40-70) Exam 1 10 (5-15) Exam 2 15 (10-20) Final Exam 25 (15-50) Class Contribution 0 (0-10)
Grades will be tabulated varying the weights assigned to each category in several different ways using the ranges above. Some of those weightings will drop the lowest problem set score. In general, the weighting that is best for you is used.
In my experience, students who have put effort into this class always do well. Spend your energy focusing on what you are learning, instead of worrying about your grade.
Using these Materials