CS 2120: Class #12

_images/you_are_here.jpeg

You are here

  • At this point in the course you should feel like:

    • The Python shell prompt is a relatively familiar sight

    • You’re growing more comfortable using Python to accomplish small tasks

    • If you saw a simple Python program, you could figure out, more or less, what it does without having to run it

    • You know what a variable is

    • You know what a data type is (particularly: strings, integers, booleans and floating point numbers)

    • You know that you have to be very careful with floating point values

    • You know what lists, arrays, tuples and dictionaries are, how they differ and when to use each

    • You know about mutability and aliasing in data structures

    • You know how to use if statements to conditionally execute code

    • You know how to write, and call, functions

    • You know the basics of NumPy (and a bit of SciPy)...

    • You know what a “pure” function is and what “side effect” means.

    • You know how (and when) to use both for loops and while loops

    • You know how to develop your own code, one small step at a time, testing along the way.

    • You know how to comment your code so you can read it next week.

    • You know how to get data into, and out of, Python (CSV, .mat, Internet, plain text)

    • You know how to do some simple visualizations with matplotlib.

  • Other things you’ve been exposed to:
    • Newton’s method
    • Discrete event simulation
    • Graph theory
    • Stochastic Simulation
    • Ab initio data analysis
    • Statistical modelling
    • The method of Maximum Likelihood

Back to fundamentals

  • Having spent some time on very practical issues (file I/O and visualization), we’re going to take a step back to fundamentals.

  • Right now our knowledge of data structures is a bit better than our knowledge of algorithms.

  • For the most part, we’re relying on existing functions (e.g., in SciPy) to do most of the heavy algorithmic work for us. This is good! We’re here to find new tools to do exciting research, not become full time programmers.

  • However, it’s also good to understand how our tools work. Would you trust an anesthesiologist who didn’t understand how their equipment worked?

  • We’re going to look at the two most fundamental algorithms in computing:
    • Searching
    • Sorting

Searching

  • I bet you can teach the first part of this section yourself.

Activity

Write a function find_element(element,list) that returns True if element is in list and False otherwise.

You may not use the in operator (that’s cheating!)

  • Nothing for me to teach then. You already know how to search an unordered list.

Activity

Discuss this with your neighbours:

  • On average, how many iterations through your loop does your function make?
  • How about in the worst case?
  • Is your solution the best possible?
  • Might there exist some super clever algorithm that is somehow better (faster) than yours?

  • These kinds of questions are getting you closer to computer science and further from straight “programming”.

Activity++

Write a function find_element(element,sorted_list) that returns True if element is in sorted_list and False otherwise.

You may not use the in operator (that’s still cheating!).

This time, I promise you that I will only call your function on a list which is already sorted. Do this in a group. It’s not an easy one.

  • Now we need to ask the same questions as before:
    • On average, how many iterations through your loop does your function make?
    • How about in the worst case?
    • Is your solution the best possible?
    • Might there exist some super clever algorithm that is somehow better (faster) than yours?
  • This is a very common pattern in developing algorithms:
    • The more general your problem is, the slower the solution is.
    • The more you know about the structure of your problem (e.g., “the list is always sorted”), the more opportunities you have to use that knowledge to make the solution faster.

Sorting

  • We just saw a case where it was useful to be able to sort a list... but, honestly, it’s pretty clear that this is useful in many cases.

Activity++++

Write a function sort_list(intlist) that will return a list of integers intlist with the elements sorted from smallest to biggest.

You may not use any of Python’s built in sorting routines (e.g., intlist.sort() ).

Remember, we’ve moved from the level of simply using a tool to trying to understand that tool. This is REAL computer science!

NO PEAKING PLZ

Warning

Don’t read this part until you’ve finished the above activities!

Here’s a binary search in Python, an advanced sorting algorithm:

def binary_search(inlist,val,left,right):
        while left <= right:

                midpoint = (left+right)/2

                if inlist[midpoint] > val:
                        right = midpoint - 1
                elif inlist[midpoint] < val:
                        left =  midpoint + 1
                else:
                        return midpoint

        return -1

Activity

Add a print statement that outputs the values of midpoint, right and left immediately after the midpoint=(left+right)/2 statement. Run a few searches like this: binary_search([1,4,5,7,9,15,18,19],4,0,8) .

Make sure your list is sorted! Try some examples that fail, too. Can you see what’s happening?