Jason's CSC 236 Blog

Problem solving - sum of products

2008-12-05T11:31:00.007-05:00

I did this on the last day, way too busy for other courses.

I chose this question, "If n represents a positive whole number, what is the largest product that can be formed by multiplying the elements of a list of positive whole numbers that sum to n?" because it is very interesting, plus I like to play around with numbers a lot. Anyways, onwards to the proof:

1. Understand the problem:

This question basically asks a formula for the largest product made up of numbers that sums up to any number n.

2. Devising a plan:

Many ways to do this:

brute force - trying out a large number of values, find a pattern and test it out with extremely large number to confirm the formula. It's a good way to check your own intuition but not very efficient (especially if your guess is wrong).

equations - there's got to be some ways of relating sum and products as an equation, certainly this way is fast and more efficient as it is already mathematically rigorous and straightforward.

working backward - It may work with other problems, but may not work with this one. Basically use a random number, find the most numbers you can that makes up the two largest multiplier.

I choose a combination of brute force (this problem is relatively small), and equations (to express the formula).

3. Carrying out the plan:

The first few natural numbers are not interesting, the pattern starts to make sense with n >= 6.

number 6

list of possible sums (1, 1, 1, 1, 1, 1), (1, 1, 1, 1, 2), (1, 1, 1, 3), (1, 1, 4), (1, 5), (2, 2, 2), (1, 2, 3), (3, 3)

biggest product 9

number 7

list of possible sums (1, 1, 1, 1, 1, 1, 1), (1, 1, 1, 1, 1, 2), (1, 1, 1, 1, 3), (1, 1, 1, 4), (1, 1, 5), (1, 6), (1, 2, 2, 2), (1, 1, 2, 3), (1, 3, 3), (2, 2, 3)

biggest product 12

number 8

list of possible sums (1, 1, 1, 1, 1, 1, 1, 1), (1, 1, 1, 1, 1, 1, 2), (1, 1, 1, 1, 1, 3), (1, 1, 1, 1, 4), (1, 1, 1, 5), (1, 1, 6), (1, 7), (2, 2, 2, 2), (2, 3, 3), (1, 2, 2, 3), (1, 1, 3, 3)

biggest product 18

... and so on.

Next, onwards to the formula, from the pattern above the biggest product from the list of sums is a combination of 2s, and 3s.

Given a number n, breaks the number into two-halves and find all possibles factor of floor(n/2) and ceil(n/2) (in case n is odd) those two halves represented with 2s and 3s, with 3s the most priority (i.e. a number 8 can be made by 2 X 2 X 2 X 2, but it's value is the biggest for 3 X 3 X 2).

If n is even, let k = n - 3m, where k <= n mod 3, with m \in N. Then either k is 0 or even, thus k can then be represented as powers of 2 (i.e. k = 2^p, for p \in N). Therefore n = 3m or n = 3m + 2^p, for m, p \in N, that will represent the biggest product by multiplying p 2s and m 3s (i.e. 8 = 3 X 2 + 2^1, and product = 2 X 3 X 3 = 18).

Similar case for n = odd. Then it will be of three cases: if it equals 0 after mod 3, then it is a multiples of 3, say, 3m, for m \in N. If it equals 1 after mod 3, then the equation becomes (let t be the odd half) t = 3^(s-1) + 2r, with r, s \in N, where s is the biggest powers of 3 t can obtain). If it equals 2 after mod 3, then t = 3^s + 2r, s, r \in N, since the remainder of mod 3 is a multiples of 2. Then the biggest product can be obtained by multiplying s 3s and r 2s.

So n = 3m or 3m + 2^p or 3^(s-1) + 2r or 3^(s) + 2r, depending on the situation. The biggest product is then the multiples of m or s times of 3s and p or r times of 2s.

4. Looking back:

I'm done the proof, but the mathematical expression can be simplified greatly, I need more knowledge in order to do so.

