1

I've often been slightly stumped by recursive algorithms that seem to require magical leaps (with a large dose of shrunken notation born of an ink shortage) of logic.

I realize that the alternative is to simply memorize the Big O notation for all the common algorithms but at a certain point, that approach fails. For example, I am happy to disclose the performance for bubble sort, insertion sort, binary tree insertion/removal, mergesort, and quicksort but don't ask me to come up with the performance of AVL trees or Djikstra's shortest path algorithm off the top of my head.

Where can I go to get:

  1. A discussion of recursive algorithm analysis that uses words instead of a profusion of symbols
  2. Practice problems to confirm that my newly-obtained understanding is actually correct

Example:

Bad:

Sigma v e T (1+cv)

Possible 'good' equivalent:

The amount of work required for 1 node in the tree (which is 1+the # of children of a node), which is then executed once for every element in the tree where the original node is the root.

Side commentary:

I could simply watch a video for every single algorithm because there's no way to make one's voice turn into a subscript (or any of the other contortions) but I suspect that would take an inordinate amount of time compared to reading textual descriptions.

Update:

Here's 1 source of solved problems: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/ (this tackles #2 above)

Improve this question
4
  • 5
    You should learn to get comfortable with the communication of these ideas in symbols. It's efficient, precise, and the language that almost everyone uses. Commented Apr 2, 2011 at 16:40
  • @Jason: If you are cs student or mathematical and theoratical focused. For a good programmer it should be enough to understand the meaning. Commented Apr 2, 2011 at 16:44
  • 2
    +1 to Jason's point. For getting comfortable (and better than most people, actually!) with notation and analysis, I recommend the wonderful book Concrete Mathematics: A Foundation for Computer Science. Just the first two chapter should be enough (plus possibly the last), but it's so well written it's hard to resist reading the other chapters as well. Commented Apr 3, 2011 at 3:31
  • I should comment that I was dramatically underselling myself in the original post. :D I'm quite handy with things like sigmas, aleph-nulls, and so on. I just have trouble with the way the material is presented in the textbok that was required by my introductory class when I was getting my B.S (hence my commentary on ink shortages). Commented Apr 14, 2011 at 1:12

2 Answers 2

Reset to default
1

TopCoders has a great source of tutorials and thorough explanations. Have you tried them out?

http://www.topcoder.com/tc?d1=tutorials&d2=alg_index&module=Static

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Well, their particular tutorials on recursion (Part 1, Part 2), while very good, do not go into much detail of analysis.
I've reviewed the tutorials and must agree that there is almost nothing on analysis.
1

To 'officially' answer this question...

Source of sample problems: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/

An explanation of analysis for CS: http://en.wikipedia.org/wiki/Concrete_Mathematics.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.