Photo by Markus Winkler on Unsplash

Contents:
  1. Travelling Salesman Problem
  2. Huffman Code
  3. Graph Coloring
  4. Knuth-Morris-Pratt String Matching
  5. Strongly Connected Components

Travelling Salesman Problem

Introduction
Salesman wants to sell. He goes to different location. Distance between one location and another are different. He wants to go with the shortest path possible. Help him.

Dynamic Programming
In order to solve this problem using DP, we use the following formula:

Given that:
  • p(i,L) distance from starting node to node i through the path L
  • c(j,i) distance from node j to node i
  • L-{j} distance of path L subtracted by node j

  Example 1.1 - Travelling Salesman Problem: DP
Determine the shortest path possible for the salesman if he starts from A:
Example 1.1 - Travelling Salesman Problem: DP

Solution:


















In conclusion, the shortest path possible that the salesman can take is the path {A, C, B, D, A} with cost: 44.

  Example 1.2 - Travelling Salesman Problem: DP
Given the following cost matrix:


  1. Draw the TSP graph.
  2. Determine the shortest path possible for the salesman, if he starts from A.
Solution:
  1. Draw the TSP graph:
    Example 1.2 - Travelling Salesman Problem: DP
  2. Determine the shortest path possible for the salesman, if he starts from A.




    ...




    In conclusion, the shortest path possible that the salesman can take is the path {A, D, C, E, B, A} with cost: 45.

Branch and Bound
The best solution in all possible solutions in each step will be chosen. It will also backtrack when the possible solutions in a step are not optimal.

  Example 1.3 - Travelling Salesman Problem: Branch and Bound
Given the following cost matrix:


Determine the shortest path possible for the salesman, if he starts from A.

Solution:


In conclusion, the shortest path possible that the salesman can take is the path {A, D, C, E, B, A} with cost: 45.


Huffman Code

Introduction
It is a method to compress data using a Binary Tree. First, make a list of frequencies of each character that appear in the string that will be compressed (ascendingly sorted). The top two characters will be removed and become the leaf nodes, and its parent node will be the sum of its frequencies, and then inserted back to the list. The process is repeated until all nodes are removed from the list/table.

  Example 2.1 - Huffman Code
Create Frequency Table, Huffman Tree, and Huffman Code to compress the string DESIGN AND ANALYSIS OF ALGORITHMS

Solution:
  • Frequency Table:
    A S I N O G L D M H F E R T Y
    4 4 4 3 3 2 2 2 2 1 1 1 1 1 1 1

  • Huffman Tree:
    Example 2.1 - Huffman Code

  • Huffman Code:
    A S I N O G L D M H F E R T Y
    000 001 010 1100 1101 1011 1000 1001 0110 0111 11100 11101 10100 10101 11110 11111


    D 0110
    E 10100
    S 001
    I 1100
    G 1000
    N 1101
    010
    A 000
    N 1101
    D 0110
    010
    A 000
    N 1101
    A 000
    L 1001
    Y 11111
    S 001
    I 1100
    S 001
    010
    O 1011
    F 11101
    010
    A 000
    L 1001
    G 1000
    O 1011
    R 10101
    I 1100
    T 11110
    H 11100
    M 0111
    S 001


    In total, the memory used is 67 bits.


Graph Coloring

Vertice Coloring
Given a graph, color each vertex so that adjacent vertices have different color. In order to solve this problem, the Welsh & Powell algorithm can be used. First, list all nodes based on its degree (descendingly sorted). Assign a color from the top-most node to the bottom-most node on the list. If a node is adjacent to an already used color, assign a new color.

  Example 3.1 - Vertice Coloring
Use Welsh & Powell algorithm to color the graph below!

Example 3.1 - Vertice Coloring

Solution:
  • Sorted Vertex:
    H 11
    I 6
    A 5
    G 5
    C 4
    E 4
    J 4
    K 4
    L 4
    N 4
    B 3
    D 3
    F 3
    M 3

  • Colored Graph:
    Example 3.1 - Vertice Coloring Solution

    In conclusion, the chromatic number is 4 because the number of colors used to color the entire graph is 4.


Knuth-Morris-Pratt String Matching

Introduction
Given a string S with length n and a string K with length m, determine whether string K exists in S or not. The naive solution is not recommended to use because comparing each character of string K when a character in string K matches with string S takes O(nm) complexity in the worst case.

  Example 4.1 - KMP
Use KMP algorithm to determine whether the string ABABABAB exists in the string AABAABABABAABABAABABABABA!

Solution:
  • Failure Function:
    i f(i)
    0 0
    1 0
    2 1
    3 2
    4 3
    5 4
    6 5
    7 6

  • Simulation:
    Example 4.1 - KMP Solution


Strongly Connected Components

Introduction
Given a graph, determine the connected components of the graph. A connected component maximal subset of the vertices such that each vertice pair can be reached from another.

  Example 5.1 - SCC Tarjan Algorithm
Use Tarjan algorithm to determine the SCCs of the following graph!
Example 5.1 - SCC

Solution: