For information about Web accessibility, please contact the Webmaster at webmaster@haverford.edu.

Haverford College

Computer Science

header image

CMSC 105: Introduction to Computer Science

Fall 2013, Prof. Sorelle Friedler



See the Class Google Calendar containing all due dates for this class. Also includes office hours.

See the Lab monitor calendar for times when there will be someone in the lab to help with your lab assignments.

The approximate topics as covered by week are given below. Specific topics covered can be found by looking through the class slides (a Google Directory only accessible when signed into a haverford.edu account). You can also look at the lab instructions by week.

  1. Vocabulary: computer science, problem instance, general problem, algorithm, computer.
    Problem examples: power, window overlap, pig latin, dinner party problem
    Concepts: input, precondition, postcondition, test cases and test suites, basic Python constructs / code
    Skills: interactive python, DocTest, running Python code in Eclipse
  2. Labs: Problems, Algorithms and Python Functions first lab due at the end of this week. Includes: power, circle overlap, tests for circle / rectangle overlap
    Problem examples: window overlap
    Concepts: basic Python constructs, functions, if statements, comparators, arithmetic operations, variables, choosing tests, Python indentation, user interfaces and the separation between UI and the rest of the code, tests for window overlap, recursion (and infinite recursion), doubles vs. ints, forms of input and output, parameters vs. return values
    Skills: writing DocTest tests, importing a library in Python, 1.0 vs. 1
  3. Labs: Design by Cases, Preconditions, and Postconditions second lab due at the end of this week. Includes: fibonacci, palindrome, and circle rectangle overlap implementation.
    Problem examples: pig latin
    Concepts: debugging techniques, preconditions, postconditions, string operations in Python, algorithm design, review answers to lab 1, algorithm design concepts (mathematical, top down, by cases, basic recursion), defining correctness, execution methods (substitution, in order).
  4. Problem examples: graph coloring
    Concepts: execution methods (substitution, in order / step-by-step), call trees, rewriting rules for substitution execution, variable scope, enumerate and test, defining correctness (tests, formal specification, progress), proofs
  5. Labs: Basic Recursive Design third lab due at the beginning of this week. Includes: design comments for fibonacci and palindrome, test suite for is_a_legal_coloring. Also, code reviews on the circle rectangle overlap problem for the next two weeks.
    Problem examples: dinner party problem
    Concepts: algorithm design (focusing on enumerate and test), create is_valid_party (as a model for the lab) in class.
  6. Labs: Formal Methods, Enumerate and Test algorithm design (part 1) fourth lab due at the end of this week. Includes: proof of strange_fib, is_a_legal_coloring.
    Problem examples: dinner party problem
    Concepts: algorithm design (focusing on enumerate and test and combining options), expressing inputs as parameters, variable scope, review for the midterm.
  7. Mid-semester break followed by the midterm exam.
  8. Problem examples: dinner party problem
    Concepts: example problem instances for lab coloring (as help for the lab) in class, advanced recursive design techniques, dinner party problem enumeration example done fully in class.
  9. Problem examples: dinner party problem
    Concepts: putting “enumerate” together with “test,” complexity
  10. Labs: Advanced Recursive Design, Enumerate and Test algorithm design (part 1) due at the beginning of this week.
    Concepts: more complexity
  11. Labs: Complexity Analysis lab six due at the beginning of this week.
    Problem examples: power
    Concepts: imperative paradigm: side effects, variable naming and scope, box and arrow diagrams for understanding variables in memory, loops, lists with row and column diagrams for understanding memory, python syntax for all of this, understanding when assignments change memory values or create new space.
  12. Labs: Imperative programming lab due mid week (before Thanksgiving). Includes: GCD, mouse and the maze.
    Concepts: side effects, returning within a loop, if if vs. if elif, debugging techniques, reasoning about imperative programs (SSA)
  13. Problem examples: fibonacci
    Concepts: basics of data structures (dictionaries), designing large programs.
  14. Concepts: numerical precision, arrays and matrices.
    Skills: numpy
  15. Labs: Genome lab.
    Concepts: review.