The Algorithm Design Manual

Steven S. Skiena

Mentioned 25

Expanding on the highly successful formula of the first edition, this book now serves as the primary textbook of choice for any algorithm design course while maintaining its status as the premier practical reference guide to algorithms.

More on Amazon.com

Mentioned in questions and answers.

If you could go back in time and tell yourself to read a specific book at the beginning of your career as a developer, which book would it be?

I expect this list to be varied and to cover a wide range of things.

To search: Use the search box in the upper-right corner. To search the answers of the current question, use inquestion:this. For example:

inquestion:this "Code Complete"

Applying UML and Patterns by Craig Larman.

The title of the book is slightly misleading; it does deal with UML and patterns, but it covers so much more. The subtitle of the book tells you a bit more: An Introduction to Object-Oriented Analysis and Design and Iterative Development.

Masters of doom. As far as motivation and love for your profession go: it won't get any better than what's been described in this book, truthfully inspiring story!

Beginning C# 3.0: An Introduction to Object Oriented Programming

This is the book for those who want to understand the whys and hows of OOP using C# 3.0. You don't want to miss it.

alt text

Mastery: The Keys to Success and Long-Term Fulfillment, by George Leonard

It's about about what mindsets are required to reach mastery in any skill, and why. It's just awesome, and an easy read too.

Pro Spring is a superb introduction to the world of Inversion of Control and Dependency Injection. If you're not aware of these practices and their implications - the balance of topics and technical detail in Pro Spring is excellent. It builds a great case and consequent personal foundation.

Another book I'd suggest would be Robert Martin's Agile Software Development (ASD). Code smells, agile techniques, test driven dev, principles ... a well-written balance of many different programming facets.

More traditional classics would include the infamous GoF Design Patterns, Bertrand Meyer's Object Oriented Software Construction, Booch's Object Oriented Analysis and Design, Scott Meyer's "Effective C++'" series and a lesser known book I enjoyed by Gunderloy, Coder to Developer.

And while books are nice ... don't forget radio!

... let me add one more thing. If you haven't already discovered safari - take a look. It is more addictive than stack overflow :-) I've found that with my google type habits - I need the more expensive subscription so I can look at any book at any time - but I'd recommend the trial to anyone even remotely interested.

(ah yes, a little obj-C today, cocoa tomorrow, patterns? soa? what was that example in that cookbook? What did Steve say in the second edition? Should I buy this book? ... a subscription like this is great if you'd like some continuity and context to what you're googling ...)

Database System Concepts is one of the best books you can read on understanding good database design principles.

alt text

Algorithms in C++ was invaluable to me in learning Big O notation and the ins and outs of the various sort algorithms. This was published before Sedgewick decided he could make more money by dividing it into 5 different books.

C++ FAQs is an amazing book that really shows you what you should and shouldn't be doing in C++. The backward compatibility of C++ leaves a lot of landmines about and this book helps one carefully avoid them while at the same time being a good introduction into OO design and intent.

Here are two I haven't seen mentioned:
I wish I had read "Ruminations on C++" by Koenig and Moo much sooner. That was the book that made OO concepts really click for me.
And I recommend Michael Abrash's "Zen of Code Optimization" for anyone else planning on starting a programming career in the mid 90s.

Perfect Software: And Other Illusions about Testing

TITLE Cover

Perfect Software: And Other Illusions about Testing by Gerald M. Weinberg

ISBN-10: 0932633692

ISBN-13: 978-0932633699

Rapid Development by McConnell

The most influential programming book for me was Enough Rope to Shoot Yourself in the Foot by Allen Holub.

Cover of the book

O, well, how long ago it was.

I have a few good books that strongly influenced me that I've not seen on this list so far:

The Psychology of Everyday Things by Donald Norman. The general principles of design for other people. This may seem to be mostly good for UI but if you think about it, it has applications almost anywhere there is an interface that someone besides the original developer has to work with; e. g. an API and designing the interface in such a way that other developers form the correct mental model and get appropriate feedback from the API itself.

The Art of Software Testing by Glen Myers. A good, general introduction to testing software; good for programmers to read to help them think like a tester i. e. think of what may go wrong and prepare for it.

By the way, I realize the question was the "Single Most Influential Book" but the discussion seems to have changed to listing good books for developers to read so I hope I can be forgiven for listing two good books rather than just one.

alt text

C++ How to Program It is good for beginner.This is excellent book that full complete with 1500 pages.

Effective C++ and More Effective C++ by Scott Myers.

Inside the C++ object model by Stanley Lippman

I bough this when I was a complete newbie and took me from only knowing that Java existed to a reliable team member in a short time

Not a programming book, but still a very important book every programmer should read:

Orbiting the Giant Hairball by Gordon MacKenzie

The Pragmatic programmer was pretty good. However one that really made an impact when I was starting out was :

Windows 95 System Programming Secrets"

I know - it sounds and looks a bit cheesy on the outside and has probably dated a bit - but this was an awesome explanation of the internals of Win95 based on the Authors (Matt Pietrek) investigations using his own own tools - the code for which came with the book. Bear in mind this was before the whole open source thing and Microsoft was still pretty cagey about releasing documentation of internals - let alone source. There was some quote in there like "If you are working through some problem and hit some sticking point then you need to stop and really look deeply into that piece and really understand how it works". I've found this to be pretty good advice - particularly these days when you often have the source for a library and can go take a look. Its also inspired me to enjoy diving into the internals of how systems work, something that has proven invaluable over the course of my career.

Oh and I'd also throw in effective .net - great internals explanation of .Net from Don Box.

I recently read Dreaming in Code and found it to be an interesting read. Perhaps more so since the day I started reading it Chandler 1.0 was released. Reading about the growing pains and mistakes of a project team of talented people trying to "change the world" gives you a lot to learn from. Also Scott brings up a lot of programmer lore and wisdom in between that's just an entertaining read.

Beautiful Code had one or two things that made me think differently, particularly the chapter on top down operator precedence.

K&R

@Juan: I know Juan, I know - but there are some things that can only be learned by actually getting down to the task at hand. Speaking in abstract ideals all day simply makes you into an academic. It's in the application of the abstract that we truly grok the reason for their existence. :P

@Keith: Great mention of "The Inmates are Running the Asylum" by Alan Cooper - an eye opener for certain, any developer that has worked with me since I read that book has heard me mention the ideas it espouses. +1

I found the The Algorithm Design Manual to be a very beneficial read. I also highly recommend Programming Pearls.

This one isnt really a book for the beginning programmer, but if you're looking for SOA design books, then SOA in Practice: The Art of Distributed System Design is for you.

For me it was Design Patterns Explained it provided an 'Oh that's how it works' moment for me in regards to design patterns and has been very useful when teaching design patterns to others.

Code Craft by Pete Goodliffe is a good read!

Code Craft

