Please enable JavaScript.

Coggle requires JavaScript to display documents.

Sets and Dictionaries, Hashing - Coggle Diagram

- - - - The first considers only set that are subsets of some large set U, called the universal set. If set U has n elements, then any subset S of U can be represented by a bit string of size n, called a bit vector, where the ith element is 1 if and only if the ith element of U is included in set S. Example: U = {1,2,3,4,5,6,7,8,9}, S = {2,3,5,7}. S can be represented as 011010100.
        
        It makes implement the standard set operations very fast, but at the expense of potentially using a large amount of storage.
      - The second and more common way to represent a set for computing purposes is to use the list structure to indicate the set's elements. This option is feasible only for finite sets. need. Note, however, the two principal points of
        distinction between sets and lists.
        
        First, a set cannot contain identical elements; a list can. This requirement for uniqueness is sometimes circumvented by the introduction of a multiset, or bag, an *unordered collection of item that are not necessarily distinct.
        
        Second, a set is an unordered collection of items.
      - A list, defined as an ordered collection of items, is exactly the opposite. It is not important for many applications. It is also worth mentioning that if a set is represented by a list, depending on the application at hand, it might be worth maintaining the lit in a sorted order.
- - - - The ways a dictionary can be implemented range from an unsophisticated use of arrays to much more sophisticated techniques such as hashing and balanced search trees.
- - - - Dynamic Programming: An algorithm design technique that solves overlapping subproblems and records their solutions in a table, leading to an efficient overall solution.
        
        Space-Time Trade-Off: The relationship between time and space in algorithm design, which doesn't always involve competition but can also be optimized together to improve algorithm efficiency.