5
$\begingroup$

Can data structures be thought of as algorithms themselves?

For example, I could implement a stack data structure that has certain non-functional characteristics.

Is the separation between data structures and algorithms formally defined?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ I am not sure if this question can be answered in an objective way. People, if you answer make sure to cite authorative references! $\endgroup$ Commented Nov 3, 2015 at 23:25
  • $\begingroup$ the distinction between code and data blur esp in OOP theory and even lambda calculus. in a sense "each is made out of the other". might try to cook up an answer on this at some pt. $\endgroup$ Commented Nov 4, 2015 at 16:23
  • $\begingroup$ Related questions here and here. $\endgroup$ Commented May 25, 2016 at 9:23

5 Answers 5

Reset to default
7
$\begingroup$

Yes, a data structure can be thought of as an algorithm. A data structure is a collection of state together with one or more algorithms that operate on that state.

A data structure can be thought of as a tuple $(s,f_1,f_2,\dots,f_k)$ where $s$ is its state, and each $f_i$ is an operation that can be performed on the data structure; the operation $f_i$ can read the state $s$ and its input parameters, and possibly modifies $s$ and possibly returns a new value. Alternatively, from an object-oriented viewpoint, you can think of a data structure as an object; $s$ is the state of the object, and $f_1,\dots,f_k$ are the methods that can be invoked on the object. Normally, $f_1,\dots,f_k$ are described as algorithms that operate on $s$ and their inputs. This lets you use the language and concepts of algorithms to analyze various data structures.

I'm not sure there is a formal specification of what counts as a data structure, but this seems to get about close as I've seen.

You might be interested in the notion of abstract data type (ADT) from programming languages. You can think of a data structure as an ADT, or more carefully, you can think of an ADT as the specification and the data structure code as a particular implementation of that ADT. When people talk about data structures informally, they don't always distinguish between specification vs implementation; the term ADT helps make that distinction more precise.

I don't know if people normally try to formally define what we mean by "data structure"; it's a loose term that is more useful to illustrate a particular type of concept in computer science. If I wanted to make it as precise as possible, the notion of an ADT would probably be the first formalization I'd consider. An ADT is like an interface specification, and a specific data structure is like a particular way of implementing that specification.

Improve this answer
$\endgroup$
6
  • $\begingroup$ How is homoiconicity related to your answer? $\endgroup$ Commented Nov 3, 2015 at 23:54
  • $\begingroup$ @BenAston, I've no idea. (I'm not familiar with that term, but after a quick glance at the Wikipedia page I don't see any obvious reason to expect it to be related.) $\endgroup$ Commented Nov 3, 2015 at 23:57
  • $\begingroup$ Not sure I agree with this answer. In your example you are presentating a set of parameters that can alter the outcome, but those parameters will only mean anything as long as the algorithm is already in place to interpret them. $\endgroup$ Commented Nov 4, 2015 at 3:14
  • $\begingroup$ @Octopus, I confess you've lost me there. $f_i$ is an operation (e.g., think DeleteMin or Insert). So $f_i$ is a function that accepts some parameters; I wouldn't call $f_i$ a parameter itself. DeleteMin can alter the state $s$. Insert can accept a parameter (the item to insert) and alter the state $s$. I'm not entirely sure what you mean by "outcome" or "parameter". I also don't know what you mean by "already in place to interpret them"; the description of a data structure specifies $f_1,\dots,f_k$, typically by presenting an algorithm or pseudocode for each $f_i$. $\endgroup$ Commented Nov 4, 2015 at 3:37
  • $\begingroup$ Well I suppose you could take the state of your machine as one big "data structure" and argue that it includes several "algorithms" in the form of instruction codes (which is what it sounds like you're doing), but isn't that blurring the distinction between data and code? $\endgroup$ Commented Nov 4, 2015 at 4:39
7
$\begingroup$

A data structure is an implementation of the ADT. An ADT can be assumed to be a contract which guarantees certain operations in a promised amount of time. It doesn't state how it will layout the underlying data in memory.

Now, it's up to the programmer to implement the ADT which is known as Data Structure. For example, Stack is an ADT and it can be implemented over a linear data structure like Array or over a linked data structure like Linked List.

Regarding your question I am not sure because it's said that:

$Programs = Data Structures + Algorithms $ Reference

So, Stack in itself is not an algorithm, but evaluating a postfix expression using a Stack is an algorithm.

It seems a subjective matter though.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I don't think its subjective. I believe the answer is one of semantics and you have hit the proverbial nail on the head. Data Structures and Algorithms are necessarily two different things by definition. +1 $\endgroup$ Commented Nov 4, 2015 at 6:06
  • $\begingroup$ @Octopus thanks, actually I am newbie too so, I need to gain some confidence. Hopefully I am going in correct direction. $\endgroup$ Commented Nov 4, 2015 at 6:07
1
$\begingroup$

Many divide-and-conquer algorithms map directly to tree structures which match their call graphs. For instance Bentley and Sedgewick's Fast Algorithms for Sorting and Searching Strings introduces both a recursive algorithm and a search tree with the same structure; the sorting process amounts to traversing the tree without physically instantiating it (beyond the nodes saved in the stack). There's also a table in there of other algorithm-tree examples.

These tree structures are often necessary to do proper algorithm analysis, because information-theoretic results about the average number of nodes in a trie or Patricia tree can be mapped to the number of recursive calls and character comparisons in a string sorting algorithm, for instance.

It's also a fairly common pattern to instantiate only part of this mapped data structure as an intermediate step in, eg, a sorting process, where a search tree is used to divide the input into bins which are then procedurally sorted. For instance parallel sorting may instantiate only the first few levels of a search tree to distribute data among nodes, which then procedurally sort each bin.

Improve this answer
$\endgroup$
0
$\begingroup$

Both concepts are about mapping some input to some output. Algorithms does this mapping by following a sequence of instructions whereas data structures does the mapping (Array map index to value, dictionary map key to value etc) by memory lookup(s). From this point of view both are same but the way they does the mapping is different.

NOTE: Mutating a data structure can be thought of mapping where the output also contains new update data structure.

Improve this answer
$\endgroup$
0
$\begingroup$

“Can data structures be thought of as algorithms themselves?” (Aston, 2015) It is possible to map the information about a process kept in record-based structures into a computer program (Chionglo, 2104). Thus data kept in records can be thought of as algorithms.

If you consider records as data structures and if you consider the following (a repeating countdown timer/counter) an algorithm:

  1. Initialize a variable to 9.
  2. Subtract 1 from the variable.
  3. If the value of the variable is 0, go to step 1 else go to step 2.

Then a process description of the algorithm can be “stored” in several record structures. The entities in the records are (Petri) net elements and their properties/annotations. The annotations include logic computations and interfaces (such as graphics, user events, and system events) for visualization and interaction purposes. These properties give the user or reader the ability to see and to step through the algorithm. The information kept in the record structures may be mapped to a JavaScript program that controls Figure 1 in the PDF version of this reply, an interactive process description (based on Petri Nets) of the algorithm.

References

Aston, B. (2015). Data structures as algorithms themselves. Computer Science Stack Exchange.

Chionglo, J. F. (2014). Net elements and annotations for computer programming: computations and interactions in PDF.

Improve this answer
$\endgroup$

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.