I’ve been working on a method research project lately. It’s basically a modified version of a current available algorithm. But we modified it to make it suitable to some new conditions the original method not designed to handle.

Interestingly, there are two available softwares implementing the same concept of the original algorithm. I checked out their code online and found one to be very concise and elegant, the other is rather lengthy and messy.

Although I respect both groups and I am sure both of the softwares can get the job done, I found the one with beautiful code “sparks joy” while the other one make me feel frustrated.

Then I ask myself: which way do I want my scripts to be? Of course I want to move in the direction of making code clear and conside. As I don’t have much formal computer science training and found myself writing “ugly” code all the time, I decide to start from the basics.

I found the curriculum for CS undergrads and picked a introductory course: MIT 6.0001 and started today.

MIT 6.0001

Here I summarize the points that are most useful to me in the first 7 lectures. I’ll update when I finish the rest of the courses.

Notes for 6.0001 (Lec 1-7)

Lec 1.

basic machine architecture

memory (instruction + data)

control unit (program counter) arithmetic logic unit (do primitive ops)

input output

instruction (built from predefined set of primitive instructions) stored inside computer

program (interpreter) execute each instruction in order (control unit read a line of code, give it to arithmetic logic unit, receive result from it, add 1 to counter, and read next line)

where things go wrong

syntactic errores
static semantic errors:
semantic errors: different meaning than intended

program

definitions
commands: instruct interpreter to do things

Lec 2

for vs while loops

for loops:

know number of iterations

can end early via break

use a counter (each time, for variable + 1)

can rewrite for loop using a while loop

while loops:

unbounded number of iterations (while condition true, continue)

can end early via break

can use a counter of initialize before loop

may not be able to rewrited by for loop

Lec 3

bisection search:

half interval each iteration, new guess is halfway in between

converge on order of log2N steps

cube = 27
#cube = 8120601
# won't work with x < 1 because initial upper bound is less than ans
#cube = 0.25
epsilon = 0.01
num_guesses = 0
low = 0
high = cube
guess = (high + low)/2.0
while abs(guess**3 - cube) >= epsilon:
   if guess**3 < cube:
       # look only in upper half search space
       low = guess
   else:
       # look only in lower half search space
       high = guess
   # next guess is halfway in search space
   guess = (high + low)/2.0
   num_guesses += 1
print('num_guesses =', num_guesses)
print(guess, 'is close to the cube root of', cube)

Lec 4

return vs print

return:

only has meaning inside a loop

only one return executed inside a function

code after return statement not executed

has a value, given to function caller

print:

can used outside functions

can execute many times

outputted to the console

decomposition: create sturctures

abstraction: suppress details

scope

def func_a():
    print('inside func_a')

def func_b(y):
    print('inside func_b')
    return y

def func_c(z):
    print('inside func_c')
    return z()

print(func_a())
print(5+func_b(2))
print(func_c(func_a))

in the global scope: no functions are called, so the instructions/code just sit around

func_a, func_b, func_c

then called func_c(func_a), start a new scope: func_c scope, with code for func_a inside

then call func_a: start a func_a scope, get returned value to func_c, close func_a scope,

inside a function, can access a variable defined outside, but cannot modify global variables

Lec 5

tuples:

ordered

immutable

slice tuple

t = (2,'mit',3)
t[1:2] # ('mit',)
t[1:3] # ('mit',3)

swap

(x,y) = (y,x)

return > 1 elements from a function

lists

ordered

mutable

# aliasing
warm = ['red', 'yellow', 'orange']
hot = warm
hot.append('pink')

# cloning
cool = ['blue', 'green', 'grey']
chill = cool[:]

L.remove(2)
del(L[1])
l.pop()
'_'.join(l)

Lec 6

recursion

recursive step: reduce problem to simpler

base case: reduce until a single case that can be solved directly

function scope

def fact(n):
    if n == 1:
        return 1
    else:
        return n*fact(n-1)
print(fact(4))

global scope: fact (some code)

fact scope (called with n = 4): n 4 return 4*fact(3)

fact scope (called with n = 3): 3*fact(2)

fact scope (called when n = 2): 2*fact(1)

fact scope (called when n = 1): return 1

each recursive call to a function create its own scope/environment
binding of variables in a code not changed by a recursive call (so if in this scope, n= 4, it won’t be changed by other scopes n values)
flow of control passes back to previous scope once function call returns value

tower of hanoi

def printMove(fr, to):
    print('move from ' + str(fr) + ' to ' + str(to))

def Towers(n, fr, to, spare):
    if n == 1:
        printMove(fr, to)
    else:
        Towers(n-1, fr, spare, to) # from -> spare: (n-1) 
        Towers(1, fr, to, spare) # from -> to: 1
        Towers(n-1, spare, to, fr) # spare -> to : n-1

fib

def fib(n):
# recal the same values many times
    if n == 1:
        return 1
    elif n == 2:
        return 2
    else:
        return fib(n-1) + fib(n-2)


def fib_efficient(n, d):
# keep track of already cal values
    if n in d: # look up first in case already calculated
        return d[n]
    else: # modify dic as progress through calls
        ans = fib_efficient(n-1, d)+fib_efficient(n-2, d)
        d[n] = ans
        return ans
        

Lec 7

defensive programming

assertions:

want to be sure assumptions on state of computation as expected

use an assert statement to raise an AssertionError exception if assumptions not met

don’t allow programmer to control response to unexpected conditions

ensure execution halt if expected conditions not met

typically used to check inputs

can check outputs

use for: types, invariants, constrains, violations

def avg(grades):
    assert len(grades) != 0, 'no grades'
    return sum(grades)/len(grades)

exceptions

stop execution, signal error condition

def get_ratios(L1, L2):
    """ Assumes: L1 and L2 are lists of equal length of numbers
        Returns: a list containing L1[i]/L2[i] """
    ratios = []
    for index in range(len(L1)):
        try: # where you put code that might get an error
            ratios.append(L1[index]/L2[index])
        except ZeroDivisionError: # only if this type of error
            ratios.append(float('nan')) #nan = Not a Number
        except:
            raise ValueError('get_ratios called with bad arg')
        else: # no error 
            print("success")
        finally: # always executed, run no matter what happens
            print("executed no matter what!")
    return ratios
    
print(get_ratios([1, 4], [2, 4]))

do

write a function, test the function

backup code, change code, write comment, test, compare new to old

don’t

write entire program, test entire program, debug

change code and forget what bug/change

when test?

code runs

have a set ot expected (input, output)

set up for easy testing

break program up into modules

document constraints on modules (expected input, output)

document assumptions behind code design

Intro to programming

notes from MIT 6.0001 Lecture 1-7