Waste less time on Facebook — follow Brilliant.
×

Intro to Computation

           

In math, a function takes an input and returns an output. For example \(f(x)=x^2\) returns the square of the input. Another example - common in computer science - is \(\text{sort(list)},\) which returns a list with the same elements as the input list except in increasing order.

For how many distinct inputs is \(\text{sort(list)}=[1,2,3,4]?\) That is, how many lists, when sorted, give \([1,2,3,4]?\)

There are a lot of things we can say about functions in math, but we don't usually concern ourselves with how "difficult" a function is to evaluate; it just has an input and an output.

However, how "difficult" a function is to evaluate is a central question we ask when working with algorithms. It determines which computations are feasible in a reasonable amount of time with a computer, and which are not.

Computers know how to directly evaluate some "native" functions (like comparisons, addition, multiplication, etc.), and can only computer higher-order functions using these native operations.

Thus, a central question is how many native operations it takes to complete a higher-order function for different inputs. Let's take a look at concrete example of this in the next question.

Let's take an ElementList object that has two native functions:

  1. You can compare the any two values in the list to see which one is bigger.
  2. You can swap any two values in the list.

Below is a routine that uses some number of these native operations to sort the list. Across all four-element input lists, what is the maximum number of element comparisons made?

Feel free to modify the input list in line 4 and re-run the code!

from brilliant.algorithms.lists import *

# Try changing the order of these elements and running the code!
lst = ElementList('c', 'b', 'd', 'a')

n = len(lst)
assert n==4 

for i in range(n-1):
    for j in range(i+1,n):
        if lst[i] > lst[j]:
            lst.switch(i, j)

print('Sorted list: ' + str(lst))
print('Number of comparisons: '+str(lst.num_comparisons))
print('Number of switches: ' +str(lst.num_switches))
Python 3

Across all four-element input lists, what is the maximum number of switches made?

from brilliant.algorithms.lists import *

# Try changing the order of these elements and running the code!
lst = ElementList('c', 'b', 'd', 'a')

n = len(lst)
assert n==4 

for i in range(n-1):
    for j in range(i+1,n):
        if lst[i] > lst[j]:
            lst.switch(i, j)

print('Sorted list: ' + str(lst))
print('Number of comparisons: '+str(lst.num_comparisons))
print('Number of switches: ' +str(lst.num_switches))
Python 3

We have seen the worst-case number of switches and comparisons for this particular way of sorting the list. But what if we want to make a statement about any way of sorting that uses these two native operations (comparisons and switches)?

One way to get a lower bound for the number of comparisons needed is by using the Pigeonhole principle.

Suppose that an algorithm uses at most two comparisons on any four-element list. There are only \(2^2=4\) possible outcomes from those comparisons, but 24 different possible orderings. This means at least two orderings must correspond to the same outcome. However, that means that the algorithm is unable to distinguish between these two orderings and thus cannot correctly sort at least one of them.

Using this argument, what is the largest \(N\) for which we can definitively say that any algorithm that makes at most \(N\) comparisons cannot sort a four-element list?

In this quiz, we've seen how we can measure algorithms by the number of times they call a primitive function. By studying algorithms, we can learn efficient ways to solve common problems, as well as get a rich toolkit with which to reason about how well a given algorithm performs.

×

Problem Loading...

Note Loading...

Set Loading...