Week 9 (Problem Solving)

Finally I have finished writing all of my midterms and submitted all my projects. I thought it was time to tackle a problem in my slog!

At the beginning of this week Danny introduced a function which purpose was to find the slice that had the maximum sum of a sequence of integers. The function that he showed us was a solution using O(n³) time complexity. As a challenge he proposed we find a solution using O(n²⁾ time complexity, and even trying O(n) time complexity. Here is my attempt to solve that problem!

1   UNDERSTANDING THE PROBLEM

o The problem given by Danny was to take the original function using O(n³) time complexity and improve its efficiency by using O(n²) time efficiency. After this to further the efficiency of the function, I must try to simplify the function further and use O(n) time efficiency.

o   The unknown of this problem is O(n²) and O(n) time complexity. The information given in this problem is the original function, which allows us to create a solid example to base the testing of all of our simplified functions.

Ex: With this type of function you begin with a sequence of integers, and the goal is to find the slice with the largest sum. Here is the example I referred to when solving this problem:

L = 5, -7, 3, 5, -2, 4, -1

*The slice highlighted in yellow represents the slice with the largest sum, that sum being 10. I will use this same sequence as a test for all my functions

o   With the first function, and with the help of an example simplifying this function is very possible. In order, to do this I must first dissect the function and understand exactly the purpose of each loop.

2   DEVISING A PLAN

o   Looking at the original function I know that looking at all the possible slices requires O(n²) time complexity, and then for each of those slices when use O(n) time complexity.

o   The first challenge here is to re-create this function using O(n²) time complexity

o   To do this I took the original function, and with my test sequence of integers, I kept in mind that my expected output would be 10.

o   Then I began to write out a plan where instead of doing 3 iterating loops I reduced it to just 2 loops

o   I did this process again for O(n) time complexity, yet this time it was slightly easier for me, and took less time to plan out my approach.

o   My approach for O(n) was simply to take the sequence of integers and calculate the largest sum that ends in a certain position. You would do this until you have looked at all the slices that are possible, and this will determine which slice has the largest sum.

3   CARRYING OUT THE PLAN

o   Now it’s time to carry out my plan, and take all of my thoughts, and put them into code. Here are the two improved functions that I wrote:

O(n²) time complexity solution:

Although this function definitly is an improvement from the O(n³) time complexity, there is still room for improvement.

O(n) time complexity solution:

This time complexity (O(n)) represents the fastest algorithym for a max slice problem.

4   LOOKING BACK

o   Looking back at my code I believe I went about this in an efficient way, and everything seems to work fine. There definitely is other ways of going about this problem, such as using for loops instead of my while loops. This would reduce the amount of variables, but I decided to keep it consistent with the original example used by Danny.