The combination works greatly because brute force allows me to find a pattern, while using equations allows me to reduce the amount of explanation I need to write/type (it's still a lot to explain the cases).

My solution may not be the neatest, but I think it works perfectly with all n. However I believe there are other equations that are shorter and much more elegant, my skill of proving is not up to that level yet...

Last day and test

2008-12-05T11:21:00.002-05:00

This is the first time that the question typo actually messed me up completely.

So, the last day of lecture, the third test is on Chapter 7 (but what exactly?), so I have a hard time focusing on which part to study on, instead I used lots of time just to read through the course notes.

Apparently I haven't prepared myself for the Cartesian product DFSA, plus the minor typos on this question really got me stuck there for a while (yes, I know the typo was already mentioned by Danny, but actually I haven't paid attention to it). I still managed to figure out with the last few minutes I have, the other two questions are very straightforward, so nothing to say about those.

After this intensive thirteen week lecture, obviously I've learned a lot about the theory of computation, all those wonderful proof techniques are very useful for us later on in our undergraduate studies. I personally think Danny is a very good lecturer, I've learned a lot from it (and also from this course), the only think I regret so far is to not spent enough time for this course. I think I lucked out in so many places, and I know that the exam will get me for sure.

Oh well, I enjoyed this course a lot, I certainly need to improve my sleeping habits because I cannot handle morning courses (or exams!), and appeared tired sitting near the front of the class is rather embarrassing.

Back to more studying, I'll write out a proof later.

A rather pointless entry

2008-12-04T00:03:00.003-05:00

I'm late for this entry again!

Oh well, this lecture was spent on preparing for the exam next Friday (still can't believe it's that close now), and the TA evaluate form.

There's nothing new here to write, I can spent more productive time studying and finding out a problem to solve for this slog.

Logging off~

Push-down Automata

2008-12-02T00:08:00.003-05:00

Date: Monday
Hmm... seems like I forgot, I was busy studying for other courses.

Ah, December, the last week of university, the last week of brain torture, the beginning of a holiday.

The projector is not working again, so back to old fashion chalk-and-blackboard teaching. Today we relate the similarity between context free grammars and finite state automata, then finally show what we couldn't do in FSA (a binary string with the same number of 0s and 1s) by adding memory (a.k.a stacks) onto a similar looking FSA - the PDA! - to make it work.

I was quite relieved to find out that they are extremely similar, guess I don't have to worry about not understand it, because I can study off FSA with a few slight changes and a few more objects added to it. However, I do have to begin preparing for test 3, in the midst of me studying for other courses as well.

Context-Free Grammars

2008-11-29T23:04:00.002-05:00

Date: This Friday

Today we moved on to what we do best, proving that the context-free grammar works. The one grammar we are proving in the lecture denotes the set of binary strings having the same number of 0s and 1s.

The proof itself is not hard, but extremely long (just like proof of correctness and the proof of the DFSAs/NFSAs). Not to mention the random Intermediate Value Theorem jumping in out of nowhere to save the day (it works perfectly with this proof), that really surprises me.

I'm still enjoying my relatively free week to study before the exam storm brew, 4 consecutive exams, with my first two exams (back-to-back - right after each other) on the first day.

Oh, scratch that! I'll have to find time in the midst of studying to do well in the third test/think up a problem solving question for this Slog, not to mention 207 project in its final phase... there's still quite a lot of things to keep me busy these days...

New lesson

2008-11-26T23:20:00.003-05:00

We finished with all the regular expressions and formal automata stuff, now we moved on to context-free grammers.

Everything's still related, with the grammer taking in variables, terminals, production and start states similar to the DFSA/NFSA material. I liked how you can express many strings in the language this way, it is also very fun but tricky like the exercises for today.

I'm still enjoying my rare workload-free week, I plan to start studying for the third test during the weekend.

It's all over (I guess?)

2008-11-24T23:15:00.004-05:00

Bad day, bad day, bad day >_<

First, there's phase 3 for the 207 project due in the morning, second, there's stat problem set to hand in, third, assignment 3 for this course. I have to cope through the whole day with massive sleep deprivation.

Back on topic, today we learn the definition of non-regular languages, what surprises me the most is the fact that there are more non-regular languages than regular languages, as well as the fact that the alphabet we are using (binary digits of 0 and 1) was not even regular at all!

