Fin???

In less than 30 min, I will be officially done all my assignments for my first year at UFT. And since this will most likely be my last post for this blog, I guess it should be somewhat special.

In my very first post, I talked about what computer science is really about (yup, it is more than just studying computers) and now that I am done csc165, I am quite convinced with this even more.

Computer science is about much more:

It is about logic, algorithms, problem solving (even to problems as fun as deciding your correct spot at a lunch table), patterns, rigour, planning and carrying out a plan, complexity, efficiency, understanding an argument, choosing your stance and trying to convince others about your point of view, collaboration, clear and unambiguous expression, uncomputable algorithms and computation theory, paradoxical situations, “inspirational puzzles”, meeting new people, making friends………….. just to name a few.

This course was great, my favourite this semester, I had an amazing instructor, a helpful Ta and met many great people. It helped me to think differently and look at arguments logically.

And while I am glad that I am almost done my first year at UFT, I really feel sort of unhappy that this course is coming to an end.

Of course, I still have the exam to worry about. I hope all of us do well on the exam. 

I guess: BYE for now 

Free lunch problem

Here is another problem that I found interesting:

• understand the problem:

if you are part of a group that choose who treat to lunch by sitting in a circle and reciting the natural numbers in a counter-clock wise direction starting with the one sitting at the northern extreme of the circle. friends who utter even numbers are eliminated from the counting (and won't get the free lunch either). the counting continues until all but one person is remaining and this person gets the free lunch. so if there are n friends, where would you choose to sit to get the free lunch?

• devise a plan:

draw the outcome for a bunch of n values until you notice a pattern.

• carry out the plan:

here is some values of n that I considered:

observations:

- of course, friends with even numbers get eliminated each round

i.e half of the people get eliminated each round

- when n is odd f1 never gets free lunch since the last number said would be odd = n and f1 would have to say an even number = n+1.

- when n is even, f1 sometimes get free lunch which makes sense since if n is even then half the people get eliminated n/2 can be either even or odd. which takes us back to the starting point (recursion???)

so we can conclude:

 - if dividing n/2 each round will always result in an even number then we should sit at position 1

i.e if n can be written as (2^x)

- if n = (2^x) + y then we should sit at the yth odd number from 1 

so if n = 6 = (2^2) + 2 then we need to sit at the 2nd odd number away from 1 -> 5

i.e. 1+2(y)

here is a python program that would do this for us:

just for fun, I ran this function for n in [1, 50]:

1 -> 1	11 -> 7	21 -> 11	31 -> 31	41 -> 19
2 -> 1	12 -> 9	22 -> 13	32 -> 1	42 -> 21
3 -> 3	13 -> 11	23 -> 15	33 -> 3	43 -> 23
4 -> 1	14 -> 13	24 -> 17	34 -> 5	44 -> 25
5 -> 3	15 -> 15	25 -> 19	35 -> 7	45 -> 27
6 -> 5	16 -> 1	26 -> 21	36 -> 9	46 -> 29
7 -> 7	17 -> 3	27 -> 23	37 -> 11	47 -> 31
8 -> 1	18 -> 5	28 -> 25	38 -> 13	48 -> 33
9 -> 3	19 -> 7	29 -> 27	39 -> 15	49 -> 35
10 -> 5	20 -> 9	30 -> 29	40 -> 17	50 -> 37

Assignment 3, limits AGAIN...

The last week of classes has been crazy for me with 3 different assignments due (this slog being one) and knowing that in less than a week, I will be writing my first exam has made it even worse.
One of the remaining 2 assignments was assignment 3 for csc165. And now that it is done, I can look back and reflect upon what I did. I don’t intend to write a detailed exclusive post of assignment 3 as I did for assignment 2 (don’t know why, just don’t feel like it, I guess). However, there is something that came up on assignment 3 that I would like to discuss:

Limits !!!!!

Limits have come up quite a lot in all calculus courses I have taken so far (which are not that many); they came up in high school calculus, 1st year university differential calculus and 1st year University integral calculus. And although in each of these courses we have extensively studied techniques to manipulate these limits and get all sorts of answers, we have not talked about what they actually mean as much. Sure, there would be a section of the book talking about deltas and epsilons, and the professor would discuss what they mean in 3-5 minutes, but at the end we always hear that we “don’t need to know them for the test” or that we “don’t really need to worry about them unless [we] want to major in math.” And therefore the meaning of limits is taught extensively in only these math courses that prepare students to be math majors.

In short, I was taught to solve the limit but not to interpret it.

In csc165, the definition of limits came up at the very beginning of the course when we were just talking about ∀ and ∃. Lately, it has come up again and been linked to determining the algorithms’ complexity.

In csc165, we have spent lots of time trying to understand what a limit means and to visualize it using graphs.And now that I understand what a lim of x going to infinity means, I think it is quite great that stuff we are taking in cs can link back to stuff we took in calculus courses.

products of sum problem

Hey again!

towards the beginning of the term we were introduced to George Polya's method to approaching problems presented in "How to solve it". I intend to follow this method to try to reach a solution to a problem that was presented to us in class.

• Understand the problem:

we are trying to find the maximum product that can be formed of a list of positive integers that sum up to n where n is a positive integer and if we can generalize the solution, we can write a function in python that returns the biggest product of n.

• Plan a solution:

I think the easiest way to tackle this problem is to actually write down all possible lists that sum up to a particular integer and then try to find the biggest product. And if we do this process to enough integers, hopefully, we will recognize a pattern that will help us to reach the solution.

• Carry out the plan:

First: 

we need to write down all the possible lists of positive integers of n for n = 1 till n=6 and determine the largest product for each. 

The best way to write all lists is to start splitting up n into 1s and then gradually group them together to form all possible lists, keeping track at the same time of the product produced by each list (product of elements in the list). and then finding the max of all these products.

Here is the possible lists for n in the interval [1,6]:

                                 

 

1-> 1	(1)=1
2 -> 2	(1,1) = 1	(2) =2
3 -> 3	(1,1,1)=1	(3)=3
	(2,1) =2
4-> 4	(1,1,1,1) =1	(4)=4
	(1,1,2) = 2	(2,2)=4
	(1,3)=3
5->6	(1,1,1,1,1)=1	(5)=5
	(1,1,1,2)=2	(3,2)=6
	(1,1,3)=3
	(1,4)=4
6->9	(1,1,1,1,1,1)=1	(6)=6
	(1,1,1,1,2)=2	(2,2,2)=8
	(1,1,1,3)=3	(1,2,3)=6	(3,3)=9
	(1,1,4)=4	(2,4)=8
	(1,5)=5

Second:

we can observe the following:

- lists that include 1 as an element are not the ones with the biggest sum (except for 1, of course).

- grouping n into 3s and 2s produce the largest product.
However, as you might expect having more 3s would increase the product than having more 2s.

Third:

now we can write a python function that groups n into 3s when possible or 2s.
I used recursion for that:

Halting problem.....SO CoNfUsiNg

we have finished the running time calculations and algorithms complexity section of the course and we are now working on the last section of the course: uncomputable functions, which is really confusing. 

we first started talking about the halting problem which is really one of these mathematical paradoxical situations which makes you very confused just by talking about it.

so here is what it is all about in a nutshell:

We know that some algorithms/programs halt while others don't. (halt meaning that the algorithm/program either give an outcome or raise an exception; in other words, it just stop working at some point while an algorithm that doesn't halt will loop forever.) and no one was ever able to implement an algorithm that checks if the function halts or not and turns out that no one would ever be able to find one (it is proved!). That makes halt a non-computable function.

Interestingly, halt is not the only non-computable function; there are many more and you can prove that they are not computable by using them to implement halt.

This section is getting even more complicated. (I really need to keep up with the material)