# CS 101 Lab: Week # 9 (Lists and Algorithms) <ul class="pager"> <li><a href="../w08/">← Previous lab</a></li> <li><a href="../w10/">Next lab →</a></li> </ul> It is planned to cover the following during the 9th week of CS101 labs. --- ## Outline: Lists and Algorithms 1. Quick reminders of the concept of a list, how to create one (e.g. `l = [1, 6, -4]`), and how to access elements (`l[0], l[1]`), and how to *loop over* the elements of a list (`for i in l: ...`), 2. Basic examples of list-related computation (min, max, sum and product, second smallest, average, standard deviation etc). 3. Generating a random list of values, based on [random.uniform](https://docs.python.org/2/library/random.html#random.uniform) from Python's builtin [random module](https://docs.python.org/2/library/random.html). 4. Testing if a list is sorted (algorithm in $O(n^2)$ for the worst case). 5. Writing our own sorting algorithm : [Bubble Sort](https://en.wikipedia.org/wiki/Bubble_sort) or [Insertion Sort](https://en.wikipedia.org/wiki/Insertion_sort) (both in $O(n^2)$ for the worst case). 6. A really stupid idea : the "shuffle as long as needed" sort (very stupid: a possibly but not statistically non-terminating 2-line algorithm but which always work in practice!). 7. Using Python's builtin library: lists can be sorted with the `.sort()` method / the `sorted` function (which is a well optimized $O(n \log(n))$ in place sort). Make a remark: optimal sorting algorithms (in $O(n \log(n))$) will be studied shortly in CS101 with the [Merge sort](https://en.wikipedia.org/wiki/Merge_sort), and be studied again in CS202, with [Quick sort](https://en.wikipedia.org/wiki/Quick_sort) and [Heap sort](https://en.wikipedia.org/wiki/Heap_sort). ### Bonus (if the time allows it) 1. After computing the average and standard deviation, ask them about the median (harder). 2. About the Shuffle sort, ask them to think about the time complexity (it is a random algorithm). In average, the algorithm runs in $O(n!)$ (which is incredibly big, resulting in general in 30-seconds for sorting 7 values !), --- ## Assignments (for today and next lab): ### Problem 1 : reminders on list #### Accessing elements of a list 1. Define today's date and your birthday date in two list variables, following the format `today = [02, 03, 2015]`, ie `today = [day, month, year]` *numerically*). 2. Write a `print` statement that will print the date on the formats `day - month - year` (easy) and `day/month/year` (harder). 3. Write a small function called `print_date` that will take one list as its only argument, assumed to follow the format used in question 1, and will print a message of your choice that gives the date (something like *"This day is the day-month-year"*). > *Warning:* the indexing starts **from 0 and not 1** ! > So in this example, the day will be obtained by `today[0]`. #### Looping over a list 1. Define a list called `roomies` that contain the roll numbers of you and your roommate, and with a simple `for` loop, print both number in two lines (with a message of your choice, like *"In my room there is 14XJ00297"*, *"In my room there is 14XJ00463"*). 2. Similarly, define a list called `team` containing the roll numbers (or names) of the team member for your HS103 project (4 to 6 members right?), and print each member, one by line, with a simple `for` loop (which has to start with `for member in team`). #### One basic operation: swapping two elements - Write a small function called `swap` that takes 3 arguments: a list (`mylist` in the example below), one index i (1 below), and another index j (2 below), and modify *in place* the list mylist so that the new values at i, j are the old values at j, i. - The math operation that you should perform is `mylist[i], mylist[j]` $\longleftarrow$ `mylist[j], mylist[i]`. - Modifying *in place* means your function is directly modifying its list *argument*, and so there is no need of *returning* anything. > Example: <blockquote><pre><code class="language-python" style="font-size:130%;">>>> mylist = [1, 4, -3, 9] >>> swap(mylist, 1, 2) >>> print mylist [1, -3, 4, 9] </code></pre></blockquote> ------ ### Problem 2 : some simple statistical computations for a list 1. Write a small list called `grades` that has to contain a dozen of grades from $0$ to $20$. 2. Use Python builtin functions `len`, `min`, `max` and `sum` to print a nice statement giving the number of grades, the lowest and the highest, and the sum of grades. 3. Now write a function called `average` that accept one *argument* (a list of int or float numbers), and *return* the **mathematical average** (arithmetical mean), given by the formula $\overline{x} = \frac{1}{n} \sum\limits\_{i = 0}^{n-1} x\_i$ for a list of values $[x\_0, \dots, x\_{n-1}]$. **Warning:** be cautious of any special case (what happens if $n = 0$, ie the list is empty?). 4. (*Bonus, harder question*) Write a function that computes the [**standard deviation**](https://en.wikipedia.org/wiki/Standard_deviation#Uncorrected_sample_standard_deviation) of the list, returned as a float number. This quantity is defined as $S = \sqrt{\frac{1}{n}\sum\limits\_{i = 0}^{n-1} (x\_i - \overline{x})^2} $ for a list of values $[x\_0, \dots, x\_{n-1}]$ of average $\overline{x}$. 5. Use your `average` (and `stdeviation`) function on this list of grades, to print the average grade of these students (and standard deviation if you did question 4). 6. *Bonus:* you can write a small `if-elif-else` loop to print a message depending on the average. If the average is too low, you can yell *"Work more seriously please!"*, and conversely if the average is good you can print *"Good job!"*. ------ ### Problem 3 : generating a random list of artificial grades - Write a function called `artificial_grades` that shall accept two arguments, `N` the size of the list to produce, and `max_grade` the maximum grades. - This function has to produce (and *return*) a list of $N$ floating numbers $x\_i$ (for $i\in[|0, N-1|]$) that has to be *uniformly* taken in the real interval $[0, \mathrm{max\\_grade}]$. - *Hint:* Python has a builtin module called [random](https://docs.python.org/2/library/random.html). You can get more information about it by searching on the **Python Documentation** (menu "Help" in Spyder), or by importing it and calling its help (`import random` and then `help(random)` or `random?`) - *Bonus:* you can make the second argument `max_grade` *optional*, with default value to be 100. The `def` statement used to define the function (and start the indented block) will be: `def artificial_grades(N, max_grade=100)`. ------ ### Definition: being sorted > In all the following, when we say sorted, we mean sorted in in ascendant order. A list $l$ of numbers is said to be **sorted in ascendant order** when: $$ \forall i, j \in [|0, n-1 |], i < j \implies l[i] \leq l[j].$$ ### Problem 4 : testing if a list is sorted (in $O(n^2)$) Write a simple function called `is_sorted`, that uses two `for` loops on the list elements to check if the list is sorted or not. Your function should *return* a **boolean** value, `True` if the list (given in argument to the function) is sorted, or `False` if not (if you found one pair of badly ordered values, ie two $i, j \in [|0, n-1 |]$, with $i < j$ but $l[i] > l[j]$). This function `is_sorted` is required for the first sorting method that you will implement, on the next problem: ------ ### Problem 5 : first sorting algorithm ("shuffle as long as needed") Write a sort function based on the following algorithm (written here as pseudo-code) : while the list is not sorted: shuffle the list # It might take a VERY LONG TIME to finish this loop *Hint:* this *shuffling* operation is very easy to perform, look for the good function to used (in the [random module](https://docs.python.org/2/library/random.html)). ------ ### Problem 6 : [the Bubble sort](https://en.wikipedia.org/wiki/Bubble_sort#Pseudocode_implementation) Write your own bubble sort *function*. You can call it bubble, and it has to accept one argument (the list to be sorted). You can either chose to: 1. copy the input list (with `newlist = list(argumentlist)`) and work on that new list, to finally *return* it when it is sorted (`return newlist`). 2. work *in place* on the argument list, and in this case no need to return anything (your function is modifying its argument). *Hint:* you need to loop on indexes and not on elements on the loop. Two *interlaced* loops are needed, of the form `for i in xrange(n)` and `for j in xrange(n)` (if `n = len(list_to_sort)` is the length of the list). The loops should **not** be written `for element in list_to_sort`. The pseudo-code algorithm, presented in Prof. Arya's lecture, is the following (that you can improve a little bit -- be smart!): # to sort the list called values: for i an index from 0 to n-1: for j an index from 0 to n-1: if values[i] > values[j] and i < j: # we found a pair in the wrong order, we correct it! swap(values, i, j) - You can then try your function on small lists, like the dates or roll numbers (as integers) from problem 1. - Finally, try your function on one *randomly generated* list of $230$ grades from $0$ to $100$ (by using `artificial\_grades` from problem 3). - Is your function quick? Do you think you can improve it ? ------ ### Problem 7 : using Python's `sorted` function or `.sort()` list method Python has two builtin way to sort a list: - One way is to use the [*function* sorted](https://docs.python.org/2/library/functions.html#sorted), that take a list as its argument, and *returns* a new sorted list (in ascendant order). - Another way is the use the [.sort() *method*](https://docs.python.org/2/tutorial/datastructures.html#more-on-lists) of a list. *Warning:* it operates in place (ie, modifies the list but does not return anything). With two small lists of your choice (for example, two lists of 27 random grades from 0 to 20), try both solution (`sorted(grades1)` or `grades2.sort()`). ------ ### Problem 8 : comparing the three sort algorithms Can you try to see by yourself how the computation times evolve when $n$ the size of the list grows? By using your function that generate a random list of grades of size $n$, try to sort a list of size $1000$ and then of size $10000$: 1. How the computation times of your Bubble sort increased? 2. How the computation times of Python's builtin sort increased? Can you concretely observe the difference between their two time complexity ($O(n^2)$ and $O(n \log(n))$) ? *Warning:* if your Bubble sort operates in-place, the list will be sorted after the first step, so the second step will happen very quickly. Be cautious to either generate two lists, or make a copy to be used for the second try. ### More details ? - More details on sorting with Python can be found on-line (or inside Python's documentation) : [HowTo/Sorting](https://docs.python.org/2/howto/sorting.html#sortinghowto). - If you are interested, you can quickly study two more simple sorting algorithms, of the same complexity than the Bubble sort : the [Insertion sort](https://en.wikipedia.org/wiki/Insertion_sort) and [Selection sort](https://en.wikipedia.org/wiki/Selection_sort). All the three approaches run in $O(n^2)$ in the worst case, and $O(n^2), O(n^2), O(n)$ in the best case (a list already sorted). Some *optimal* sorting algorithms (in $O(n \log(n))$) will be studied shortly in CS101 with the [Merge sort](https://en.wikipedia.org/wiki/Merge_sort), and be studied again in CS202, with [Quick sort](https://en.wikipedia.org/wiki/Quick_sort) and [Heap sort](https://en.wikipedia.org/wiki/Heap_sort). ------ ## Example programs > All this will also be on Moodle by next Friday (06-03). #### For the problem 1.a <blockquote><pre><code class="language-python" style="font-size:130%;">def print_date(date): day = date[0] month = date[1] year = date[2] # the 3rd value has index 2 (warning!) print "Day number is", day, " and month number is", month, " and the year is", year print_date([02, 03, 2015]) </code></pre></blockquote> #### For the problem 1.b <blockquote><pre><code class="language-python" style="font-size:130%;">team = [ '134', '123', '058', '096', '155', '007', '241' ] print "This team has", len(team), "member(s), with the following roll numbers:" # example of len() for nb in team: # example of a loop rollnumber = '14XJ00' + nb # TODO: update every year! print "- someone has the roll number", rollnumber </code></pre></blockquote> #### For the problem 1.c <blockquote><pre><code class="language-python" style="font-size:130%;">def swap(values, i, j): """ Swap the ith and jth value of the list, in place.""" values[i], values[j] = values[j], values[i] </code></pre></blockquote> #### For the problem 2 <blockquote><pre><code class="language-python" style="font-size:130%;">def average(values): """ Compute the numerical average of the list.""" n = len(values) if n == 0: # math convention is that an empty sum is 0 return 0 else: # Python's builtin function sum() sum_of_values = sum(values) return float(sum_of_values)/float(n) grades = [ 7.5, 15, 7, 2.5, 9, 9.5, 14, 12 ] print " - For these", len(grades), "students, their average is", average(grades), "(out of 20)." from math import sqrt def standard_deviation(values): """ Compute the standard deviation of the list.""" n = len(values) if n == 0: return 0 else: mean = average(values) # our own new function average return sqrt(sum([ (x - mean)\*\*2 for x in values ])/float(n)) # We use a nice Python feature called list comprehension: # [ (x - mean)\*\*2 for x in values ] creates the list of (x-mean)**2 print " - For these", len(grades), "students, the standard deviation is", standard_deviation(grades), "(for grades out of 20)." </code></pre></blockquote> #### For the problem 3 <blockquote><pre><code class="language-python" style="font-size:130%;">from random import uniform # A short version as another example of list comprehension # We use round(x, 1) to get only one digit after the comma, as a usual grade def artificial_grades(N = 231, max_grade = 100.0): return [ round(random.uniform(0, max_grade), 1) for i in xrange(N) ] # Generate artificial grades for the First Mid Term Exam for CS101 grades_midterm = artificial_grades(N=231, max_grade=100.0) </code></pre></blockquote> #### For the problem 4 <blockquote><pre><code class="language-python" style="font-size:130%;">def is_sorted(values): """ Tests if the list is sorted (in O(n**2) worst case).""" # we assume that the list is sorted answer = True # the answer that will be produced n = len(values) for i in xrange(n): for j in xrange(i+1, n): if values[i] > values[j]: answer = False break # useless to keep searching! return answer # This can even be written in one-line (with the lambda syntax, and the all function) # is_sorted = lambda l: all([ l[i] < l[j] for i in xrange(len(l)) for j in xrange(i+1, len(l))]) </code></pre></blockquote> #### For the problem 5 <blockquote><pre><code class="language-python" style="font-size:130%;">from random import shuffle def shuffle_sort(values): """ Shuffle the list as long as it is not sorted.""" while not is_sorted(values): print "The values are still not sorted, let shuffle them!" # Next line shuffles the list in place random.shuffle(values) # this while loop might take a LOT OF TIME to finish # but do you think it ALSWAYS terminates? return values </code></pre></blockquote> #### For the problem 6 <blockquote><pre><code class="language-python" style="font-size:130%;">def bubble_sort(values): """ Sort the list by 'fixing' every bad-ordered consecutive pair.""" n = len(values) for i in xrange(n): for j in xrange(i+1, n): if values[i] > values[j]: swap(values, i, j) grades_labexam = artificial_grades(N=27, max_grade=20.0) print "==> Trying the Bubble sort for these 27 artificial grades of the First CS101 Lab Exam:" bubble_sort(grades_labexam) print grades_labexam </code></pre></blockquote> #### For the problem 7 <blockquote><pre><code class="language-python" style="font-size:130%;">grades = artificial_grades(N=231, max_grade=20.0) print "==> Trying Python's sorted function for these 231 artificial grades of the First CS101 Mid Term Exam:" grades.sort() # this sorts the list, in place print grades </code></pre></blockquote> #### For the problem 8 <blockquote><pre><code class="language-python" style="font-size:130%;">N = 1000 biglist = artificial_grades(N, 20) bigcopy = list(biglist) print "\n\nSorting", N, "numbers with three approaches:" print "1) Python's sorted function (optimized one, in O(n log(n)):" biglist.sort() # About 5' 50" for 10000 numbers assert is_sorted(biglist) print "2) Our own Bubble sort function (naive one, in O(n ** 2):" bubble_sort(bigcopy) # About 12 seconds for 10000 numbers assert is_sorted(bigcopy) </code></pre></blockquote> For the final problem, trying the shuffle sort is **useless** (and will probably never terminate): it runs in $O(n!)$, so even for $60$ numbers, it will (*in average*) take some $10^{80}$ elementary operations (which is already bigger than the computed number of atoms in the universe). For example, to sort $19$ numbers with the shuffle sort, if we assume that our 3 GHz processor can perform $3.10^9$ operations by seconds (which is a very large upper-bound, especially when using Python), it will (in average) take **one month** to sort them ! In comparison, the bubble sort does it in less than 10 ms. --- <ul class="pager"> <li class="previous"><a href="../w08/">← Previous lab</a></li> <li class="next"><a href="../w10/">Next lab →</a></li> </ul>