As well, the pumping lemma. I also raise the question about the "lemma" alongside with Danny, because to me it seems very important in this topic. The pumping lemma is useful to determine whether a language is regular or not, as well as its simplicity, both in diagram and definition. I also find it rather funny how you can "pump" a language to make it irregular.

Now that most of the workload is done, with two more weeks to go, I'll catch up on the study, get more sleep, and prepare for the final exams during December.

Ack!

2008-11-23T00:40:00.002-05:00

Date: Friday

Apparently I'm not good at keeping track, it is now Sunday (when I'm writing this).

Today lecture is similar to the lecture we did a few weeks ago regarding how PWO, PCI and PSI relates to each other, we started first by deriving a regular expression given a DFSA, and show that how regex, NFSA, and DFSA also has very close relationships with each other.

I still have trouble grasping the purpose of epilson transitions in NFSA, is it just some kind of a placeholder?

I haven't started working on assignment 3 yet, I looked at it a long time ago, thought about it, but haven't written any conceivable proofs regarding it. It doesn't seem that hard, I just have trouble formulating the definition of the Kleene star (question 3) in the head, and how I should go about to prove it. Right now, I'll take a rest - a brain's always clearer when you're not tired.

Pointless entry

2008-11-19T23:08:00.003-05:00

Ah, so I finally understands what NFSA is, and how it relates to DFSA in today's lecture.

The massive amounts of epsilon transitions confuses me a little, but everything makes sense with a picture of a FSM.

Still cannot grasp the ideas behind many of the regular expression symbols, but it should be cleared when I worked through problem set 6 and assignment 3.

Should start on both above-mentioned work.

A new week

2008-11-17T22:31:00.002-05:00

Due to my poor eyesight for today, I'm unable to write everything down, so I'll recall with my memory of today's lecture.

So we started to prove that a Deterministic Finite State Automata (DFSA) is correct given what the machine supposed to do and a proper string in the alphabet. The prove itself, like the proof of correctness, is rather long but not hard.

Next, we went on to the definition of NFSA (what's the N stands for anyways?), which I (unfortunately) can't see too clearly what it is about, I assume it is quite similar to that of the DFSA.

I'll take a break today, got to rest my eyes.

second midterm....

2008-11-15T23:28:00.003-05:00

Date: Friday

I see a pattern correlating with me and the midterm (of all kinds):
- When I'm not confident, when I feel I'll do bad on it, the mark generally are higher than what I expected.
- When I'm confident, when I feel alright about the midterm, the mark is lower than what I expected (well... not really, just lower then average... overall).

I don't get it, so maybe I'll just stay insecure about every kind of of written exam, there's much more improving I needed to do to get better on it.

Today's class is gone basically into course evaluation and handing back problem sets and midterms, since there are not much to write about on Friday, I'll finish here.

FSAs

2008-11-12T23:04:00.002-05:00

I think I finally can grasp the usage and idea behind regular expressions now, so I think this will propel me quickly in understanding the lecture.

Today's class is rather interesting - more deterministic finite state automata, it was so interesting that I might just search for the same program that Danny used in the class today and the previous lesson before that.

But the darker side, I'm still a bit confused about the definition of language and a set of alphabets (afterward when I'm doing my problem set 5 I finally understand the difference between them), so there's hopefully no problem with this topic from now on. All I need is to spent time wisely and catch up with my work.

Sigh...

2008-11-10T21:01:00.004-05:00

I've suffered a major sleep deprivation today finishing off A2 for 207, sleeping at 4 a.m. and waking up at 8 a.m., not that it's a big deal for other people (who I guess have experienced worst) who had been through this many times, but I just don't feel like myself today.

Strangely, it's the opposite that happened. Usually I'm awake mentally but tired physically, but today I felt I can stay through the lecture without completely collapsing mid-way through the lecture, yet I have trouble concentrating mentally, oh well... this happens only today I guess...

The lack of practice for today's topic (regular expression/finite state automata) certainly had me at a loss yet again, this is amplified more by the lack of sleep explained above. With enough time (I still haven't studied for the MAT 223 quiz on Thursday yet) I'll have to try harder reviewing those to get a better grasp of this and prevent me from falling seriously behind.

Then there's another problem set, oh great..., well..., at least my workload eases up a bit after this week.

