Week 11: Sorting and Efficency

In this final week, we will review the concepts of efficiency that were introduced in the previous post, Preliminary Algorithm Analysis, and apply them to sorting.  Assume that we have a list of prime numbers in non-ascending order:

[3, 5, 11, 7, 13, 2, 17]

Our goal is to rearrange the numbers in ascending order.  For us humans, the list above takes little time to sort.  However, what if we have to sort a list of a million numbers that are in non-ascending order?  We can make some computer do it for us with one of the sorting algorithms: bubble, selection, insertion, merge and quick sort.  Perhaps you are wondering why we have so many sorting algorithms.  The answer is that every one of them has a unique sorting strategy.  However, in the world of efficiency, not every sorting algorithm is created equal.  We can compare the sorting algorithms to see their efficiencies but first some review.  In the previous post, we discussed how an algorithm’s efficiency is determined by its memory usage and time complexity.   Time complexity is how the size of the input influences the number of steps that it takes to accomplish its task.  We also became acquainted with the Big-O, which is the notation that represents time complexity.  For example, an algorithm whose number of steps increases by n log n as the input increases by n has a time complexity of O(n log n).  Additionally, we deliberated on how algorithms vary in efficiency depending on the input and how this leads to an algorithm’s best, average and worst-case complexity, which correspond to an algorithm’s maximum, average and minimum efficiencies.  With these tools, we can now compare the algorithms:

Algorithm	Similarities in Characteristics	Differences in Characteristics
Bubble Sort	Brute Force Algorithms:  Let n  be the number of elements in the list.  Bubble, selection and insertion sort tackle the problem of unsorted lists head on by performing n outer iterations of the list and less than n inner iterations for every outer iteration. Average and Worst-Case Complexities:  Bubble, insertion and selection sort perform at average efficiency if the input is a randomized list; they perform at minimum efficiency if the input is a sorted list in reverse.  In both cases, they perform outer iterations of the list and inner iterations for every outer iteration.  This causes them to have an average and worst-case complexities of O(n ** 2). Best-Case Complexities: Bubble and insertion sort perform at maximum efficiency if the input is a sorted list.  They do not have to perform inner iterations and therefore, their best-case complexity is O(n).	Outer Iterations:  Unlike selection and insertion sort, bubble sort does not traverse the list in the outer iterations.  Instead, the outer iterations act as a brake that only terminates if the list is sorted. Inner Iterations:  It is here where bubble sort traverses the list.  Bubble sort switches the current element with the next element in the list if they are not in order. Too Many Switches:  A single switch rarely places the elements in the correct position the first time so bubble sort usually makes additional switches.
Selection Sort		Outer Iterations:  Selection sort switches the current element with the minimum element. Inner Iterations: It is here where selection sort finds the minimum element.  It does so by iterating through the sublist that is to the right of the current element.   Fewer Switches:  Every switch of the current and minimum element guarantees that the minimum element is in the correct position. Best-Case Complexity:  Selection sort performs at maximum efficiency if the input is a sorted list.  However, the design of the algorithm prevents it from terminating early if the list is sorted.  Therefore, it has a best-case complexity of O(n ** 2).
Insertion Sort		Outer Iterations:  Insertion sort determines if the current element is greater than the previous element.  If not, then it has to determine the correct position of the current element. Inner Iterations:  It is here where insertion sort determines the correct position of the current element.  It does so by iterating through the sorted sublist that is to the left of the current element. Inserts:  Unlike bubble and selection sort, insertion sort does not switch the positions of two elements.  Instead, it inserts the current element into the correct position, which is determined by the inner iterations.

You are probably wondering why I left out merge and quick sort.  Merge and quick sort are too dissimilar to bubble, selection and insertion and sort.  It becomes clear why this is so when we compare merge and quick sort in a new table:

ALGORITHM	SIMILARITIES IN CHARACTERISTICS	DIFFERENCES IN CHARACTERISTICS
Merge Sort	Divide and Conquer Algorithms:  Merge and quick sort tackle the problem of unsorted lists by recursively partitioning the list until the sublists are of length one. Best and Average-Case Complexities:  Let n be the number of elements in the list.  The number of partitions that they perform is usually either log n or approaches log n.  For every partition, they traverse through the list to compare the elements and rearrange them.  This gives them a best and average-case complexities of O(n log n).	Partitioning of List:  Merge sort partitions the list down the middle into equal or nearly equal halves. Rearranging of Elements:  Unlike quick sort, merge sort rearranges the elements after the partitioning is complete.  This rearranging works by comparing the elements from the elements from one sorted sublist with the elements from the other sorted sublist and combining them into a sorted list. Worst-Case Complexity:  Merge sort performs at minimum efficiency if the input causes it to make the maximum number of comparisons.  However, the number of partitions is still at or close to log n.  Therefore, its worst-case complexity is still O(n log n).
Quick Sort		Partitioning of List:  Quick sort partitions the list by placing every element that is less than the first element, which is called the pivot, into the left sublist and every element that is greater than the pivot into the right sublist.  The left and right sublists are usually of unequal lengths but quick sort requires less memory than merge sort so it is generally more efficient for large inputs. Rearranging of Elements:  Unlike merge sort, quick sort rearranges the elements with every partition so that by the time it partitions the list into one element sublists, the union of the sublists is the sorted list. Worst-case Complexity:  Quick sort performs at minimum efficiency if the input is a sorted list or a sorted list in reverse.  This causes quick sort to partition the list into sublists such that either the left or right sublists have a length of one for every partition.  In that case, it performs n partitions.  Since quick sort compares n elements for every partition, then its worst-case complexity is O(n ** 2).

So those are the five sorting algorithms.  Bubble, selection and insertion sort are brute force sorting algorithms; they attack the problem of unsorted lists head-on with multiple traversals without any thoughts about how inefficient they can be.  In contrast, merge and quick sort are divide and conquer sorting algorithms; they divide the problem of unsorted lists into smaller unsorted lists before conquering them.  To help with my general understanding of the sorting algorithms, I like to use an analogy from Roman times.  You should try this too.  When I think of bubble, selection and insertion sort iterating through lists, I think of the barbarian tribes attacking the ailing Roman Empire head-on without any thoughts about the destruction that they may cause.  When I think of merge and quick sort partitioning lists, I think of the Roman general and politician, Julius Caesar, dividing the Gallic Tribes before conquering them one-by-one in the Gallic Wars.  Perhaps you find this strange.  If so, then how do represent the sorting algorithms in your mind?

Barbarians After Sacking Rome (410 CE)

Julius Caesar, the Divider and Conqueror of the Gauls (100 - 44 BCE)

Week 10: Preliminary Algorithm Analysis

        In the week before the midterm, we will introduce some concepts in algorithm analysis, which is a field in computer science that deals with determining the efficiency of algorithms.  Efficiency is not determined by the time an algorithm takes to accomplish its task; factors such as the quality of computer hardware come into play and they are independent of algorithm efficiency.  Instead, efficiency is determined by an algorithm’s memory usage and time complexity.  For simplicity, we will only look at the latter.  An algorithm’s time complexity is the function of its input and number of steps it takes to accomplish its task.  We use a notation known as the Big-O to classify algorithms by their time complexity.  For example, an algorithm whose number of steps increases linearly as the input increases has a time complexity of O(n) while an algorithm whose number of steps increases quadratically as the input increases has a time complexity of O(n ** 2).  We can list the most well-known time complexity classes in order of decreasing efficiency:

O(1), O(log n), O(n), O(n log n), O(n ** 2), O(2 ** n), O(n!)

Although there exist algorithms that have the same time complexity for every input, most algorithms become more efficient for certain inputs while others become less efficient.  The time complexity for an algorithm at its maximum efficiency is its best-case complexity, at its average efficiency is its average-case complexity and at its minimum efficiency is its worst-case complexity.  With these tools, we can perform basic analysis of the time complexities of algorithms.

Week 9: Problem Solving Algorithm for Linked Data Structures

       In the previous post, I said that I was in ‘pretty good shape’ with regards to my comfort with the material.  This week, I will have to eat my words.  While the concepts are still manageable, the problems that we have to solve in the labs are now unbearably difficult.  I have no choice but to take action before it is too late.
          The topic of this week is problem solving.  This topic choice is inspired by the linked data structures that the professor introduced to us over the last three weeks (linked lists, binary trees and binary search trees).  Although the professor introduced us to binary search trees with linked lists in the previous week, I decided to focus on linked lists only. What a mistake that was.  Binary trees are trees with an arity of two.  Binary search trees are a special case of binary trees in that for every node in the tree, every node in the left subtree is less than the node and every node in the right subtree is greater than the node.  Although the concept is simple enough, the problems that we have to solve can be challenging.  I believe that the difficulties lie in structuring the solutions.  Therefore, I developed a problem solving algorithm that represents a systematic approach to solving problems that involve linked data structures.  Here is the algorithm:

Step 1:  Determine the parameters and return value of the function that will solve the problem.  This sounds trivial but it helps us stay organized for complicated problems.

Step 2:  Decide if we need a helper function.  A clear instance of when we need a helper function is if parts of the problem can only be solved by a function with a different return type than the final return value.  If a helper function is necessary, then follow the problem solving algorithm recursively.  Return to step 1 for the helper function and go through every step.  Then proceed to step 3 for the parent function.

Step 3:  Decide if while loops or recursion is necessary.  In the post, Running with Recursion, I argue that iteration is better for simpler problems and recursion is better for complex problems.  Just like the decision with helper functions, making the right choice can ease the difficulty of problem.

Step 4:  Determine the terminating condition(s).  For while loops, under what condition will the loop terminate?  For recursion, under what condition will the function or method assume as the base case?  Be mindful that for certain problems, there may be multiple terminating conditions.

Step 5:  Determine how the function will put the solution together.  For while loops, what variables do we need?  Which variables will be inside the loop?  Which will be outside?  For recursion, will the function put the solution together on the way to the base case or on the way back?

Week 8: Linking with Linked Lists

The focus of this week, or should I say last week (I am running a little late), is a data structure called linked lists.  We will go over the basics of linked lists and compare it to Python lists.  So what is a linked list?  A linked list is a sequence of nodes.  Every node in the sequence contains an object and a link to next node in the sequence.  We can represent a linked list with this diagram:

2  ---> 5 ---> 7 ---> 11 ---> 13 ---> 17 ---> 19 ---> None

Notice that 2 is actually a node that contains both the item 2 and a link to the node that contains the item 3.  Every node in this linked list follows this structure with the exception of the node that contains the item 17, which contains a link to None.  This indicates that the node that contains the item 17 is the last node in the linked list. Due to the similarities between linked lists and Python lists, the elements of the linked list in the diagram can be represented equivalently in a Python list:

[2, 5, 7, 11, 13, 17, 19]

However, linked lists have an important advantage over Python lists when it comes to inserting items.  If you insert an item into the front or middle of a Python list, Python shifts every element with an index that is equal to or greater than the index of insertion to the right.  The efficiency of the insertion operation can be greatly reduced if there are many items to shift.  In contrast, if we are to insert an item 3 at index 1 to the following linked list, then the operation is as follows:

Start:  2  ---> 5 ---> 7 ---> 11 ---> 13 ---> 17 ---> 19 ---> None

Step 1:  2 ---> 3

Step 2:  3 ---> 5 ---> 7 ---> 11 ---> 13 ---> 17 ---> 19 ---> None

End:  2 ---> 3 ---> 5 ---> 7 ---> 11 ---> 13 ---> 17 ---> 19 ---> None

No items are shifted if we are performing an insertion operation on a linked list.  Instead, the node that is to the left of the insertion index re-links to the node of the inserted item.  Meanwhile, the node of the inserted item links to the node that previously occupied the insertion index.  As a result of linked lists being a sequence of connected nodes, not only do linked lists have the data storage capabilities of Python lists but also they handle the insertion operation to the front and middle indexes with a much greater efficiency.

            My personal reaction with the linked lists is not too different from that of trees.  As the professor said, the two are somewhat similar in that linked lists are simply linear trees with an arity of one.  Additionally, my comfort level with the syntax of classes increased after relentless exposure to them in these two months.  Therefore, I think I am currently in pretty good shape. 

Week 7: Running with Recursion

The goal of this week is to provide an intro into recursion: this includes what it is, when we use it and why we use it.  We will look at what recursion is first.  Recursion is a programming technique in which a function or method repeatedly calls itself in its body so that it can break down a large, complex task into smaller, simpler instances of the same task.    We will introduce two ways to understand recursion.  One is by its components.

