Algorithm analysis

algorithm and program

algorithm:described by human languages,flow charts,programming lanuage,pseudocode
program:written in some programming language(==can be meaningless==)

what to analyze

running time?

==run time==:machine and compiler-dependent
==Time & space complexities==:machine and compiler-independent

Assumption(usually not true)

sequentially executed
each instruction is simple,tasks exactlyone time unit
integer size is fixed & infinite memory
$T_{avg}(N)\ T_{worst}(N)$ --the average and worst time complexity , as function of input size N

Asympotic Notation

$\begin{aligned} \begin{cases} O:upper\ bound(worst\ case)\\ \Omega:lower\ bound(best\ case)\\ \Theta:upper=lower\\ o:T(N)=O(p(N))\ and\ T(N)\neq\Theta(p(N)) \end{cases} \end{aligned}$

rules

Function	Name
c	Constant
$\log N$	Logarithmic
$\log^2N$	Los-squared
$N$	Linear
$N\log N$	Log linear
$N^2$	Quadratic
$N^3$	Cubic
$2^N$	Exponential
$N!$	Factorial

recursions

long int Fib(int N)  /*T(N)*/
{
	if(N <= 1)      /*O(1)*/
		return 1;
	else
		return Fib(N - 1) + Fib(N - 2);
		       /*T(N - 1)*//*T(N - 2)*/
}

$\begin{align} T(N) =T(N-1)+&T(N-2)+2\geq Fib(N)\\ \bigg(\frac 32\bigg)^N\leq Fib&(N)\leq\bigg(\frac 53\bigg)^N \end{align}$

Compare the algorithm

example

find the largest list

$T(N)=O(N^3)$

int MaxSubsequenceSum (const int A[], int N)
{
    int ThisSum, MaxSum, i, j, k;
    MaxSum = 0; /* 初始化最大和 */
    for(i = 0; i < N; i++) /* 从 A[i] 开始 */
        for(j = i; j < N; j++) { /* 到 A[j] 结束 */
            ThisSum = 0;
            for(k = i; k <= j; k++)
                ThisSum += A[k]; /* 计算从 A[i] 到 A[j] 的和 */
            if (ThisSum > MaxSum)
                MaxSum = ThisSum; /* 更新最大和 */
        } /* 结束内层 for-j 和 for-i */
    return MaxSum;
}

$T(N)=O(N^2)$

int MaxSubsequenceSum ( const int A[], int N )
{
    int ThisSum, MaxSum, i, j, k;
    MaxSum = 0; /* initialize the maximum sum */
    for(i = 0; i < N; i++) { /* start from A[i] */
        ThisSum = 0;
        for(j = i; j < N; j++) { /* end at A[j] */
            ThisSum += A[j]; /* sum from A[i] to A[j] */
            if ( ThisSum > MaxSum )
                MaxSum = ThisSum; /* update max sum */
        } /* end for-j */
    } /* end for-i */
    return MaxSum;
}

Divide and Conquer
recursion time complexity

$\begin{aligned} T(N)=&2T(\frac N{2})+cN\\ T(\frac N{2})=&2T(\frac N{2^2})+cN\\ T(\frac N{2^2})=&2T(\frac N{2^3})+cN\\ &\vdots\\ T(1)=&2T(\frac N{2^k})+cN\\ \\ \\ T(N)=&2^kO(1)+cN\log N\\ =&O(N\log N) \end{aligned}$

On-line Algorithm $T(N)=O(N)$

int MaxSubsequenceSum( const int A[], int N )
{
    int ThisSum, MaxSum, j;
    ThisSum = MaxSum = 0;
    for (j = 0; j < N; j++) {
        ThisSum += A[j];
        if ( ThisSum > MaxSum )
            MaxSum = ThisSum;
        else if ( ThisSum < 0 )
            ThisSum = 0;
    } /* end for-j */
    return MaxSum;
}

Logarithm in the running time

find the median

Binary Search

