ULTIMATE REVIEW: MIT: Introduction to Computer Science and Programming in Python

What Does a Computer do?

A computer fundamentally performs (built-in/primitive and personally defined) calculations and stores the results, but only knows what to do when told.

Declarative Knowledge

statements of fact that computers do not know how to handle

Imperative knowledge

a recipe or “how to” (sequence of steps)

Recipe

1. Sequence of simple steps

2. flow of control process that specifies when each step is executed (different decisons, repeating.)

3. a means of determining when to stop

*Overall an ALGORITHIM

Fixed Program computer

machines with only one function

Stored program computer

Sequence of instructions stored inside the computer, built from a predefined set of primitive instructions. Has a special program (interpreter) that executes each instruction in order (uses tests to hcange flow of control of sequence)

1) arithmetic + logic operations

2) simple tests (equality/inequality statements)

3) moving around and/or storing data

Basic Machine Architecture

4 main parts; goes linearly/step-by-step unless there’s a test that may change the sequence (control flow)

6 Basic Primitives

Instructions/commands that Alan Turing (Great computer scientists) stated can be used to compute anything with.

1. Move left

2. move right

3. read

4. write

5. scan

6. do nothing

Expressions

complex but legal combinations of primitives (objects + operators) in a programming language that have values and meanings in a programming language;

Primitive Constructs in Python

• Floats

• Booleans

• Strings

• Simple Operators

Syntax of Programming Languages

Bad = number word; Good = operator, operand, operator

Semantics

the meaning associated with a syntactially correct string of symbols with no static semantic errors

Syntax/ Syntactic Errors

Common and easily caught by Python

Static Semantic Errors

can be caught by Python if program has some decisions to make and goes down the path where error happens. Some languages check for these before running program. Can cause unpredictable behavior

no semantic errors but different meaning than what programmer intended

most frustrating; program crashes, stops running; program runs forever; program gives an answer but different than expected

program

a sequence of definitions/expressions that are evaluated and commands that are executed

commands (statements)

instruct interpreter to do something; can be typed directly in a shell or stored in a file that is read into the shell and evaluated

Objects/ data objects

what everything is in Python; programs manipulate these; all have a type that defines the kinds of things programs do to them

Scalar Object

very basic objects in Python form which everything can be made; cannot be subdivided; int, float, bool, NoneType

int

represent integers (all whole numbers like 5)

float

represent real numbers (anything with a decimal like 3.27)

bool

represent Boolean values True and False (needs capital T and F!)

NoneType

special and has one value, None; represents the absence of a type

type()

special command used to see the type of an object

Non-Scalar Objects

have some internal structure and can be subdivided (ex. list of numbers)

int → float