Minor complaint here: It just seemed like this course, together with STA 247, has been giving us weekly work throughout the semester, it's hard as it is for me to went through this (plus other courses) without a break or a two in between, plus I'm behind in all of my courses yet again, oh time... you are certainly very elusive when I need you.

Reflections on the second midterm

2008-11-08T23:23:00.002-05:00

Date: Friday

I still didn't do quite well, but at least I'm more confident in my proofs now having been through two months of inductive proof training. The reason why I didn't get a chance to finish writing up the midterm is because I spent way too much time on question 2 - trying to make sure all the cases work. I managed to find the loop invariant and write out the proof structure, but I handed the midterm in early because I figured there's nothing you can do in less than 1 minute. Question 1 otherwise was easy and relatively straightforward, yet I tripped myself a bit (overwhelmed?) at the beginning when I couldn't figure it out.

I just hope that I can continually to improve all the way to the exam.

The proofs of regular expression

2008-11-05T21:07:00.002-05:00

Such a wonderful topic...

Yes, I need to get myself acquainted with the definition of regular expression/formal languages first before re-reading the lecture notes to fully understand it.

We did the mutual exclusion of binary numbers 0 and 1 for x \in L1, X \in L(1*(01*01*)*). The amounts of *s, 0s, and 1s really make me uncomfortable, so does all other regular expression I've seen so far.

Oh well! Guess I need practice, but first I need to make sure I prepare myself well for the next term test ahead.

First entry in November

2008-11-03T22:19:00.002-05:00

I kind of forgot that the daylight saving actually was moved to last week in October, so I guess this has a bit of side-effect regarding my physically wellness...

Leaving that aside, we started November with a brand new topic - formal languages. Having briefly skimmed through the near-end of the textbook, the mass amount of symbols is extremely daunting. I felt a bit of relief from today's lecture, where we started everything from scratch.

We were exposed with the definition of alphabets (a set of symbols that is undividable, denoted capital sigma), string (a finite sequence of symbols from capital sigma), and language (all possible strings over capital sigma to capital sigma star), as well as various operations regarding them.

We also get started on regular expressions (the basic definition really) before the time is up. Despite being tired, I still managed to absorb most of the lecture in my head. I find the proof for this type of topic will be interesting, especially when you treat strings (or characters) as normal real/integer numbers.

I find this course to be very beneficial to future computer scientists, from learning the various ways of proving using induction, recursion/iterative proves, correctness proof of programs to this topic (programming languages) and more stuff to come (chapter 8 stuff?), it will surely prepare future computer scientists with a number of important skills that they need.

Discrepancy

2008-11-01T23:02:00.002-04:00

Date: Halloween Friday, supposedly this post should belong to the October posts but oh well...

The end of the eighth week gave us the hardest part of correctness proving - the nested loop. Even staying focused for this lecture doesn't help, as I'm hopelessly lost in finding ways to understand it. First of all, I'm enormously distracted by other assignments/problem sets due next week to even bother reviewing for the second term test next week. Second, my understanding of loop invariant is not sufficient enough - I thought that it is some variable staying unchanged throughout the loop, using it to prove the postcondition certainly had me going back to re-understand this stuff (if I got the time for it). And lastly, as I stated in previous posts that it will take awhile for me to understand and prove correctness for iterative loop - especially the part about finding a decreasing sequence that will make the loop terminate.

So much stuff to do yet so little time, ah... certainly I need to spent time wisely from now on...

...Tired

2008-10-29T22:50:00.002-04:00

For some reason, my physical wellness behaves just like biorhythms, guess today I hit a record low, I'm very tired lately... just couldn't get enough quality sleep...

Today's lecture I didn't even bother copying it down or do the brainstorming excercise, that's how bad it was, but I still remembered Danny lectured about a more complicated case of an iterative loop.

Ack! Because of that I don't think I did well on the 207 midterms either, but what can I do?

Guess I'll have to sleep earlier today.

A long entry

2008-10-27T21:02:00.003-04:00

Ahh... a lot of things to write about:

First, the deadline for problem set 4 got extended until today (originally due on Fridays), being lazy as I'm usual was, I practically delayed doing it until Sunday, it wasn't that hard, just have a lot of explanation to do.