int BinarySearch ( const ElementType A[], ElementType X, int N )
{
    int Low, Mid, High;
    Low = 0; High = N - 1;
    while (Low <= High) {
        Mid = (Low + High) / 2;
        if ( A[ Mid ] < X )
            Low = Mid + 1;
        else
            if ( A[ Mid ] > X )
                High = Mid - 1;
            else
                return Mid; /* Found */
    } /* end while */
    return NotFound; /* NotFound is defined as -1 */
}

$T_{worst}(N)=O(\log N)$

Euclid’s algorithm（欧几里得算法）

Find the GCD(Greatest Common Divisor)

function gcd(a, b):
    while b ≠ 0:
        temp := b
        b := a mod b
        a := temp
    return a

$T(N)=O(\log{\min\{a,b\}})$

Exponentiation（快速幂算法)

To compute $a^b \mod m$ efficiently

function mod_pow(a, b, m):
    result := 1
    a := a mod m
    while b > 0:
        if b mod 2 == 1:
            result := result * a
        a := a * a 
        b := b / 2
    return result

$T(N)=O(\log b)$

Check your analysis

$when\ T(N)=O(f(N)),check\ if\lim_{N\rightarrow +\infty}\frac{T(N)}{f(N)}=constant$

Lists,Stacks, and Queues

Abstract Data Type(ADT)

A date type that is organized in such a way that the specification on the objects and specification of the operations on the objects are separated from the representation of the objects and the implementaion on the operations.

The List ADT

Operations

Find the length
Print
Making an empty
Find the k-th
Insert
Delete
Find next
Find previous

implementations

array
- maxsize has to be estimated
- find_kth takes O(1) time
- insetion and deletion takes O（N） time, involve a lot of data movements

1	array[i]=item

linked list
- find kth takes O(n) time
- insertion and deletion takes O(N) time to find , and O(1) time to change
- cursor implementation of linked list
  - requires customized malloc
Doubly linked circular lists

Multilist

Cursor implementation of linked list

Use the linked list to serve as malloc and free function.

The Stack ADT

fundamental data arrange
Last-In-First-Out -> reverse order

operation

IsEmpty
CreatStack
DisposeStack
MakeEmpty
Push
Top
Pop

a pop on a empty stack is errror in the stack ADT

Implements

linked list

array

struct stack{
	int capacity;
	int topofstack;
	Elementtype *array
}

Application

balancing symbols
check if parenthesis , brackets , braces are balanced

Algorithm {
    Make an empty stack S;
    while (read in a character c) {
        if (c is an opening symbol)
            Push(c, S);
        else if (c is a closing symbol) {
            if (S is empty) { ERROR; exit; }
            else { /* stack is okay */
                if (Top(S) doesn’t match c) { ERROR, exit; }
                else Pop(S);
            } /* end else-stack is okay */
        } /* end else-if-closing symbol */
    } /* end while-loop */
    if (S is not empty) ERROR;
}

postfix conversion
Infix to Postfix Conversion

the order of operands is the same
operators with higher precedence appear before those with lower precedence

function calls

void PrintList (List L) {
    if ( L != NULL ) {
        PrintElement ( L->Element );
        PrintList( L->next );
    }
} /* a bad use of recursion */

void PrintList (List L) {
top: if ( L != NULL ) {
    PrintElement ( L->Element );
    L = L->next;
    goto top; /* do NOT do this */
}
} /* compiler removes recursion */

The Queue ADT

limited resources
First-In-First-Out

operation

isempty
creatqueue
disposequeue
makeempty
enqueue
front
dequeue

Implementation

Array

struct QueueRecord {
    int Capacity; /* max size of queue */
    int Front;    /* the front pointer */
    int Rear;     /* the rear pointer */
    int Size;     /* Optional - the current size of queue */
    ElementType *Array; /* array for queue elements */
};

Circular Queue

Tree

A tree is a collection of nodes. The collection can be empty;otherwise, a tree consists of