(1)    Base Case:  This component determines if the recursive function is given a trivial task to complete.  If the task is trivial, then the function will not call itself.  If a function is given a complex task, then this component lets it know when it should stop calling itself.

(2)    Recursive Step:  This component is where function calls itself.  Every time the function calls itself, it gives a portion of a complex task to another instance of itself to complete.  The function continues dividing the work until it reaches the base case.

(3)     Work:  This component uses the solution from a simpler instance of the task to help it complete a current, more complex instance of the same task.

We can illustrate what the components look like with an example.  Assume that we have to return every number in a possibly nested list in a new empty list.  Then the recursive function, with every one of the components commented in the body of the code, looks like:

def collect_num(L: list) -> list:

            ‘’’

            Return a new list in which every element of new list is a number in L.

            L.

            ‘’’

            new_L = []

            for x in L:

                        if isinstance(x, int) or isinstance(x, float):

                                    new_L.append(x)

# The base case is the if statement.  If x is a number, then the function can append it to new_L without any additional work.

                       

                        elif isinstance(x, list):

                                    new_L = new_L + collect_num(x)

# The recursive step is collect_num(x).  This step executes if x is a list because there exists a chance that there are numbers in x.

# The work component is when new_L is concatenated with the return value of collect_num(x).

           

            return new_L

In addition to understanding recursion by its components, another way to understand it is by comparing its design to that of a mathematical proof by induction.  Mathematical statements that are provable by induction are generally in the form of for every n that is an element of the set of natural numbers, S(n) where the proof of S(1) is called the base case.  We can think of the base case in induction as parallel to that of the base case in recursion because of their easiness to work out.  To us as human beings, the base case in induction is generally the most trivial instance of the statement to prove.  To the recursive function, the base case represents the most trivial task that it can complete.  Likewise, the inductive step of mathematical induction also has its parallel in recursion.  When we assume that for every k that is an element of the set of natural numbers, S(k) is true, we use that assumption to prove that S(k + 1) is true.  Similarly, when the recursive function has a solution for a simpler instance of a task, it uses that solution to complete a more complex instance of the same task.  As a result, there are two possible ways to understand recursion; one is through an analysis of its components and another is through its comparison to that of a mathematical proof by induction.

        The reason why we use recursion is that it is a more efficient for completing complex tasks.  The alternative to a recursive function is a function that only uses iteration.  Iteration with for loops and while loops is best for functions that complete simpler tasks.  For example, assume that we have to multiply the elements in a list of numbers.  Compare the function that only uses iteration to the function that uses recursion:

def multiply_elements(L: list) -> None:

            ‘’’

            Return the result of every element in L multiplied with each other.

            ‘’’

           

            m = 1

           

            for x in L:

                        m = m * x

           

            return m

def recursive_multiply(L: list) -> None:

            ‘’’

            Return the result of every element in L multiplied with each other.

            ‘’’

            if len(L) == 0:

                        return 1

            return L[0] * recursive_multiply(L[1:])

Recursion for this task is unnecessary because the task is already at its most trivial form.  For the task of collecting every number in a possibly nested list however, recursion is the most natural solution.  In that scenario, an iterative solution will most likely result in a hideously complicated function.  Therefore, as a general rule of thumb, recursion should be used in complex tasks that can be broken down into simpler instances of the same task.  If the task is already at its simplest form, then iteration is the best solution.

Week 6: Trolling for Trees

After our tour of Python’s memory model, we arrive at a data structure called a tree.  We will go over what is a tree and we will introduce some terms that come with trees.  So what is a tree?  A tree is set of nodes such that every node is an object with a value and a link to other nodes.  We can represent the appearance of a tree horizontally from left-to-right with this diagram.

                                                           

                                                            9                                                         

                                                                                    4

                                    5

                        2

                                                                                                11

                                                                        6

                                                                                                5

                                                7

                                                                        2

My apologies that I cannot get the vertical to work.  I could just steal one from the internet but they look very strange next to this background…

There are terms to describe the nodes by their positions.  Here are the ones that come from the analogy of the tree as a plant:

(1)  Root:  This is the node with the value of 2 at the top of the tree (or the left of the in sideways representation).

(2)  Leaves:  These are nodes with values 2, 5, 11 and 4 at the bottom of the tree (or the right of the tree in sideways representation).  They have no links to other nodes.

