Week 12 – Project Euler

Project Euler is a great website that any CS student interested in math should look at. What it basically does is take a bunch of math related problems that are great for practicing your understanding of certain mathematical concepts and polishing up your programming. This week, I’m going to look at two questions, one which I’ve solved and one which I’m currently (and have been for a while) working on – #__ and #487 for those interested.

(Note: No answers will be given, and the number for the first one is removed because sample code is given.)

We’ll start with the hard one first.

Just looking at the question, it’s not very difficult to write one that goes through the problem through brute force, however there are two problems with this approach.First, it takes an extremely long time for this to run if you just power through it (to be honest, I have no clue if I had an infinite loop – pretty sure I didn’t –  or whether this thing would run on for days. I wasn’t booing to wait days). Secondly, one of Project Euler’s requirements is that anything you write should be able to give you the answer in under a minute. I approached this question like this at first. I then tried doing it again with a new approach. The trick with this question is simplifying the summation into a formula that speeds the process. The problem is that (1) I couldn’t think of how to simplify the last summation, and (2) though I’m certain my approach to is quite fast, I’m positive that it can be made more efficient. Also, the current prime sieve I’m using is complete trash for this question. This is one I’m going to enjoy tackling after finals. I can’t wait to get this one, then I can brag to my friends that use project Euler that I figured out one of the more difficult questions 🙂 .

The second question is this.

The cool thing about this one is that you really can go through it through brute force. By no means is it an elegant way of going through it, but with something this simple, it’s very tempting. The first approach I took with this one worked, and this is thecode I came up with:

(I just realized that capitol ‘S’ in the function name. The things you notice when you double check.)

What basically happens here is that I take every number from 0 to , and raise it to , this way I get every number from , instead of from . And every number, I add it to x, make x a string, and return the last ten digits as requested. For me, the thing that took a small amount longer than I expected was getting  the last 10 digits. I had two options, return x, and copy+paste the last 10 digits, or making my not so elegant code a bit more elegant, that’s when I thought to just make it a string and splice out the last 10 digits.

Project Euler is really a great thing. I’ve been trying to do 1 question a week, and it’s really good excersize.

If you learn anything from this blog, I think the most important thing is this:

1) CSC165 is really a great course. The things you learn in it are quite helpful in Math and Philosophy, and of course, Computer Science (interestingly enough, I’m taking all three this year). The instructors really care and want you to understand. One of the most important things you learn from this course is how to solve problems, and for me personally, the most important lesson was something Prof. Heap talked about in the first week of school, the methods one should take towards problem solving.

2) Do Project Euler questions. They’re great “brain food” and help you think abstractly.

There are other sites that do similar things, you could also do those.

Thank you all,

NDE.

Week 11 – Halting Problems and Computability.

There are infinities bigger than each other. I’ve had some sort of understanding of this from AP Calculus, but it is still something extremely interesting to think about. The Naturals are “countable.” Reals are bigger than the Naturals. But they’re both infinite sets. When a list is going to infinity, does it really matter “large” your infinity is? It turns out it does. The rate at which you go to infinity is quite important. Aside from that, even more interesting to me is that both humans and computer cannot solve more problems than the Natural numbers. Our problem solving skills are “limited” to that specific set of infinity. Quite interesting.

We looked at some halting proofs in class this week. Talking about functions that are impossible to write confused me a bit. Also, the idea that you can’t tell if a function is going to continue forever or if it’s taking a long time to compute seems extremely obvious, but it still quite mind boggling. Maybe I should wait out my infinite loops (just kidding).

I can’t believe the next SLOG will be the last. It’ll be nice to take a break from me pouring my frustrations and successes in this course on this blog and do something more math-y. I’ve got a pretty good thing I’m working on solving that I want to share.

Until next time,

NDE

Weak 10.

so weak right now.

But the term is almost over, so that’s good. I’ve really enjoyed this course. We just did Big O and Omega proofs. I’m a bit disappointed that we didn’t do any Omega proofs. They aren’t so different from Big O that it’s that big of a deal, but I still think an example would be great. Maybe during the next tutorial we’ll get one? I struggled with it at first, but after reading through the slides I’m starting to understand the purpose and the procedure for these proofs. Now I’m just waiting to start Assignment 3, but I think I’ll start that after my math test. I think i’ll do a problem solving slog next week.

Until next time,

NDE

Week 9: Shall I Compare Thee to a Winter’s Day?

And the exam is over! Two down and one to go! I don’t know if I should be extremely happy about that, or extremely worried. I feel like I did well on the exam, out of the three questions, I know I got the first and the last, and I have the proof structure for the middle one, with a little bit of work. Talking to friends after the exam made me realize a really simple technique I could have used, one that I completely forgot about: changing not(A or B) to from (not( A) and not B) to  [(not A) and not(B)] to [(not A) implies B]. It’s unfortunate that I thought about doing this for a slight moment during the test, but I didn’t go with that plan. This situation reminds me of something professor Heap talked about during the first weeks of class: the method for solving a problem, or something like that.

