COMP 211: Principles of Imperative Computation

Objectives

This course is an introduction to computer science, focusing on the following skills:

• Computational Thinking [Wing, 2010]: You will learn to formulate problems and their solutions so that they can be solved by a computational agent. Computational thinking draws on both mathematical thinking and engineering thinking. It has already had tremendous impact on science and engineering, and has begun to influence areas beyond them, such as medicine, archeology, economics, finance, journalism, law, social science, and political science. Computational thinking involves being able to
  • understand what aspects of a problem are amenable to computation
  • reformulate problems to be amenable to computation
  • evaluate the match between computational tools and techniques and a problem
  • understand the limitations and power of computational tools and techniques
  • apply or adapt a computational tool or technique to a new use
  • recognize an opportunity to use computation in a new way
  • explain problems and solutions in computational terms
  • ask new questions that were not previously considered because of scale
  • apply computational strategies to many domains
  • make new discoveries through the analysis of large data
  This course will begin the process of acquiring these skills, which is a high-level goal a computer science degree.
• Algorithms: You will learn to design and analyze algorithms for solving computational problems. Specific knowledge includes: Common algorithmic patterns, such as divide-and-conquer, randomized algorithms, and self-adjusting data-structures. Basic ideas of time and space algorithm analysis, such as big-O notion, common complexity classes, the distinction between worst- and average-case analysis, and amortized analysis.
• Specification and Verification: You will learn to specify the intended behavior of programs and prove their correctness. Programs will specified using contracts consisting of pre- and post-conditions and loop invariants. You will learn to prove that contracts are satisfied statically (when you write the program), and also to use dynamic checking of contracts (when you run the program) to debug.
• Programming: You will learn to transform algorithmic ideas into imperative programs, by writing, testing, and debugging code. You will gain some familiarity with the C programming language, which is an imperative language that is relatively close to the machine. We will use a teaching-oriented subset of C called C0, which supports reasoning via contracts.

Activities

There will be two lectures per week, Tues-Thurs 1:10pm-2:30pm in Exley 141 or 2:40pm-4pm in Hall-Atwater 84. This time will be used for chalk-board lectures, for interactively coding as a whole class, and possibly for small-group or individual work. Lectures will be your primary source of information for the course, and attendance is strongly encouraged.

There will be weekly lab sessions held on Wednesday 6pm - 7:30pm and 7:30pm-9pm in Exley 72/74. These sessions are required and may be used as follows: for you to work on warm-up problems with the course staff's assistance, for presentations of additional material to reinforce the lectures, and for you to work on assignments and ask questions.

There will be weekly written and programming assignments, due at the beginning of your lab on Wednesday (unless otherwise specified). If you cannot make lab for some reason, you may drop the HW off at Dan's office, Exley 633.

There will be an in-class midterm and final exam.

Assessment

Your grade will be based on homework assignments (60%), a midterm exam (15%), a final exam (20%), and lab/class participation (5%). (Percentages are subject to change.) Generally, 90%-100% should be interpreted as A work, 80-90% as B, 70-80% as C, 60-70% as D, and below that as failing. However, the instructor may tune the final letter grade boundaries (in either direction) at the end of the semester, to account for differences between the intended and actual difficulty of the assignments. Assignments may be graded for correctness, clarity, and efficiency.

Credits

This course is adapated from Carnegie Mellon University's 15-122, designed by Frank Pfenning, William Lovas, Tom Cortina, Rob Arnold, Rob Simmons, Andre Platzer, and others.