Log Seven

For assignment 3 my partner and I divided up the questions so we could work on them individually, as we didn't have much time to meet up for this week. I found that the first problem that I worked on, which was question 2, seemed unnaturally hard for me to prove. Unfortunately the issue here involved a misunderstanding of the usage of the less than or equal sign. When I first tried working on the question, which was to prove that 5n^3 - 3n^2 + 2n + 3 was in big O of 2n^3 - n^2 + n + 1, after some reductions I ended up with the problem of trying to prove that one expression could be both greater than or equal to another expression. To me it seemed that there was an issue here; even though one side can be greater than the other, there was no way for it be equal. I eventually looked through some of the practice questions and found out that the equivalence doesn't have to be satisfied, as long as the "greater" sign is. Although I should have known this, due to the "or" part, it just seems to be something that slipped my mind. Hopefully I don't repeat this mistake again as its a very fundamental concept. After fixing this misunderstanding, which hopefully is correct in the end, the question became a lot simpler to prove.

As for the problem solving question, I managed to find one on the CEMC website for problems of the weeks. I picked out the most recent one for gr.11/12, which is for week 23. Although by appearance this seems a little bit "under" in terms of grade, I think that the question itself is of reasonable difficulty. I also felt uncomfortable with the questions given on the problem solving website, so I chose this one instead.

http://cemc.uwaterloo.ca/resources/potw/2012-13/POTWE-12-GP-NP-23-P.pdf

Determine the sum of all the three-digit numbers that can be made by choosing three different numbers from the list {1, 2, 3, 4, 5, 6, 7}.

Understanding The Problem

Sum up all distinct three digit numbers using permutations of the numbers from 1-7. This means no repetitions of numbers in a digit.

Devising A Plan

There are only 3 different positions numbers can be on in a 3-digit number, which are the hundreds, tens and ones position. From all of the possible numbers made, each number from 1 to 7 will appear in each of these positions an equal number of times. Summing up all the 3-digit numbers is just equivalent to the sums of all the digits in the hundreds position times 100, plus the sums of the tens digits times 10, plus the sums of the ones digit. By finding the number of times a distinct digit will appear in a distinct position, we can apply this to all of the numbers in the list and all of the possible positions to find the total sum of 3-digit numbers.

Carry Out The Plan

The example digit used here will be 1. "1" appears in the 100's position 6P2(6!/(6-2)!) times. This determines the number of possible combinations for the other two digits from the remaining 6 numbers in the list. Overall this will show the number of 3-digit numbers that start with 1.

6! / (6 - 2)! = 6! / 4!
                   = 6 * 5
                   = 30

This can be applied to all the other numbers, meaning that there will be 30 three digit numbers that have 2-7 as the hundreds digit. Summing up all the numbers from 1-7 and multiplying it by 30 will give the total sum of all the digits in the hundreds position.

30 * (Sum(1, 7)) = 30 * 7 * (7 + 1) / 2
                           = 840

This number will also be the sum of all the tens digits and ones digits, as the previous methods can be applied in the exact same manner for those positions. By multiplying 840 by powers of 10, we can find out the total sum of all 3-digit numbers that can be made by choosing three different numbers from the list.

Sum = 840 * (10^2 + 10^1 + 10^0)
        = 840 * (111)
        = 93240

Looking Back

Extending this, the sum of all "m" digit numbers, where "m" is no greater than "n", that can be created with a list of size "n" containing numbers from 1 to "n" will be,









If the list does not contain digits from 1 to "n" then n(n +1)/2 will simply be replaced with the sum of those digits.

Log Six

Even though we have spent two weeks of lectures and tutorials on these bounding type questions, I'm still having some difficulty with them. There hasn't been any new major changes with how the answers should be structured, so the issue isn't with newer content. For the more complicated questions, it just becomes harder to keep track of all the information, and how it can be used to reach the end result. Hopefully working on the next tutorial and assignment will help with this, as I'm lacking in practice on the many types of usable methods.

