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.