For some reason, my mind has been mush all day, so I didn't get to work on the Clojure launcher like I wanted. Late yesterday, I also bought the book Python Algorithms by Magnus Lie Hetland, and I could only half-heartedly read through the first chapter today.
Nevertheless, I really want to get back to CS basics. For the first two years out of college, I didn't really use any of my training I used in school. Only once did I start to work on a C-based xml parser, but I left shortly thereafter and never got a chance to flesh it out. What did the xml parser have anything to do with what I learned in school?
Ironically, it had a lot to do with something else I've done recently. In both cases, I needed to implement a depth-first search algorithm (and data structure). I recently had need of creating a software dependency manager. We have many tools, scripts, programs, frameworks and libraries which have dependencies on other tools, scripts, programs, frameworks or libraries. It dawned on me one day that this transitive dependency list was really just a tree structure, and I could safely install some 'artifact' if that artifact had no children (it was a leaf node). So once I figured out these dependencies were a tree, I then had to come up with a depth-first search algorithm to find an artifact with no children. The recursion would then pop-off the stack and I would be back to the parent. If the parent then had no more children, it too could be installed, otherwise I descended down the child branch of the parent.
Surprisingly, in school, we didn't cover depth first or breadth first searches in our Analysis of Algorithms class. Instead, we covered these in an introductory AI course. My recollection of my Analysis of Algorithms class was that I did fairly well in it, but honestly, many of the algorithms were just something I memorized. Sure, I understood some of the basic principles, like divide and conquer for search algorithms, or 'greed is good' for certain other algorithms, or how memoization could save computational cycles. But many of the algorithms just seemed like something to memorize and they never really sank in (to this day, I still don't conceptually understand how quick sort works, though I can tell you that on average it has the best average search time, though the worst worst case search time if the items are already sorted).
One problem when you are going through school is that in many ways, you are still struggling to master the programming language, so you can't really concentrate on the essence of the problem at hand. My belief is that simpler languages should be used to teach the concepts (like python or ruby), while using C or C++ to get students used to the idea of pointers, the difference between the stack and the heap, and generally a better view of how the machine itself actually functions. I'm NOT a believer that students should only learn C# and/or Java (especially without some kind of introductory microcontroller class that teaches assembly) because otherwise students will never truly appreciate how operating systems and drivers work.
That being said, trying to learn how to heapify some data structure while still struggling with how pointers work is not a good combo. Now that I'm more confident with actual programming languages, I'd like to go back and revisit some of the courses I took in school, and hopefully I can pay more attention this time around.
Another pet Clojure project I'd like to work on is to create a multi-threaded merge sort function. It seems to me that because the dividing up of the sequence into halves requires no synchronization, this should be feasible. If you think about the problem, every split could be done by a new thread. It's the recombining part that I'm not sure about.
One thing I am curious though about calculating the runtime efficiency of an algorithm is whether they take into account parallelism. As far as I can remember, only one thread of execution was implied. But if you can create an algorithm that can be worked on in parallel, then obviously, the runtime efficiency should be better. I do not see why several of the divide-and-conquer sorting algorithms could not be faster than quick sort (IIRC, as far as I understood quick-sort...which isn't well....it seemed to me that the whole pivot point thing couldn't be parallelized). But most of the divide and conqueror algorithms (merge-sort, heap-sort for example) should be able to take advantage of multiple threads or processes of execution.
No comments:
Post a Comment