Regarding the recently marked work and test, I feel a little disappointed about the mark my partner an I got on assignment 2. Although we got around average, we lost the most marks on one of the easier questions. As for the test, I feel that I did fairly well. I actually thought that my answer for question three wasn't sufficient enough, but it turned out that I only lost a couple of marks for it. Overall the test was fairly easy, and could've been easier if I hadn't missed the fact that the answers for the sample test were given.

Log Five

I find that trying to prove the time complexity of algorithms is a lot harder to do than the previous types of proofs from the lectures. Getting used to the different styles and uses of notations within the proof statements is one issue, although that problem seems to be easily fixed with more practice. The main problem is not the structure of the proof, but the actual proof itself. Utilizing sequences to simplify certain steps looks to be the best method for all the algorithms shown up until now, but how this can be applied to reach the implication is still something that I'm not used to. A lot more practice in this area seems to be needed until I'm comfortable enough to do these types of questions.

Log Four

After working on and seeing more types of proofs, via the tutorials, exercises and lectures, solving them has become a lot easier. Getting used to writing down the structure has definitely helped in figuring out many problems. For assignment two, it only took a couple of hours for my partner and I to finish working on the questions. Although some statements took a while to determine whether they were supposed to be true or false, there has been a major improvement in how easily we can solve proofs since the first time we encountered them.

While I felt that there wasn't much to write during the previous week, as it was just more practice on proofs, I feel that this week has had something good to offer as we start learning about time complexity. The other computer science courses that I'm taking do not go into this topic very deeply, so I'm hoping that there will be more information on this in future lectures. It's also a nice departure from proofs into something more involved with the computational side of this course, as proofs have already taken up a good chunk of time.

Log Three

I haven't been able to update my blog recently due to all my midterms being this past week, so I'll try my best to recap the last two weeks. For the first assignment, even though the marks have not been updated yet, I was able to get a good look at the solutions that were given out during one of the lectures. The questions themselves did not seem to be too difficult when I was working on them, but after seeing the correct answers, I know that I probably did not do as well as I expected. The main issue was translating statements from English to a symbolic form. I can't really suggest any good ways to deal with this, other than lots of practice. Even if I figure out one symbolic form of a statement that seems correct, it seems that there are always better ways to describe the statement.

The midterm however was relatively simple compared to the assignment. Almost all of the questions were straightforward and not too complicated. The aid sheet was not really required for the test, but it helped in confirming some of the conversions and definitions.

Learning about proofs was probably the hardest part of these two weeks for me. Although I've done a lot of other types mathematics in the past, proofs were never something that I liked or was good at. It will probably get easier for me to do later on if I get accustomed to the structure of proofs used by this course. Most of the questions reviewed mainly involved taking a universal statement, or one that is stated in the question, and manipulating into the end result. Keeping that in mind when proving should also be useful for the basic direct proofs. As for any other types of proofs, hopefully more techniques will be shown in future lectures to help with those proofs.

Log Two

This week was a lot more challenging than the previous one, mostly due to the tutorial exercises and further application of the "implication" sign. Although the majority of the tutorial questions were simple to understand, it was harder to visualize answers for questions like "no course has more than two prerequisites". Compared to universal and "there exists" types of claims, questions that involve specific numbers seem to have much more complicated answers. This becomes an even bigger problem for me when the "implies" sign is used as I don't have any prior experience in utilizing it, making it easy to mix it up with the conjunction sign. It'll probably get easier to understand with more practice, which means this will be less of an issue as time goes on. As for the rest of the lectures, I've worked with circuits and logic in the past so most of the laws and concepts are just review.

Log One

First few days in CSC165 and everything is moving along smoothly. So far none of course work, concepts, and quizzes have proved to be too challenging. Everything up to this point has simply been a brief review of general concepts. Hopefully there will be many more interesting topics to come as the course goes on.