# CS 2120: Class #12¶

## 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 valuesYou 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 codeYou know how to write, and call, functions

- You know the basics of NumPy (and a bit of SciPy)...
- ... especially
*slicing*. You know how to slice arrays like a sushi chef .

- ... especially

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

You know how (and when) to use both

`for`

loops and`while`

loopsYou 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.

- The more

- This is a

## 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?