Lab 15 Minute Rule: If no student shows up within the first fifteen minutes, that hour be canceled and the TA will leave.
Resources
Recommended supplemental textbooks are:
- Introduction to Computer Science by David Evans, Online at Udacity.
- Introduction to Computing: Explorations in Language, Logic, and Machines, by David Evans.
- Godel, Escher, Bach: an Eternal Golden Braid, by Douglas Hofstadter
- 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/cs1120. 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 cs1120-staff@cs.virginia.edu to reach the whole course staff.
Instructor:
- Westley Weimer (weimer@virginia.edu, phone x4-1021, Rice 423).
- In addition to my office hours, I am also available by appointment. Just send email.
Teaching Assistants:
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 CS1120. 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.
The problem set topics are:
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.
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.
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 Python 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.
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:
Collaboration Policy.
Your fellow students are your best resource. Except on Exams and some
Quizzes 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.
Assignments
Topics
Evaluation
| Problem Sets | 50 (40-70) |
| Exam 1 | 15 (10-20) | Exam 2 | 15 (10-20) | Final Project | 20 (10-30) | Class Contribution | 0 (0-10) |
Grades will be tabulated varying the weights assigned to each category in several different ways using the ranges above. For example, PS9 (the final project) is worth significantly more than the other problem sets.
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").
cs1120: Introduction to Computing: Explorations in Language, Logic, and Machines
Tuesdays and Thursdays, 3:30-4:45pm in Olsson 011
Mo 15:00-17:00 Stacks (J, L)
Mo 17:00-19:00 Olsson 001 (C, M)
Tu 13:00-15:00 Stacks (D, M)
We Noon-13:00 Rice 423 (Weimer)
We 13:00-14:00 Olsson 001 (C, J, M)
We 14:00-16:00 Olsson 001 (C, J, L)
We 16:00-17:00 Olsson 001 (C)
Fr 13:30-15:30 Olsson 001 (C, M, J)
Su 13:00-15:00 Olsson 001 (C, L)
Su 15:00-17:00 Olsson 001 (C, D)
Su 17:00-19:00 Olsson 001 (D, J)
Located in Thornton Stacks
or Olsson 001
or Rice 423 (We Noon-13:00)