Contact info.
 
My Secret Life as a Spaghetti Coder
home | about | contact | privacy statement
The latest Ruby Quiz asks us to find the maximum contiguous subarray, given an array. This ties in nicely to something I've been wanting to ask for a while: how do you design your algorithms? What heuristics do you use? What different approaches do you try? How can you improve your skill set at designing algorithms?

For the maximum subarray problem, if you didn't know any better, you'd probably implement a solution that analyzes every possible subarray, and returns the one with the maximum sum:

class Array
        def sum
                result = 0
                self.each do |i|
                        result+=i
                end
                return result
        end
        #test every sub array - brute force!
        def max_sub_array_order_ncubed
                left_index = 0
                right_index = 0
                max_value = self[left_index..right_index].sum
                for i in (0..self.length)
                        for j in (i..self.length)
                                this_value = self[i..j].sum
                                if (this_value > max_value)
                                        max_value = this_value
                                        left_index=i
                                        right_index=j
                                end
                        end
                end
                return self[left_index..right_index]
        end
end

If you were a bit more clever, you might notice that self[i..j].sum is equal to self[i..(j-1)].sum + self[j] in the innermost loop (the sum method itself), and use an accumulator there as opposed to calculating it each time. That takes you down from n3 to n2 time.

But there are (at least) two other ways to solve this problem:
  • A divide and conquer approach that uses recursion and calculates the left and right maximum contiguous subarrays (MCS), along with the MCS that contains the right-most element in the left side and the left-most element in the right side. It compares the three and returns the one with the maximum sum. This gets us to O(n log n) time.

  • An approach I'll call "expanding sliding window." If memory serves me correct, this aptly describes it or was the way a professor of mine described it. In any case, the "expanding sliding window" can do it in one pass (O(n) time), at the cost of a few more variables.
Clearly, these last two approaches aren't nearly as obvious as the first two - so how do you devise them? I'm fairly confident that the only reason I know about them is from a course in algorithms where they were presented to me (and I didn't take the time to work-through and reimplement them for this post). I'm not sure that TDD or just a long ponder would have led me in that direction. (Although, one of the solution submitters claims he TDDed the O(n) solution.)

Three thoughts in designing algorithms I use off the top of my head are:
  • There's always brute force, but is there something better?

  • Is divide and conquer and option? If so, is it easy enough to implement and understand?

  • How can I trade space complexity for gains in time complexity, or vice versa if the situation warrants? (overview on computational complexity)
My assumption here is that you're not looking for someone else's code that has implemented it, or that no one has already solved it. Of course in real work you'd probably want to look for an algorithm that had already been discovered and published that provides a solution.

Is it just a matter of reading Knuth's compendium and books on algorithms, becoming familiar with many different types of them for many different data structures?

So I'll ask again: how do you design your algorithms? What heuristics do you use? What different approaches do you try? How can you improve your skill set at designing algorithms? What other questions do you ask yourself?

Hey! Why don't you make your life easier and subscribe to the full post or short blurb RSS feed? I'm so confident you'll love my smelly pasta plate wisdom that I'm offering a no-strings-attached, lifetime money back guarantee!


Comments
Leave a comment

Can u pls explain me ? I could not understand the sum function

Posted by Ganesh on Feb 25, 2012 at 07:48 PM UTC - 6 hrs

Leave a comment

Leave this field empty
Your Name
Email (not displayed, more info?)
Website

Comment:

Subcribe to this comment thread
Remember my details
Google
Web CodeOdor.com

Me
Picture of me

Topics
.NET (19)
AI/Machine Learning (14)
Answers To 100 Interview Questions (10)
Bioinformatics (2)
Business (1)
C and C++ (6)
cfrails (22)
ColdFusion (78)
Customer Relations (15)
Databases (3)
DRY (18)
DSLs (11)
Future Tech (5)
Games (5)
Groovy/Grails (8)
Hardware (1)
IDEs (9)
Java (38)
JavaScript (4)
Linux (2)
Lisp (1)
Mac OS (4)
Management (15)
MediaServerX (1)
Miscellany (75)
OOAD (37)
Productivity (11)
Programming (168)
Programming Quotables (9)
Rails (31)
Ruby (67)
Save Your Job (58)
scriptaGulous (4)
Software Development Process (23)
TDD (41)
TDDing xorblog (6)
Tools (5)
Web Development (7)
Windows (1)
With (1)
YAGNI (10)

Resources
Agile Manifesto & Principles
Principles Of OOD
ColdFusion
CFUnit
Ruby
Ruby on Rails
JUnit



RSS 2.0: Full Post | Short Blurb
Subscribe by email:

Delivered by FeedBurner