I wish I had found a better problem for the previous post. Initially I wanted to find a solution to the 2-player game where you have n columns, and m_i rings in the ith column, and each player can take as many rings as s/he wants from any one of the colums (but is not allowed to touch more than one column, and must take at least one ring). The player who takes the last ring loses. I tried to prove it using some sort of nested induction, but I failed. I did manage to solve it for the special case n=2, but then again, that is probably not very hard to do.
Anyway, later I found out that the game is called Nim, and I read it's solution and proof in wikipedia. It is safe to say I could have never solved it within the end of this semester.
Overall, I would say this was a very nice course. Regular expressions, CFG's, FSA's, and PDA's were of much greater interest to me than I thought they would be (which is not to say that I thought they would be boring). I'm definitely going to pick up a more advanced book on the subject to study during the summer. Either that or a book on computability (if anyone reading this has any suggestions, it would be nice if you told me in a comment).
I did think that the tests were marked a bit too harshly and marks were taken off for fairly trivial things, but that's ok.
Friday, December 5, 2008
Math problem
First, some definitions and results that will be assumed to be true (and in fact are true, but will not be proven here):
Definitions:
Rn is the set of all n-tuples with real coordinates.
If A is a subset of Rn, A is a rectangle if A = [a1, b1]x[a2, b2]x...x[an, bn] (where ai, bi \in R, and ai <= bi for all 1<=i<=n). If A is a rectanlge in Rn then let the volume of A be vol(A) = (b1-a1)*...*(bn-an). If f:Rn -> R and A is a rectangle in Rn, then f|A is the function from A to R defined by f|A(x) = f(x), \forall x \in A.
If f:A -> B (A, B are any sets), define the graph of f to be F = {(x, f(x)) | x \in A}. (So F is a subset of AxB)
A partition P of a closed interval [a, b] is a non-decreasing, finite sequence of numbers t0, ..., tk such that t0 = a and tk = b.
If f:A -> R (where A is a rectangle in Rn), a partition P of A is P = (P1, ..., Pn) where Pi is a partition of [ai, bi] (where A = [a1, b1]x[a2, b2]x...x[an, bn]);
mS(f) = inf{f(x) | x \in S}, MS(f) = sup{f(x) | x \in S} (where S is a subrectangle formed by P); L(f, P) = Sum(mS(f)*vol(S), over all S's in P), U(f, P) = Sum(MS(f)*vol(S), over all S's in P); and f is integrable if and only if
sup({L(f, P) | P is a partition of A}) = inf({U(f, P) | P is a partition of A}). We say that sup({L(f, P)}) is the integral of f.
If S is a subset of Rn we say that S has measure 0 if, for any e > 0, there is a sequence of closed rectangles A1, A2, ... such that S is a subset of the union of all Ai's, and Sum(vol(Ai), over all i \in N) <> R is integrable if and only if for any e > 0 there is some partition P of A such that U(f, P) - L(f, P) <>= 1, there is a set of countably many closed rectangles that are subsets of Rn, the union of all of which is Rn (this is easily proved by induction on n: for n = 1, ... [-1, 0], [0, 1], [1, 2], ... is the obvious candidate, and for n+1 the collection that satisfies the required properties is the result of taking the cartesian product of each set in the collection for R1 with each set in the collection for n).
So, I decided that the math problem I will solve as a SLOG requirement is this: if f:Rn -> R is a function such that f|A is integrable for any closed rectangle A \in Rn, does f's graph have measure 0?
The answer is yes. Intuitively, this is because for every point in Rn we only have one point in R, and f is integrable so it is fairly well behaved; so in some sense, in most places the graph is infinitely thin and we can chose rectangles that are as thin as we want and still manage to cover it.
Let O be a collection of countably many closed rectangles in Rn such that their union is Rn. For any A \in O, we will prove that the graph of f|A has measure 0. For any e > 0: we know that f|A is integrable, which means that there is a partition P such that U(f, P) - L(f, P) = Sum(MS(f)*vol(S), all S's in P) - Sum(mS(f)*vol(S), S's in P) = Sum((MS(f)-mS(f))*vol(S), all S's in P) < e (%%). Let Q = {Sx[mS(f), MS(f)] | S is a subrectangle of P}. By the definition of the volume of a rectangle, the sum of the volumes of all the rectangles in Q is Sum(vol(S)*(MS(f) - mS(f)), S is a subrectangle of P) < e by (%%).
For any (x, y) in the graph of f|A, y = f(x) (by definition of graph). Since P is a partition of A, there must be some subrectangle S' of P such that x \in S'. By definition of mS(f) and MS(f), mS'(f) <= f(x) <= MS'(f), which means that f(x) \in [mS'(f), MS'(f)], which means that (x, f(x) \in S'x[mS'(f), MS'(f)] \in Q. So for any (x, y) in the graph of f|A, (x, y) in some rectangle in Q. So Q covers the graph of f|A. As we just showed, the sum of the volumes of all rectangles in Q is smaller than e. So by definition of measure 0, the graph of f|A has measure 0.
Since there are countably many rectangles in O, and since their union is Rn it follows that the graph of f is the union of the graphs of f|A (A \in O). Since each of those graphs has measure 0, and since there are countably many of them (one for each member of O, which has countably many members), it follows that the graph of f has measure 0.
Definitions:
Rn is the set of all n-tuples with real coordinates.
If A is a subset of Rn, A is a rectangle if A = [a1, b1]x[a2, b2]x...x[an, bn] (where ai, bi \in R, and ai <= bi for all 1<=i<=n). If A is a rectanlge in Rn then let the volume of A be vol(A) = (b1-a1)*...*(bn-an). If f:Rn -> R and A is a rectangle in Rn, then f|A is the function from A to R defined by f|A(x) = f(x), \forall x \in A.
If f:A -> B (A, B are any sets), define the graph of f to be F = {(x, f(x)) | x \in A}. (So F is a subset of AxB)
A partition P of a closed interval [a, b] is a non-decreasing, finite sequence of numbers t0, ..., tk such that t0 = a and tk = b.
If f:A -> R (where A is a rectangle in Rn), a partition P of A is P = (P1, ..., Pn) where Pi is a partition of [ai, bi] (where A = [a1, b1]x[a2, b2]x...x[an, bn]);
mS(f) = inf{f(x) | x \in S}, MS(f) = sup{f(x) | x \in S} (where S is a subrectangle formed by P); L(f, P) = Sum(mS(f)*vol(S), over all S's in P), U(f, P) = Sum(MS(f)*vol(S), over all S's in P); and f is integrable if and only if
sup({L(f, P) | P is a partition of A}) = inf({U(f, P) | P is a partition of A}). We say that sup({L(f, P)}) is the integral of f.
If S is a subset of Rn we say that S has measure 0 if, for any e > 0, there is a sequence of closed rectangles A1, A2, ... such that S is a subset of the union of all Ai's, and Sum(vol(Ai), over all i \in N) <> R is integrable if and only if for any e > 0 there is some partition P of A such that U(f, P) - L(f, P) <>= 1, there is a set of countably many closed rectangles that are subsets of Rn, the union of all of which is Rn (this is easily proved by induction on n: for n = 1, ... [-1, 0], [0, 1], [1, 2], ... is the obvious candidate, and for n+1 the collection that satisfies the required properties is the result of taking the cartesian product of each set in the collection for R1 with each set in the collection for n).
So, I decided that the math problem I will solve as a SLOG requirement is this: if f:Rn -> R is a function such that f|A is integrable for any closed rectangle A \in Rn, does f's graph have measure 0?
The answer is yes. Intuitively, this is because for every point in Rn we only have one point in R, and f is integrable so it is fairly well behaved; so in some sense, in most places the graph is infinitely thin and we can chose rectangles that are as thin as we want and still manage to cover it.
Let O be a collection of countably many closed rectangles in Rn such that their union is Rn. For any A \in O, we will prove that the graph of f|A has measure 0. For any e > 0: we know that f|A is integrable, which means that there is a partition P such that U(f, P) - L(f, P) = Sum(MS(f)*vol(S), all S's in P) - Sum(mS(f)*vol(S), S's in P) = Sum((MS(f)-mS(f))*vol(S), all S's in P) < e (%%). Let Q = {Sx[mS(f), MS(f)] | S is a subrectangle of P}. By the definition of the volume of a rectangle, the sum of the volumes of all the rectangles in Q is Sum(vol(S)*(MS(f) - mS(f)), S is a subrectangle of P) < e by (%%).
For any (x, y) in the graph of f|A, y = f(x) (by definition of graph). Since P is a partition of A, there must be some subrectangle S' of P such that x \in S'. By definition of mS(f) and MS(f), mS'(f) <= f(x) <= MS'(f), which means that f(x) \in [mS'(f), MS'(f)], which means that (x, f(x) \in S'x[mS'(f), MS'(f)] \in Q. So for any (x, y) in the graph of f|A, (x, y) in some rectangle in Q. So Q covers the graph of f|A. As we just showed, the sum of the volumes of all rectangles in Q is smaller than e. So by definition of measure 0, the graph of f|A has measure 0.
Since there are countably many rectangles in O, and since their union is Rn it follows that the graph of f is the union of the graphs of f|A (A \in O). Since each of those graphs has measure 0, and since there are countably many of them (one for each member of O, which has countably many members), it follows that the graph of f has measure 0.
Saturday, November 15, 2008
Week 10.
Last week's lecture was pretty nice (except the disappointing test mark). I always liked DFSA. I like their names too. "Deterministic automaton". It has a nice sound and reminds me of automatons in some expansion of Age of Mythology and Syberia II.
We also learned the formal definition of a DFSA which was very interesting. I always liked the formalizations of intuitive concepts like functions, graphs, trees, DFSA's. Every time I read about one of them, I am happily surprised by how complete it is and how closely it matches the intuitive notion. Also, it gives a reassuring feeling (since now things can actually be proved about them without relying on hand-waiving (which I always found troubling)) and a feeling of empowerment since it is a discovery that math is much broader and more powerful than the 12 years of studying algebraic manipulations and simple R->R functions might have led us to believe.
Although DFSA's aren't really new to me. In fact, we did an example where we had to construct a DFSA that accepted only strings containing the substring "110" (or maybe some other substring of length three, I don't remember the exact one). It brought back good memories of CSC148 and the O(n) substring searching problem. Since thursday I have been trying to remember the algorithm used for creating the DFSA for a general substring. So far, I am unsuccessful.
Unfortunately I will not be able to go to class on the 20th until 7:30. I am reading ahead to compensate.
We also learned the formal definition of a DFSA which was very interesting. I always liked the formalizations of intuitive concepts like functions, graphs, trees, DFSA's. Every time I read about one of them, I am happily surprised by how complete it is and how closely it matches the intuitive notion. Also, it gives a reassuring feeling (since now things can actually be proved about them without relying on hand-waiving (which I always found troubling)) and a feeling of empowerment since it is a discovery that math is much broader and more powerful than the 12 years of studying algebraic manipulations and simple R->R functions might have led us to believe.
Although DFSA's aren't really new to me. In fact, we did an example where we had to construct a DFSA that accepted only strings containing the substring "110" (or maybe some other substring of length three, I don't remember the exact one). It brought back good memories of CSC148 and the O(n) substring searching problem. Since thursday I have been trying to remember the algorithm used for creating the DFSA for a general substring. So far, I am unsuccessful.
Unfortunately I will not be able to go to class on the 20th until 7:30. I am reading ahead to compensate.
Tuesday, November 11, 2008
Week 9.
So we got the results of the second assignment this week and all I can say is wooooohooooooooo! Hopefully I did well in the second test - I already wasted the 6% on the first test.
Finally we are learning new things. So far I like regular expressions and formal languages (just as I thought I would). The downside of this is that now I can't rely on my usual studying schedule - I have to make more room for CSC236. Sudden changes like this are never good.
Finally we are learning new things. So far I like regular expressions and formal languages (just as I thought I would). The downside of this is that now I can't rely on my usual studying schedule - I have to make more room for CSC236. Sudden changes like this are never good.
Saturday, November 1, 2008
Week 8, part 2
The second reason is that I never much liked proving correctness and time complexity bounds. Correctness isn't so bad, but all time complexity proofs that we have done so far have been fairly simple, but very long. Even in math, I never liked proofs that took so much longer to write formally than to go through in your head.
I find that whenever I try to participate in the lectures (i.e. answering questions), it's much easier for me to pay attention, and I get much more from the lecture. The downside of that, is that inevitably I say something really stupid and embarrassing from time to time. For example, last time I said "it must reach 0" (when we were doing loop termination proofs, and were asked what was so special about decreasing sequences of natural numbers) and if I remember correctly, Danny corrected me and said that it has a smallest element.
Although that's not really relevant; every sequence of natural numbers has a smallest element by the principle of well ordering. What we need to prove termination is that it's finite, and that's what the "decreasing" part gives us.
I find that whenever I try to participate in the lectures (i.e. answering questions), it's much easier for me to pay attention, and I get much more from the lecture. The downside of that, is that inevitably I say something really stupid and embarrassing from time to time. For example, last time I said "it must reach 0" (when we were doing loop termination proofs, and were asked what was so special about decreasing sequences of natural numbers) and if I remember correctly, Danny corrected me and said that it has a smallest element.
Although that's not really relevant; every sequence of natural numbers has a smallest element by the principle of well ordering. What we need to prove termination is that it's finite, and that's what the "decreasing" part gives us.
Friday, October 31, 2008
Week 8, part 1.
Well, this has been a ridiculous week (as a testament to that: as of now, I have spent 40 consecutive hours without any sleep at all).
I have to say, these last few lectures haven't been very interesting to me, for two reasons. Most of it was done in csc165 (not just the concepts - even a lot of the examples). In fact, the only things I can think of from this course, that weren't treated in csc165 are: the master theorem, the equivalence of the 3 principles, and the "find a decreasing sequence of natural numbers" method for proving loop termination (which, by the way, was explained very well. I didn't really fully understand it until yesterday).
And since it feels like someone is drilling a hole in my head, I will continue this when I wake up.
I have to say, these last few lectures haven't been very interesting to me, for two reasons. Most of it was done in csc165 (not just the concepts - even a lot of the examples). In fact, the only things I can think of from this course, that weren't treated in csc165 are: the master theorem, the equivalence of the 3 principles, and the "find a decreasing sequence of natural numbers" method for proving loop termination (which, by the way, was explained very well. I didn't really fully understand it until yesterday).
And since it feels like someone is drilling a hole in my head, I will continue this when I wake up.
Friday, October 24, 2008
Week 7.
I did not go to week 6's lecture (I had to finish my 207 assignment) so I felt it would have been somewhat dishonest to write a blog entry. I also had nothing to say. But this week went pretty well, even though there was nothing really new. The gcd algorithm and it's proof would have been much more interesting if I hadn't encountered them about 5 times before. It would be hypocritical to complain about the slow pace of the course; however, since if the workload was any heavier I would not be able to keep up.
Saturday, October 11, 2008
Week 5.
Grade-wise, this was a good week in CSC236, but I am a bit disappointed because I could have done better. I did not get 8/8 in the problem set because the "P(n)" predicate symbol was missing. But the statement of the predicate I was trying to prove was still there, so this annoyed me.
I was fairly happy with assignment 1, but in the second question I had forgotten to prove that my algorithm for generating the cycles produced every possible menu.
I thought the test was easy. Two of the questions were very straightforward induction. I am a bit concerned with my argument of a certain point in the other question, but I doubt it will affect me much.
I was very pleased with the explanation of how one could get the closed form formula for calculating the nth Fibonacci number. It disturbs me when I see some result that is "pulled out of a hat" in math books.
I was fairly happy with assignment 1, but in the second question I had forgotten to prove that my algorithm for generating the cycles produced every possible menu.
I thought the test was easy. Two of the questions were very straightforward induction. I am a bit concerned with my argument of a certain point in the other question, but I doubt it will affect me much.
I was very pleased with the explanation of how one could get the closed form formula for calculating the nth Fibonacci number. It disturbs me when I see some result that is "pulled out of a hat" in math books.
Sunday, October 5, 2008
Week 4.
The week 4 lecture was ok. Well, at least the first two hours were. The stuff about recursive functions and the Fibonacci numbers was pretty interesting. The Fibonacci pattern (the one with the sum of the first n numbers) was pretty easy to guess, especially since Prof. Heap had posted it in his blog a few days before the Thursday lecture.
In the third hour it became very hard for me to pay attention, but I think I'm getting better in this respect (two weeks ago I spaced out after just one hour).
At some point, when we were proving the time complexity of the recursive binary search, the lecture became slow and the class was not contributing at all. And then Prof. Heap stopped talking for about 10 minutes. I thought we had angered him (it reminded me very much of a lecture in first year where no one had done the required reading, and the professor got very disappointed and dismissed us all). I felt really bad. Then, it turned out that we were supposed to be jotting down our attempts at solving a problem, like usual. I had not been doing anything, and so I felt even worse.
These evening sessions are killing me.
In the third hour it became very hard for me to pay attention, but I think I'm getting better in this respect (two weeks ago I spaced out after just one hour).
At some point, when we were proving the time complexity of the recursive binary search, the lecture became slow and the class was not contributing at all. And then Prof. Heap stopped talking for about 10 minutes. I thought we had angered him (it reminded me very much of a lecture in first year where no one had done the required reading, and the professor got very disappointed and dismissed us all). I felt really bad. Then, it turned out that we were supposed to be jotting down our attempts at solving a problem, like usual. I had not been doing anything, and so I felt even worse.
These evening sessions are killing me.
Tuesday, September 30, 2008
Week 3.
This post is 2 days late, but then again, I have been very busy. Week 3 was nice. I really liked the problem with the round-robin tournament, especially its solution. Seeing it put a smile on my face. It was so simple, and yet I could not think of it on my own. That also upset me a bit.
I am ashamed to say that I did not pay any attention to the proof of the equivalence of the three principles. It was about 7:30 and I was very tired. However I did read the proofs in the notes.
I also liked the wrong proofs that we had to analyze. I am a big fan of bug hunting in general, be it in proofs or programs. It's like vaccination. In fact, I would like to do more of this here and there, especially in circumstances when we are not expecting them. It will make us less susceptible to blindly believing things we are told. Also, it will keep us on our toes.
I finally finished the first 3 questions of the assignment. In retrospect, my proofs in the third question could have been better. That's what happens when you leave things for the last minute.
I am ashamed to say that I did not pay any attention to the proof of the equivalence of the three principles. It was about 7:30 and I was very tired. However I did read the proofs in the notes.
I also liked the wrong proofs that we had to analyze. I am a big fan of bug hunting in general, be it in proofs or programs. It's like vaccination. In fact, I would like to do more of this here and there, especially in circumstances when we are not expecting them. It will make us less susceptible to blindly believing things we are told. Also, it will keep us on our toes.
I finally finished the first 3 questions of the assignment. In retrospect, my proofs in the third question could have been better. That's what happens when you leave things for the last minute.
Saturday, September 20, 2008
Problem set 2.
And I am finished with problem set 2. I was a little disappointed when I saw "5 cent, and 11 cent stamp". I thought it would be identical to what we did in class, but question (b) makes it a good problem set. It's that kind of problem that can be solved by brute force, but that approach is annoying and long enough to make you look for better ways.
Friday, September 19, 2008
Week 2, continued.
I am sorry for the two quick posts, but this is a bit too long to just stick in the previous one as an edit.
A few days ago we proved that any chocolate bar of n squares can be broken up into 1x1 squares by n-1 breaks. We didn't consider the case n=0. I claimed that P(n) was vacuously true for n=0 because there are no chocolate bars with 0 squares. Prof. Heap countered this claim, but I am not fully convinced and this matter has been bothering me since then.
How can there be a chocolate bar with 0 squares? If we reduce the size of a chocolate bar to 0 rows and 0 column, we're left with nothing. So there's nothing there, so there is no chocolate bar at all.
Right?
A few days ago we proved that any chocolate bar of n squares can be broken up into 1x1 squares by n-1 breaks. We didn't consider the case n=0. I claimed that P(n) was vacuously true for n=0 because there are no chocolate bars with 0 squares. Prof. Heap countered this claim, but I am not fully convinced and this matter has been bothering me since then.
How can there be a chocolate bar with 0 squares? If we reduce the size of a chocolate bar to 0 rows and 0 column, we're left with nothing. So there's nothing there, so there is no chocolate bar at all.
Right?
Week 2.
I must say that this has been a very rough start to the year. My bad time-management skills and laziness meant that I did not do as much work as I should have in the first week. So, unfortunately, this week I have focused on math to the exclusion of all else, including csc236 and this blog. This means that the assignment (still not started) is in the bottom of a very long priority queue, but at least I have two weekends to complete it. All of this is making me suspect that maybe summer school burned me out.
I finally could not endure any more of the (how long before the sled stops)/(what's the speed at position x)/(what's the terminal velocity) questions in MAT267, so I dropped it and took CSC438. I am excited and terrified at the same time. It should be very theoretical and fun, and I am looking forward to Professor Cook's lectures. On the other hand, it's a fourth year course (graduate course too), and I have missed the first four lectures, and still have not done all the reading. This relates to CSC236 in the following way: 438 conflicts with 236 on all 3 days, so I will have to start attending the evening section. I am not happy about this. I took an evening course last year (ECO100), and the third hour was a battle just to stay awake. On the other hand economics is a lot more boring than computer science so it may not be as bad as I am expecting.
One more thing. I was very upset to discover that CSC448 has been canceled. It almost seems like a sequel to 438, it has all the prerequisites of 438 with the addition of CSC236, and my next semester isn't very busy so it would have been perfect for me to take. But it is canceled, and 438 seems like it is offered in alternating years, which makes me think that 448 is offered in alternating years. So if it was supposed to be offered this year, it might not be offered the next year, which means I cannot take it before 4th year.
It is a pity - many great courses were canceled this year.
I finally could not endure any more of the (how long before the sled stops)/(what's the speed at position x)/(what's the terminal velocity) questions in MAT267, so I dropped it and took CSC438. I am excited and terrified at the same time. It should be very theoretical and fun, and I am looking forward to Professor Cook's lectures. On the other hand, it's a fourth year course (graduate course too), and I have missed the first four lectures, and still have not done all the reading. This relates to CSC236 in the following way: 438 conflicts with 236 on all 3 days, so I will have to start attending the evening section. I am not happy about this. I took an evening course last year (ECO100), and the third hour was a battle just to stay awake. On the other hand economics is a lot more boring than computer science so it may not be as bad as I am expecting.
One more thing. I was very upset to discover that CSC448 has been canceled. It almost seems like a sequel to 438, it has all the prerequisites of 438 with the addition of CSC236, and my next semester isn't very busy so it would have been perfect for me to take. But it is canceled, and 438 seems like it is offered in alternating years, which makes me think that 448 is offered in alternating years. So if it was supposed to be offered this year, it might not be offered the next year, which means I cannot take it before 4th year.
It is a pity - many great courses were canceled this year.
Saturday, September 13, 2008
CSC236, First Impressions
I must admit, coming into this course I was skeptical. This was fueled by the disappointment of not being able to take CSC240 (since it's only offered in the second semester) and by my suspicions that this course would have a lot of the bad things of CSC165.
I had mixed feelings about CSC165. One one hand, I liked the small amount of material that we learned. On the other hand, I did not appreciate the enormous attention that was paid to the needless formality.
The excessive formality seems to be gone, which is very good, but it has been replaced some other annoying things.
One of those things is the emphasis there seems to be on the problem solving thought process. This is apparent when we do all those exploratory cases in the proofs in class. I don't think that is a good way to approach induction. I find that going immediately to the general induction step is usually more enlightening. It forces you to think in an abstract manner and thus, you gain a deeper understanding of the problem. Moreover, in non-trivial induction proofs (unlike the ones we have been doing) it is usually impossible (or not any easier than the general case) to explore the first few cases. If anyone wants to know what I mean, go to the mathematics section of bookstore and open Friedberg's "Linear algebra" (4th ed.) to page 261 or 490 and read the proofs there.
That is also apparent in the "as well as give some insight into how you found the solution" part of the assignment. Everyone thinks differently and I don't think much can be gained by learning some other person's way of approaching a problem.
Another annoying thing is that we have to submit the assignment solutions as .txt documents.
This seems counterproductive, since typing math is a slow process and because we are doing it in notepad (or some other similar editor), the end result will be very ugly and hard to read. Every small change that we want to make will mean that we have to review and make changes to the whole document after that point (the characters per line limit makes this worse).
One of the good things is that prof. Heap is good at explaining things. I like the use of the tablet PC, and I definitely appreciate the black backgrounds, with yellow and green writing. White backgrounds are harder on the eyes, white writing on black backgrounds provides too much contrast, but yellow and green on black is perfect. It also probably uses less energy compared to white backgrounds, making it more efficient. Efficiency is good.
Even thought this post might seem a bit negative, I am optimistic in thinking that some of the "bad" things that I pointed out will go away, and the rest will not be as big of a problem as they seem. Also, I am very much looking forward to the last 6 weeks (which is when we learn about automata and context-free grammars). However, I wish we did not have to spend so much time on program correctness. We have done a lot of it in CSC165, and it seems like we will do a lot more in CSC263, so I am afraid that what we do in this course might be made redundant by what we do in those two courses.
I had mixed feelings about CSC165. One one hand, I liked the small amount of material that we learned. On the other hand, I did not appreciate the enormous attention that was paid to the needless formality.
The excessive formality seems to be gone, which is very good, but it has been replaced some other annoying things.
One of those things is the emphasis there seems to be on the problem solving thought process. This is apparent when we do all those exploratory cases in the proofs in class. I don't think that is a good way to approach induction. I find that going immediately to the general induction step is usually more enlightening. It forces you to think in an abstract manner and thus, you gain a deeper understanding of the problem. Moreover, in non-trivial induction proofs (unlike the ones we have been doing) it is usually impossible (or not any easier than the general case) to explore the first few cases. If anyone wants to know what I mean, go to the mathematics section of bookstore and open Friedberg's "Linear algebra" (4th ed.) to page 261 or 490 and read the proofs there.
That is also apparent in the "as well as give some insight into how you found the solution" part of the assignment. Everyone thinks differently and I don't think much can be gained by learning some other person's way of approaching a problem.
Another annoying thing is that we have to submit the assignment solutions as .txt documents.
This seems counterproductive, since typing math is a slow process and because we are doing it in notepad (or some other similar editor), the end result will be very ugly and hard to read. Every small change that we want to make will mean that we have to review and make changes to the whole document after that point (the characters per line limit makes this worse).
One of the good things is that prof. Heap is good at explaining things. I like the use of the tablet PC, and I definitely appreciate the black backgrounds, with yellow and green writing. White backgrounds are harder on the eyes, white writing on black backgrounds provides too much contrast, but yellow and green on black is perfect. It also probably uses less energy compared to white backgrounds, making it more efficient. Efficiency is good.
Even thought this post might seem a bit negative, I am optimistic in thinking that some of the "bad" things that I pointed out will go away, and the rest will not be as big of a problem as they seem. Also, I am very much looking forward to the last 6 weeks (which is when we learn about automata and context-free grammars). However, I wish we did not have to spend so much time on program correctness. We have done a lot of it in CSC165, and it seems like we will do a lot more in CSC263, so I am afraid that what we do in this course might be made redundant by what we do in those two courses.
Subscribe to:
Posts (Atom)
