Showing posts with label Algorithms. Show all posts
Showing posts with label Algorithms. Show all posts

How to create Fibonacci series using Linq

In this post I am going to show you how to generate fiboancci number series using Linq.

What is Fibonacci series : The Fibonacci Sequence is the series of numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... The next number is found by adding up the two numbers before it.

``` public static IEnumerable<int> Fib(int n)
{
List<int> fibs = new List<int>();
Enumerable.Range(0, n)
.ToList()
.ForEach(f => fibs.Add((f <= 1 ? 1 : fibs[f - 2] + fibs[f - 1])));
return fibs;

}```

Kth Largest Element in Array

```public class KthElement
{
public static int kthElement(int[] arr, int k)
{
int n = arr.Length;
int lo = 0;
int hi = n - 1;
if (lo == hi)
return arr[lo];
while (true)
{
int pivotIndex = Partition(arr, lo, hi);
int rank = pivotIndex - lo + 1;
if (rank == k)
return arr[pivotIndex];
else if (k < rank)
return kthElement(arr, k);
else
return kthElement(arr, k - rank);
}

}
private static int Partition(int[] arr, int left, int right)
{
int pivot = arr[left];
int i = left + 1;
int j = right;
while (i < j)
{
while (arr[i] <pivot) i++;
while (arr[j] >= pivot) j--;
if (i < j)
Swap(arr, i, j);
}
Swap(arr, left, j);
return j;
}
private static void Swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}```

Levenshtein distance (Edit distance)

The edit distance of two strings, s1 and s2, is defined as the minimum number of point mutations required to change s1 into s2, where a point mutation is one of:

1. change a letter,
2. insert a letter, or
3. delete a letter

```class EditDistanceAlgo
{
static int[,] m;
public static char diagCh;
public static int LevenshteinDistance(string s, string t)
{
int[,] d = new int[s.Length + 1, t.Length + 1];
for (int i = 0; i <= s.Length; i++)
d[i, 0] = i;
for (int j = 0; j <= t.Length; j++)
d[0, j] = j;
for (int j = 1; j <= t.Length; j++)
for (int i = 1; i <= s.Length; i++)
if (s[i - 1] == t[j - 1])
d[i, j] = d[i - 1, j - 1];  //no operation
else
d[i, j] = Math.Min(Math.Min(
d[i - 1, j] + 1,    //a deletion
d[i, j - 1] + 1),   //an insertion
d[i - 1, j - 1] + 1 //a substitution
);
TraceBack("", "", "", d, s.Length, t.Length, s, t);
return d[s.Length, t.Length];
}
public static void TraceBack(string row1, string row2, string row3, int[,] mm, int i, int j, string s1, string s2)
{
string result = "";
if (i > 0 && j > 0)
{
var diag = mm[i - 1, j - 1];
diagCh = '|';
if (s1[i - 1] != s2[j - 1])
{
diag++; diagCh = ' ';
}
if (mm[i, j] == diag)
TraceBack(s1[i - 1] + row1, diagCh + row2, s2[j - 1] + row3, mm, i - 1, j - 1, s1, s2);    // change or match
else if (mm[i, j] == mm[i - 1, j] - 0 + 1) // delete
TraceBack(s1[i - 1] + row1, ' ' + row2, '-' + row3, mm, i - 1, j, s1, s2);
else
TraceBack('-' + row1, ' ' + row2, s2[j - 1] + row3, mm, i, j - 1, s1, s2);      // insertion
}
else if (i > 0)
TraceBack(s1[i - 1] + row1, ' ' + row2, '-' + row3, mm, i - 1, j, s1, s2);
else if (j > 0)
TraceBack('-' + row1, ' ' + row2, s2[j - 1] + row3, mm, i, j - 1, s1, s2);
else // i==0 and j==0
result += row1 + '\n' + row2 + '\n' + row3 + '\n';
Console.WriteLine(result);
}//traceBack
}```

Longest increasing subsequence problem (Dynamic Programming)

