Relation between object orientation and algorithms

Question

As I read some algorithms textbooks, they are full of clever procedures for some problems (sorting, shortest path) or some general methods (recursive algorithms, divide and conquer, dynamic programming...). I found few traces of object oriented programming there; (Why they are more procedure-oriented?).

Then I was thinking:

• What is the relation between algorithms and OOP? Are they two independent topics?
• Are there some problems which can only be presented and solved by OOP?
• How can OOP help algorithms? Or in which direction it can affect it?

Answer 1

First, lets define what we mean by OOP. By OOP I primarily mean:

• Encapsulation and hiding of details in class.
• Polymorphism of behavior through inheritance and virtual methods.

Now, to answer your question:

What is the relation between algorithms and OOP? Are they two independent topics?

Yes, algorithms and OOP are independent topics.

Are there some problems which only can be presented and solved by OOP?

No. OOP primarily offers convenience with its object-oriented-structuring of code. OOP allows the programmer to read (and write) code more easily and makes it easier to understand how code works. It neither increases nor decreases the (algorithmic) procedure behind a code.

How OOP can help algorithms? Or in which direction it can affect it?

Like I said above. Both points, Encapsulation & Polymorphism, apply here. Being able to hide details of algorithms and their data structures can help reason about the whole thing. Many algorithms contain details you don't want users of these algorithms messing around with. Hiding those details helps a lot.

The ability to have polymorphic behavior is great too. List is defined as being able to add/remove/clear the items anywhere in the collection. But it can be implemented as resizable array, double-linked or single-linked, etc. Having single API for multiple implementations can help reuse.

Why algorithms textbook are more procedure-oriented?

Like I said, OOP is not necessary to implement an algorithm. Also, many algorithms are old and created when OOP was still not widespread. So it might also be a historical thing.

Answer 2

Algorithms and OOP are two disparate terms, which have only in common, that they are CS-terms. Simply - An algorithm is like a cooking recipe: to do x you need the following ingredients and do step 1,2,3,4,5,6... then you have your meal prepared.

That said, it seems a natural fit for algortihms to be described in a procedural way. Procedural means nothing other than: first do x and then do y.

A common problem is: »How to sort a set of x?«. An easy to understand solution is bubble-sort:

1. Iterate over the set from the last element as long as you have not reached the first element and while iterating
2. Start a 2nd iteration from the beginning to the current element of the first iteration and
3. Compare the current element of (2) with its successor
4. If greater, swap positions

That is the algorithmic / verbal description of the bubblesort-algorithm.

Here comes a procedural / pseudocode implementation

bubbleSort(Array A)
  for (n=A.size; n>1; n=n-1){
    for (i=0; i<n-1; i=i+1){
      if (A[i] > A[i+1]){
        A.swap(i, i+1)
    } 
  } 
}

That was easy.

How does that releate to OOP? You could use this algorithm to treat collections (an object itself) of objects:

Example in Javascript (though no clean OO-Lingo, but with near to no boilerplate and easy to understand)

objects =[{"name":"Peter"}, {"name":"Paul"}, {"name":"Mary"}]

compareObjects=function(x,y){ return x.name>y.name };

sorted = objects.sort(compareObjects)

console.log(sorted)

We have a) a collection objects, b) a method common to this collection sort which contains / abstracts away the sorting algorithm and c) our objects Peter, Paul and Mary. The Specification for the sorting is found here.

What is the relation between algorithms and OOP? Are they two independent topics?

From what was said, it should be clear, the answer should be: yes, they are independend.

How OOP can help algorithms? Or in which direction it can affect it?

OOP is just one programming style. It can not help in any kind. Otherwise an algorithm could be implemented in an OO language to do something to objects (as shown)

Are there some problems which only can be presented and solved by OOP?

