CSC148 Lecture Week 4

  Ah, recursion, my old enemy, we meet again. I am actually so glad that university terms are only 12 weeks long. I can only maintain good study habits for a few months at a time before I need a break, and in high school, by the last month, I was just out of gas. That was the month that we learned recursion and I just gave up, although now that I think about it, I don't think that the Waterloo Canadian Computing Competition recursion questions that my teacher gave us were suited to our skill level.

  The basic recursion we did in class with one base case and a very simple recursive statement, I can understand. Recursion is a type of algorithm where within a function, the function calls itself as a helper function. Recursion is best used on problems that can be broken down into smaller version of the same problem. One basic application of recursion is the factorial function shown to us in tutorial. For example, 6! can be broken down into 6 x 5!, which is then 6 x 5 x 4! and so on until you get to 1! which is just 1. Every factorial can eventually be broken down until 1!, so that is the base case which terminates recursion. The recursive call is then to call the function on n-1. Tracing recursion has been a good experience. I think I have a better grasp on exactly how recursion works now.

CSC148 Lecture Week 3

And here I was thinking that I had written my last SLOG. But now I am back to the wonderful world of blogging for class.

This week's topic is: Why do geeks need to learn how to write? My answer is pretty simple: Documentation. In the wise words of the Mythbusters, "The only difference between science and screwing around it writing it down". Programming and computers may seem highly individual, but in reality they require a lot of teamwork. The apps, websites, and programs that we use everyday were not built by one person. Programmers need to be able to communicate ideas and tell each other how their code works. This requires us to be able write clearly and concisely in a way that another human being can understand.