`The input consists of two sequences ~x = x1, . . . , xn and ~y = y1, . . . , ym. The goal is to ﬁnd a longest common subsequence of ~x and ~y, that is a sequence z1, . . . , zk that is a subsequence both of ~x and of ~y. Note that a subsequence is not always substring: if ~z is a subsequence of ~x, and zi = xj and zi+1 = xj 0, then the only requirement is that j 0 > j, whereas for a substring it would have to be j 0 = j + 1.For example, let ~x and ~y be two DNA strings ~x = T GACT A and ~y = GT GCAT G; n = 6 and m = 7. Then one common subsequence would be GT A. However, it is not the longest possible common subsequence: there are common subsequences T GCA, T GAT and T GCT of length 4`
```
```
```
.csharpcode, .csharpcode pre
{
font-size: small;
color: black;
font-family: Consolas, "Courier New", Courier, Monospace;
background-color: #ffffff;
/*white-space: pre;*/
}

.csharpcode pre { margin: 0em; }

.csharpcode .rem { color: #008000; }

.csharpcode .kwrd { color: #0000ff; }

.csharpcode .str { color: #a31515; }

.csharpcode .op { color: #0000c0; }

.csharpcode .preproc { color: #cc6633; }

.csharpcode .asp { background-color: #ffff00; }

.csharpcode .html { color: #800000; }

.csharpcode .attr { color: #ff0000; }

.csharpcode .alt
{
background-color: #f4f4f4;
width: 100%;
margin: 0em;
}

.csharpcode .lnum { color: #606060; }
```

0/1 Knapsack problem

Description

```using System;

public class Knapsack
{
static int nbObjects = 8;
static int[] weight = { 2, 3, 5, 2, 4, 6, 3, 1 };
static int[] utility = { 5, 8, 14, 6, 13, 17, 10, 4 };
static int weightmax = 12;
static int[,] array;
static void Display()
{
int i, u, w;
u = 0;
w = weightmax;
for (i = nbObjects - 1; i >= 1; i--)
{
if (array[i, w] != array[i - 1, w])
{
Console.Write((i + 1) + " ");
w = w - weight[i];
u = u + utility[i];
}
}

if (array[0, w] != 0)
{
Console.WriteLine("1");
w = w - weight[0];
u = u + utility[0];
}
}
public static void SolveDP()
{
array = new int[nbObjects, weightmax + 1];
// initialize the first row
for (int j = 0; j <= weightmax; j++)
if (j < weight[0])
{
array[0, j] = 0;

}
else
{
array[0, j] = utility[0];

}
// for all other rows
for (int i = 1; i < nbObjects; i++)
{
for (int j = 0; j <= weightmax; j++)
{
if (j - weight[i] < 0)
array[i, j] = array[i - 1, j];
else
array[i, j] = Math.Max(array[i - 1, j], array[i - 1, j - weight[i]] + utility[i]);
}
}
Display();
}

}```

Generate permutations of a given string in c#

In this post I will show you how to generate the permutations of a given string in c#.

Pseudocode:
If you have no more characters left to rearrange, print current permutation

```for (every possible choice among the characters left to rearrange)
{
Make a choice and add that character to the permutation so far
Use recursion to rearrange the remaining letters
}
```
```using System.Collections.Generic;
using System;
using System.Generic;
using System.Linq;
using System.Text;
namespace Permutation
{
class Program
{
static void Main(string[] args)
{
Permutation("abc");
}
/// <summary>
/// Wrapper function
/// </summary>
/// <param name="input"></param>
public static void Permutation(string input)
{
RecPermutation("", input);
}
private static void RecPermutation(string soFar, string input)
{
if (string.IsNullOrEmpty(input))
{
Console.WriteLine(soFar);
return;
}
else
{
for (int i = 0; i < input.Length; i++)
{

string remaining = input.Substring(0, i) + input.Substring(i + 1);
RecPermutation(soFar + input[i], remaining);
}
}
}
}
}
```
Recursion Tree
```|-- RecPermute'', 'abc'
|   |-- RecPermute'a', 'bc'
|   |   |-- RecPermute'ab', 'c'
|   |   |   |-- RecPermute'abc', ''
abc
|   |   |   |--  return None
|   |   |--  return None
|   |   |-- RecPermute'ac', 'b'
|   |   |   |-- RecPermute'acb', ''
acb
|   |   |   |--  return None
|   |   |--  return None
|   |--  return None
|   |-- RecPermute'b', 'ac'
|   |   |-- RecPermute'ba', 'c'
|   |   |   |-- RecPermute'bac', ''
bac
|   |   |   |--  return None
|   |   |--  return None
|   |   |-- RecPermute'bc', 'a'
|   |   |   |-- RecPermute'bca', ''
bca
|   |   |   |--  return None
|   |   |--  return None
|   |--  return None
|   |-- RecPermute'c', 'ab'
|   |   |-- RecPermute'ca', 'b'
|   |   |   |-- RecPermute'cab', ''
cab
|   |   |   |--  return None
|   |   |--  return None
|   |   |-- RecPermute'cb', 'a'
|   |   |   |-- RecPermute'cba', ''
cba
|   |   |   |--  return None
|   |   |--  return None
|   |--  return None
|--  return None```