Second, assignment 2 was also due today (in the midst of me writing this...), I have to say those problems are extremely challenging (I have to thank whoever made this, as this assignment gave huge amounts of exercise to my brain). Strange note here, bonus marks? Oh well... I don't think I have enough stamina or brain power to do it after the horrors on that first question.

As for today's lecture, we started doing program correctness for iterative (as compared to recursive) programs. Like Danny noted, it really does get awhile to become comfortable doing such proofs as the program is longer and less straightforward compared to the recursive ones. Not only that, the fact that it is necessary to prove that the loop terminates threw me off, other than that it looks extremely similar to how you'd prove for a recursive program's correctness.

The prove of correctness, as I've observed, requires the student to have excellent and clear writing skills, which I lack both (which will undoubtedly gave me a disadvantage). Guess finding time to practice is my only hope...

End of the seventh week

2008-10-25T23:10:00.002-04:00

Date: Friday

Oh my, guess I'll never been free again until the end of school year - with midterms gone, assignments/problem sets of various kinds resume again.

We finished writing out the program correctness for the greatest common divisor, as well as starting on the divide-and-conquer (theory or algorithm?) for natural powers. As I've been through 2 midterms and lack of sleep throughout the whole week, it's natural for me to collapse (fall asleep) during the middle of the lecture, don't worry... I still picked up the lecture while resting~

Since the fourth problem set gets postponed, my natural inclination tells myself to put it off till the weekend. With both the second assignment and problem set due on Monday (at different times of course), it's very hard to decide which one to focus on.

Either way, I'm done writing here, got to go working on the assignments and problem sets.

GCD

2008-10-22T21:08:00.002-04:00

...This sure is a busy week...

We finished off proving the program correctness for the binary search function, I have to say it was long: it took off one side of a blank line paper! I can never do anything like that requiring to write so much. As well, we got started on the greatest common divisor (GCD) that has been delayed for some time.

Ack! Two midterms in one week, I really couldn't concentrate on today's lecture as my mind is split between studying and working on the assignment, oh well... time to end it here then.

Guest lecturer

2008-10-21T10:29:00.002-04:00

Date: Meant to post it yesterday, but I'm just too tired and I forgot...

On Monday Danny was away to UTM doing some... fictitious research? Either way we have a special lecturer from UTSC, named Nick, to start on proving the correctness of your program.

It's something not that hard I guess, having seen precondition/postcondition everywhere when coding programs, yet I find it intriguing to prove how a program is correct.

It was... overall extremely interesting, Nick was a wonderful lecturer despite not many people shown up to this class (I assume they are away studying for the stat midterm, which is a killer). Wish we could have him again (or someone else) someday.

First test results

2008-10-18T21:24:00.002-04:00

Date: Friday

I'm always pessimistic about tests, but always ended up getting higher then hoped for. This is a good thing to lower your expectation in U of T slightly as you feel better when you are not looking too high up at what you are expecting, but still I need to improve as I think the TAs really gave us easy marks on this test.

As well, we handed the third problem set in. I'm a bit worried about what I conjectured because there has been a little bit of confusion with the term "closed formula", I ended up deriving a sum notation which on the discussion board is obviously incorrect, I really hope I didn't mess up on that.

Anyhow, we officially moved away from induction to time complexity proofs, which, I hope, is less abstract than the multiple flavours of induction.

...Kind of forgetting what I learned on Friday, because I'm spending time right now doing rough works for the second assignment, I have to say those questions are really interesting, especially the ternary trees one.

Refreshed

2008-10-15T22:18:00.003-04:00

Certainly, after a long weekend of productivity, I managed to get some rest and caught up with all my courses, what a relief.

I felt different too, even though I'm physically tired, I still am able to concentrate on the lecture today mentally and perform above-average on the brainstorming session. I'm in a much better state compared to before, when I'm exhausted both mentally and physically.

We carried on with more recursion "unwinding" practice and proving the closed form formula... nothing new here, so I'll end my entry now, got to go study another midterm in this "Fantastic" month.

Reflections on the first midterm

