Pros and Cons of CSC148

    I felt that discussing some of the pros and cons of this semester's CSC148 is important, so I am going to talk about a few things I liked and some that I did not. The most helpful thing this semester were the exercises in my opinion. They managed to serve as nice refreshers to the course materials for me. However, what I did not like about them is that they were getting marked and there weren't too many of them. I think it would have been better if we were simply given a lot more exercises to work on that were not getting marked. The automarking for the exercises meant that there weren't enough of them to help us understand the course material better. What I think was done really well this semester were both of the assignments and tests, regardless of what most other people say. All of them were fair, yet the right amount of difficulty. What I particularly did not enjoy too much this semester are the SLOGs. I don't feel that they helped me at all with my programming skills. What I think would have been better is to have forum participation instead of SLOGs because then we would actually look at each other's ideas about the course. With different blogs, it is much more difficult to communicate with other people since they all have different SLOG urls.

    All in all, bring more exercises Dan. Also, forum participation would be better than blogs in my opinion.

Applying memoization to A1 solver

    Ever since we talked about memoization, I have been wondering about how to optimize tour_of_four_stools method in Assignment 1, tour.py file. My original approach was to use a method which would generate the lowest k value for the function, k being a number that gives the lowest number of moves for the equation : [2*k - 1 + 2*tour_of_four_stools(n - k)]. When I was doing preliminary testing that would calculate the optimal number of moves, I was able to reach up to a million cheeses and it would still calculate the answer in a second. However, when I actually implemented it in the assignment, it would not calculate the moves after 1000 cheeses. I was initially thinking of a bottom up approach, but it was actually less efficient than my recursive approach. Of course, I wasn't using the function which actually sped things up for my recursive tour_of_four_stools method, which is the generate_lowest_k function.

    Now, generate_lowest_k generated a list of k values for the equation mentioned previously such that the number at index (k-1) of the list lowest_k would be the optimal k for the lowest number for that equation. The pattern being 1,1,2,2,2,3,3,3,3... and so on. Now, I thought of two approaches of possibly speeding up tour_of_four_stools function. The first is to generate all the answers from 1 to n and just use lowest_k to pick the ideal two numbers from two separate lists, one for 2*k - 1, and the other from 2*tour_of_four_stools(n - k). 2*k - 1 list will be of length k to make things more efficient and the other will be of length (n - k). I am going to think of some more ways of optimizing this algorithm as I am not completely convinced that this will be faster than my previous approach.

Exam tips

    Exam time is coming up. Since CSC148 is a drastically different course from any others, studying techniques are also drastically different for it. It isn't enough to just memorize everything, if at all useful, but to have a deep understanding of how certain programming techniques work. An effective strategy for any course would be to look at the past exams, but even that might not work too well for computer science since even the curriculum is very dynamic from one year to another. In my opinion, the best way to study for a computer science exam is to do the assignments over again as efficient as possible. This will make you think of how to use things that were learned during the year. Also, I find reviewing the labs to be really helpful because it might be a completely different experience doing the labs by yourself compared to doing it in a group. If possible, challenge yourself by trying to get your programs correct the first few times (for labs and exercises that is) because obviously you will not have a computer to test stuff on during the exam. Those were my exam tips and I hope they help out whoever reads them.

Test 2 thoughts

    Well, in my opinion, Test 2 was fair. It tested us on things which we should have mastered a while ago through assignment 1 and 2. The first question should have taken no time to figure out as it was a matter of understanding the concept of what a binary search tree and inorder traversal is, which is not too tricky. The rest of the questions were not too difficult either. The only tricky question was the one where you had to write is_plex. To be honest, I think both test 1 and test 2 should have been more challenging because I am pretty confident that the exam is going to be lot more difficult, if this exam is anything like the previous one. Last semester, I felt the difficulty of the course suddenly took a huge spike when I started writing the exam. It was ridiculously difficult compared to what we did during the term. Hopefully the difficulty scales a lot better with this exam, or at least if the future exams are this difficult, I would at least appreciate it if the term work is also close to the exam difficulty.

Sorting algorithm

    So recently, I just thought of a pretty efficient sorting algorithm. Suppose that you have a list of unsorted elements ranging from lets say 1 to 99. A natural first step to sorting these elements would be to look at the number in front of all the elements. Since the most digits you could have in these sets of numbers is 2, you would look at each number divided by a 10 and then converted to integer, and depending on that, a bunch of sublists can be created to hold all the smaller lists with the same first digit (0 for single digit). These sublists are now half sorted and now a sorting pass should be done on all of these sublists but by looking at the number % 10. After doing that, just put all the sublists back together again and there you have a sorted list. This is an O(n) function. First you would need to find the highest amount of digits, then you would start the sorting passes. There is a shortcoming to this algorithm when for example you have a list as follows:

[99999999999999999999999999999999, 1, 2, 3, 4, 5]

    In that case there would be a ridiculous amount of sorting passes going on for each digit that the first number has. Maybe a better idea is to keep track of all the possible digit lengths and then just skip to the next smallest one if there is only one number for a specific digit length.

Assignment 1

    Okay, I think I have finally devised an algorithm for solving assignment (which is not a fast guess algorithm by the way). I just thought using a brute force guessing algorithm would be make this assignment too easy. Besides, I love math, so I decided why not try to create an actual algorithm to solving the problem. It took me a huge amount of time experimenting with numbers. I'm not actually sure if it is any faster than just guessing numbers, but it sure was fun to figure out how to do it. I'm just trying to figure out how to optimize my algorithm even further. I would love to post my algorithm here, but then you guys don't get to indulge yourself within the awesomeness of trying to figure it out yourself.

    I really love this assignment. This is the first assignment that was fun, challenging and not tedious at the same time. Squeal assignment was fun too, but it became more of a chore after a while when it came to fixing the code. This assignment is more thinking and less coding, which is the type of assignments I enjoy doing. 

    Keep these awesome assignments coming Dan.

Recursions

    Assignment 1's due date is fast approaching. I looked at what we have to do for
assignment 1 and started out with thinking what to do for the automated part. It turned
out to be easier than I expected, however if you are worried about it, I suggest to get
a head start on it as soon as possible, as it does take a fair amount of thinking to
solve the last part.

    Overall, my thoughts on recursion are that it is definitely a difficult topic to
understand for several reasons. It is difficult to think of a solution in a way that it
is composed to several smaller, easier solutions to a big problem instead of just
thinking of a solution which solves a problem entirely in one instance. I was a bit
disappointed that there weren't any exercises for recursion, but the in-class problems
helped a ton.