I for one hate writing comments, but no one (at least I'm assuming) likes to read uncommented code. I can't read the mind of whoever wrote the code. The code could be the most innovative amazing thing ever, but if I can't understand it, it is of no use to me. My human brain needs some plain English to process what it going on.

As another blogger points out, knowing how to write also helps us understand the problems we are trying to solve. Computer programming is fundamentally about solving problems, and we have to know what we are trying to solve before even attempting to do something about it.

CSC165 Lecture Week 12

So this is my last SLOG. I wish I could say that I'm sad, but I'm really not.

I actually really liked assignment 3. I finally understand what the point of all those limit proofs were. For the limit of a function as x goes to infinity, if that limit is infinity, then the output of the function can be larger than any given number past a certain breakpoint for the input. For the limit of a function as x goes to infinity, if that limit equals to zero, then the output of the function can be smaller than any given number after a certain breakpoint for the input.

The zero limit also really helped in my understanding of infinity. No matter how small a number I can think of between 0 and 1, there will always be a real number that is smaller than the number I've come up with. I'm also glad, I finally managed actually apply the limits and derivatives that I have spent the past year and a half learning.

After reading some other SLOGs, I've found a couple that have good summaries of computability, which I think was the hardest of the topics that we covered:
http://fromatothis.blogspot.ca/
http://mrbunnyua.blogspot.ca/

CSC165 Lecture Week 10/11

This is technically just for lecture week 10, since we won't be having a lecture week 11 for the Tuesday evening class, but anyway, onto the SLOG.

This week in lecture we learned about computability. First let's talk about a few definitions. A function is considered to halt when it eventually stops. For some functions we can write a function halt(f, n) that can tell us whether or not the passed function f will halt with the given input n, but we cannot write a universal halt(f, n) function for all possible inputs.

A function is well defined if and only if we can tell what the output is for every input in some domain. A function is computable if and only if it is well-defined and we know how to compute the output for every input in some domain. By these definitions halt(f, n) is non-computable.

We can prove that a function is non-computable by using reductions. If a function, f, can be implemented by using another function g, that function reduces to g. If g is computable, f is also computable and by the contrapositive, if f is non computable, g is also non computable.  

CSC165 Lecture Week 9

This is my problem solving session. I will be attempting to solve the Free Lunch problem on the problem solving wiki.

Understand the Problem

You are part of a group of friends who choose which to treat to lunch in the following manner:

1.    They arrange themselves in an (approximate) circle.

2.    They begin reciting the positive natural numbers, in order, in a counter-clockwise direction (viewed from above), starting with the friend at the northern extreme of the circle (who utters "one").

3.    As a friend utters an even number, he or she is eliminated from the counting (and consideration for lunch). The counting "wraps around" so that those who avoided one of the dreaded even numbers on the first round may be exposed on subsequent rounds.

4.    The last person left is treated to lunc.

For example, if there are friends f1, f2, f3, f4, and f5 arranged counter-clockwise, with f1 at the northern extreme, the first round would eliminate f2 and f4. Then f1 and f5 would be eliminated in the next round, leaving f3 to enjoy the free lunch.

If there are n friends, where should you position yourself to get the free lunch? Do you have a technique that will work for any positive natural number n?

This picture helps illustrate the problem. Basically, you don't want to ever say an even number.

Devise a Plan 

Go through the first couple of natural n by hand and see if a patter emerges.

Carry out the Plan

n	Iterations	winner
1	F1	F1
2	F1 f2	F1
3	F1 f2 f3 F1 f3	F3
4	F1 f2 f3 f4 F1 f3	F1
5	F1 f2 f3 f4 f5 F1 f3 f5	F3
6	F1 f2 f3 f4 f5 f6 F1 f3 f5 F1 f5	F5
7	F1 f2 f3 f4 f5 f6 f7 F1 f3 f5 f7 F3 f5	F5
8	F1 f2 f3 f4 f5 f6 f7 f8 F1 f3 f5 f7 F1 f5	F1
9	F1 f2 f3 f4 f5 f6 f7 f8 f9 F1 f3 f5 f7 f9 F3 f7	F3
10	F1 f2 f3 f4 f5 f6 f7 f8 f9 f10 F1 f3 f5 f7 f9 F1 f5 f9 F1 f9	F1
11	F1 f2 f3 f4 f5 f6  f7 f8 f9 f10 f11 F1 f3 f5 f7 f9 f11 F3 f7 f11 F3 f11	F3
12	F1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 F1 f3 f5 f7 f9 f11 F1 f5 f9 F1 f9	F1

Initial observations:

It’s pretty obvious that you don’t want to be an even numbered friend. F1 wins all of the even numbered n except for 6. (Realized that I made an error once I looked back)

Look Back
An obvious pattern has not revealed itself. I will take a look at another possible source of a patter: what number each of the people say.

n	Iterations	winner
1	F1 1	F1
2	F1 f2 1    2	F1
3	F1 f2 f3 F1 f3 4    5	F3
4	F1 f2 f3 f4 F1 f3 5    6	F1
5	F1 f2 f3 f4 f5 F1 f3 f5  6   7   8	F3
6	F1 f2 f3 f4 f5 f6 F1 f3 f5 7    8   9 F1 f5 10 11	F5
7	F1 f2 f3 f4 f5 f6 f7 F1 f3 f5 f7 8    9  10 11 F3 f7 12 13	F7
8	F1 f2 f3 f4 f5 f6 f7 f8 F1 f3 f5 f7 9   10 11 12 F1 f5 13 14	F1
9	F1 f2 f3 f4 f5 f6 f7 f8 f9 F1 f3   f5  f7 f9 10 11 12 13 14 F3 f7 15 16	F3
10	F1 f2 f3 f4 f5 f6 f7 f8 f9 f10 F1 f3   f5  f7  f9 11 12 13 14 15 F1  f5  f9 16 17 18 F1 f9 19 20	F1
11	F1 f2 f3 f4 f5 f6  f7 f8 f9 f10 f11 F1  f3  f5  f7 f9 f11 12 13 14 15 16 17 F3 f7 f11 18 19 20 F3 f11 21 22	F3
12	F1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 F1  f3  f5 f7  f9  f11 13 14 15 16 17 18 F1  f5  f9 19 20 21 F1 f9 22 23	F9

Initial observations:

I actually made one error in finding out who won, so I should really double check my work.

Winner	1	2	3	1	3	5	7	1	3	1	3	9
# said to win	1	1	5	5	7	11	13	13	15	19	21	23

Look Back

Still no obvious pattern. I am out of ideas at this point, and will continue on later and look for more complex patterns.

CSC165 Lecture Week 8

This week the most interesting things that we learned was how to count steps and analyze algorithms. I now know that nesting loops is inefficient. Insertion sort with one nested loop has a worst case time complexity of O(n^2). A maximum slice algorithm with three nested loops has a worst case time complexity of O(n^3). Nesting loops greatly increases the number of steps needed to do something.

I also found it really interesting that for upper bounds you can overestimate them because they're upper bounds. A function is upper bounded by another if it grows no faster than that other function, so if that function happens to grow a lot faster, it doesn't matter because it is still an upper bound. Also, you can underestimate them because they are lower bounds. A function is lower bounded by another function if that other function grows slower than the first one. If the other function grows a lot slower it also doesn't matter because it is still a lower bound.

CSC165 Lecture Week 7

I have always wondered what something like O(nlogn) meant after my brief foray into reading about sorting algorithms on Wikipedia. Now I know. O() is the notation for asymptotic upper bound. Efficiency is very important in computer programming. Computing time takes up money and resources. Asymptotic notation allows us to analyze the efficiency of functions.

When we say running time, we don't actually mean running time. We mean the the number of steps (lines of code) that need to be executed in order to run a function. With asymptotic upper bound, we focus on the worst case scenario. So if you are searching for an something in the list, the worst case scenario is when that thing does not appear in the list at all. This would require the largest number of lines to be run. As well with asymptotic notion, we do not care about constant terms, and only the highest order term matters. So everything from n^2 to n^2 + 3n + 4 to 109352543n^2 + n + 43243 all belong in O(n^2).