# Introduction to Computer Science and Programming

Massachusetts Institute of Technology

This subject is aimed at students with little or no programming experience. It aims to provide students with an understanding of the role computation can play in solving problems. It also aims to help students, regardless of their major, to feel justifiably confident of their ability to write small programs that allow them to accomplish useful goals. The class will use the Python programming language.

• ##### Introduction and Goals of the Course
Eric Grimsom

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

• ##### Operators and Operands
Eric Grimsom

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

• ##### Common Code Patterns
Eric Grimsom

Common code patterns: iterative programs

• ##### Decomposition and Abstraction Through Functions
Eric Grimsom

Decomposition and abstraction through functions; introduction to recursion

• ##### Floating Point Numbers
Eric Grimsom

Floating point numbers, successive refinement, finding roots

• ##### Bisection Methods
Eric Grimsom

Bisection methods, Newton/Raphson, introduction to lists

• ##### Lists and Mutability
Eric Grimsom

Lists and mutability, dictionaries, pseudocode, introduction to efficiency

• ##### Complexity
Eric Grimsom

Complexity; log, linear, quadratic, exponential algorithms

• ##### Binary Search
Eric Grimsom

Binary search, bubble and selection sorts

• ##### Divide and Conquer Methods
Eric Grimsom

Divide and conquer methods, merge sort, exceptions

• ##### Testing and Debugging
Eric Grimsom

Testing and debugging

• ##### Knapsack Problem
Eric Grimsom

More about debugging, knapsack problem, introduction to dynamic programming

• ##### Dynamic Programming
Eric Grimsom

Dynamic programming: overlapping subproblems, optimal substructure

• ##### Introduction to Object-Oriented Programming
Eric Grimsom

Analysis of knapsack problem, introduction to object-oriented programming

• ##### Abstract Data Types Classes and Methods
Eric Grimsom

Abstract data types, classes and methods

Eric Grimsom

• ##### Computational Models
Eric Grimsom

Computational models: random walk simulation

• ##### Presenting Simulation Results
Eric Grimsom

Presenting simulation results, Pylab, plotting

• ##### Introduction to Digital Communication
Eric Grimsom

Course overview; what do computer scientists do?

• ##### Biased Random Walks
Eric Grimsom

Biased random walks, distributions

• ##### Monte Carlo Simulations
Eric Grimsom

Monte Carlo simulations, estimating pi

• ##### Validating Simulation Results
Eric Grimsom

Validating simulation results, curve fitting, linear regression

• ##### Normal, Uniform, and Exponential Distributions
Eric Grimsom

Normal, uniform, and exponential distributions; misuse of statistics

• ##### Stock Market Simulation
Eric Grimsom

Stock market simulation