I can not think of one (but that doesn't mean, that it is impossible). But if you look it the other way around: OOP is useful, if you want to model some problems and solve ith with an appropriate algorithm. Say you have a record of friends you could model them as objects with properties and if you want a list of friends sorted in any way, you could use the example-code given above to do exactly that.

Why algorithms textbook are more procedure-oriented?

As said: it is more natural, since procedural is the character of algorithms.

Answer 3

you have a problem.

The business domain model describes your problem, and the concepts from the problem domain you are going do be dealing with.

Algorithms describe the way you are going to solve your problems, conceptually; what will your implementation look like; and how do you deal with your problem after you translated it into "Computer Science" terms.

Programming paradigm whether OOP, Functional, Logical, Procedural, or even Non-Structured, describe how are you going to structure your solution, which form is it going to take, which "Software Engineering" concepts are you going do employ, and which "Programming Language Theory" concepts you are going to employ.

To put it more simply, algorithms describe in general your solution to the problem ("This is what I'm going to do"). While programming paradigm deals with your actual implementation ("This is how I'm going to do it").

Answer 4

Algorithms = tell the "How" story (i.e. how to manipulate input data using data structures in time to produce desired results)

OOP = a "Methodology" facilitated by OO-languages to write programs (=algorithms + data structs) that gives you memory safety and abstraction

OOP is just a paradigm of implementing algorithms.

Good analogy: movies

You can record scenes by employing a stuntman or not. Screenplay (algorithm) does not change. People shouldn't see any difference in final result.

EDIT: you could try out a good quality MOOC: https://www.coursera.org/course/algs4partI which interleaves the discussed topics (especially OOP approach) and gives the essence of what you ask here.

Answer 5

Alexander Stepanov is the original creator of the C++ Standard Template Library, (STL), which is the foundational algorithm library for C++. C++ is a multi-paradigm language that includes "Object Oriented" features, but Alexander Stepanov has this to say about Object Orientation:

http://www.stlport.org/resources/StepanovUSA.html

STL is not object oriented. I think that object orientedness is almost as much of a hoax as Artificial Intelligence. I have yet to see an interesting piece of code that comes from these OO people.

I find OOP technically unsound. It attempts to decompose the world in terms of interfaces that vary on a single type. To deal with the real problems you need multisorted algebras - families of interfaces that span multiple types. I find OOP philosophically unsound. It claims that everything is an object. Even if it is true it is not very interesting - saying that everything is an object is saying nothing at all. I find OOP methodologically wrong. It starts with classes. It is as if mathematicians would start with axioms. You do not start with axioms - you start with proofs. Only when you have found a bunch of related proofs, can you come up with axioms. You end with axioms. The same thing is true in programming: you have to start with interesting algorithms. Only when you understand them well, can you come up with an interface that will let them work.

I spent years trying to find some use for inheritance and virtuals, before I understood why that mechanism was fundamentally flawed and should not be used.

Stepanov expressed his algorithm library not with Objects, but with Generic Iterators.

Answer 6

Algorithms describe what the computer should do. Structure describes how the algorithm is laid out [in source code]. OOP is a style of programming which leverages certain "object oriented" structures.

Algorithm books often eschew OOP because they are focused on algorithm, not structure. Fragments of code which heavily rely on structure tend to be poor examples to put in an algorithm book. Likewise, OOP books often eschew algorithms because they clutter up the story. The selling point of OOP is its fluidity, and pegging it to an algorithm makes it appear more rigid. It's more about the focus of the book than anything else.

In real life code, you will use both side by side. You can't solve computer problems without algorithms, by definition, and you'll find its hard to write good algorithms without structure (OOP or otherwise).

As an example of where they blur, take Dynamic Programming. In an algorithm book, you would describe how to take a homogenous dataset in an array and use Dynamic Programming to arrive at a solution. In an OOP book, you may come across a structure such as Visitor, which is a way to do arbitrary algorithms across a set of heterogeneous objects. The DP book example could be thought of as a very simple Visitor operating on objects in a generally bottom-up order. The Visitor pattern could be thought of as the skeleton of a DP problem, but missing the meat and potatoes. In reality, you will find you often need both together: You use the Visitor pattern to deal with heterogeneity across your dataset (DP is bad at that), and you use DP within the structure of Visitor to organize your algorithm to minimize runtime (Visitor doesn't specify an algorithm).

We also see algorithms operating over the top of design patterns. Its harder to word examples in a small space, but once you have structure, you start wanting to manipulate that structure, and you use algorithms to do it.

Are there some problems which can only be presented and solved by OOP?

This is a more difficult question to answer than you think it is. To the first order, there is no computational reason why you need OOP to solve any problem. The simple proof is that every OOP program gets compiled down to assembly, which is a decidedly non-OOP language.

However, in the greater scheme of things, the answer starts to shy towards yes. You are rarely limited simply by computing methodologies. Most of the time there are things like business needs and developer skill that factor into the equation. Many applications today could not be written without OOP, not because OOP is somehow fundamental to the task, but because the structure provided by OOP was essential for keeping the project on track and on budget.

This does not say that we will never abandon OOP in the future for some funny new structure. It merely says it is one of the most effective tools in our toolbox for a surprisingly large fraction of programming tasks out there today. Future problems may cause us to approach development using different structures. For one, I expect neural nets to require a very different development approach, which may or may not turn out to be "Object Oriented."

I do not see OOP dissapearing in the near future due to the way algorithm designers think. To date, the usual pattern is that somebody designs an algorithm which doesn't leverage OOP. The OOP community realizes the algorithm doesn't really fit the OOP structure, and really doesn't need to, so they they wrap the entire algorithm in an OOP structure and start using it. Consider boost::shared_ptr. The reference counting algorithms that rest inside shared_ptr are not very OOP friendly. However, the pattern did not get popular until shared_ptr created an OOP wrapper around it that exposed the capabilities of the algorithms in an OOP structured format. Now, it's so popular that it made it into the latest spec for C++, C++11.

Why is this so successful? Algorithms are great at solving problems, but they often require a substantial initial research investment to understand how to use them. Object Oriented development is very effective at wrapping such algorithms and providing an interface which requires less initial investment to learn.

Answer 7

In addition to the great answers, I will mention an additional conceptual commonality between OOP and Algorithms.

Both OOP and Algorithms strongly emphasize the use of preconditions and postconditions to ensure the correctness of code.

In general, this is standard practice in all areas of computer science; however, this guiding principle results in an evolutionary path in OOP that makes it mutually beneficial to implement algorithms in OOP environment.

In OOP, a group of objects that can satisfy the same contract (preconditions and postconditions) can be made to implement an interface. The user of such interface will not need to know which implementation is used in the underlying object, except in some rare situations (in which leaky abstraction happens).

An algorithm is an implementation of steps used to perform a computation, one that will take the precondition and produce the postcondition.

Therefore, one can borrow the idea of abstraction in the way of preconditions and postconditions, and apply it to algorithms. You will find that sometimes complicated algorithms can be decomposed into smaller steps, and these smaller steps can permit different implementation strategies as long as the same preconditions and postconditions are met.

By implementing algorithms in OOP, one can make these smaller steps interchangeable.

Finally, keep in mind that FP and OOP are not mutually exclusive. Anything described above can be equally applicable to FP as well.

Answer 8

What is the relation between algorithms and OOP? Are they two independent topics?

Algorithms are about how to solve a problem (How to generate output from the given input), OOP is about how to formulate or express our solution (the steps of the algorithm).

An algorithm can be described in natural language or in assembly language, but the concepts we have in a natural language help us to write and understand it better. For example the algorithm for bubble-sort could be:

bubbleSort(Array A)
  for (n=A.size; n>1; n=n-1){
    for (i=0; i<n-1; i=i+1){
      if (A[i] > A[i+1]){
        A.swap(i, i+1)
    } 
  } 
}

To hide the details of swap and to relate it to the A we used an OOP syntax and feature, then OO makes the algorithm closer to our natural language and understanding.

Are there some problems which can only be presented and solved by OOP?

No, if you consider that any program (or algorithm) on a computer will be translated to a set of instructions executed on CPU (Turing Machine) and if we regard these instructions as the ultimate algorithm which solves the problem on a computer, then OOP can't do something further. It just makes it closer to the human understanding and reasoning. It's a way to package our procedures and data structures.

How OOP can help algorithms? Or in which direction it can affect it?

It may help to state or formulate an algorithm easier or more understandable. It can hide details and provide a big picture of the solution.

In theory, the algorithm is first and implementing it the second. But in reality, we can't be sure that our algorithm works as expected until we trace it or generate the expected output. Computers help us to do that, but you don't expect to write it in machine language (assembly).

In this regard, OOP facilitate the implementation, test and refinement of our algorithm on computers and write it for a computer in a language near to our natural language.