First post
Recursion and Resolution. Wow. That’s a long name for a blog. I like it though. All I can suggest is if you’re planning on coming back here with any sort of frequency, bookmark it.
Now the usual first post business. I’m Blake. I attend the University of Alabama, Computer Science major. Roll Tide. I intend for this blog to be of two purposes:
- To post about myself and day-to-day occurrences, and
- To post about my interests
It is this second purpose for which the blog is named. Recursion refers to Computer Science and Mathematics (specifically algorithm theory), while Resolution (as in pixels) alludes to my artistic interests of Photography and Graphic Design. Oh, and the carat-y looking thing ∧ is the logical ‘and’ sign. Geek humor.
Lucky for me, I have classes in CS, Math, and Photography this semester. Maybe I can work in a Graphic Design bias with another class too. That’ll make this blog be a bit more well rounded.
As I mentioned before, I’m a CS major, so I might as well start off with a topic in that field.
Radix Sort (stop reading if you don’t care about CS, or neat algorithms)
This is a particularly nifty sorting algorithm. Its time complexity is O(n), or linear, which just means it’s among the fastest with certain constraints. I’ve been implementing this as part of my Data Structures class this semester (even though it doesn’t have much to do with data structures…) Anyway, this algorithm will sort numbers digit by digit. Say I give you the number 7326. The value in the ones place is 6, 2 in the tens place, etc. Well, if I gave you a list of numbers, say
154, 654, 762, 691, 325, 768, 374, 198, 243, 179, 280,
one possible strategy in ordering them is by each digit. Examples are forthcoming. You can either start from the highest radix (in this case, the hundreds place) or the lowest radix (the ones place). To go along with my research, we’ll do the latter. So, we first order our numbers by the ones place, putting each number into 1 of 10 smaller lists.
0. 280
1. 691
2. 762
3. 243
4. 154, 654, 374
5. 325
6.
7.
8. 768, 198
9. 179
Now, you repeat this step, but use the tens place.
0.
1.
2. 325
3.
4. 243
5. 154, 654
6. 762, 768
7. 374, 179
8. 280
9. 691, 198
An important thing to note is that you must put each number into its smaller list as you encounter it. So, even though 280 gets put into the 8 list, it needs to get put there first. This is important because the initial step orders by the ones place, and we can’t throw that ordering away. Take for example, 762 and 768. They both get put into the 6 list, but 762 must get put there before 768 to preserve the order. Finally, we go back down the list, putting the numbers in the correct sublist by hundreds place.
0.
1. 154, 179, 198
2. 243, 280
3. 325, 374
4.
5.
6. 654, 691
7. 762, 768
8.
9.
And so, with no comparisons between any numbers, you can sort a list. (i.e. you never had to ask yourself “Is 198 larger than 179?”) This is a big thing as far as sorting algorithms go, because comparison based sorting algorithms have a limit to just how fast they can go. (O(n*log(n)) if you’re interested)
Ok, well, that was enough CS for a while. I think I’ll do photography next…
P.S. The iPhone Tumblr app is very nicely done. I’ll have to use it sometime.
