MITx Week 2: Algorithms and Python Functions

MITx and the Python DUDE .: I completed all the video tutorials and practice exercises assigned this week. Left unfinished is the Week 2 Problem Set (due Feb 2nd).

The big idea this week is recursion and creating functions in Python that call themselves to solve problems. One of the exercises involved finding the greatest common divisor of two positive integers (that is, the largest integer that divides each of them without remainder). Here is a cool animated example of recursion using Euclid's algorithm to find the GCD of two numbers.

Translated into Python code ...

def gcdRecur(a, b):
    '''
    a, b: positive integers
    returns: a positive integer, the greatest common divisor of a & b

    A clever mathematical trick (due to Euclid) makes it easy to find
    greatest common divisors. Suppose that a and b are two positive
    integers:

    If b = 0, then the answer is a

    Otherwise, gcd(a, b) is the same as gcd(b, a % b)
    '''
    if b == 0:
        return a
    else:
        return gcdRecur(b, a % b)

A big help trying to figure out how to code solutions this week was the online Python Tutor resource. It allows you to insert your code and then visualize what the computer is doing step-by-step as it executes the instructions. Here is an exercise which required writing a recursive function that executes a bisection search to determine if a character is in a string (the MITx grader uses example strings that are sorted in alphabetical order) ...

I am doing the coursework on a system running Ubuntu 16.04 LTS and writing code using Neovim. A few modifications in ~/.config/nvim/init.vim to give the text editor super Python powers ...

set tabstop=4               " number of columns occupied by a tab character
set softtabstop=4   " see multiple spaces as tabstops so <BS> does the right thing
set expandtab               " converts tabs to white space
set shiftwidth=4    " width for autoindents
set autoindent      " indent a new line the same amount as the line just typed
set number          " add line numbers
set cc=80           " set an 80 column border for good coding style

Onward!

More • pythonprogrammingmooc