Oh, and I’m finally starting to understand this big O stuff. Tutorials really help in this class. And would you look at that, this week’s post is longer than lasts. Test relief.

Also, if you want a fun read about folding a paper, check out this blog!

Until next time,

NDE

Week Ate My Life.

Big Oh of what? Worst case? Best case? Step counting??? I feel like the lectures this week moved to fast for my pace. I would finally understand something after staring at my printed slides for a few minutes or so. I think that simply listening through the lecture and sorting (ha, no pun intended) through everything I remember/understood with the information in the annotated slides and course notes might help. I have an hour between this class and my next class which I can make use of.

Oh look, word length is getting even shorter…

Until next time,

NDE

Week 7. Getting Tired :(

Sorting Algorithm Complexity and Big-Oh! That’s what we’re working on this week. I am having quite a difficult time with big O (I’ll probably get it by next week); however the sorting algorithms are really interesting, it’s cool how even though some algorithms seem inefficient, they work better for smaller sets or for larger sets. It did remind me of this comic though:

However, I realize the important in efficiency and time cost in algorithms after attempting a Project Euler project (#487), and finding out that even though writing the code so it implements the problem through brute force wasn’t difficult, having it give a result within a minute (as Project Euler requires) proves to be a much greater challenge.

Looking at the calendar, I realize that there’s another term test in 2 weeks. All these assignments and exams (from all my classes) are starting to accumulate. I need to make sure not to procrastinate and stay on top of my work. I’m getting tired.

Until next time,

NDE

WEEK SIX YO!

We got our exams back this week. I did alright, though I could’ve done much better. One question i misread the placement of parenthesis, the other question i was thinking too “big,” trying to force a statement to work with real numbers. We’ve started to go into proofs now; gone are the easy days of structuring, now we actually have to think. On the bright side, this is much more fun, and there’s that feeling of satisfaction upon having proved something (I live for that feeling).

Despite what I thought about this class during the first two weeks (I didn’t really like it or understand what was going on), this is now one of my favourites.

WEEK FIVE.

WE HAD AN EXAM THIS WEEK!

It went well, I think. That last question…I could’ve figured it out (if I had five more minutes) but I was thinking too big–Real Numbers big. Other than that, the material has been getting better. We’re doing proofs, mainly the structure for now, but I am really looking forward to it. I’ve finally learned to go to sleep earlier than 1 so I can be completely “awake” during my 9AM tutorial. You would think that it would obvious, but the lure of movies and League of Legends override common sense sometimes (don’t tell, but I might be an addict (; ).

The direct overlap between MAT137 and CSC165 is thinning (see this post for more similarities), but there are indirect similarity between the classes–notation, proofs, etc. I’m enjoying both but hating the work. #UofT

It seems that everybody’s SLOGS just get smaller and smaller as the year goes by. I wonder if there’s a rate at which word count decreases…maybe a project for a later date.

Happy Thanksgiving!

Until Next Time,

NDE

Week 4?

It’s already week 4.

I’ll let that sink in. Take a minute, get a coffee or whatever you use to stay up (and procrastinate), and come to terms with that.

It’s already week 4, and I’m tired.

Assignment 1 is due tomorrow, and while on the whole it was not too difficult, some individual aspects of it were time consuming and extremely difficult, with difficulty here being the amount of effort I needed to exert to figure out number 4. Sometimes it really is a stroke of luck, memory that randomly appears, that allows you to find something. 4a took me 15 minutes, 4b around three hours. It turned out that a solution I dismissed early on because I didn’t “like” it actually worked; it goes to show that nothing should be dismissed in its entirety. One great positive about this assignment is that I learned LaTeX because of it. Pretty fun and useful resource. Thank you CSC165.

In terms of the material we are learning in the course, Week 3’s material and Week 4’s are the first that I am actually enjoying. I found it fun! (gasp). And if what we learn becomes more “fun,” I am going to have a great time in this class.

Until next time,

N.D.E

Week 3

CSC165 – Mathematical Expression and Reasoning for Computer Science

This week was good, I finally learned how to keep with lectures. Actually printing out the slides. The first week I looked at the slides before I came to class and then took notes on binder paper. It worked, but it was very slow, and I missed a lot of the information. Second week I opened up my laptop and tried taking notes on the slides using Evernote. That would have been fine except that despite the speed of typing, the speed of drawing was excruciatingly slow and the temptation to ignore the lecture and check Facebook and reddit was too high. Got rid of that method quickly. This week I looked at the slides, printed them, and wrote on top of them. Quick, easy to write, and easy to learn from.

I really enjoyed the truth tables we used this week, and for many reasons. One, lines are easier to draw than circles; secondly, at least for me, the venn diagram approach did not help me visualize the statements (though I understand the venn diagrams and what they mean better now). As the weeks progress, I am starting to understand this subject better, and I plan on putting more effort into reviewing notes and paying better attention during lectures in order to hopefully master this subject.

Until next time,

N.D.E