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)

Moving on....

We got the results for both Test 2 and assignment 2 ( I did pretty well on both J) so now we are moving on with the course material and I have to admit, it is getting harder again. 

I find it especially hard, when we are given a function and are asked to know its performance at worst case. 

It was also confusing that we were introduced to a way for solving these problems in tutorial that was different than the way we learnt in class.  

As for the tutorial quizzes, they are getting harder as well; I really need to keep up with the material. 

ALL you need to know about assignment 2

Hey again

I know it is sort of late to talk about assignment 2. However, I just noticed that while other blogs have intensively discussed assignment 2, I have only briefly mentioned it in the previous post and thus figured out that I should give the assignment more credit so here you go,

EVERYTHING YOU MAY (or may not) WANT TO KNOW ABOUT ASSIGNMENT 2:

• BEFORE:

In general, I think most students in this course (including me) prefers proofs to the first part of the course; they are challenging, fun, and you feel pretty smart once you have finished one.

However, most of us (again, including me) were worried that we won't be able to solve proofs we have never seen before.

• DURING:

Luckily, I think the assignment was quite fair in terms of easiness especially that tons of office hours were available.

However, it is important to note that this assignment was our first major course work regarding proofs. And as you might expect, different people had different opinions about the assignment. 

Here are some I quote from other blogs/slogs:

http://165uoft.blogspot.ca/ :I found this assignment wasn't as bad as the first. I'm finding this one more concise in terms of its statements. The hardest question I would have to say is number 6 as it utilizes a small trick

http://annakovale.blogspot.ca/: I think Assignment 2 was great practice for proofs and I liked it more than the first assignment (I like proofs)...... I feel like it deserves a separate post.

http://slogjourney.blogspot.ca/:Oppose to watching the professor write the proofs and unanimously agreeing, this assignment was great practice in independently building up my proofs.

So, overall, the assignment was a great chance to practice for the test.

and as you might expect lots of questions were asked:

Here are couple of questions posted by http://1d10terror.blogspot.ca/:

is if there is a statement that I know a counter example for, can I state the counterexample and reach the conclusion thatP(x) -> notQ(x) for all values? Will that be enough to invalidate the entire statement? Also if I have a statement that has a for all assertion in the consequent, what on earth do I do? For example x in D, P(x) -> ( y in D, Q(y) ^ P(y)), is there anything I can do to solve this or am I completely boned and should view the statement from a different angle?

again, I know I am answering these after the assignment but I guess, it is better than never (we still have an exam to write anyway).
So here is my attempt at answering these questions:

1.     If you are trying to negate P(x) -> q(x), you shouldn't prove that p(x)-> not q(x) since this (as discussed in class) is proving "too much" than what you actually need to prove all you need is one example in which P(x) is true and q(x) is not 

2.     proving a for all in the consequent should be treated as any for all: by assuming that y is a generic element of D and then trying to prove that the predicates p and q apply to every single element in D (by proving that they evaluate as True to the generic element y). It might have been confusing due to the many /for alls/ . Personally, what I do to minimize confusion is to go over the statement from left to right in order, writing assume...... for every for all or implication, pick... for each there exists. This way by just building the "skeleton" of the proof, you have given yourself a head start to how your proof will look like and what exactly do you need to find out (to fill in the blanks).    

• AFTER:

I think the assignment was a really good exercise and an awesome preparation for midterm 2. Proof: most people did well on term test 2. 

