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.