-1
$\begingroup$

I often heard that "program = algorithm + data structure".

But I notice that

  1. It seems to me that a data structure is (or may be) just a data type or extension thereof. Is it correct? But a data type is a part of a programming language, but a data structure isn't.

  2. the operations/methods in a data structure actually implement algorithms.

  3. both computability of a problem (i.e. existence of an algorithm for solving the problem) and complexity of an algorithm seem not depend on which data structure to use. Is it correct?

  4. Although there are books specially for data structures.

    • books on programming languages introduce their data types, but not data structures.

    • books on algorithms may introduce data structures in an appendix.

So are "data structures" part of algorithms or of programming languages?

where does "data structure" lie in computer science wrt algorithms and programming languages? Thanks.

$\endgroup$
  • 1
    $\begingroup$ Depends on who's talking, probably. Is there a reason why the answer can't be "both"? Also, I don't know which algorithms books you've read; CLRS and Sedgewick/Wayne definitely feature data structures as major chapters. $\endgroup$ – Raphael Oct 2 '14 at 17:39
  • $\begingroup$ coin = heads + tails. The advantage of coins is that you can flip them. $\endgroup$ – babou Oct 2 '14 at 20:28
  • $\begingroup$ @babou: nice analogy, but I don't get what it implies here. $\endgroup$ – Tim Oct 2 '14 at 20:28
  • 1
    $\begingroup$ @Tim I just think that the formula is simplistic and misleading. Data structures are usually meaningless without code to turn it into an abstraction. Programs are always more than that, unless they are homeworks. etc. $\endgroup$ – babou Oct 2 '14 at 21:07
  • 1
    $\begingroup$ Why does it have to be either? $\endgroup$ – David Richerby Oct 2 '14 at 21:20
3
$\begingroup$

Some aspects of data structures belong to algorithmics ("Theory A"), some to programming language theory ("Theory B"). Since I'm not qualified to discuss the latter, I can mention a few aspects of the former.

Suppose we want to implement a data structure supporting a certain set of operations:

  1. How fast can the operations be, given some computational model (Turing machine, RAM machine, decision trees, memory accesses [the cell probe model])? Worst case, average case; amortized, non-amortized; offline (the list of operations is known in advance) or online.

  2. How much space is required to support the data structure? Is there a tradeoff between the space used and the running times of operations?

  3. If implemented in a distributive fashion (say given limited space on each computation node), how much communication is needed?

Data structure theory is also related to complexity theory, which is used as a tool to prove lower bounds on data structures. For example, communication complexity has been used to this end.

$\endgroup$
3
$\begingroup$

Data structures belong with algorithms. You can implement a red-black tree, associative array, fibonacci heap, and so on in any general purpose language.

However, a language can certainly favor certain kinds of data structures. For example, J, K, APL, and Matlab all favor array/matrix oriented programming styles. Haskell and Clojure suggest use of persistent tree-based data structures. TCL, PHP, and Perl encourage stringly-typed programming.

Regarding your third question: Complexity of algorithms depends very heavily on data structures chosen. Much of the reason to develop data structures, such as red-black trees or finger trees, is to help control and reduce algorithmic complexity of programs that use them.

$\endgroup$
  • $\begingroup$ Does using data structures help to migrate some complexity from algorithm to building the data structures? Is the overall complexity of algorithms and building data structures still conserved, like the conservation of energy? If not, what is conserved? $\endgroup$ – Tim Oct 3 '14 at 18:27
  • $\begingroup$ An appropriate choice of data structures will often greatly reduce complexity - both algorithmic and conceptual - compared to a poor choice, i.e. a poor choice can create a lot of unnecessary work. Complexity is not a 'conserved' quantity. Information is conserved, however (though if you delete information, the representation of information as heat is quite unrecoverable ;). $\endgroup$ – dmbarbour Oct 3 '14 at 21:41
  • $\begingroup$ I meant if "complexity of algorithm + complexity of data structure" is conserved, regardless of your choice of the data structure for a given problem? $\endgroup$ – Tim Oct 3 '14 at 21:48
  • $\begingroup$ Complexity isn't conserved. Proof: Watch a Rube Goldberg machine (youtube.com/watch?v=mTjJzF_Oaow&list=RDuF3nV0r87v8). Or program in Whirl for a few hours (bigzaphod.github.io/Whirl). I'm not sure why you think it should be. Conceptually, there may be some minimum optimal complexity. But we can certainly do worse than that if we try. And, very often, we do worse than the optimum without trying. $\endgroup$ – dmbarbour Oct 3 '14 at 21:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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