lectures/algorithm

created : 2020-04-07T11:37:08+00:00
modified : 2020-06-27T06:23:12+00:00
lecture algorithm
  1. Basic Sorting algorithm The most common uses of sorted sequences are

Sorting algorithm

The output of any sorting algorithm must satisfy two conditions

Classification of Sorting Algorithms

Common sorting algorithms

  1. Divide and Conqure # Divide and Conquer Paradigm

Advantages of Divide and Conquer

Implementation issues

General Method

Divide and Conquer Strategy

  1. divide the problem instance into two or more smaller instances of the same problem, solve the smaller instances recursively, and assemble the solutions to form a solution of the original instance.
  2. The recursion stop when an instance is reached which too small to divide
  3. When dividing the instance, one can either use whatever division comes most easily to hand or invest time in making the division carefully so that the assembly is simplified.

  4. Effective Sorting Algorithm

    Review : Divide and conquer algorithms

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/2f9a9793-fbfb-4a26-bc7a-91a20bfb9a6d/Untitled.png

Overview of Merge Sort

Because we’re using divide-and-conquer to sort, we need to decide what our subproblems are going to look like. The full problem is to sort an entire array. Let’s say that a subproblem is to sort a subarray.

In particular, we’ll think of a subproblem as sorting the subarray string at index p and going through index r. It will be convenient to have a notation for a subarray, so let’s say that array[p..r] denotes this subarray of array.

Note that we’re using “tow-dot” notation just to describe the algorithm, rater than a particular implementation of the algorithm in code. In terms of our notation, for an array of n elements, we can say that the original problem is to sort array[0..n-1].

Here’s how merge sort uses divide-and-conquer:

  1. Divide by finding the number q of the position midway between p and r. Do this step the same way we found the midpoint in binary search: add p and r, divide by 2, and round down.
  2. Conquer by recursively sorting the subarrays in each of the two subproblems created by the dividing step. That is, recursively sort the subarray array[p..q] and recursively sort the subarray array[q+1..r].
  3. Combine by merging the two sorted subarrays back into the single sorted subarray array[p..r].

Linear-time merging

THe remaining piece of merge sort is the merge function, which merges two adjacent sorted subarrays, array[p..q] and array[q+1..r] into a single sorted subarray in array[p..r]. We’ll see how to construct this function so that it’s as efficient as possible.

Analysis of merge sort

  1. The divide step takes constant time, regardless of the subarray size. After all, the divide step just computes the midpoint q of the indices p and r. Recall that in big-Theta notation, we indicate constant time by Theta(1).
  2. The conquer step, where we recursively sort two subarrays of approximately n/2 elements each, takes some amount of time, but we’ll account for that time when we consider the subproblems.
  3. The combine step merges a total of n elements, taking Theta(n) time.

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/e67189ca-6023-4485-8062-7b5e04603a16/Untitled.png

Overview of Quick Sort

  1. Divide by choosing any element in the subarray array[p..r]. Call this element the pivot. Rearrange the elements in array[p..r] so that all elements in array[p..r] that are less than or equal to the pivot are to its left and all elements that are greater than the pivot are to its right. We call this procedure partitioning . At this point, it doesn’t matter what order the elements to the left of the pivot are in relation to each other, and the same holds for the elements to the right of the pivot. We just care that each element is somewhere on the correct side of the pivot.
  2. Conquer by recursively sorting the subarrays array[p..q-1] (all elements to the left of the pivot, which must be less than or equal to the pivot) and array[q+1..r]. All elements to the right of the pivot, which must be greater than the pivot.
  3. Combine by doing nothing. Once the conquer step recursively sorts, we are done.

Linear-time Partitioning

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/9d8abd3b-d978-4a02-9a48-a0537fc9798c/Untitled.png

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/6ac383e4-4ea5-4f12-acb7-e0e9454e68a4/Untitled.png

  1. Greedy Algorithm

    Introduction

Knapsack Problem

Optimal Storage on Tapes

Job Sequencing with Deadlines

Optimal Merge Patterns

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/5ce9d81e-671d-45bb-b9ad-15413a88913b/Untitled.png