The first book that made a real impact on me was Mastering Turbo Assembler by Tom Swan.

Other books that have had an impact was Just For Fun by Linus Torvalds and David Diamond and of course The Pragmatic Programmer by Andrew Hunt and David Thomas.

In addition to other people's suggestions, I'd recommend either acquiring a copy of SICP, or reading it online. It's one of the few books that I've read that I feel greatly increased my skill in designing software, particularly in creating good abstraction layers.

A book that is not directly related to programming, but is also a good read for programmers (IMO) is Concrete Mathematics. Most, if not all of the topics in it are useful for programmers to know about, and it does a better job of explaining things than any other math book I've read to date.

For me "Memory as a programming concept in C and C++" really opened my eyes to how memory management really works. If you're a C or C++ developer I consider it a must read. You will defiantly learn something or remember things you might have forgotten along the way.

http://www.amazon.com/Memory-Programming-Concept-C/dp/0521520436

Agile Software Development with Scrum by Ken Schwaber and Mike Beedle.

I used this book as the starting point to understanding Agile development.

Systemantics: How Systems Work and Especially How They Fail. Get it used cheap. But you might not get the humor until you've worked on a few failed projects.

The beauty of the book is the copyright year.

Probably the most profound takeaway "law" presented in the book:

The Fundamental Failure-Mode Theorem (F.F.T.): Complex systems usually operate in failure mode.

The idea being that there are failing parts in any given piece of software that are masked by failures in other parts or by validations in other parts. See a real-world example at the Therac-25 radiation machine, whose software flaws were masked by hardware failsafes. When the hardware failsafes were removed, the software race condition that had gone undetected all those years resulted in the machine killing 3 people.

It seems most people have already touched on the some very good books. One which really helped me out was Effective C#: 50 Ways to Improve your C#. I'd be remiss if I didn't mention The Tao of Pooh. Philosophy books can be good for the soul, and the code.

Discrete Mathematics For Computer Scientists

Discrete Mathematics For Computer Scientists by J.K. Truss.

While this doesn't teach you programming, it teaches you fundamental mathematics that every programmer should know. You may remember this stuff from university, but really, doing predicate logic will improve you programming skills, you need to learn Set Theory if you want to program using collections.

There really is a lot of interesting information in here that can get you thinking about problems in different ways. It's handy to have, just to pick up once in a while to learn something new.

I saw a review of Software Factories: Assembling Applications with Patterns, Models, Frameworks, and Tools on a blog talking also about XI-Factory, I read it and I must say this book is a must read. Altough not specifically targetted to programmers, it explains very clearly what is happening in the programming world right now with Model-Driven Architecture and so on..

Solid Code Optimizing the Software Development Life Cycle

Although the book is only 300 pages and favors Microsoft technologies it still offers some good language agnostic tidbits.

Managing Gigabytes is an instant classic for thinking about the heavy lifting of information.

My vote is "How to Think Like a Computer Scientist: Learning With Python" It's available both as a book and as a free e-book.

It really helped me to understand the basics of not just Python but programming in general. Although it uses Python to demonstrate concepts, they apply to most, if not all, programming languages. Also: IT'S FREE!

Object-Oriented Programming in Turbo C++. Not super popular, but it was the one that got me started, and was the first book that really helped me grok what an object was. Read this one waaaay back in high school. It sort of brings a tear to my eye...

My high school math teacher lent me a copy of Are Your Lights Figure Problem that I have re-read many times. It has been invaluable, as a developer, and in life generally.

I'm reading now Agile Software Development, Principles, Patterns and Practices. For those interested in XP and Object-Oriented Design, this is a classic reading.

alt text

Kernighan & Plauger's Elements of Programming Style. It illustrates the difference between gimmicky-clever and elegant-clever.

to get advanced in prolog i like these two books:

The Art of Prolog

The Craft of Prolog

really opens the mind for logic programming and recursion schemes.

Here's an excellent book that is not as widely applauded, but is full of deep insight: Agile Software Development: The Cooperative Game, by Alistair Cockburn.

What's so special about it? Well, clearly everyone has heard the term "Agile", and it seems most are believers these days. Whether you believe or not, though, there are some deep principles behind why the Agile movement exists. This book uncovers and articulates these principles in a precise, scientific way. Some of the principles are (btw, these are my words, not Alistair's):

  1. The hardest thing about team software development is getting everyone's brains to have the same understanding. We are building huge, elaborate, complex systems which are invisible in the tangible world. The better you are at getting more peoples' brains to share deeper understanding, the more effective your team will be at software development. This is the underlying reason that pair programming makes sense. Most people dismiss it (and I did too initially), but with this principle in mind I highly recommend that you give it another shot. You wind up with TWO people who deeply understand the subsystem you just built ... there aren't many other ways to get such a deep information transfer so quickly. It is like a Vulcan mind meld.
  2. You don't always need words to communicate deep understanding quickly. And a corollary: too many words, and you exceed the listener/reader's capacity, meaning the understanding transfer you're attempting does not happen. Consider that children learn how to speak language by being "immersed" and "absorbing". Not just language either ... he gives the example of some kids playing with trains on the floor. Along comes another kid who has never even SEEN a train before ... but by watching the other kids, he picks up the gist of the game and plays right along. This happens all the time between humans. This along with the corollary about too many words helps you see how misguided it was in the old "waterfall" days to try to write 700 page detailed requirements specifications.

There is so much more in there too. I'll shut up now, but I HIGHLY recommend this book!

alt text

The Back of the Napkin, by Dan Roam.

The Back of the Napkin

A great book about visual thinking techniques. There is also an expanded edition now. I can't speak to that version, as I do not own it; yet.

Agile Software Development by Alistair Cockburn

Do users ever touch your code? If you're not doing solely back-end work, I recommend About Face: The Essentials of User Interface Design — now in its third edition (linked). I used to think my users were stupid because they didn't "get" my interfaces. I was, of course, wrong. About Face turned me around.

"Writing Solid Code: Microsoft's Techniques for Developing Bug-Free C Programs (Microsoft Programming Series)" by Steve MacGuire.

Interesting what a large proportion the books mentioned here are C/C++ books.

While not strictly a software development book, I would highly recommend that Don't Make me Think! be considered in this list.

As so many people have listed Head First Design Patterns, which I agree is a very good book, I would like to see if so many people aware of a title called Design Patterns Explained: A New Perspective on Object-Oriented Design.

This title deals with design patterns excellently. The first half of the book is very accessible and the remaining chapters require only a firm grasp of the content already covered The reason I feel the second half of the book is less accessible is that it covers patterns that I, as a young developer admittedly lacking in experience, have not used much.

This title also introduces the concept behind design patterns, covering Christopher Alexander's initial work in architecture to the GoF first implementing documenting patterns in SmallTalk.

