[RA] Ch20 Introduction To Algorithms and Data Structures

Reading Assignment: All of Programming Chapter 20 Introduction To Algorithms and Data Structures

Key to efficient algorithm:

• Correct data structure.
• Abstraction.

Big-O notiation

The formalization we use is Big-O notation, which considers the number of steps our algorithm must execute as a function of its input size, and considers the asymptotic behavior-what happens for large input sizes only-of that function, and ignores constant factors-it considers $f(N)=N$ and $f(N) = 3N$ to be the same.

What we do care about here is how the number of steps scales as the input size grows large. From this perspective, we care primarily about this asymptotic behavior for two reasons.

1. Computers are really fast.
2. If one functions grows faster than another by more than a constant factor, then for sufficiently large inputs, the faster growing function will exceed the more slowly growing function-and the gap between them will continue to increase as the input grows.

Definition

As big-O is a mathematical formalism, it has a mathematical definition:

$f(x)$ is $O(g(x)) \Leftrightarrow \exists { x }{ 0 },c,\forall x>{ x }{ 0 },f(x) \le c*g(x)$

Practical Big-O for Algorithms

• $O(1)$: constant time
• $O(lg^*N)$: log-star time
• $O(lg(N))$: logarithmic time
• $O(N)$: linear time
• $O(N \cdot lg(N))$: linerarithmic time
• $O(N^2)$: quadratic time
• $O(N^3)$: cubic time
• $O(N^4)$: quartic time
• $O(N^c)$: polynomial time
• $O(2^N)$: exponential time
• $O(N!)$: factorial time

Typical, Worst, or Amortized

One way that we might analyze the algorithm is to consider the typical case-what happens for most inputs. Another way that we might analyze the algorithm is to consider what the worst case is.

Space

We can use Big-Oh notation to describe space requirements as well as time requirements.

Limitations

Constant factors do matter. Consider these two algorithm:

• A executes $10,000,000N$ steps
• B executes $2N^2$ steps

Abstract Data Types

In the context of data structures, the abstraction arises from separating the Abstract Data Type from its concrete implementation. An Abstract Data Type defines the interface, it specifies what the data structure does, but says nothing about how it accomplishes those tasks.

Queues

A queue is a FIFO sequence of items. The primary operations of a queue are enqueue and dequeue.

Uses of Queues

Frequently, we find that we may wish to process one piece of data, and in processing that, it generates several next piece of data. We wish to immediately process all of those pieces of data before processing any of the “next” data that they generate.

ADT Definition

template<typename T>
class Queue{
 public:
  void enqueue(const T& item);
  T dequeue();
  T & peek();
  const T & peek() const;
  int numberOfItems const.
};

You can read all about the queue class in C++’s STL online.

An Array or Vector Implementation

Deque

Stacks

A stack is a Last-In-First-Out sequence of items.

Uses of Stacks

• Call stack
• Parsing
• Undo/redo.

ADT Definition

template<typename T>
class Queue{
 public:
  void push(const T& item);
  T pop();
  T & peek();
  const T & peek() const;
  int numberOfItems const.
};

An Array or Vector Implementation

Sets

A set is simply a collection of elements, much like those found in mathematics. By set in computer can not be infinite.

Uses of Sets

ADT Definition

template<typename T>
class Set{
 public:
  void add(const T& item);
  bool contains(const T& item) const;
  bool numItems() const;
  void remove(const T & item);
  Set<T> intersect(const Set<T>&s)const;
  Set<T> unionSets(const Set<T> &s)const;
};

An Array or Vector Implementation

Maps

A map tracks a mapping from keys to values.

Uses of Maps

social networking site: user id to the value.

ADT Definition

template<typename K, typename V>
class Map{
 public:
  void add(const K& key, const V & value);
  const V & lookup(const K& key) const;
  V & lookup(const K & key);
  bool numItems() const;
  void remove(const K & key);
};

An Array or Vector Implementation

The approach that C++’s STL takes is to provide two different ways to find an element, with two different behaviors. The []operator is overloaded to take a key, and return a reference to the corresponding value. If the key is not in the map already, the [] operator will add the key, with a default-constructed value, that is V() to the map, and return a reference to the newly constructed value. Note there is no const overloading, as the operator modifies the map if the key is not found.

ADTs and Abstract Classes