## 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.