## CMSC 105: Introduction to Computer Science

### Fall 2014

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.

- 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

- 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

- 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). - 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 - 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. - 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. - Mid-semester break followed by the midterm exam.
- 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. - Problem examples: dinner party problem

Concepts: putting “enumerate” together with “test,” complexity - Labs: Advanced Recursive Design, Enumerate and Test algorithm design (part 1) due at the beginning of this week.

Concepts: more complexity - 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. - 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) - Problem examples: fibonacci

Concepts: basics of data structures (dictionaries), designing large programs. - Concepts: numerical precision, arrays and matrices.

Skills: numpy - Labs: Genome lab.

Concepts: review.