a distinguished node r,called theroot

zero or more nonempty (sub)trees $T_1,\cdots,T_k$ ,each of whose roots are connected by a directed edge from r

degree of a node:number of subtrees of the node
degree of a tree:the max degree of the nodes of the tree
parent:a node that has subtrees
children:the roots of the subtrees of a parent
siblings:children of the same parent
leaf:a node with degree 0
path from $n_1$ to $n_k$ :a (unique) sequence of nodes $n_1,n_2,\cdots,n_k$ such that $n_i$ is the parent of $n_{i+1}$
length of path:number of edges on the path
depth of $n_i$ :length of the unique path from the root to $n_i$
height of $n_i$ :length of the longest path from $n_i$ to a leaf
height(depth) of a tree:height(root)=depth(deepest leaf)
ancestors of a node:all the nodes along the path from the node up to the root
descendants of a node:all the nodes in its subtrees

Implementation

List representation

The size of each node depends on the number of branches.

FirstChild-NextSibling Representation

Binary Tree

A binary tree is a tree in which no node can have more than two children

Expression tree

Tree traversals

Preorder Traversal
void preorder (tree_ptr tree) {
    if (tree) {
        visit (tree);
        for(each child C of tree)
            preorder (C);
    }
}

Postorder Traversal
void postorder (tree_ptr tree) {
    if (tree) {
        for(each child C of tree)
            postorder (C);
        visit (tree);
    }
}

Levelorder Traversal
void levelorder (tree_ptr tree) {
    enqueue (tree);
    while(queue is not empty){
        visit ( T = dequeue ());
        for(each child C of T)
            enqueue (C);
    }
}

Inorder Traversal
void inorder (tree_ptr tree) {
    if (tree) {
        inorder (tree->Left);
        visit (tree->Element);
        inorder (tree->Right);
    }
}

An interative program of inorder traversal

void iter_inorder(tree_ptr tree){
	Stack S = CreatStack(MAX_SIZE);
	for(;;){
		for(;tree;tree = tree->left)
			Push(tree,S);
		tree = Top(S);
		Pop(S);
		if(!tree)
			break;
		visit(tree->Element);
		tree = tree->Right;
	}
}

Skewed binary tree

Complete binary tress

Properties

The max number of nodes on level $i$ is $2^{i-1}$
The max number of nodes in a binary tree of depth $k$ is $2^{k-1}$
For any none empty binary tree $n_0 =n_2+1$

$\begin{aligned} n&=n_0+n_1+n_2\\ n&=B+1=n_1+2n_2+1 \end{aligned}$

Binary Search Trees

A binary search tree is a binary tree.It may be empty.If it is not empty,it satisfies the following properties:

Every node has a key which is an integer ,and the keys are distinct.

The keys in a nonempty left subtree must be smaller than the key in the root of the subtree.

The keys in a nonempty right subtree must be larger than the key in the root of the subtree.

The left and right subtree are also binary search trees

ADT

Operations

MakeEmpty
Find

Position Find(ElementType X, SearchTree T) {
    if (T == NULL)
        return NULL; /* not found in an empty tree */
    if (X < T->Element) /* if smaller than root */
        return Find(X, T->Left); /* search left subtree */
    else if (X > T->Element) /* if larger than root */
        return Find(X, T->Right); /* search right subtree */
    else /* if X == root */
        return T; /* found */
}

$T(N)=O(d)\ where\ d\ is\ the\ depth\ of\ X$

Position Iter_Find(ElementType X, SearchTree T) {
    /* iterative version of Find */
    while (T) {
        if (X == T->Element)
            return T; /* found */
        if (X < T->Element)
            T = T->Left; /* move down along left path */
        else
            T = T->Right; /* move down along right path */
    } /* end while-loop */
    return NULL; /* not found */
}

FindMin

Position FindMin(SearchTree T) {
    if (T == NULL)
        return NULL; /* not found in an empty tree */
    else if (T->Left == NULL)
        return T; /* found left most */
    else
        return FindMin(T->Left); /* keep moving to left */
}

