9

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?
  • 4
    Not a duplicate, but related programmers.stackexchange.com/questions/239045/… – Doc Brown Feb 6 '15 at 7:42
  • @DocBrown Thank you, that was very helpful, however here we may consider some concepts around the OO like inheritance, polymorphism ... – Ahmad Feb 6 '15 at 7:49
  • 1
    "Why algorithms textbook are more procedure-oriented?" Java is also procedure-oriented. Java is an object oriented procedural language. – Pieter B Feb 6 '15 at 8:01
  • 1
    @gnat I modified my question, don't know if those explanation was necessary or good or not. However I admit the question addressed by Doc Brown possess more answers which are related to my concerns. – Ahmad Feb 6 '15 at 10:04
10

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

  • 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.

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

No. OOP primary offers convenience and ability to reason about code for programmer. It doesn't increase your expressive power.

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

Like I said above. Both points I described OOP as 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 user of that algorithm messing around with. Hiding those details helps a lot.

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.

  • 1
    Despite the age of texts, you would probably not want to muddy the water of an algorithm with OOP, just because it is modern. – Gusdor Feb 6 '15 at 11:55
15

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.

  • 7
    This answer presupposes that algorithms are naturally procedural. Certainly some of them are, but there is such a thing as functional algorithms. The reason why algorithm books are procedural probably has more to do with the fact that they're focused on performance, and so it's up to the reader to worry about enforcing abstractions, and because imperative languages are more popular than functional languages. – Doval Feb 6 '15 at 13:19
  • I think, that's not quite right. When speaking of functional programming languages, you are talking about the implementation, not of the algorithm itself. Take for example Haskell's quicksort wiki.haskell.org/Introduction#Quicksort_in_Haskell We both would agree, that this is a functional implementation to the quicksort-algortihm. But if you describe, what is done, you have to fallback in a prodecural mode of description. And from this description, you could implement a procedural implementation. – Thomas Junk Feb 6 '15 at 13:49
  • 1
    @ThomasJunk You don't have to fall back to a procedural mode of description, because a functional implementation says what things are, not a sequence of steps. How will you give a sequential description for a pure and lazy computation? You don't know ahead of time how much of an expression will be evaluated, nor in what order its sub-expressions will be computed. – Doval Feb 6 '15 at 14:01
  • 2
    Unfortunately I have no CS degree, so I lack of a broad skillset to prove the following: but I think, every algorithm could be described one way or the other.So there is no genuine pure functional algorithm. Isn't that, what touring completeness means in consequence? – Thomas Junk Feb 6 '15 at 14:20
  • 2
    @Doval well since Turing himself proved that lambda calculus and Turing machines are equivalent, then it's obvious everything you can state in a functional way, you can do imperatively. Also it's trivial to convert lazy computation into imperative form - Haskell's compiler does it all the time... In the end it's just a matter of preference. Sometimes functional is more suitable, and sometimes imperative, and other times logical is the best... – AK_ Feb 6 '15 at 15:38
5

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").

  • Note that in a possibly imperfect way, declarative languages aim at reducing or eliminating the "how" step. Their goal is for you to simply say "this is what I want" (for example, by writing high level equations). Think of a typical SQL query: very little of it is "algorithmic"; you simply tell the database what you want, and it's up to it how it handles your request (within certain limitations, of course). – Andres F. Feb 6 '15 at 20:35
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.

  • I really enjoyed your movie analogy. I'll be borrowing that one in the future. – Marc LaFleur Jan 9 '16 at 17:19
2

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.

  • Well he is wrong... mostly because the STL is very much object oriented... Object oriented in the more modern since of the term... – AK_ Feb 6 '15 at 15:55
  • 1
    @AK_ - I don't think he's wrong at all. STL is not even approximately OO in any sense of the term. You could translate the STL directly into a non-OO language that has parametric polymorphism (eg Haskell or SML) without needing to change it in any substantial way. – Jules Aug 2 '16 at 7:54
2

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.

1

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.

  • Thank you for the point! As you said if algorithm is just some steps, then OOP can help us to provide more abstract steps. You pointed about "implementing algorithms in OOP", I modified my question to ask is it always beneficial? – Ahmad Feb 6 '15 at 14:19
  • 1
    you are confusing OOP with "Design by Contract". It's very well useful without OOP, and most OOP languages (C#, Java) don't provide real support for it (they support simple interfaces, not pre/post conditions) – AK_ Feb 6 '15 at 15:47
  • 1
    @AK_ I agree that Design by Contract is the correct name for the commonality described in my answer. What I am claiming is that OOP as a design paradigm strongly embraces Design by Contract - just read any OOP textbook. My original answer also mentions that this commonality is not exclusive to OOP. – rwong Feb 6 '15 at 16:06
-1
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.

protected by Community Feb 6 '15 at 14:39

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.