Test 2 coming up :(

Only one week has passed since the reading week (more or less) and we have already finished the second assignment and are currently preparing for the second term test :( 

The second assignment was "less ambiguous" than the first one. I actually prefer proofs to the first part of the course. However, that does not mean that I have done any better on this. Hopefully, I didn't do so bad. I guess I will just have to wait for the results.

Back to the test. I am really nervous about the second test. The reason is while proofs are easier than the first part of the course in the sense that you know whether you "got it" or not and that you can get part marks by just writing the proof structure,  it usually takes me time to come up with a good proof (depending on what I am required to prove though) but I am only given 50 min to write the whole test. Another problem is that sometimes I skip steps because I think "it is too obvious anyway" and that usually causes me to lose marks since every thing (EVERY THING) has to be explicitly justified and stated. 

 

Midterm 1

Hey again

Last Friday has sure been a remarkable one. Not only, because of the storm that caused all schools and universities except ours to close, but also because last Friday has witnessed my first csc165 test. The test was not so bad (at least, not as bad as I thought it would be). You see, once the sample answers for assignment one were posted, I discovered many hidden mistakes I didn't even consider.
One main problem, that I discovered after comparing my answers to the sample answers, was that I translate literally from English to symbols without taking in consideration the ambiguity in English wording which might require extra quantifiers to disambiguate.

Here is a concrete example:

S1: There is one developer more important than code finger

my answer (which is not quite right) was:

 ∃x ∈X, ∃y∈X, I(x, Codefinger) ∧ I(y, Codefinger) ⇒ E(x,y)

What this is saying is: 

if you pick two developers who are more important than Code finger, they will be the same person. Which is fine, except it doesn't quite say the same thing as S1. 

I had this problem of not being able to precisely translate English into symbols until I decided to use the friend-enemy game we used in defining limits. 

Here is what S1 mean unambiguously:

If you pick a developer who is more important than code finger then any developer you pick after that if he is more important than Code finger, I guarantee you that he will be the same person you originally picked. 

I know it might not seam as a huge change from the first explanation but it actually is: interpreting it this way means that you will introduce an existential quantifier then a universal quantifier instead of having two existential quantifiers.

This technique really helped me to determine when to introduce quantifiers.

News so far......

I know it has been a long time since the first post but that’s because I was preparing some cool program Danny had challenged us to do but since I am still not done yet (have not started actually J, it has been a busy week) and haven’t posted anything new, I figured it is time for me to post something before I actually tell you about the cool mental experiment we did in class (probably, I will have enough time by the reading weak). So wait for that, but for now, here is what has been happening in csc165 so far:

we have had our 3^rd tutorial this week and OUR FIRST ASSIGNMENT. I can’t describe the assignment as hard but I can’t describe it as easy either. Well, that’s the weird thing about this course. You might think your answer is right just because it makes sense to you and turns out it is completely wrong. That is why you must read what you have written from many different angles and try to prove yourself wrong (which is a common thing between all sciences). I hope I did well on the assignment.

As for the lectures, I really loved the part when we try to prove that one statement is equivalent to another statement (since now, you can actually know if your answer is right or wrong). We are starting proofs so I guess that should be fun and I am looking forward to it.

what is computer science really about?

What is Computer science really about?

    Since we are almost two weeks into the second semester, I can probably provide a somewhat accurate answer for this question and hopefully, as I proceed through this semester, I will get to discover more about csc165 and about computer science in general.

    First off, I have to mention that I was not originally considering computer science as a major. I decided to take csc108 in the first semester to get an idea about what computer science is really about. And now, as a computer science student, I am really glad I tried it out. 

    

    Now, I have to mention the purpose behind this quick biography; through studying computer science, I have found that lots of comments concerning computer science are totally untrue. Here are the top 3 'computer science myths' :

I have to state that these are not facts, it is just my own personal opinion and if you have different views, please share. 

MYTH 1:

computer science is all about programming/computers/codes.……etc

This may seem as a very reasonable claim but I think computer science is more than just using a programming language to write codes.

Computer science is not only about implementing a code, but also about making the code work and proving that it will do what it is supposed to do.

In other words, it is about logic and reasoning and I can find no better proof than the fact that we have to take csc165 in our first year of studying computer science, a course about logic and mathematical reasoning.

In csc165, we have barely used computers and most of the work is happening on paper (and in our brains).

MYTH 2:

  If you want to take computer science in university, you must have a programming experience.

This was of a huge concern for me since I had no programming experience  whatsoever and although I admit people with past programming experience had some sort of an advantage over me (They got to skip csc108). What I notice now is it does not matter since computer science is also about logic and implementing is only one part of it and thus I think that anyone who is eager to learn computer science has the potential to do great.

MYTH 3:

csc is all about human machine interactions (you don’t get to talk to other people)

Totally wrong! I think by far, my computer science courses are where I got to talk to many people. In all lab/tutorial sections, we are always encouraged to work together in pairs. group programming (I think that is the correct term ) is always stressed and supported in all labs. And in csc165 lectures, we always get time to talk to other people about our reasoning for a certain problem, which really helps.