2008-10-11T23:19:00.004-04:00

Date: Late by one day

It's always usual to do bad on your first attempt, it is also true that people can improve from it after their first mistakes.

I don't think I did well on the first midterm, I still managed to finish all the proofs but I doubt I'll get full marks on any one of them. The first page of the midterm specifically said not to mislead the marker, but I ignored the warning and write something that looks very ambiguous and then quickly joined up the induction step to the conclusion since I'm running out of time (I started the writing part after half the midterm time had passed).

It can be attributed to the lack of practice writing proofs, as well as the lack of preparation on this midterm (how surprised I was when I looked at the question - note to self: never underestimate this course again). Luckily whatever mark I got from the midterm can be canceled out by the extremely lucky high mark obtained on the assignment.

A mistake is a mistake, the only thing I wish I could do is to learn from it and do better next time!

Quick entry

2008-10-08T22:56:00.003-04:00

Not going to write much here as I have Linear Algebra quiz and this course's midterm on Friday: we finished up proving using structural induction on the number of nodes in a binary tree, and started to prove the matching parenthesis claim.

The claim itself is a bit weird (haven't seen a proof like this), along with the fact that I am always tired in the morning that affects my thinking (so I didn't even bother trying out the proof for it but just plainly write the initial solution down).

Don't really want to waste time here, as I'm behind in reading for both MAT223 and this course, got to get as much as I can done before the test starts.

Just need that much more time...

2008-10-06T22:25:00.007-04:00

Just like I'm always late for Friday entries, I'm always tired when it is Monday (perhaps due to the cause of weekend?).

This week we learned about finding the closed form for the Fibonacci sequence, as well as trying out a similar sequence just like the Fibonacci number. As my brain is not functioning as much as I wanted, I did what I can by following the example on the slide and managed (surprisingly) to work out half the solution to the closed form for the sequence.

Not only that, we also started learning to define sets with induction for trees, let's just say that everything about this part of the lecture just flies through my brain, how I hate Mondays...

Back to midterm preparations, just need as much time as I can put it in... as well as a decent sleep (at least) before the dreaded week begins and as well as to get more sleep the day before the midterm.

The "always late by one day" Friday entry

2008-10-04T22:38:00.004-04:00

Date: Yesterday

Guess I'm always late for Friday entries, since I find it so tempting to just relax it away...

Today's class we looked at the binary search function and tries to unwind it's patterns as well as analyzing its running time. With most of the stuff coming back from CSC165, I find it not that hard at all even though my brain is half-dead from waking up extremely early today.

There's... a bit of break from all the assignments and problem sets this week, since the midterm is next week for this course (unfortunately there's still the STA 247 homework). I won't write too much here then... I will use this time wisely (I hope, I'm a huge procrastinator...) to catch up on my other courses as well as preparing for the midterm-filled October.

October!

2008-10-01T22:29:00.003-04:00

It is October already, that was fast!

We continued on with induction for the Fibonacci numbers, where we shrunk the base cases from 2 to 1 (we really just need n=0 to make the prove work).

Then we moved onto Python recursion program, zero-pair binary strings, which looked extremely similar to the link I've found from the last post, we did some algorithm analysis in which we learned back in CSC236.

We also take a quick look at recursion functions that are not very well-defined, in fact, the third function surprises me a lot - it was quite hard to grasp the concept right after the lecture, but after working out the algebra I felt a bit relieved to see that it actually can work.

Off-topic tidbit: We actually went through the overheating "time-out" of the projector (that happened since last week) and got it working again. I really wonder what's going on with the projector (why didn't it happen before?) and why the maintenance people did not fix it yet. Also, somehow the lecture room (compared to my other lecture classes) is quite... humid, is it because of the small room and huge amount of people? That I will never know...

The start of my busiest week

2008-09-29T22:20:00.005-04:00

Gah... someday my body will tell me to stop doing my assignments on the last day it is due, today I've already handed two assignments in, now for the next one due tomorrow...

Assignment 1 is brutal, not in the sense of being extremely hard, nor the question being too ambiguous. It is challenging in the way that requires me to brainstorm, then to think about a possible way of writing a valid proof for that question.