$T(N)=O(d)$

FindMax

Position FindMax(SearchTree T) {
    if (T != NULL)
        while (T->Right != NULL)
            T = T->Right; /* keep moving to find right most */
    return T; /* return NULL or the right most */
}

$T(N)=O(d)$

Insert
1. check if the new number is already in the tree
2. the last key when search for the key number will be the parent of the new node

SearchTree Insert(ElementType X, SearchTree T) {
    if (T == NULL) {
        /* Create and return a one-node tree */
        T = malloc(sizeof(struct TreeNode));
        if (T == NULL)
            FatalError("Out of space!!!");
        else {
            T->Element = X;
            T->Left = T->Right = NULL;
        }
    } /* End creating a one-node tree */
    else /* If there is a tree */
        if (X < T->Element)
            T->Left = Insert(X, T->Left);
        else if (X > T->Element)
            T->Right = Insert(X, T->Right);
        /* Else X is in the tree already; we'll do nothing */
    return T; /* Do not forget this line!! */
}

$T(N)=O(d)$

Delete
1. Delete a leaf node:reset its parent link to NULL
2. Delete a degree 1 node:replace the node by its single child
3. Delete a degree 2 node:
  1. replace the node by the largest one in its left subtree or the smallest one in its right subtree.
  2. Delete the replacing node from the subtree

SearchTree Delete(ElementType X, SearchTree T) {
    Position TmpCell;
    if (T == NULL)
        Error("Element not found");
    else if (X < T->Element) /* Go left */
        T->Left = Delete(X, T->Left);
    else if (X > T->Element) /* Go right */
        T->Right = Delete(X, T->Right);
    else /* Found element to be deleted */
        if (T->Left && T->Right) {
            /* Two children */
            /* Replace with smallest in right subtree */
            TmpCell = FindMin(T->Right);
            T->Element = TmpCell->Element;
            T->Right = Delete(T->Element, T->Right);
        } /* End if */
        else {
            /* One or zero child */
            TmpCell = T;
            if (T->Left == NULL) /* Also handles 0 child */
                T = T->Right;
            else if (T->Right == NULL)
                T = T->Left;
            free(TmpCell);
        } /* End else 1 or 0 child */
    return T;
}

$T(N)=O(d)$

lazy deletion
add a flag field to each node ,to mark if a node is active or is deleted

Retrieve

Average-Case Analysis

Place $n$ elements in a binary search tree.How high can this tree be?

The height depends on the order of insertion

Priority Queues(Heaps)

Operations

Initialize
Insert
DeleteMin
FindMin

Simple Implementation

Binary Heap

A binary tree with $n$ nodes and height $h$ is complete iff its nodes correspond to the node number from 1 to $n$ in the perfect binary tree of height $h$

$h=\lfloor\log N\rfloor$

Array representation

Initialize

PriorityQueue Initialize(int MaxElements) {
    PriorityQueue H;
    if (MaxElements < MinPQSize)
        return Error("Priority queue size is too small");
    H = malloc(sizeof(struct HeapStruct));
    if (H == NULL)
        return FatalError("Out of space!!!");
    /* Allocate the array plus one extra for sentinel */
    H->Elements = malloc((MaxElements + 1) * sizeof(ElementType));
    if (H->Elements == NULL)
        return FatalError("Out of space!!!");
    H->Capacity = MaxElements;
    H->Size = 0;
    H->Elements[0] = MinData; /* set the sentinel */
    return H;
}

Heap Order Property

A min tree is a tree in which the key value in each node is no larger than the key values in its children.
A min heap is a complete binary tree that is also a min tree

Insertion

The only possible position for a new node

void Insert(ElementType X, PriorityQueue H) {
    int i;
    if (IsFull(H)) {
        Error("Priority queue is full");
        return;
    }
    for (i = ++H->Size; H->Elements[i / 2] > X; i /= 2)
        H->Elements[i] = H->Elements[i / 2];
    H->Elements[i] = X;
}