I think that anyone who enjoyed Head First Design Patterns but still finds the GoF very dry, should look into Design Patterns Explained as a much more readable (although not quite as comprehensive) alternative.

Even though i've never programmed a game this book helped me understand a lot of things in a fun way.

How influential a book is often depends on the reader and where they were in their career when they read the book. I have to give a shout-out to Head First Design Patterns. Great book and the very creative way it's written should be used as an example for other tech book writers. I.e. it's written in order to facilitate learning and internalizing the concepts.

Head First Design Patterns

97 Things Every Programmer Should Know

alt text

This book pools together the collective experiences of some of the world's best programmers. It is a must read.

Extreme Programming Explained: Embrace Change by Kent Beck. While I don't advocate a hardcore XP-or-the-highway take on software development, I wish I had been introduced to the principles in this book much earlier in my career. Unit testing, refactoring, simplicity, continuous integration, cost/time/quality/scope - these changed the way I looked at development. Before Agile, it was all about the debugger and fear of change requests. After Agile, those demons did not loom as large.

One of my personal favorites is Hacker's Delight, because it was as much fun to read as it was educational.

I hope the second edition will be released soon!

You.Next(): Move Your Software Development Career to the Leadership Track ~ Michael C. Finley (Author), Honza Fedák (Author) link text

I've been arounda while, so most books that I have found influential don't necessarily apply today. I do believe it is universally important to understand the platform that you are developing for (both hardware and OS). I also think it's important to learn from other peoples mistakes. So two books I would recommend are:

Computing Calamities and In Search of Stupidity: Over Twenty Years of High Tech Marketing Disasters

Working Effectively with Legacy Code is a really amazing book that goes into great detail about how to properly unit test your code and what the true benefit of it is. It really opened my eyes.

So I am a Computer Science student and in about a week or so... I will be retaking a Data Structures course, using C++ for applying the theory. Yes, I did say "retaking". I took the course last Fall and I feel like there is more that I need to learn. Being a student, I feel that I MUST know the basics because it will be much easier to understand new concepts in future classes by already knowing the basic concepts... not having to relearn every time.

The first time around, I had no experience in C++ and the course expected us to be coding by the end of the first week. I struggled getting through several of the first programming assignments (MPs). Needless to say, I got used to it and had little trouble with the syntax the remainder of the semester. But then the harder Data Structures came around and the theory (Big O), became the difficult part.

All in all it was a great experience, but I feel my problem was that I didn't develop good study habits. I did the MPs and showed up to lecture, but it seems like my heart wasn't there with me. I want to change this the second time around because looking back at the class, I did have a good time and I enjoyed the material. But I found myself spending too much time thinking about/setting up the data structure(s) when I needed to be spending the time thinking about how to put the data structure to use effectively.

Learning theory is difficult (mostly because it isn't so exciting) so how should I apply myself to truly understand the Data Structures covered class? I've always been a visual learner, an interactive learner... I don't want to spend time just doing my MPs. Rather, I want to spend my time in such a way that I truly learn/understand the concepts and then directly apply the knowledge.

I'm looking for any suggestions... perhaps advice on study habits that have worked for you in the past learning such concepts... or suggestions on good note-taking techniques... anything that you'd like to share :) ... and most importantly, how to prepare before the semester starts.

Please feel free to provide feedback even if an answer has been selected. I am looking for your advice... this is why I posted :) Thanks!


NOTE: Data Structures and Topics covered in the course: Lists, Stacks, Queues, Trees (different kinds), Hash Tables, Graphs, Searching/Sorting/Traversal techniques.


UPDATE: Here's a list of links and references compiled from the answers so far.

UPDATE 2: Here's a list of some more sources that I found:

When I taught programming, I always referred the Demystified books to my students.

I suggest you read:
- Data Structures Demystified
- OOP Demystified

These two books do a good job at breaking down data structures and OOP principle in simpler easy to read terms, with easy to follow examples. It's a good overview, but it does not go into the data structures supplied by the STL.

To me the best book I've found (so far) for understanding data structures is Steven Skiena's The Algorithm Design Manual.
Aside from the first part covering algorithm analysis, algorithm & data structures the second part is absolutely invaluable in finding (or at least narrowing down) the proper data structure/algorithm for solving a problem.

After overloading my classes one fateful semester in my college days, I ended up dropping my algorithms course and never taking it again.

I'd like to finally fix this by doing some self study, but I'm wondering how best to approach it.

I've got a few algorithm texts, notably the CLRS book and Skiena's book, and links to various online sources.

Should I read both books cover to cover? Read one? Just check out some online lectures? How would you do it?

Edit: I had trouble finding a question like this, hence the post. Sorry for the dupe. Good info in that other question too.

I'm currently running Skiena cover to cover...it's very good so far...

I'm looking for an overview of algorithms, you need every now and then. If there is a problem, you either do reinvent the wheel or spend a lot of time searching for an algorithm to a common known problem which has been solved a hundred times before.

Best one would be a website with sorted algorithms, like:

  • Compression
    • ...
  • Decryption
    • ...
  • Encryption
    • Symetric
      • ...
    • ASymetric
      • ...
  • Search
    • ...
  • Sort
    • Bubble Sort
    • Quicksort
    • ...

I think you get a feeling what I mean.

What pages do you know?

In addition to seconding The Algorithm Design Manual, I've had a very positive experience with this book:

Algorithms in a Nutshell

I loved the Head First series book on object oriented design. It was a very gentle and funny introduction to the subject. I am currently taking a data structures class and find the text we are using (Kruse/Ryba Data Structures and Program Design in C++) to be very dry and hard to comprehend. This is mostly due I think to my own limitations in the area of Mathematics.

Does anyone know of a Data Structures text that is written in a lighter style, with a sense of humor, that still covers all the basics like Binary Trees, B Trees, and Graphs?

This too is not light either but it is pretty decent

Algorithms and data structures by Robert Lafore

I'm currently using Larry Nyhoff's ADTs, Data Structures, and Problem Solving with C++.

It's not as light or enjoyable to read as a Head First series book, but it's really well detailed on binary trees, b trees, and graphs. Its code samples have been really helpful for completing my assignments. No higher math knowledge is required to understand the text (except, of course, on the chapter dedicated to algorithm analysis).

The Algorithm Design Manual by Steve Skiena isn't exactly a barrel of laughs, but it's relatively light on the deeper mathematics and contains lots of what he calls "War Stories", which are illustrative examples from real world situations where algorithm work really paid off (or, sometimes, totally failed). He's also got his audio and video lectures online, and he's got a nice lecture style with bits of humor interspersed, so it might be what you are looking for.

Beginning Algorithms by Harris and Ross (a Wrox Press book) was one I liked, although its examples are presented in Java, not C++. Might be a nice accompaniment to the text you're trudging through in class.

I've heard good things about "Introduction to algorithms, A creative approach - Udi Manber" I can't verify it though since it's not available locally :(