Interesting enough, exploring the assignment questions can lead to valuable results. By looking into question 2, I found a binary way of proving the question (the real trouble is actually doing the proof - to tie this information together).

Today's class we started on proving recursively, the same stuff we did in CSC165. If only my brain is not that tired yet...

End of third week

2008-09-27T19:29:00.005-04:00

Date: Late by one day, grr...

I've handed in my second problem set to the instructor, the first part is extremely easy as it is just the exact problem we did in class with different numbers. The second part is, however, not quite as easy.

The main reason to this is that we can't use induction efficiently to proof the statement (it is still possible). I ended up doing it using proof of contradiction, and I doubt I'll get full mark for it because of that. Next time, I'll start the problem set way earlier so that I don't have to panic the day before the problem set is due.

In class we spent the whole class critiquing three different proofs, it was mildly funny to see that a proof can be constructed even though the base case can be wrong. I got lost on the more wordy proofs, but they were interesting in their own ways.

Back to the first assignment, I have to say that the assignment is quite challenging, and will take people awhile to figure out a reasonable proof to a question. I've figured out the pattern for question 2 already but I'm stuck at how to convert the pattern into a proof. Other than that, I just have to keep on trying :).

Messing with bases.

2008-09-24T23:15:00.004-04:00

After understanding the lecture taught in last class, I find today's lecture to be slightly easier. It is basically a modified version of induction where the base cases are unusual and has to be found and proved.

Writing out the proofs for today's problem is not that hard as well, the only thing I need to improve my proving (or problem solving) technique is to understand the question quickly and get a rough idea going as soon as possible, that way I can save valuable time for actually determine the solution. But this doesn't come easily as I need to get more exercises to practice, other than that, this will be the end of this post.

P.S. I hope my blog is not too messy (filled with entries).

Overwhelmed

2008-09-22T23:04:00.003-04:00

Date: Same day, finally I caught up!

