Wednesday 3 December 2014

Week 9: Addressing Maximum Slice and Provng Big O of Polynomials

What's up guys this is Kyle checking it to give you guys a weekly report for week 9 of CSC 165, This week we focused on two main concepts. One was a concept we previously learned about that was being applied to a very challenging context, and one was a new concept that would help us in the later weeks. So without further ado let's dive into this.

The first concept we addressed was the finding the sum of steps of a function called max_sum, which returned the maximum sum over slices of a set L. Keep in mind L can be any generic set. Now for this problem we had to take a little bit more time to find the number of steps to execute this function in the worst case simply because there were two nested loops, and step counting gets increasingly difficult when multiple nested loops are introduced because the number of steps increase exponentially when a nested loop is introduced. To solve this problem Danny separated this problem into three different parts in order to address each loop one by one before coming up with a way to produce the summation of all the loops. This process was and still is hard for me to understand, and I think I definitely need to read it over a couple more times and either ask Danny or my other peers to help me understand the solution if I can't understand it after multiple reads. The second concept we learned about was proving if certain polynomials were in big O of other polynomials. We learned about which functions could be bounded above others and how the proof structure would look like. What I found was that in order to prove a function was in big O of another function, some underestimation of the original function needed to be made in order to compare it to the function it was in big O of. We also learned an important rule that a polynomial function cannot be bounded above by a polynomial function with a lower degree than it. Such an occurrence would immediately require a disproof of the statement. This concept I found I understood immediately and I'm glad that I did because I would hate to have added another idea to the list of ideas I needed to look back on and study more closely.

Overall this week was pretty balanced. It started off pretty intense for me but it mellowed out and stayed with something I felt comfortable doing, which was big O proofs with polynomials. Anyways, let me know what all of you guys thought of week 9 of CSC165 we're definitely getting closer to the finish line, time is flying. Be sure to comment your thoughts on this week's topics and anything else you want to discuss. My apologies for this going up super late, I honestly just got behind on doing these SLogs so I'm trying to pump all the ones I have left to do now, thanks for the understanidng. As always, words are hard, comp-sci is awesome, and later days. This is Kyle signing out.

No comments:

Post a Comment