http://www.amazon.com/Introduction-Algorithms-Creative-Udi-Manber/dp/0201120372

I have an big array of length N, let's say something like:

2 4 6 7 6 3 3 3 4 3 4 4 4 3 3 1

I need to split this array into P subarrays (in this example, P=4 would be reasonable), such that the sum of the elements in each subarray is as close as possible to sigma, being:

sigma=(sum of all elements in original array)/P

In this example, sigma=15.

For the sake of clarity, one possible result would be:

2 4 6    7 6 3 3   3 4 3 4    4 4 3 3 1
(sums: 12,19,14,15)

I have written a very naive algorithm based in how I would do the divisions by hand, but I don't know how to impose the condition that a division whose sums are (14,14,14,14,19) is worse than one that is (15,14,16,14,16).

Thank you in advance.

This is very similar to the case of the one-dimensional bin packing problem, see http://www.cs.sunysb.edu/~algorith/files/bin-packing.shtml. In the associated book, The Algorithm Design Manual, Skienna suggests a first-fit decreasing approach. I.e. figure out your bin size (mean = sum / N), and then allocate the largest remaining object into the first bin that has room for it. You either get to a point where you have to start over-filling a bin, or if you're lucky you get a perfect fit. As Skiena states "First-fit decreasing has an intuitive appeal to it, for we pack the bulky objects first and hope that little objects can fill up the cracks."

As a previous poster said, the problem looks like it's NP-complete, so you're not going to solve it perfectly in reasonable time, and you need to look for heuristics.

I want to solve geometry problems in online programming contests. But whenever I read them, I just find too difficult. Please suggest some books and resources which I can study computational geometry.

And of course there's Computational Geometry - An Introduction, by Preparata and Shamos. I own it, and recommend it for an introduction to the principles. Not really a dictionary of code, though.

I recommend two books (among others):

As I am in my starting career year in software development (C++ & C#) I now see my flaws and what I miss in this sphere. Because of that I came into some conclusions and made myself a plan to fill those gaps and increase my knowledge in software development. But the question I stumbled upon after making a tasks which I need to do has not quite obvious answer to me. What is the priority of those tasks? Here are these tasks and my priority by numbering:

Learning:

  1. Functional programming (Scala)
  2. Data structures & Algorithms (Cormen book to the rescue + TopCoder/ProjectEuler/etc)
  3. Design patterns (GOF or Head First)

Do you agree with this tasks and priorities? Or do I miss something here? Any suggestions are welcome!

I think you have it backwards. Start with design patterns, which will help you reduce the amount messy code you produce, and understand better code made by other people (particularly libraries written with design patterns in mind).

In addition to the book of four, there are many other design pattern books -- Patterns of Enterprise Application Architecture, for example. It might be worth looking at them after you get a good grounding. But I also highly recommend Domain Driven Design, which I think gives you a way of thinking about how to structure your program, instead of just identifying pieces here and there.

Next you can go with algorithms. I prefer Skiena's The Algorithm Design Manual, whose emphasis is more on getting people to know how to select and use algorithms, as well as building them from well known "parts" than on getting people to know to make proofs about algorithms. It is also available for Kindle, which was useful to me.

Also, get a good data structures book -- people often neglect that. I like the Handbook of Data Structures and Applications, though I'm also looking into Advanced Data Structures.

However, I cannot recommend either TopCoder or Euler for this task. TopCoder is, imho, mostly about writing code fast. Nothing bad about it, but it's hardly likely to make a difference on day-to-day stuff. If you like it, by all means do it. Also, it's excellent preparation for job interviews with the more technically minded companies.

Project Euler, on the other hand, is much more targeted at scientific computing, computer science and functional programming. It will be an excellent training ground when learning functional programming.

There's something that has a bit of design patterns, algorithms and functional programming, which is Elements of Programming. It uses C++ for its examples, which is a plus for you.

As for functional programming, I think it is less urgent than the other two. However, I indicate either Clojure or Haskell instead of Scala.

Learning functional programming in Scala is like learning Spanish in a latino neighborhood, while learning functional programming in Clojure is like learning Spanish in Madrid, and learning functional programming in Haskell is like learning Spanish in an isolated monastery in Spain. :-)

Mind you, I prefer Scala as a programming language, but I already knew FP when I came to it.

When you do get to functional programming, get Chris Okasaki's Purely Functional Data Structures, for a good grounding on algorithms and data structures for functional programming.

Beyond that, try to learn a new language every year. Even if not for the language itself, you are more likely to keep up to date with what people are doing nowadays.

In algorithms, I've mostly been self-taught and that's largely been fine. However, I'm having trouble grasping graph algorithns. I'm looking for some kind of reference that has concepts and actual code so I can not only learn the theory (which I usually do ok with) but also get a feel for how graphs are represented and manipulated in practice (what I usually have a harder time grasping). Can SO deliver? Anything from books, to links, to existing projects would be great as long as they have both concept and implementation.

This is language agnostic, but I'm most familiar with python and don't have much experience with FP.

Steve Yegge says this is a terrific book on algorithms that uses graphs extensively.

Both of these are very good:

Free Stuff:

I've been asked to recommend a resource (on-line, book or tutorial) to learn Algorithms (in the sense of of the MIT Intro to Algorithms) for non-CS or Math majors. Obviously the MIT book is way too involved and some of the lighter treatments (like OReilly's Algorithms in a Nutshell) still seem as if you would need to have some background in algorithmic analysis. Is there resource that presents the material in a way that developers who do not have a background in theoretical computer science will find useful?

I think the best way to learn algorithms are through the various competition sites.

  • USACO - my personal favorite, as it gives a clear path through the material
  • TopCoder - already mentioned
  • Sphere Online Judge - great if you want to work in another language other than C/C++/Java

As far as books, the best single intro I've seen for the non-math specialist is Data Structures and Algorithms. It takes you through an algorithm line by line and shows you how it decomposes mathematically, something CLRS's otherwise excellent analysis section is a little less clear on.

Skiena's Algorithm Design Manual is also excellent, as is his Programming Challenges, which is essentially a tutorial through the Valladolid Online Judge.

Honestly, though, I think the single most helpful thing a beginner can do is to implement the various algorithms -- merge sort, say, followed by Quicksort -- and time them against variously sized inputs. Create a spreadsheet with a graph that shows their growth over time. Very few non-specialists will have the patience or the know-how to set up a recurrence relation and solve their way through it. But you must understand the effect of, say O n^2 growth over time, and there's no better way to learn this than to watch your own program blow through its memory stack. :)

I say this as a non-CS, non-math programmer who has spent a good couple of months wrapping my mind around algorithmic analysis.

Assume that I have a list of 100 products, each of which has a price. Each one also has a energy (kJ) measurement.