Recursive merge sort implementation in c#

```Merge Sort
```

```using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MergeSort
{
public class Program
{
private int[] originalArray;
private int[] resultArray;

public void MergeSort(int[] array)
{
this.originalArray = array;
this.resultArray = new int[array.Length];
Merge(0, array.Length - 1);
}

private void Merge(int low, int high)
{
if (low < high)
{
int middle = (low + high) / 2;
Merge(low, middle);
Merge(middle + 1, high);
Sort(low, middle, high);
}
}
/// <summary>
/// Returns a new sorted list containing the same elements as L
/// </summary>
/// <param name="low"></param>
/// <param name="middle"></param>
/// <param name="high"></param>
private void Sort(int low, int middle, int high)
{

for (int index = low; index <= high; index++)
{
resultArray[index] = originalArray[index];
}
int i = low;
int j = middle + 1;
int k = low;
while (i <= middle && j <= high)
{
if (resultArray[i] <= resultArray[j])
{
originalArray[k] = resultArray[i];
i++;
}
else
{
originalArray[k] = resultArray[j];
j++;
}
k++;
}
while (i <= middle)
{
originalArray[k] = resultArray[i];
k++;
i++;
}
}
public static void Main(String[] args)
{
int[] arr = { -4, 7, -9, 11, 8, 22, 98, 5 };

Program example = new Program();
example.MergeSort(arr);
}
}

}
```

Quicksort implementation in c#

```Quicksort is a very efficient sorting algorithm invented by C.A.R. Hoare. It has two phases:
the partition phase and
the sort phase.

Quicksort a good example of the divide and conquer strategy for solving problems.  In quicksort, we divide the array of items to be sorted into two partitions and then call the quicksort procedure recursively to sort the two partitions, ie we divide the problem into two smaller ones and conquer by solving the smaller ones.

```

How to implement selection sort in c#

In this post I will show you how to implement selection sort in c#.Before going to implement selection sort let's describe how selection sort works.

1. go through the list one item at a time.
2. keep track of the smallest item found.
3. Find the smallest item out and add it to a list of sorted items.
4. Repeat until all the items have been sorted

```class Program
{
// Selection Sort Algorithm
public static void SelectionSort(int[] arr)
{
int i, j;
int min;
for (i = 0; i < arr.Length - 1; i++)
{
min = i;
for (j = i + 1; j < arr.Length; j++)
{
if (arr[j] < arr[min])
{
min = j;
}
}
Swap(arr, i, min);
}
}
private static void Swap(int[] arr, int i, int min)
{

int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
static void Main(string[] args)
{

int[] arr = new int[] { 1, 2, 0, -3, 32 };
SelectionSort(arr);

}

}```

Boyer-Moore search algorithm implementation in c#

Boyer-Mooreis a string searching algorithm. It avoids checking most positions in the source string. The implementation here uses constant characters.
```public class Search
{
{
for (int i = 0; i < 256; i++)
{
}
int last = needle.Length - 1;
for (int i = 0; i < last; i++)
{
}
}

public static int boyerMooreHorsepool(String pattern, String text)
{
char[] needle = pattern.ToCharArray();
char[] haystack = text.ToCharArray();

if (needle.Length > haystack.Length)
{
return -1;
}
int offset = 0;
int scan = 0;
int last = needle.Length - 1;
int maxoffset = haystack.Length - needle.Length;
while (offset <= maxoffset)
{
for (scan = last; (needle[scan] == haystack[scan + offset]); scan--)
{
if (scan == 0)
{ //Match found
return offset;
}
}
}
return -1;
}

}```

How to implement bubble sort in c#

In this post,I am going to show you how to implement bubble sorting in c#.
What is Bubble Sort
Bubble sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order.
Implementation

```using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace SortingDemo
{
public class BubbleSort
{
public void BubbleSort()
{
//Initialize array data
int[] data = { 5, 3, 6, 1, 8, 7, 2, 4 };

for (int outerIndex = 0; outerIndex < data.Length; outerIndex++)
{
for (int innerIndex = 0; innerIndex < data.Length-1; innerIndex++)
{

if (data[innerIndex] > data[innerIndex+1])
{
//swap data.
Swap(data, innerIndex);
}
}
}
}
private static void Swap(int[] data, int innerIndex)
{
int temp = data[innerIndex + 1];
data[innerIndex + 1] = data[innerIndex];
data[innerIndex] = temp;
}
}
}
```