0
$\begingroup$

While reading the classic text Introduction to Algorithms by Cormen et. al. I came across the following claim:

Sets are as fundamental to computer science as they are to mathematics. Whereas mathematical sets are unchanging, the sets manipulated by algorithms can grow, shrink, or otherwise change over time. We call such sets dynamic.

I felt a bit odd after reading the statement that "set" in Mathematics and in CS are different from the mutable point of view. Now in Mathematics what we deal with are theoretical aspect of things and as such "set" is a theoretical concept and so it is in Theoretical CS. If it is immutable in mathematics then so it is in CS. Mathematics and Theoretical CS are interlinked. So given a graph algorithm which say finds the minimum shortest path between a pair of vertices , we can't say whether it belongs to Mathematics or CS.

Often in algorithms we write statements as :

$$S = S \cup \{a\} \quad \text{view $1$}$$

Which seems to sort of change our set $S$, but if we look it in this way:

$$S'= S \cup \{a\} \quad \text{view $2$}$$

$$S=S'$$

So in the second situation we are not modifying our actual set $S$ we are forming a new set $S'$ with $S$ augmented with $a$ and then after that we are making the variable $S$ refer to $S'$.

What I feel is that the concept of the set being mutable or immutable is solely dependent on the data-structure of representation of the abstract concept of "sets" and since in data-structure the two steps in view $2$ are combined and implemented, so they are called dynamic sets.

In short I feel that Dynamic Sets are data-structure implementation of sets and not the abstract sets.

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ In mathematics everything is immutable. $\endgroup$
    – Yuval Filmus
    Commented Jun 23, 2020 at 21:45
  • 2
    $\begingroup$ I'm not familiar with the book--maybe that the authors are just being sloppy--but in teaching, there can be tradeoffs between what helps students learn and and what is precisely correct. That's true in the classroom, and even moreso in a book, where you can't be sure who your audience is. Maybe the authors just wanted a simple way to introduce mutable "sets". (In class, sometimes I add a little "footnote", saying something like, "When you take the advanced course, you'll learn the truth, but this is good enough for now." I don't teach CS, but precision does matter in my discipline.) $\endgroup$
    – Mars
    Commented Jun 24, 2020 at 0:26

1 Answer 1

Reset to default
2
$\begingroup$

Set are at a higher level of abstraction than algorithms. You can certainly analyze algorithms at that level of abstraction but that's not the usual level of abstraction for discussing algorithms, instead you'd refer to data structures such as stacks, vectors, lists, linked lists etc.

Sets are instead used in formal modeling contexts (Z,Coq,Agda,F-Star) to describe specifications but not algorithms.

They're also used do describe algorithms in functional programming (see e.g. Purely Functional Data Structures by Chris Okasaki ) but that is not very common in literature as most algorithms are described in terms of ephemeral data structures.

To answer your question, sets are the same both in Mathematics and CS, they're immutable. Dynamic sets is a data structure loosely related to sets.

The author is not saying that sets are different in CS than in Mathematics. He's saying that the data structures, as commonly described in algorithms are mutable. CS is much more than algorithms and data structures.

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.

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