Huffman Codes

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/4d71a77e-cc28-4ad4-9206-d87e14b813a0/Untitled.png

13.Graph Algorithm

Basic definitions

Representation of Graphs

Adjacency Matrix

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/bb8cd6cc-1c54-4d2e-8786-5121420ff916/Untitled.png

Adjacency List

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/0e6d4092-6a9e-46d7-a369-8fa655795c15/Untitled.png

Path, Cycles, and Subgraphs

Trees and Spanning Trees

Minimum Spanning Trees (MST)

MST related algorithms

Dijkstra’s Algorithm

Algorithm : Complexity

Kruskal’s Algorithm

Complexity

Prim’s Algorithm

  1. Initialize a tree with a single vertex, chosen arbitarily from the graph.
  2. Grow the tree by one edge: of the edges that connect the tree to vertices not yet in the tree, find the minimum-weight edge, and transfer it to the tree
  3. repeat step 2 until all vertices are in the tree

Complexity

  1. Dynamic algorithm
    • Dynamic Programming (Bellman equation)

Introduction

All pairs shortest paths

Floyd’s algorithm (Time complexity : O(n^3))

function floyd(cost, a, n){
  for i := 1 to n do {
    for j := 1 to n do {
      a[i,j] := cost[i,j];
    }
  }
  for k := 1 to n do {
    for i := 1 to n do {
      for j := 1 to n do {
        a[i,j] := min(a[i,j], a[i,k] + a[k,j]);
      }
    }
  }
}

Multi-Stage Graphs (Time complexity : Theta(|V| + |E|))

function fgraph(G, k, n, p){
  cost[n] : = 0;
  for j := n-1 to 1 step -1 do {
    let r be a vertex such that (j,r) is an edge of G and c[j,r] + cost[r] is minimum;
    cost[j] := c[j,r] + cost[r];
    d[j] := r;
  }
  p[1] := 1;
  p[k] := n;
  for j:= 2 to k-1 do {
    p[j] := d[p[j-1]];
  }
}

The Knapsack Problem

  1. Basic Traversal Methods

    Definitions

Traversal

Techniques for Traversal of a Binary Tree

Inorder Traversal

Algorithm inorder(Node t)
{
  if t!=0, then
  {
    inorder(t->left_child);
    visit(t);
    inorder(t->right_child);
  }
}

Preorder Traversal

Algorithm preorder(Node t)
{
  if t!=0, then
	{
    visit(t);
    preorder(t->left_child);
    preorder(t->right_child);
  }
}

Postoder Traversal

Algorithm postorder(Node t)
{
  if t!=0, then
	{
    postorder(t->left_child);
    postorder(t->right_child);
	  visit(t);
  }
}

Non-Recursive Binary Tree Traversal Algorithms

Non-Recursive Inorder Traversal

Algorithm inorder(){
			stack[1] = 0;
			vertex = root;
top:	while(vertex!=0){
				push the vertex into the stack, vertex = leftchild(vertex)
			}
			pop the elemenet from the stack and make it as vertex
			while(vertex!=0){
				print the vertex node
				if(rightchild(vertex)!=0){
					vertex = rightchild(vertex)
					goto top
				}
			pop the element from the stack and made it as vertex
			}
}

Non-Recursive Preorder Traversal

Algorithm Preorder(){
			stack[1] = 0;
			vertex = root;
			while(vertex!=0){
				print the vertex node
				if(rightchild(vertex)!=0){
					push the right child of vertex into the stack
				if(leftchild(vertex) !=0){
					vertex := leftson(vertex)
			  else
					pop the element from the stack and made it as vertex
			}
}

Non-Recursive Postorder Traversal

Algorithm postorder(){
			stack[1] = 0;
			vertex = root;
top:	while(vertex!=0){
				push vertex onto stack
				if(rightchild(vertex)!=0)
					push -vertex onto stack
				vertex := leftson(vertex)
			}
			pop from stack and make it as vertex
			while(vertex > 0){
				print the vertex node, pop from stack and make it as vertex
			}
			if(vertex < 0){
				vertex := -vertex
				goto top
			}
}