float (#) converts integer # to float #.0

float → int

int (#.#) truncates (takes decimal away without rounding) float #.# to integer #

print ()

command used to show output from code to a user

syntax for a simple expression

<object> <operator> <object>

i + j

the sum (addition)

i - j

the difference (subtraction)

i * j

the product (multiplication)

i / j

the quotient/division (result is always float no matter what)

Result of addition, subtraction, and multiplication

if both are ints, result is int. if either or both are floats, result is float (object type of result depends on both variable types)

i % j

modulus operator; the remainder when i is divided by j

i ** j

exponentiation operator; i to the power of j

Simple Operations

Arithmetic operations in Python are done in PEMDAS order (parentheses, exponents, multiplication, division, addition and subtraction (depends on which is first left to right))

equal sign (=)

an assignment of a value to a DESCRIPTIVE variable name; assigns right to left

Why give names to values of expressions?

To reuse names instead of values which makes it easier to change code later and makes code look nicer

Programming vs Math

in programming, you do not “solve for x” (computer needs formulas/steps to solve)

Changing bindings

can re-bind (change value of a variable) variable names using new assignment statements; previous value may still be stored in memory but is useless.

Strings

object type; sequences of any character (letters, special characters, spaces, digits); enclose in quotation marks or single quotes (doesn’t matter as long as your consistent); can do some operations as defined in Python docs such as multiplication (repeats string # of times)

Concatenate strings

put strings together with "+” ; doesn’t implicitly add spaces between variables (need to insert space manually)

,

automatically adds a space between two things (not everything needs to be a string)

+(concatenation)

no spaces; combines strings together into one big string; all things need to be strings

input (““)

prints whatever is in the quotes; user types in something (default given will be a string) and hits enter; binds that value to a variable

int (input(““)

casts string into a integer (can do arithmetic operations)

i >, <, <=, >=, j

comparison operators used on integers, floats, and strings that evaluate to a Boolean (True or False)

i == j

equality test; True if i is the same as j

i != j

inequality test, True if i is not the same as j

Comparison Operator Rules

Can compare: integers with integers, floats with floats, strings with strings (lexographically, a-z), and floats with integers, but CANNOT compare strings with numbers (floats/integers)

not

logic operator that inverts True or False values

and

Logic operator; needs both conditions to be True to have a True value overall

or

Logic Operator; needs at least one condition to be True to have a overall True value

if statement only

checks if condition is True (executes if code block) or False (keep going through code without executing if code block)

if statement and else statement

either executes if statement code block (if condition is True) or else code block (if condition is False) NEVER BOTH

if, elif, and else statements

only one of the statements’ code block will be executes (earliest True condition)

Control Flow - Branching

Allows computers to make decisions based on programmed alogrithim; <condition> has a True or False; evaluate expressions in that block if <condition> is True

Indentation

matters in Python; how you denote blocks of code

If you use = instead of == in if statements..

leads to syntax error! ( = is a assignment operator with == is for equality test)

while Loops

<condition> evaluates to a Boolean; if <condition> is True, do all the steps inside the while code block; check <condition> again; repeat until <condition> is False

for Loops

Each time through the loop, <variable> takes a value; 1st time, <variable> starts at the smallest value; next time, <variable> gets the prev value +1, etc.

range (start,stop,step)

default values are start = 0 and step = 1 (optional to state (only need stop) and is customizable); loop until value is stop -1; has to be ints not floats

break statement

immediately exits whatever loop it is in; skips remaining expressions in code block; exits only innermost loop

for vs while Loops

lens()

a function used to retrieve the length (how many characters) of the string in the parentheses

function

sort of procedure that does something for you

indexing

gets value of a certain index/position of a string; always start at 0 and last element always at index -1

slicing

creating substrings from a string using [start index: stop index: step]

immutable

cannot be modified

for char in string

use when need only one character in string; more pythonic (simple and elegant)

for i in range (indexing)

use when need to compare character positions or accessing nearby characters not to find one character

Guess-and-Check/Exhaustive Enumeration Algorithm

Try all possible solutions one by one (brute force), stop when you find the correct one. Need to be able to check if the solution is correct to use.

Approximate Solutions Algorithm

Test guesses that are "close enough" to the real solution using a small increment. Decreasing increment size causes slower program but more accurate answer while increasing epsilon (close enough guess) causes a less accurate answer but faster program.

Bisection Search Algorithm

Start with a high and low guess and repeatedly cut the range in half.

How do we write code?

so far we… open a file → type some code/sequences of instructions (may contain assignments, loops, conditionals,etc.) to solve a particular problem given.. using only a SINGLE file

Problems of only using a Single file

• Easy for small-scale problems but messy for larger problems

• hard to keep track of details (to know if the right info is supplied to the right part of code)

Good Programming

more code not necessarily a good thing, instead it’s measured by the amount of functionality (introduce functions!)

Functions

mechanism to achieve decomposition and abstraction; reusable pieces of chunks of code that need to be written; aren’t run in a program until they are “called” or “invoked” in a program

Decomposition

in programming, divide code into modules (achieved with functions and classes); idea is that different devices/ parts of codes (modules) work together to achieve a common end goal; used to create structure

modules

self-contained; used to break up code; intended to be reusable (can be used with different inputs); keeps code organized and coherent

Abstraction

Used to suppress details; in programming, think of a piece of code as a black box (cannot see unnecessary nor wanted tedious coding details) which can be achieved with function specifications or docstrings; idea is to not need to know how program works to use it (just need to know inputs and outputs)

Functions characteristics

• has a name

• has parameters (0 or more)

• a docstring (optional but recommended)

• a body

• returns something

Sample function

def (name) (parameters):

(indent) “““specification/docstring(multiline comment)”””

(indent) body(run commands and include return statement with expression to evaluate)

Scope

mapping of names to objects

If NO return statement..

Python returns the value None (not Boolean, NoneType) which represents the absence of a value

return vs print

Define a function with a variable that’s also defined outside of function →

no interference

function called with a variable that’s only defined outside of function →

use outside definition

function tries to increment/modify a variable that’s only defined outside →

not allowed in Python but could try global variables

global variables

not recommended to use in Python but they allow for the modification of variables (that are only defined outside of a function) inside a function (defeats purpose of functions)

Tuples

an immutable and ordered sequence of elements; element types can be mixed; represented with parentheses (); can perform indexing, concatenation, and len() on them

empty tuple

variable = ()

singleton tuple

tuple of one character/element

for loops with tuples

iterate over the tuple object at each position

Lists

ordered and mutable sequence of info/ elements that are usually homogenous, accessible by index; denoted by square brackets []; can index and len()

Iterating over a list

compute the sum of elements of a list; common pattern, iterate over list elements; indexed 0 to len(variable)-1 and range(n) goes from 0 to n-1

L.append(element)

add elements to end of list (mutates the list)

L.extend (some_list)

combines lists together

del(L[index])

delete element at a specific index