Would it be possible to find the best combination of 15 products for under $10 of which the sum of the energy (kJ) was greatest, using programming?

I know C#, but any language is fine. Cheers.

Update: Having a bit of troble finding some sample source code for the knapsack issue. Does anyone have any or know where to find some. Been googling for a few hours and need to get this sorted by tomorrow if possible. Ta.

The Stony Brook Algorithm Repository lists implementations for the knapsack problem.

Their book The Algorithm Design Manual has this kind of information for a vast array of problems.

What are the most common problems that can be solved with both these data structures?

It would be good for me to have also recommendations on books that:

  • Implement the structures
  • Implement and explain the reasoning of the algorithms that use them

The Algorithm Design Manual contains some interesting case studies with creative use of graphs. Despite its name, the book is very readable and even entertaining at times.

The first thing I think about when I read this question is: what types of things use graphs/trees? and then I think backwards to how I could use them.

For example, take two common uses of a tree:

  • The DOM
  • File systems

The DOM, and XML for that matter, resemble tree structures.
alt text

It makes sense, too. It makes sense because of how this data needs to be arranged. A file system, too. On a UNIX system there's a root node, and branching down below. When you mount a new device, you're attaching it onto the tree.

You should also be asking yourself: does the data fall into this type of structure? Create data structures that make sense to the problem and the rest will follow.

As far as being easier, I think thats relative. Are you good with recursive functions to traverse a tree/graph? What if you need to balance the tree?

Think about a program that solves a word search puzzle. You could map out all the letters of the word search into a graph and check surrounding nodes to see if that string is matching any of the words. But couldn't you just do the same with with a single array? All you really need to do is move an index to check letters to the left and right, and by the width to check above and below letters. Solving this problem with a graph isn't difficult, but it can create a lot of extra work and difficulty if you're not comfortable with using them - of course that shouldn't discourage you from doing it, especially if you are learning about them.

I hope that helps you think about these structures. As for a book recommendation, I'd have to go with Introduction to Algorithms.

@DavidJoiner / all:

FWIW: A new version of the Algorithm Design Manual is due out any day now.

The entire course that he Prof Skiena developed this book for is also available on the web:

http://www.cs.sunysb.edu/~algorith/video-lectures/2007-1.html

Algorithms for Java: Part 5 by Robert Sedgewick is all about graph algorithms and datastructures. This would be a good first book to work through if you want to implement some graph algorithms.

Are there any books for C# developers that will help me to improve my performance answering programming questions during an interview? I need practice, and need to work on algorithm types of questions.

I'd highly recommend the O'Reilly book "C# Cookbook" since it will give you specific algorithm implementations. Another good one is "Algorithms in a Nutshell", for more language agnostic algorithms.

O'Reilly - C# Cookbook
Algorithms in a Nutshell

I like Algorithms in a Nutshell.

Edit: and The Algorithm Design Manual is fun, but don't start there.

Is there a chart or table anywhere that displays a lot of(at least the popular ones) data structures and algorithms with their running times and efficiency?

What I am looking for is something that I can glance at, and decide which structure/algorithm is best for a particular case. It would be helpful when working on a new project or just as a study guide.

Collecting all algorithms and/or data structures is essentially impossible -- even as I'm writing this, there's undoubtedly somebody, somewhere is inventing some new algorithm or data structure. In the greater scheme of things, it's probably not of much significance, but it's still probably new and (ever so slightly) different from anything anybody's done before (though, of course, it's always possible it'll turn out to be a big, important thing).

That said, the US NIST has a Dictionary of Algorithms and Data Structures that lists more than most people ever know or care about. It covers most of the obvious "big" ones that everybody knows, and an awful lot of less-known ones as well. The University of Canterbury has another that is (or at least seems to me) a bit more modest, but still covers most of what a typical programmer probably cares about, and is a bit better organized for finding an algorithm to solve a particular problem, rather than being based primarily on already knowing the name of the algorithm you want.

There are also various collections/lists that are more specialized. For example, The Stony Brook Algorithm Repository is devoted primarily (exclusively?) to combinatorial algorithms. It's based on the Algorithm Design Manual, so it can be particularly useful if you have/use that book (and in case you're wondering, this book is generally quite highly regarded).

Do you know any real applications for Simulated Annealing?

Simulated Annealing is a heuristic algorithm used for problems like the traveling salesman or the knapsack problem.

And yes, this is homework. I have to write a paper on this, and I thought this would be the best starting point. Perhaps someone actually works on a project that relies on Simulated Annealing.

Simulated annealing is usually a method where random sampling techniques,
ie the Monte Carlo method, can be used to find a solution.

The good part is that it does not suffer from the local minimum problem.
For example, it can be used to find a solution on Set cover problems.


Update: The Algorithm Design Manual

7.5.4 Applications of Simulated Annealing

We provide several examples to demonstrate how these components can lead to elegant simulated annealing solutions for real combinatorial search problems.

Maximum Cut

The "maximum cut" problem seeks to partition the vertices of a weighted graph G into sets V1 and V2 to maximize the weight (or number) of edges with one vertex in each set. For graphs that specify an electronic circuit, the maximum cut in the graph defines the largest amount of data communication that can take place in the circuit simultaneously. As discussed in Section 16.6 (page 541), maximum cut is NP-complete. [...]

Independent Set

An "independent set" of a graph G is a subset of vertices of S such that there is no edge with both endpoints in S. The maximum independent set of a graph is the larger such empty induces subgraph. Finding large independent sets arises in dispersion problems associated with facility location and coding theory [...]

Circuit Board Placement

In designing printed circuit boards, we faced with the problem of positioning modules (typically, integrated circuits) on the board. Desired criteria in a layout may include (1) minimizing the area or aspect ratio of the board so that it properly fits within the allotted space, and (2) minimizing the total or longest wire length in connecting the components. Circuit board placement is representative of the kind messy, multicriterion optimization problems for which simulated annealing is ideally suited. [...]

I think this is a scheduling problem, but I'm not even sure on that much! What I want is to find the optimal sequence of non-overlapping purchase decisions, when I have full knowledge of their value and what opportunities are coming up in the future.

Imagine a wholesaler who sells various goods that I want to buy for my own shop. At any time they may have multiple special offers running; I will sell at full price, so their discount is my profit.

I want to maximize profit, but the catch is that I can only buy one thing at a time, and no such thing as credit, and worse, there is a delivery delay. The good news is I will sell the items as soon as they are delivered, and I can then go spend my money again. So, one path through all the choices might be: I buy 100kg apples on Monday, they are delivered on Tuesday. I then buy 20 nun costumes delivered, appropriately enough, on Sunday. I skip a couple of days, as I know on Wednesday they'll have a Ferrari at a heavy discount. So I buy one of those, it is delivered the following Tuesday. And so on.