$T(N)=O(\log N)$

DeleteMin

ElementType DeleteMin(PriorityQueue H) {
    int i, Child;
    ElementType MinElement, LastElement;
    if (IsEmpty(H)) {
        Error("Priority queue is empty");
        return H->Elements[0];
    }
    MinElement = H->Elements[1]; /* save the min element */
    LastElement = H->Elements[H->Size--]; /* take last and reset size */
    for (i = 1; i * 2 <= H->Size; i = Child) { /* Find smaller child */
        Child = i * 2;
        if (Child != H->Size && H->Elements[Child + 1] < H->Elements[Child])
            Child++;
        if (LastElement > H->Elements[Child]) /* Percolate one level */
            H->Elements[i] = H->Elements[Child];
        else
            break; /* find the proper position */
    }
    H->Elements[i] = LastElement;
    return MinElement;
}

$T(N)=O(\log N)$

Other Heap Operations

Finding any key except min will have to take a linear scan through the entire heap
DecreaseKey
IncreaseKey
Delete
BuildHeap

Application

Given a list of N elements and a integer K.Find the kth largest element.

d-Heaps

DeleteMin will cost $O(d\log_d N)$

Disjoint set ADT

Equivalence Relations

A relation R is defined on a set S if for every pair of elements $(a,b),a,b\in S,a\ R\ b$ is either true or false.If $a\ R\ b$ is true ,then we say that a is related to b

A relation,~, over a set,S,is said to be a equivalence relation over S iff it is symmetric(对称性),reflexive(反身性) and transitive(传递性) over S

Two member x and y of a set S are said to be in the same equivalence class iff $x\sim y$

/* Step 1: Read the relations in */
Initialize N disjoint sets;
while (read in a ~ b) {
    if (! (Find(a) == Find(b))) {
        Union the two sets;
    }
} /* end-while */

/* Step 2: Decide if a ~ b */
while (read in a and b) {
    if (Find(a) == Find(b)) {
        output(true);
    } else {
        output(false);
    }
}

Operation

Union
1. Implementation1:
2. Implementation2:

/* Union by setting the parent pointer of one root to the other root */
void SetUnion(DisjSet S, SetType Rt1, SetType Rt2) {
    S[Rt2] = Rt1;
}

Find
1. Implementation1:
2. Implementation2:

/* Find operation */
SetType Find(ElementType X, DisjSet S) {
    for (; S[X] > 0; X = S[X]);
    return X;
}

Algorithm using union-find operations

/* Algorithm using union-find operations */
{
    Initialize Si = { i } for i = 1, ..., 12;
    for (k = 1; k <= 9; k++) {
        /* for each pair i ~ j */
        if (Find(i) != Find(j)) {
            SetUnion(Find(i), Find(j));
        }
    }
}

Smart Union Algorithm

Union-by-size

always change the smaller tree

$h\leq\lfloor\log_2 N\rfloor+1$

N Union and M Find operations takes $O(N+M\log_2N)$

Union-by-Height

always change the shallow tree

Path Compression（Union-by-rank）

SetType Find(ElementType X, DisjSet S) {
    if (S[X] <= 0)
        return X;
    else
        return S[X] = Find(S[X], S);
}

/* Another version of Find with path compression */
SetType Find(ElementType X, DisjSet S) {
    ElementType root, trail, lead;
    for (root = X; S[root] > 0; root = S[root]); /* find the root */
    for (trail = X; trail != root; trail = lead) {
        lead = S[trail];
        S[trail] = root;
    } /* collapsing */
    return root;
}

Worst Case For

$k_1M\alpha(M,N)\leq T(M,N)\leq k_2M\alpha(M,N)$

Ackermann’s Function