Here are the terms that come from the analogy of a tree as a family tree:

(1)  Parents:  These are the nodes with values 2, 7, 6, 5, and 9.  They have links to other nodes. 

(2)  Children.  Every node in a tree, except the root, is a child because they are linked by other nodes.

Here are some other terms:

(1)  Arity:  If we have a set that contains the number of children for every parent in a tree, then the arity of that tree is the maximum number in that set.   The arity for the tree above is two because every parent either has one child or two children.

(2)  Length of path:  The length of the path between two nodes is number of nodes in the sequence of every node from the first node to the last.

(3)  Depth of a node:  The depth of a node is the length of the path from the root to the node.

(4)  Tree traversal:  The act of visiting every node in the tree.  There are three ways of traversing a tree: preorder, postorder and inorder.

(5)  Preorder:  Preorder traversals start from the root.  They visit the parents first and then the left and right children.  The preorder traversal for the tree above is 2, 7, 2, 5, 6, 11, 5, 9, 4.

(6)  Postorder:  Postorder traversals start from the leftmost node.  They visit the left and right children first and then the parent.  The postorder traversal for the tree above is 2, 5, 11, 6, 7, 4, 9, 5, 2.

(7)  Inorder:  Inorder traversals also start from the leftmost node.  They visit the left child, then the parent and then the right child.  The preorder traversal for the tree above is 2, 7, 6, 5, 11, 2, 5, 9, 4.

One important thing to note is that trees are not cyclical.  Nodes of the left subtree cannot link to nodes in the right subtree.  If the node with value 4 in the tree above links to the node with value 11, then it is not a tree.

            When my professor introduced the concept of a tree to us, I did not find it terribly difficult to understand.  However, my problem with implementing classes from the post about Object-Oriented Programming are still present three weeks later.  This is mostly related to the syntax.  However, I believe I am getting better at it.  Probably a little more work should do it.

Week 5: Remembering Python's Memory Model

        The goal of this week is to appreciate how Python’s memory model brings two interesting advantages to programmers.  A memory model in the context of programming languages is the structure of how a programming language stores information about its objects during program execution.  In Python, when a name is defined, it refers to an id, which stores an object.  The link between the name and the id is stored in a dictionary-like data structure called a namespace.  What makes Python’s memory model interesting is that a separate namespace is created for every module and function call during program execution; when a module or function exits, its namespace is deleted.  We can then introduce two basic rules in Python's memory model:

(1) If there exists two same names in two separate namespaces, then the names do not interfere with each other during program execution.

(2) If a function needs to work with a name that is defined in the global namespace of a module, then the function will a create an identical name with the same id in its local namespace.

The creation of separate namespaces is the first interesting advantage of Python's memory model.  We can illustrate why this is an advantage with a thought experiment:  assume that the negation of rules (1) and (2) are true for Python's memory model.  The result is that programming in Python becomes very difficult because we can never use the same name twice in a program.  Additionally, if we run multiple programs at a time, then we have to ensure that there are no overlapping names between the programs.  Therefore, the inability to alter the ids of names in a separate namespace is one advantage of Python’s memory model.

        Another advantage of Python’s memory model is its flexibility.  To illustrate this advantage, assume that in the animated solver of the Towers of Anne Hoy game, function min_moves(n) has to find an integer i between zero and the number of cheeses n, such that the solver can solve the game in the minimum moves.  The problem is that the function returns the minimum moves for the chosen i but it does not return i itself.  So how can we access the chosen i?  A possible solution is to define i in the global namespace of the module.  Then use the global assignment in function min_moves to assign global i another id:

def min_moves(n: int) -> int:

        …

        for something in something:

        …min_moves(n - i)

            if something:

                global i

        …

                i = something

        …

        return fewest_moves

Every name i after ‘global i’ in the function refers to the i in the global namespace of the module.  Since we can access global i from anywhere in the module, then the global assignment is a solution to the inability of function min_moves(n) to return i.  Therefore, the existence of a global assignment that can change the id of a name in the global namespace is another advantage of Python’s memory model; it demonstrates its flexibility under special conditions.  Combined with a function's inability to alter the ids of names in a separate namespace under normal conditions, these are two interesting advantages of Python's memory model.