You can consider compounding profits or not. The algorithm comes down to a decision at each stage between choosing one of today's special offers, or waiting a day because something better is coming tomorrow.

Let's abstract that a bit. Buy and delivery become days-since-epoch. Profit is written as sell-price divided by buy-price. I.e. 1.00 means break-even, 1.10 means a 10% profit, 2.0 means I doubled my money.

  buy    delivery   profit
    1        2       1.10    Apples
    1        3       1.15    Viagra
    2        3       1.15    Notebooks
    3        7       1.30    Nun costumes
    4        7       1.28    Priest costumes
    6        7       1.09    Oranges
    6        8       1.11    Pears
    7        9       1.16    Yellow shoes
    8       10       1.15    Red shoes
   10       15       1.50    Red Ferrari
   11       15       1.40    Yellow Ferrari
   13       16       1.25    Organic grapes
   14       19       1.30    Organic wine

NOTES: opportunities exist only on the buy day (e.g. the organic grapes get made into wine if no-one buys them!), and I get to sell on the same day as delivery, but cannot buy my next item until the following day. So I cannot sell my nun costumes at t=7 and immediately buy yellow shoes at t=7.

I was hoping there exists a known best algorithm, and that there is already an R module for it, but algorithms or academic literature would also be good, as would anything in any other language. Speed matters, but mainly when the data gets big, so I'd like to know if it is O(n2), or whatever.

By the way, does the best algorithm change if there is a maximum possible delivery delay? E.g. if delivery - buy <= 7

Here is the above data as CSV:

buy,delivery,profit,item
1,2,1.10,Apples
1,3,1.15,Viagra
2,3,1.15,Notebooks
3,7,1.30,Nun costumes
4,7,1.28,Priest costumes
6,7,1.09,Oranges
6,8,1.11,Pears
7,9,1.16,Yellow shoes
8,10,1.15,Red shoes
10,15,1.50,Red Ferrari
11,15,1.40,Yellow Ferrari
13,16,1.25,Organic grapes
14,19,1.30,Organic wine

Or as JSON:

{"headers":["buy","delivery","profit","item"],"data":[[1,2,1.1,"Apples"],[1,3,1.15,"Viagra"],[2,3,1.15,"Notebooks"],[3,7,1.3,"Nun costumes"],[4,7,1.28,"Priest costumes"],[6,7,1.09,"Oranges"],[6,8,1.11,"Pears"],[7,9,1.16,"Yellow shoes"],[8,10,1.15,"Red shoes"],[10,15,1.5,"Red Ferrari"],[11,15,1.4,"Yellow Ferrari"],[13,16,1.25,"Organic grapes"],[14,19,1.3,"Organic wine"]]}

Or as an R data frame:

structure(list(buy = c(1L, 1L, 2L, 3L, 4L, 6L, 6L, 7L, 8L, 10L, 
11L, 13L, 14L), delivery = c(2L, 3L, 3L, 7L, 7L, 7L, 8L, 9L, 
10L, 15L, 15L, 16L, 19L), profit = c(1.1, 1.15, 1.15, 1.3, 1.28, 
1.09, 1.11, 1.16, 1.15, 1.5, 1.4, 1.25, 1.3), item = c("Apples", 
"Viagra", "Notebooks", "Nun costumes", "Priest costumes", "Oranges", 
"Pears", "Yellow shoes", "Red shoes", "Red Ferrari", "Yellow Ferrari", 
"Organic grapes", "Organic wine")), .Names = c("buy", "delivery", 
"profit", "item"), row.names = c(NA, -13L), class = "data.frame")

LINKS

Are there any R Packages for Graphs (shortest path, etc.)? (igraph offers a shortest.paths function and in addition to the C library, has an R package and a python interface)

You can solve this as a linear programming problem. This is the standard approach to solving logistics problems, such as those faced by airlines and corporations, with much larger problem spaces than yours. I won't formally define your problem here, but in broad terms: Your objective function is the maximisation of profit. You can represent the buy days, and the "only one purchase per day" as linear constraints.

The standard linear programming algorithm is the simplex method. Although it has exponential worst case behaviour, in practice, it tends to be very efficient on real problems. There are lots of good freely available implementations. My favourite is the GNU Linear Programming Kit. R has an interface to GLPK. Lp_solve is another well-known project, which also has an R interface. The basic approach in each case is to formally define your problem, then hand that off to the third party solver to do its thing.

To learn more, I recommend you take a look at the Algorithm Design Manual, which should give you enough background to do further research online. p.412 onwards is a thorough summary of linear programming and its variations (e.g. integer programming if you have integrality constraints).

If you've never heard of linear programming before, you might like to take a look at some examples of how it can be used. I really like this simple set of tutorial problems in Python. They include maximising profit on tins of cat food, and solving a Sudoku problem.

Specifically a Multigraph.

Some colleague suggested this and I'm completely baffled.

Any insights on this?

It's an acceptable approach. You need to consider how that information will be manipulated. More than likely you'll need a language separate from your database to do the kinds graph related computations this type of data implies. Skiena's Algorithm Design Manual has an extensive section graph data structures and their manipulation.

Without considering what types of queries you might execute, start with two tables vertices and edges. Vertices are simple, an identifier and a name. Edges are complex given the multigraph. Edges should be uniquely identified by a combination two vertices (i.e. foreign keys) and some additional information. The additional information is dependent on the problem you're solving. For instance, if flight information, the departure and arrival times and airline. Furthermore you'll need to decide if the edge is directed (i.e. one way) or not and keep track if that information as well.

Depending on the computation you may end up with a problem that's better solved with some sort of artificial intelligence / machine learning algorithm. For instance, optimal flights. The book Programming Collective Intelligence has some useful algorithms for this purpose. But where the data is kept doesn't change the algorithm itself.

Given a path, I want to optimize it so that all verticies that are straight on a line can be removed.

For example: Path:

*******
*      *
*        *
***********

Could be optimized to:

*-----*
|      \
|        \
*---------*

However I want to have control over the deviation from the slope so that it doesnt have to be exactly on the slope.

What sort of algorithm can do this?

Thanks

I think this page should help you: Simplyfing Polygons (and I also recommend the book).

i'm reading this book: The Algorithm Design Manual, and i'm having a problem to understand, it's about inductive assumption, so i've this pseudocode:

Increment(y)
  if y = 0 
    then return(1) 
 else if (y mod 2) = 1 
   then return(2 · Increment(⌊y/2⌋))
  else 
    return(y + 1)

So i've to prove through mathematic induction that this code really work, the first part is easy:

if y = 0 
    then return(1)

The last part is easy too, it's get even number

else 
    return(y + 1)

But middle part being very difficult for me:

else if (y mod 2) = 1 
   then return(2 · Increment(⌊y/2⌋))

here is the explanation of the book:

Now, the case of odd y (i.e. y = 2m + 1 for some integer m) can be dealt with as:
(y = 2m + 1; because 2m + 1 is equal to any odd number)//this is what i understand

= 2 · Increment(⌊(2m + 1)/2⌋)//(2m + 1)/2 = m + 1/2
= 2 · Increment(⌊m + 1/2⌋)//ok we get here, but how (m + 1/2) will be the "m" bellow?
= 2 · Increment(m)
= 2(m+1)
= 2m+2 =y+1

Anyone could explain how to prove that this recursive really work? And how prove this by mathematic induction.

= 2 · Increment(⌊m + 1/2⌋) //ok we get here, but how (m + 1/2) will be the "m" bellow?

Because ⌊m + 1/2⌋ = m, that's as simple as that. (I'm assuming you know that ⌊m + 1/2⌋ means floor(m + 1/2).

Note that m is an integer, and given that 1/2 is fractional, then floor(m+1/2) is m. In fact, floor(m + x), where 0 <= x < 1, is just m: adding any fractional part to m does not change the result of floor().

So you get 2 * Increment(m) = 2(m+1) = 2m+2 = (2m+1)+1 = y+1

UPDATE: Proof by induction is pretty similar.

Recall the general layout of proof by induction: first, we elaborate the induction hypothesis. Then, we show that this hypothesis holds for a base case (usually, a base case is when n = 0, or n = 1). Last, but not least, we show, using the hypothesis, that if it works for some value of n, then it also works for n+1. Since the hypothesis works for the base case, and because we showed (with an induction step) that if it works for n, then it works for n+1, then it must be true for every value greater than or equal to the base case value.

Hypothesis

In this specific case, our hypothesis is that this function:

I(n) = 1 if n is 0
       n+1 if n is even
       2*I(floor(n/2)) otherwise

is equal to n+1, that is,

I(n) = n+1

Where I(n) is just a short hand notation for Increment(n). You can also see the hypothesis as a set of 3 mathematical statements (in other words, the hypothesis is that each of the three cases evaluates to n+1 in the conditions stated).

Base case

The base case is when n = 0. For n = 0, I(n) evaluates to 1, which is n+1 (with n being 0), so we have proven that the hypothesis works for n = 0.

Now, we want to prove that if our hypothesis works for n, then it works for n+1.

Induction step

If I(n) = n+1 holds, then I(n+1) = (n+1)+1 must be true. Basically, we are saying, "OK, if I(n) evaluates to its argument plus one, then it means that I(n+1) must be (n+1)+1. This is what we have to prove: we must show that I(n+1) = (n+1)+1.

Now, according to the original definition for I(n), we have two cases: either its argument is even, or it is odd.

This time, the argument to the function I is n+1 - let's consider both cases.

If n+1 is even, by the definition of I(n), we can immediately see that I(n+1) = (n+1)+1.

If n+1 is odd, then we know that n+1 = 2m+1 for some integer m, because if n+1 is odd, then n is even, which means that there is an integer m less than n such that 2m = n. So, we can rewrite n+1 as 2m+1:

I(n+1) = I(2m+1) = 
       = 2*I(floor((2m+1)/2)) =
       = 2*I(floor(m + (1/2)) =
       = 2*I(floor(m)) = // we can remove 1/2 for the same reason
       = 2*I(m) =
       = 2*(m+1) = // inductive step; we used the hypothesis that I(n) = n+1
       = 2*m+2 = 
       = (2*m+1)+1 =
       = (n+1)+1

This shows that if the proposition is true for floor(n/2) (because m is n/2), then it is also true for n+1. By using strong induction, we can prove that if the proposition is true for all m, 0 <= m <=n, it is also true for n+1 (see comment below).

So, indeed, I(n+1) = (n+1)+1 for any integer, assuming that I(n) = n+1 is valid.

We showed that the hypothesis works for n+1 if it works for n, and we showed that it works for n = 0. Thus, it works for n >= 0.

I need a good source for reading up on how to create a algorithm to take two polylines (a path comprised of many lines) and performing a union, subtraction, or intersection between them. This is tied to a custom API so I need to understand the underlying algorithm.

Plus any sources in a VB dialect would be doubly helpful.

This catalogue of implementations of intersection algorithms from the Stony Brook Algorithm Repository might be useful. The repository is managed by Steven Skiena, author of a very well respected book on algorithms: The Algorithm Design Manual.

That's his own Amazon exec link by the way :)

Would a function that traversed a graph work equally well to traverse a tree?

Well a tree is just a special type of graph called a directed acyclical graph, so yes...Breadth First and Depth First traversal both work on a tree.

I could write out a detailed explanation of the differences between breadth and depth first traversals, but I'd probably get it wrong (I'm not a heavy comp-sci guy yet).