$A(i,j)=\begin{cases} 2^j&i=1\ and\ j\geq1\\ A(i-1,2)&i\geq2\ and\ j=1\\ A(i-1,A(i,j-1))&i\geq2\ and\ j\geq2 \end{cases}$

$\alpha(M,N)=\min\{i\geq1|A(i,\lfloor M/N\rfloor)>\log N\}\leq O(log^*N)\leq 4$

Graph Algorithms Notes

1. Definitions

Graph $G = (V, E)$ where:

$V$ : finite, non-empty set of vertices
$E$ : finite set of edges
Undirected Graph:
Edge $(v_i, v_j) = (v_j, v_i)$
No self-loops or multi-edges (simple graph)
Directed Graph (Digraph):
Edge $\langle v_i, v_j \rangle \neq \langle v_j, v_i \rangle$
$v_i$ : tail, $v_j$ : head
Subgraph:
$G' \subseteq G$ if $V(G') \subseteq V(G)$ and $E(G') \subseteq E(G)$
Path:
A sequence of vertices with consecutive edges
Length: number of edges
Simple Path: no repeated vertices
Cycle: simple path with the same start and end vertex
Connected Graph (Undirected)
Every pair of vertices has a path
Component:
A maximal connected subgraph
Tree:
A connected, acyclic graph
Strongly Connected Graph (Directed):
For all $v_i, v_j \in V(G)$ , there exists a path $v_i \to v_j$ and $v_j \to v_i$
Degree:
$\deg(v)$ : total number of incident edges
For digraphs: $\deg_{in}(v)$ and $\deg_{out}(v)$
DAG:
Directed Acyclic Graph

2. Graph Representations

a. Adjacency Matrix

Let $adj_mat[n][n]$ :

$adj_mat[i][j] = 1$ if edge exists from $v_i$ to $v_j$
For undirected graphs: symmetric matrix

Time Complexity:

$O(n^2)$ for traversal

Space Optimization:

Store only half for undirected: 1D array index $= i(i - 1)/2 + j$

b. Adjacency List

Each vertex stores a list of its adjacent vertices:

Space: $O(n + 2e)$
Time for edge traversal: $O(n + e)$

c. Inverse Adjacency List (for directed graphs)

Needed to compute in-degree

d. Multilist

Combine forward and backward pointers in one structure
Efficient for edge marking and bidirectional operations

e. Weighted Graphs

Matrix: $adj_mat[i][j] = \text{weight}$
List: add weight field to node

3. Topological Sort

Predecessor:

$i$ is predecessor of $j$ if there exists a path $i \to j$
Immediate predecessor: edge $\langle i, j \rangle \in E(G)$

Partial Order:

Transitive and Irreflexive relation

AOV Network:

Activity-on-Vertex graph
DAG where vertices are activities and edges represent precedence

Definition

A topological order is a linear ordering of the vertices such that for every directed edge $\langle i, j \rangle$ , vertex $i$ comes before $j$ in the ordering.

Algorithm 1: Basic

void Topsort(Graph G) {
    int Counter;
    Vertex V, W;
    for (Counter = 0; Counter < NumVertex; Counter++) {
        V = FindNewVertexOfDegreeZero();
        if (V == NotAVertex) {
            Error("Graph has a cycle"); break;
        }
        TopNum[V] = Counter;
        for (each W adjacent from V)
            Indegree[W]--;
    }
}

Time Complexity: $O(|V|^2)$

Algorithm 2: Using Queue (Improved)

void Topsort(Graph G) {
    Queue Q = CreateQueue(NumVertex);
    int Counter = 0;
    Vertex V, W;
    for (each vertex V)
        if (Indegree[V] == 0)
            Enqueue(V, Q);
    while (!IsEmpty(Q)) {
        V = Dequeue(Q);
        TopNum[V] = ++Counter;
        for (each W adjacent from V)
            if (--Indegree[W] == 0)
                Enqueue(W, Q);
    }
    if (Counter != NumVertex)
        Error("Graph has a cycle");
    DisposeQueue(Q);
}