Sets and sequences: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 32: Line 32:
== Stacks and queues ==
== Stacks and queues ==


# A '''stack''' (a.k.a. '''LIFO queue''', LIFO = last-in-first-out) is a dynamic ordered sequence such that new elements may only be inserted at the beginning (the '''top'''), and no element except for the very ''first'' one may be accessed and removed.
# A '''stack''' (a.k.a. '''LIFO queue''', LIFO = last-in-first-out) is a dynamic ordered sequence such that new elements may only be inserted at the beginning (the '''top'''), and no element except for the very first one may be accessed and removed.
# A '''queue''' (a.k.a. '''FIFO queue''', FIFO = first-in-first-out) is a dynamic ordered sequence such that new elements may only be inserted at the beginning, and no element except for the very ''last'' one may be accessed and removed.
# A '''queue''' (a.k.a. '''FIFO queue''', FIFO = first-in-first-out) is a dynamic ordered sequence such that new elements may only be inserted at the end, and no element except for the very first one may be accessed and removed.


==Maps==
==Maps==

Revision as of 12:14, 31 October 2014

Sets and multisets

  1. In a set, each element occurs at most once, that is, no duplications of elements within a set.
  2. In contrast, in a multiset, an element may occur more than once. The multiplicity of an element in a multiset is the number of its occurrences in that multiset.

Remark: In computer science, as opposed to math, sets and multisets are usually dynamic, that is, elements may be inserted and removed.

Maximal and minimal sets

Let [math]\displaystyle{ \mathcal{S} }[/math] be a set of (multi)sets.

  1. A set [math]\displaystyle{ S\in\mathcal{S} }[/math] is inclusion-minimal (resp., inclusion-maximal) if [math]\displaystyle{ S'\subsetneq S }[/math] (resp., [math]\displaystyle{ S'\supsetneq S }[/math]) for no [math]\displaystyle{ S'\in\mathcal{S}\setminus\{S\} }[/math].
  2. A set [math]\displaystyle{ S\in\mathcal{S} }[/math] is cardinality-minimal (resp., cardinality-maximal) if [math]\displaystyle{ |S'|\lt [S[ }[/math] (resp., [math]\displaystyle{ |S'|\gt |S| }[/math]) for no [math]\displaystyle{ S'\in\mathcal{S}\setminus\{S\} }[/math].

Remark: Typically, [math]\displaystyle{ \mathcal{S} }[/math] is given as all subsets of a ground set that fulfill a certain property.

Ordered and sorted sequences

An ordered sequence (or sequence, for short) is given by

  1. a number [math]\displaystyle{ n \in \N_{0} }[/math], its length,
  2. some component type [math]\displaystyle{ C }[/math], and
  3. a mapping [math]\displaystyle{ \pi : \{1,...,n\} \rightarrow C }[/math].

We say that [math]\displaystyle{ 1,...,n }[/math] are the positions in the sequence (a.k.a. the indexes). The element [math]\displaystyle{ \pi (i) }[/math] of sequence [math]\displaystyle{ S }[/math] at position [math]\displaystyle{ i }[/math] is denoted by [math]\displaystyle{ S[i] }[/math].

Consider a comparison [math]\displaystyle{ c }[/math] on [math]\displaystyle{ C }[/math], as introduced above. Then a sequence [math]\displaystyle{ S }[/math] of length [math]\displaystyle{ n }[/math] is sorted with respect to [math]\displaystyle{ c }[/math], if [math]\displaystyle{ S[i] \le S[i+1] }[/math] for all [math]\displaystyle{ i \in \{1,...,n-1\} }[/math].

Remarks:

  1. Note that the first position is [math]\displaystyle{ 1 }[/math], not [math]\displaystyle{ 0 }[/math], as opposed to array indexes in many popular programming languages such as C, C++, and Java.
  2. Like sets and multisets, sequences are dynamic.

Stacks and queues

  1. A stack (a.k.a. LIFO queue, LIFO = last-in-first-out) is a dynamic ordered sequence such that new elements may only be inserted at the beginning (the top), and no element except for the very first one may be accessed and removed.
  2. A queue (a.k.a. FIFO queue, FIFO = first-in-first-out) is a dynamic ordered sequence such that new elements may only be inserted at the end, and no element except for the very first one may be accessed and removed.

Maps

A map is given by

  1. a number [math]\displaystyle{ n \in \N_{0} }[/math], its size
  2. a key type [math]\displaystyle{ \mathcal{K} }[/math] and a value type [math]\displaystyle{ \mathcal{V} }[/math],
  3. a finite subset [math]\displaystyle{ K \subseteq \mathcal{K} }[/math], the map's keys, and
  4. a mapping [math]\displaystyle{ K \rightarrow \mathcal{V} }[/math], which assigns a value to each key in the map.

Remark

A sequence may also be a map, namely if its component type is [math]\displaystyle{ \mathcal{K} \times \mathcal{V} }[/math] and each value of [math]\displaystyle{ \mathcal{K} }[/math] occurs at most once.

Like sets, multisets and sequences, maps are dynamic.