{Latest update: 26 March 2010}


Course from MIT OpenCourseWare introducing the basic concepts of Computer Science and programming. Its aims are to provide with an understanding of the role of computation in solving problems, as well as a basic ability to write some small programs. The Python programming language is used as a tool during the class, both in order to illustrate the concepts and to write the programs.

This course is taught by Prof. Eric Grimson and Prof. John Guttag.

The general reference texts for this course are:

Additional information can be obtained from the course's homepage.

Lecture 1

Goals of the course; what is computation; introduction to data types, operators, and variables.

Goals of the course

Skills to develop:

  • Computational thinking.
  • Understand code.
  • Understand abilities & limits of computation.
  • Map problems into computations.

What is computation

  • What does it mean to think like a computer scientist?
  • What is computation? (As something independent from the actual computer)
  • What is knowledge?
    • Declarative: statements of fact.
    • Imperative: description of how to do something (recipe).

  • Heart of the computer: instructions and flow.
  • A program is a recipe.
  • Recipes are based on a set of primitives that can be combined in a sequence to accomplish something.
    • Fixed set of primitives can program anything.
    • What re the right primitives? (Turing's six primitives).
    • Programming language to describe the recipe.

  • Dimensions of a programming language:
    • High-level vs. low-level.
    • General vs. targetted.
    • Interpreted vs. compiled.
  • Syntax: what are the legal expressions in this language?
  • Semantics:
    • Static semantics: what programs are meaningful?
    • Full semantics: what does it mean?, what is going to happen when we run it?
  • Interpreter or compiler checks the syntax.
  • Interpreter or compiler also provides some help with static semantics.
  • No help with full semantics (wrong answer, crash, apparently correct answer...): programming style helps here.

Data types, operators and variables

  • Values:
    • Numbers: integers, floats...
    • Strings.
  • Operators: addition, subtraction, multiplication, division...
  • Variables: to store values.

Lecture 2

Operators and operands; statements; branching, conditionals, and iteration.

Handout (PDF).

Operators and operands

Elements needed when writing a program:

  • Representation for fundamental data (numbers, strings):
    • Value.
    • Type.
  • Instructions to manipulate that data (operands, operators):
    • Entered at the interpreter: evalued & printed.
    • From script: no print, unless explictly stated.

Overall concepts about operators and operands:

  • Overloading operators:
        >>> 3*'ab'
        >>> 3+'ab'
        Traceback (most recent call last):
          File "", line 1, in 
        TypeError: unsupported operand type(s) for +: 'int' and 'str'
  • Type conversion:
        >>> str(3)+'ab'
  • Type checking (weak vs. strong):
        >>> 'a'<3
        >>> 4<'3'
        >>> '4'<'3'
  • Type discipline when programming is very important.
  • Other peculiarities about operators (integer division in Python):
        >>> 9/5
        >>> 9%5
  • Operator precedence (when in doubt, use parenthesis):
        >>> 3+4*5
        >>> (3+4)*5
  • Ability to create variables via assignment statement:
  • Assigning a variable truly creates a pointer from the variable name to the location in memory that holds its value (link):
        >>> x=3*5
        >>> z=x
        >>> print x
        >>> print z
  • What is the type of a variable? Inherited from its value.
  • Python does dynamic typing:
        >>> x=3
        >>> print x
        >>> x='abc'
        >>> print x
  • Good style: don't change types arbitrarily.
  • Variables can be used any place it's legal to use the value.


  • Statements: legal commands that Python can interpret (print, assignment, etc.).
  • Advice for good programming style:
    • Commenting the code.
    • Good variable names (documentation of sorts).
    • Some variable names are excluded:
              >>> print='abc'
                File "", line 1
              SyntaxError: invalid syntax

Branching, conditionals, iterations

  • Branching programs: something that can change the order of instructions based on some test (value of a variable, usually).
  • Conditional:
  •     x = 15
        if (x/2)*2 == x: print 'Even'
          print 'Even'
        else: print 'Odd'
  • Boolean combinations (and, or, not): true or false.
  • Iterations or loops:
        itersLeft = x
           itersLeft = itersLeft - 1
           #print 'y =',y,',itersLeft=',itersLeft
        print y
  • Loops could lead to infinite loops:
    • They have to involve a variable that is changing.
    • The variable needs to be initialized outside the loop.

Lecture 3

Common code patterns: iterative programs.

Handout (PDF)



Numbers +,-,*,/ Assignment
Strings   Input/Output
Boolean AND, OR Conditionals
    Loop mechanisms

Good programming practices:

  • Use comments to document code.
  • Type discipline: check types of operands.
  • Descriptive use of variable names.
  • Testing all branches through a piece of code.

Iterative programs

Elements of iterative programs:

  • Choose a variable that is going to "count".
  • Initialize it outside of a loop.
  • Set up end test (how do we know when we end with the loop).
  • Construct the block:
    • Change variable within the block.
  • What to do when I am done.


  • Flow charts:
  • Simulate the program (calculations) manually.
  • Defensive programming:
    • Always check the loop terminates.
    • Confirm that it always prints a logical answer.
    • Always check user-provided input.
    • Assume that other parts of the program may make a mistake (write tests into the code).

Exhaustive enumeration:

  • Try all reasonable values until you find the answer.

For loop:

  • To go through a given collection of items.
  • No need to explictly update the counter variable: it guarantees that the loop will terminate.
        x = 10
        for i in range (1,x):
          if x%i == 0:
            print 'divisor ',i

Tuple: ordered sequence of elements (inmutable):

>>> test = (1,2,3,4)
>>> test
(1, 2, 3, 4)
>>> test[0]
>>> test[1]        # selecting
>>> test[10]
Traceback (most recent call last):
  File "", line 1, in 
IndexError: list index out of range
>>> test [-1]
>>> test [-2]
>>> test [1:3]      # slicing
(2, 3)
>>> test [:3]
(1, 2, 3)
>>> test [2:]
(3, 4)

Tuples can be concatenated:

x = 100
divisors = ()
for i in range (1,x):
  if x%i == 0:
  divisors = divisors + (i)

Strings also support selection and slicing:

>>> s1 = 'abcdefg'
>>> s2 = 'hijklmn'
>>> s1
>>> s1[0]
>>> s1+s2
>>> s1[2:4]
>>> s1[:5]

All this makes it possible to manipulate strings:

sumDigits = 0
for c in str(1952):
  sumDigits += int (c)
print sumDigits

These tools also make it possible for us to use the set of commands from the table above to compute anything that can be expressed in an algorithm (the concept of a Turing machine).