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
Gaining these skills is a large part of a computer science degree.
In this course, we begin the process, focusing on techniques for
specifying and correctly implementing computational solutions to
problems, and for reasoning about the use of computational resources.
- 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. Several
fundamental 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.
- Programming: You will learn to transform algorithmic ideas
into correct imperative programs, by specifying, 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 10:30am-noon in
Exley 139. 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 7pm-8:30pm in
Exley 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 10 one-week written assignments, due at the beginning
of lab (Wednesday, 7pm). If you cannot make lab for some reason,
you may drop the HW off at Dan's office, Exley 633.
There will be 8 programming assignments. For the first part of the
semester, programming assignments will be due on Wednesdays at
7pm, before lab.
There will be an in-class midterm and final exam.
Assessment
Your grade will be based on homework assignments
(50%), a midterm exam (20%), a final exam (25%), and lab/class
participation (5%). (Percentages are subject to change.)
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.
