Riyad Parvez riyadparvez

riyadparvez / InversionCounter.cs

Created July 2, 2013 18:03

Inversion counter version in C#. This is optimized version. It uses merge sort to count number of inversions. Hence it's O(n*logn)

	public class InversionCounter
	{
	List<int> array;

	public InversionCounter (IEnumerable<int> arr)
	{
	array = arr.ToList();
	}

	private Tuple<int, List<int>> Merge(List<int> leftList, List<int> rightList)

riyadparvez / ReservoirSampler.cs

Created July 2, 2013 18:29

It selects k random element from n elements in C# using reservoir sampling algorithm. See http://propersubset.com/2010/04/choosing-random-elements.html

	public static IList<T> ReservoirSampler<T>(IEnumerable<T> arr, int k)
	{
	if(arr == null)
	{
	throw new ArgumentNullException();
	}
	if( k <= 1 \|\| k > arr.Count())
	{
	throw new ArgumentOutOfRangeException();
	}

riyadparvez / SieveOfEratosthenes.cs

Created July 2, 2013 18:44

Finds all the prime numbers up to n using Sieve of Eratosthenes in C#. See http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

	public static IList<int> SieveOfEratosthenes(int n)
	{
	if(n < 2)
	{
	throw new ArgumentOutOfRangeException();
	}

	var arr = Enumerable.Repeat(true, n+1).ToArray();

	for (int i = 2; i <= n; i++)

riyadparvez / UglyNumberNaive.cs

Created July 2, 2013 19:21

A number is ugly number in C# if it's product of 2, 3 and 5. This function finds nth ugly number using brute force approach.

	public static int PowerRemainder(int n, int divisor)
	{
	while((n%divisor) == 0)
	{
	n /= divisor;
	}
	return n;
	}

	public static int UglyNumberNth(int n)

riyadparvez / FindMissingNumber.cs

Created July 2, 2013 19:47

Find one missing number from an unsorted array of consecutive numbers in C#.

	public static int FindMissingNumber(IEnumerable<int> numbers)
	{
	int expectedSum = (numbers.Count() + 1)*(numbers.Count()+2)/2;
	int realSum = 0;

	foreach (var number in numbers)
	{
	realSum += number;
	}

riyadparvez / DepthLimitedSearch.cs

Last active December 19, 2015 06:59

An implementation of depth limited search in C#. Rudimentary node class is implemented.

	public class Tree<K, V>
	where K : class, IComparable<K>
	where V : class
	{
	private Node<K, V> root;

	/// <summary>
	/// Searches tree using BFS but the depth of the search
	/// is limited
	/// </summary>

riyadparvez / IterativeDeepeningSearch.cs

Last active March 15, 2019 08:11

Iterative deepening search in C#. A rudimentary implementation of node is also provided

	public class Tree<K, V>
	where K : class, IComparable<K>
	where V : class
	{
	private Node<K, V> root;

	/// <summary>
	/// Searches tree using BFS but the depth of the search
	/// is limited. Level of root is 0.
	/// </summary>

riyadparvez / BFS.cs

Last active March 19, 2024 20:44

An implementation of breadth first search or BFS in C#.

	public class Tree<K, V>
	where K : class, IComparable<K>
	where V : class
	{
	private Node<K, V> root;

	public V BFS(K key)
	{
	Queue<Node<K, V>> queue = new Queue<Node<K, V>>();

riyadparvez / DFS.cs

Last active August 28, 2019 00:30

Implementation of depth first search or DFS in C#.

	public class Tree<K, V>
	where K : class, IComparable<K>
	where V : class
	{
	private Node<K, V> root;

	public V DFS(K key)
	{
	Stack<Node<K, V>> stack = new Stack<Node<K, V>>();

riyadparvez / PowerBySquaring.cs

Created July 3, 2013 03:09

Implementation of exponentiation by squaring in C#. See http://en.wikipedia.org/wiki/Exponentiation_by_squaring

	public static int PowerBySquaring(int baseNumber, int exponent)
	{
	int result = 1;
	while (exponent != 0)
	{
	if ((exponent & 1)==1)
	{
	result *= baseNumber;
	}
	exponent >>= 1;