Suffice it to say that the only difference between breadth and depth first traversal is the order in which you process the vertices. Breadth first you can think of as adding vertices to a "to-be-processed" queue. Depth first you can think of as adding the vertices to a "to-be-processed" stack. When it comes time to process the vertices (after they've been added to their respective data structures) you dequeue or pop the stack to get the next vertex to process. Clever versions of depth first traversal use recursion to process the vertices instead of adding them to a stack.

I have no idea whether this was helpful or not...

A quick google search (I don't know whether it was breadth or depth first) finds this which seems pretty good at describing the differences between BFS and DFS. I can also recommend Steve Skiena's The Algorithm Design Manual if you want to get a more in depth read.

I am learning Quick Sort. I know that Quick Sort performs badly when the pivot value does an unbalanced partition , and so first element or last element is not a good choice because if the list is almost sorted the partition would be unbalanced.

As i searched i found 2 options:

One was to choose a pivot randomly between low(lowest index) and up(highest index).It seems a safe option but random number generators are time consuming.

Second would be to take the median of all the elements. This option is costly so the median of first,last and middle element can be used as the pivot element.

Which method proves out to be the most efficient for Quick Sort?.. Is there any other method available for making the choice of pivot element?

Yes, if you're worried about the array being sorted or nearly sorted, you can apply successively more effort to choosing a good pivot, as you suggest, but at the cost of slowing the algorithm down if your data is unsorted. Skienna, in The Algorithm Design Manual, has a good discussion of pivot selection and he suggests you could go as far as to randomize the array before applying quicksort, but my guess is another sorting algorithm would perform better if you're that worried.

Which method proves out to be the most efficient for Quick Sort?

The key point here is to perform performance measurements on your data.

I'm building a trading application that matches buyers/sellers that own subscription. Subscriptions have a certain quantity amount for a certain duration of time. There are 8 order types which are:

  • Buy/sell subscription (can either be partially filled in regards to quantity or time)
  • Buy/sell all quantity subscription (can only be partially filled in regards to time)
  • Buy/sell all time subscription (can only be partially filled in regards to quantity)
  • Buy/sell all quantity and time subscription (cannot be partially filled, all or nothing)

Each user that fills the


Example 1

Assuming all orders in this example can be partially filled in regards to quantity and time lets say User A places a buy order asking for 100 shares between 1/2/2014 - 1/3/2014 (dd/mm/yyyy).

There are 4 sell orders currently in the order book

  • User B is selling 25 shares between 1/1/2014 - 5/1/2014
  • User C is selling 50 shares between 1/1/2014 - 15/2/2014
  • User D is selling 70 shares between 10/2/2014 - 1/7/2014
  • User E is selling 5 shares between 15/2/2014 - 25/2/2014

Which would look like

User A                 |--------------100-----------|
User B    |----------------------------25-----------------------|
User C    |-------------------50---|
User D                       |--------------70------------------|
User E                             |--5--|

After the matching is done each users orders in the order book would look like

User A                 |-25--|           |----5-----|
User B    |------25----|                            |----25-----|
User C    |------50----|
User D                                              |----70-----|
User E has no open orders

After all said and done the order book would look like:

  • User A is buying 25 shares between 1/2/2014 - 10/2/2014
  • User A is buying 5 shares between 15/2/2014 - 1/3/2014
  • User B is selling 25 shares between 1/1/2014 - 1/2/2014
  • User B is selling 25 shares between 1/3/2014 - 5/1/2014
  • User C is selling 50 shares between 1/1/2014 - 1/2/2014
  • User D is selling 70 shares between 1/3/2014 - 1/7/2014
  • User E isn't selling anything

Example 2

This example is exactly the same except User B is of sell all quantity and time subscription type. In other words User B wants to sell his/her's entire position.

After the matching is done each users orders in the order book would look like

User A                 |-50--|     |--25-|----30----|
User B    |----------------------------25-----------------------|
User C    |------50----|
User D                       |-20--|                |----70-----|
User E has no open orders

After all said and done the order book would look like:

  • User A is buying 50 shares between 1/2/2014 - 10/2/2014
  • User A is buying 25 shares between 15/2/2014 - 25/3/2014
  • User A is buying 30 shares between 25/2/2014 - 1/3/2014
  • User B is selling 25 shares between 1/1/2014 - 5/1/2014 (doesn't even match because this order doesn't allow partial filling)
  • User C is selling 50 shares between 1/1/2014 - 1/2/2014
  • User D is selling 70 shares between 15/2/2014 - 25/2/2014
  • User D is selling 70 shares between 1/3/2014 - 1/7/2014
  • User E isn't selling anything

Process

Another requirement is I need to be able to keep track of how the orders are filled in the database. When User A's buy order comes in it will first match to User B's which would result in:

User A                 |--------------75------------|
User B    |------25----|                            |----25-----|

Both of those states would need to be saved to the database. Once that is complete then User C's order is matched up, which would look like:

User A                 |-----25----|------75--------|
User B    |------25----|                            |----25-----|
User C    |------50----|

Keep going:

User A                 |--25-|     |-------5--------|
User B    |------25----|                            |----25-----|
User C    |------50----|
User D                                              |----70-----|

Current Process

  1. Get all of the sell orders (responders) that overlap the buy orders' (requester) date range (this would be opposite if it was an incoming sell order. The requester is referred to as the person who trigger the incoming order. Responder's are the potential matches)
  2. Sort the sell orders by price first then by time
  3. Loop through each of the sell orders
    • Calculate agreed price
    • Calculate quantity to trade
    • Get the buyers date range in relation to the current sell orders date range
    • Determine by the date range relation between buyer and seller if its a partial fill
    • If the seller does not allow partial fills, then continue to the next order
    • Process the sell order
      • Does the sell order come before but overlap the buyers order? If so split the sell order and process the right end overlap and subtract the quantity requested from the buyer.
      • Does the sell order come inside the buyers order? If so don't split anything just process that order completely and subtract the quantity requested from the buyer.
      • Does the sell order come after but inside the buyer order? If so split the sell order and process the left side overlap and subtract the quantity requested from the buyer.
      • Is the sell order a larger date range then the buyer order? If so split at the start and end and process the middle piece by subtracting the quantity requested from the buyer.

That's as far as I've made it without it working properly when multiple orders are in the order book. The problem might be that for each sell order that comes in I'm always compare that to the original buy order when in fact the buy order gets filled up as sell orders are iterated. Maybe I need another nested loop? I'm not sure.


Question

Is there any existing algorithm to do what I'm asking?

EDIT: After some searching it sort of seems like I'm after an interval tree or a segment tree where I can sum up what's in the tree for a given time range. However I need to be able to store the modifications to the tree in a database with the start and dates. Are there any implementations out there of this done with LINQ or SQL?

EDIT 2: In my first edit I thought it was an interval tree but now it looks more like bin packing algorithm

EDIT 3 OK so I really seemed to have not conveyed my questions properly here. I don't really have a coding problem but more of a thinking problem of how to achieve this properly. I need a flow diagram or steps of execution to be able to process buyers and sellers by splitting their subscriptions based on the conditions outlined at the top.

I have posted this same question @ http://programmers.stackexchange.com/ as well in case this was the wrong site to post this question on.

Ryan,

Sounds like Knapsack problem to me, with the goal of minimizing the cost instead of weight. Think that the buy order is the sack that you have to fill in each day. There's a dynamic programming solution for this, it's elegant and require less memory. However I doubt that you can get historical data of how it is filled.

Random resources I get from internet: http://www.programminglogic.com/knapsack-problem-dynamic-programming-algorithm/

If you want to learn further, I would recommend you to read the explanation in [Algorithm design manual from Steven Skienna] (http://www.amazon.com/Algorithm-Design-Manual-Steven-Skiena/dp/1848000693)

Hope this helps.

How do you get started with competitive programming and get well versed with various topics in it ? What all things you can do ? Get started directly or do some concepts first.

My 2 cents...
Best option is to get registered at the following coding sites..
+ topcoder.com
+ codechef.com
+ hackerrank.com

And, while you hack code here, you can build upon your programming foundation by learning more on
+ Data structures
+ Algorithms
+ Operating system concepts
+ Networking concepts and more ...

You could also start looking at the following books in this area...
+ The Algorithm Design Manual
+ Programming Challenges: The Programming Contest Training Manual
+ Competitive Programming 2

Hi i'm having trouble doing an homework , i've to make recursive version of Dijkstra Algorithm , can somebody help me?

If you're having problems understanding the Dijkstra's Algorithm for Shortest Paths in Graphs, you can check this link. It also has some pseudocode that might be helpful.

Also, here is a fine video lecture on shortest paths, by Steven Skiena, the author of The Algorithm Design Manual. By the way, this is an amazing book on algorithms that I recommend to everyone! It contains a wide variety of data structures and algorithms, and on the second part of the book, it has a humongous collection of problems (one pagers) with various ways/algorithms to solve them.