- Language: reasonable proficiency in reading and writing English
- Math: understanding of whole numbers and addition, subtraction, multiplication, division and exponentiation.
- Logic: familiarity with logical and and or and not.
- Computer Literacy: ability to use email and browse the web.
Meetings: Mondays and Wednesdays from 3:30 to 4:45 in MEC 341.
Structured Lab Hours: There are also Structured Lab Hours on Wednesdays from 7:00-8:00pm and from 8:00-9:00pm in OLS 001. During those hours the OLS 001 lab is reserved for CS 150 students only. The TAs will answer questions and re-explain lecture material, and then help you with your problem sets and assignments. Attendance is not required at Structured Lab Hours, but attending one of them each week will be of great benefit to you.
Office & Lab Hours: Beyond the Structured Lab Hours, there are 3 Staffed Lab Hours each week (in the Small Hall Computer Lab) and 4 Office & Lab Hours each week (in the Small Hall Computer Lab or OLS 219). See the Panel on the Left for the exact hours. During Staffed Lab Hours, a TA and signup sheet will be available in the Lab and the TA will answer programming, homework and conceptual questions. Office & Lab Hours are similar, except that priority will be given to conceptual and textbook question. If there are no such questions, Office & Lab Hours work just like Staffed Lab Hours.
Sunday Lab Hour: We will run a lab hour on Sunday (as indicated on the Panel on the Left), but only on weeks when students ask for it. In particular, each week any student may start a thread on the Discussion Forum requesting that a lab hour be held on Sunday. If, by Midnight that Friday, at least 5 different students post on the thread and indicate that they will be present, then we will host the hours on Sunday. This requires you to plan in advance, but you're up to the challenge.
Lab 15 Minute Rule: If no student shows up within the first fifteen minutes, that hour be canceled and the TA will leave.
Resources
- Computational Thinking: A Whirlwind Introduction to the Third Millennial Liberal Art from Ada and Euclid to Quantum Computing and the World Wide Web, by David Evans (free!)
- Gödel, Escher, Bach: An Eternal Golden Braid, by Douglas R. Hofstadter (referred to as GEB)
A recommended supplemental textbook is:
- Structure and Interpretation of Computer Programs, by Harold Abelson and Gerald Jay Sussman with Julie Sussman (free! referred to as SICP or the Wizard Book)
Web page: http://www.cs.virginia.edu/cs150. 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.
Email: Send mail to cs150-staff@cs.virginia.edu to reach the whole course staff.
Instructor:
- Westley Weimer (weimer@virginia.edu, phone x4-1021, Olsson 219).
- My office hours will be Tuesday 11:00-12:00 in Olsson 219. I am also available by appointment; just send email.
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 problem sets from previous semesters of CS150. 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.
Assignments
The expected problem set due dates and topics (which are subject to change) are:
- Problem Set 0: Functions (Mars), due 15 January
- Problem Set 1: Problem Solving (Photomosaics), due 26 January
- Problem Set 2: Programming with Data (Poker), due 2 February
- Problem Set 3: Programming with Procedures (Fractals), due 11 February
- Problem Set 4: Review (Cryptography), due 18 February
- Problem Set 5: Programming with State (Economics), due 11 March
- Problem Set 6: Programming with Objects (Narrative), due 25 March
- Problem Set 7: Interpreters (Computer Science), due 6 April
- Problem Set 8: Dynamic Web Sites (Communities), due 13 April
- Problem Set 9: Project (Dynamic Web Site), due 04 May
Unless noted otherwise, problem sets are due at the beginning of class (3:30pm) on the day they are due.
Quizzes. There may be several short in-class quizzes throughout the semester. These may or may not be announced in advance. Except in unusual circumstances, these will have no effect on your grade. Instead, they are used to allow us to determine if important concepts have been understood throughout the semester. If you make a serious effort on all quizzes, your overall quiz grade will be the maximum of your individual quiz grades.
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 Monday, 23 February, due Wednesday, 25 February
- Exam 2: out Wednesday, 15 April, due Monday, 20 April
- Final: out Thursday, 30 April, due as required by COD
Topics
Be able to identify the primitives, means of combination, and means of abstraction for a language; describe a language using BNF or RTN; determine the set of the surface forms in a language described by a BNF grammar or RTN; determine what a surface form in a language means if you are given evaluation rules for the language; determine the value of a Scheme expression following the rules of evaluation.
Recursive Definitions
Understand a recursive definition; solve a problem by defining a procedure recursively; reason about the process produced by evaluating an application of a recursively defined procedure; define and understand procedures that take procedures as parameters; define and understand procedures that produces procedures as results.
Programming with Lists
Define procedures that manipulate lists, use and understand procedures that traverse lists.
Programming with Mutation and Objects
Define and understand procedures that use mutation; draw environment diagrams; explain what environment diagrams mean; define procedures that create objects; explain a class hierarchy; define procedures that use inheritance; explain how a method is selected given class definitions.
Metalinguistic Abstraction
Understand an evaluator; modify and evaluator to change the meaning of a language; explain why the difference between eager and lazy evaluation matters; explain the advantages and disadvantages of static type checking; understand an evaluator that does static type checking.
Programming for the Internet
Measure the latency and bandwidth of a network; explain the advantages and disadvantages of packet switching; make a dynamic web site; construct a SQL command to select or insert data in a database table; learn a new language given a BNF grammar and an informal description of its evaluation rules.
Measuring Complexity
Describe problems precisely in terms of their inputs and outputs; express the amount of work a procedure requires using Theta notation; describe a problem using O, Omega, Theta; estimate the amount of work a solution to a problem involves; classify problems into complexity classes P and NP; explain convincingly what a problem is in NP; explain what it would mean if someone developed a fast (polynomial time) procedure for an NP-Complete problem.
Computability
Explain what it means for an axiomatic system to be perfect, incomplete or inconsistent; explain the essence of Godel's proof; determine if a problem is decidable or undecidable, and provide a convincing (informal) argument why.
Models of Computation
Explain how to model computation; understand a finite state machine description and explain what it does; understand a Turing Machine description and explain what it does; explain if a problem can be solved by a finite state machine (or why it cannot); define a Turing Machine that solves a simple problem; reduce a Lambda Calculus term to normal form; create and manipulate Lambda Calculus terms that represent true, false, if, numbers and lists; show that a computing model is (or is not) capable of modeling any mechanical computation.
Evaluation
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 | 15 (5-15) |
Exam 2 | 15 (10-20) |
Final Exam | 20 (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. We will drop the lowest Problem Set Grade (one Problem Set Grade = Written + Coding for that Problem Set). In general, the weighting that is best for you is used.
Spend your energy focusing on what you are learning, instead of worrying about your grade. Although the material we cover is challenging, and the pace may seem overwhelming at times, historically all students who put effort into this class have done fine. Although not everyone will succeed, all students are expected to get an A in the course. Students who do outstanding work in the course will be considered for funded summer research positions in Prof. Weimer's research group.
Late Policy: The most important aspect of completing the assignments is that you eventually understand the material. One of the ways we help you to understand the material is to give you prompt feedback on your work. To be fair to all students, you should turn your work in on time. Late work will typically receive at least a 10% penalty per day, and will not be accepted after we have gone over the assignment in class or distributed an answer key. Note that the automatic adjudication grade summary may not show the points deducted from a late assignment (although it will show the dates).
Holding Policy: If we correct your work and you do not pick up the annotated copy promptly, we may mark down your grade (sometimes called a "holding fee").
cs150: Computer Science
from Ada and Euclid to Quantum Computing and the World Wide Web
Instructor
Westley Weimer
Teaching Assistants
Zak Fry
Paul DiOrio
Rachel Lathbury
Email Address
cs150-staff@cs.virginia.edu
Mondays and Wednesdays, 3:30-4:45pm in MEC 341
Wednesdays, 7:00-8:00pm and 8:00-9:00pm in OLS 001
(Small Hall Lab)
Monday 5:00-6:00 (Zak)
Tuesday 3:15-4:15 (Rachel)
Thursday 5:00-6:00 (Paul)
Sunday 3:00-4:00 (on request)
(Small Hall Lab)
Monday 2:00-3:00 (Rachel)
Tuesday 11:00-12:00 (Wes in Olsson 219)
Tuesday 3:00-4:00 (Zak)
Wednesday 1:00-2:00 (Paul)