We started off with a proof about the Principle of Well Ordering (PWO), then I kind of get lost on what Danny is teaching (I'm extremely tired today).

Basically, it's about the relations between PWO, Simple Induction (PSI), and Complete Induction (PCI). Which means a cycle or chain of implications joining them: PWO => PCI => PSI => PWO, and a few proofs on that.

Need sleep terribly, guess I'll review this lecture at some other time.

Stamp like crazy!

2008-09-22T01:18:00.001-04:00

Date: September 19, 2008

We handed our problem set 1 to the prof today, I wouldn't say it is too hard as the questions are just a variation of the proofs we did in lecture, still... I'm pessimistic that I might not get a high mark (from last year's experience with CSC165 assignments) since I'm afraid that I didn't explain every step clear enough.

Continued on with this course, we did a question that was given to us as an exercise back in CSC165, the question simply asks what postage can be formed with 2 different valued stamps.

I remembered solving this question rather easily in CSC165, but looking at the proof Danny wrote kind of threw me off at first, but I understood it right afterward.

We also managed to write down the definition of the Principle of Well Ordering, which is states as: every non-empty subset of natural number has a smallest integer. It's a rather obvious fact, but proving it will be kind of hard...

Back to the second problem set, oh dear... what number > k can I form a postage with 5 and 11 cent stamps...

I always have this kind of problem... staring blankly at a proof, guess it takes awhile for me to get the question and the rough idea to sink deeply in my head.

Trees and chocolates

2008-09-22T01:06:00.005-04:00

Date: September 17, 2008

Today's lecture covers FBT (Full Binary Tree) and Complete induction. I find that I needed to catch up again with the basic properties of a Full Binary Tree, as I'm not good with this type of question back in CSC165.

Besides the trees, we also did a quite interesting problem with the chocolate bar (that makes me hungry by the way). The problem states: Every chocolate grid of n squares can be broken into seperate squares with n - 1 breaks.

As usual, we have our time to write out our own ideas about this question, which I think I did pretty good on that.

Now, the real challenge for me is to keep this up for every question I've encountered...

Second week

2008-09-22T00:55:00.004-04:00

Date: September 15, 2008

After wasting off my weekend (besides being busy of course), I'm back at school again in the second week of my second year.

We learned Prime factorization, which is defines as: Prime factorization of n is a sequence of prime numbers with product of n. Something useful for proofs and was talked about it in CSC165.

As well, we moved on from the Principles of Simple Induction to a new flavour of induction called - Complete induction. Complete induction basically means if every elements up to n-1 implies P(n), then that suggests every n is true for a given claim (P(n)).

The special thing about Complete induction is that you don't need base cases at all (yipee?), well... it still wouldn't hurt to follow the structure in CSC165 by putting a few in. Complete induction is extremely useful in the case when the base case is either ambiguous or cannot be formed completely, so that we can just move along with the induction step.

Basically this is today's lecture, using Complete induction on claims relating to Prime factorization, oh well... that's it for this post!

Experience after the first week

2008-09-20T22:32:00.000-04:00

Date: September 12, 2008

A week has gone by for my second year, and it just seems so different from the start of my first year. I still remember the confusion of first year, running around trying to find the right lecture room, the massive workload, the amount of new material there is to learn...

It's all different now, with the workload and schedule lowered drastically, it's much better for me to spend time equally for all my courses, so that I won't repeat the mistake of CSC165.

Again, we cover induction from CSC165, it really isn't that hard. Strangely, the proof that we did in the first week is actually applicable in a course like STA247... how handy!

To be honest, compared to my other courses, this course has the most workload out of all 5. My reasoning is that we needed that much more practice and experience to get the most out of it for this course, as we can be better prepared for higher level CSC theory courses.

...I'm not (really!) complaining about the workload here, as I have to say CSC165 followed this pattern and that everything I learned is through though assignments and exercises, and the information is very valuable and useful in courses besides Computer Science.

The beginning of a new semester

2008-09-20T22:15:00.000-04:00

Date: September 10, 2008

Yes, the date above is wrong, but I'm a bit late at writing this, so... I'll try to not confuse too many people from now on. I'll try to keep my CSC165 way by writing a post after every lecture.

Distractions aside:

After all the administration and stuff, I finally get the first taste for this class. We start with basic "principles of simple induction" that was taught in CSC165 as well, but I'm not so sure whether this was a review or not.

Again, the uncomfortableness started again, at times I still can't believe how much time and energy is saved from relaxing the structure of a quick induction proof. For lazy people like me this is a good thing, but without the support of a properly placed structure, I get confused rather easily.

The proof in the course is also not that hard to begin with, as I did the question (and it's many variations) back in high school. I could still recall with horror the brutality of my high school "Algebra and geometry" test/exam. The experience from that course, even if it is horrible, did get me prepared for most of university courses.

Welcome to CSC 236 Course Log!

2008-09-20T21:45:00.001-04:00

Heh... guess I'm a bit late at this.

Hello all, this is my journal entry for CSC 236, where I will put my own personal reactions (to the course), problem solving solutions and what I've learned here on this blog.

First off, I will discourage anyone from viewing this blog unless they are a part of CSC236, either a fellow classmate or the instructor/TAs. Just in case they don't understand what I'm talking about and wasting their own time :P.

Onwards:
First Class (September 8, 2008):

After a relaxing summer, it's time to go back to school for my second year at U of T!
The knowledge of first year told me to never-ever take two courses right next to each other and as well not to take early morning courses. Well, there's nothing I can do about this course (unfortunately, I think that 10 a.m. classes are still way too early), so I guess I'll have to handle it for this semester.

CSC236 is, in my opinion, the continuation of CSC165 with more depth and material, having gone through CSC165 I thought I'm prepared with most of the course material...

...And I was so wrong, well... not what we are learning of course. Induction was taught over and over again in high school and rather forcefully in MAT137, so I have a clear grasp on that. But after reading through chapter 0 in the course note, I discovered that I still have a bit more gap to fill in order to succeed in this course.

Not only that, I *almost* forgot a lot of 165 material (thankfully it didn't take that long to get everything back in my head) due to the 4 month break. I'm also a bit not used to relaxing the proof structure that was done for the whole semester in 165, guess I'll have to get more comfortable with that.

The last thing that I'm uncomfortable with is to write the course journal out in public like this, I really wished to have the old CSC165 wiki/SLoG back.