Sunday, November 30, 2014

Week 12 (Last Full Week of Classes, Exams Right Around the Corner)

With week 12 over, there is only one class left and exams are right around the corner. I must say CSC165 was definitely not my favorite class; yet I have to admit I have learned a lot during this semester. This class has given me the opportunity to challenge myself, and learn many concepts, which will serve me well as I continue my degree in Computer Science. For a class that was at times very difficult to grasp the concepts, I thought Danny was a very good professor. Throughout this semester he kept me captivated throughout all the lectures, and made me really enjoy solving problems. He helped me really open up my eyes to Computer Science and made me realize just how many possibilities there are in this field. I have to admit at the beginning of this semester I sometimes had these thoughts:


Yet, now that I have been introduced to a different side of Computer Science I’ve learned to appreciate the logical side of things. Although, I definitely do not want to plan on specializing in something completely logic based, this course has helped me explore Computer Science as a degree. It also allowed me to approach problems in my other courses in a more logical way.

To sum it up, although I found this class decently difficult, I enjoyed CSC165. This course has made me very excited for the difficult problems I will have to solve through my degree here at University of Toronto.


Thursday, November 27, 2014

Week 11 (Looking at other's course experience)

This week was concentrated on talking about solving problems with Python. I thought it was crazy when Danny said that there are some problems that can’t be solved by algorithms. Since before this class every problem I had encountered had a definite solution. Here is an example Danny gave us in class:



Essentially what mathematicians have been trying to prove for over 70 years is that this function will halt for every natural number. After going over these lines of code myself I see that in theory this code should halt for every natural number. Yet, I also see what the many mathematicians have discovered, that you can’t predict if it will create an infinite loop. Personally, I find this type of problem very intriguing and one of the reasons I am interested in computer science. I really enjoy looking at a problem and thinking of a way to discover a solution. The satisfaction that I get from solving these types of problems is amazing, and is one of the reasons I am motivated to continue tackling hard problems. Even thought problem solving at first can kind of look like this:


Now to talk about my experience this week, I was very happy with tutorial this week, as I believe I did extremely well. The concept of proving Big-Oh and Big-Omega have become second nature to me, and it’s a really good feeling. With the semester coming to an end I am now starting to really concentrate on studying for the exam as well as finishing the final assignment. Personally, this last assignment is a great way to practice proofs right before the exam. Also, now that I am almost done with this course, with just one full week of class remaining I thought it was time to browse through other’s Slog’s and find something I found interesting.



Above is the link to Albert Xie’s Slog, particularly his “Week 7: Penny Piles - Recursive Solution in Python 3” entry. What I really enjoyed about this entry was that he began to solve the problem. Then going further he realized his solution was wrong and at that point revised what he had done to come to a better solution. For me, trial and error has been a big part of this course. Throughout all the exercises this year many times I ended up with the wrong solution, and on numerous occasions I had to completely restart. I believe this is a big part of problem solving, and I really liked Albert’s approach to this penny pile problem.

Wednesday, November 26, 2014

Week 10

The scary part of week 10 for me was that it’s at this point that I realized exams we’re right around the corner. I just finished cramming for all of my midterms, and I am now cramming to get all of my last assignments done. After that is done I will have to start all over again for all off my exams. This seems really stressful, but I am staying motivated thinking of Christmas break after this is all done.


On the plus side of this week, the course material was not nearly as scary as the realization I had. This week Big-oh proofs we’re introduced, and the concept was very easy to grasp. In the past doing proofs was often daunting, but these types of proofs are more straightforward in my opinion. I’m happy this week concept was very easy to understand, as it helped me be able to deal with all the other things going on in all of my courses. I just hope the concepts for the next two weeks will be as easy to fully understand!

Sunday, November 9, 2014

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(n3time complexity. As a challenge he proposed we find a solution using O(n2) 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(n3) time complexity and improve its efficiency by using O(n2time 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(n2and 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(n2time 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(n2) 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(n2) time complexity solution:



Although this function definitly is an improvement from the O(n3) 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.