Skip to content

Commit 4a75f11

Browse files
thuva4thuva4
authored
Merge branch 'master' into patch-1
2 parents 2af520c + abdf961 commit 4a75f11

File tree

11 files changed

+274
-16
lines changed

11 files changed

+274
-16
lines changed

‎CONTRIBUTING.md‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -153,4 +153,6 @@ Unfortunately, sometimes the bug can be only reproduced in your project or in yo
153153
- [Santhosh Kumar](https://github.com/santhoshsamy29)
154154
- [Judar Lima](https://github.com/judarlima)
155155
- [Jhalaa](https://github.com/jhalaa)
156-
- [Leandro Nunes - lnfnunes](https://github.com/lnfnunes
156+
- [langlk](https://github.com/langlk)
157+
- [Anat Portnoy](https://github.com/Anat-Port)
158+
- [Leandro Nunes - lnfnunes](https://github.com/lnfnunes)

‎ConnectedComponentLabeling/C/component_label.cpp‎

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
#include <iostream>
2+
#include <bits/stdc++.h>
3+
using namespace std;
4+
5+
vector <int> v[100001]; // to store the original graph
6+
bool vis[100001]={false}; // to keep track of visited vertices
7+
vector <int> components[100001]; // to label and store different connected components
8+
int label[100001];
9+
10+
void dfs(int s, int subgraph_no)
11+
{
12+
vis[s] = true;
13+
components[subgraph_no].push_back(s);
14+
label[s]=subgraph_no; // assigning the component id or label to the vertex
15+
for(int i = 0;i < v[s].size();++i)
16+
{
17+
if(!vis[v[s][i]])
18+
dfs(v[s][i],subgraph_no);
19+
}
20+
}
21+
22+
int main()
23+
{
24+
int n,m,a,b,sub=1; // sub labels the different connected components, initially we consider it to be 1
25+
cin>>n>>m; // n is the number of vertices and m is the number of edges
26+
while(m--)
27+
{
28+
cin>>a>>b;
29+
v[a].push_back(b);
30+
v[b].push_back(a);
31+
}
32+
for(int i=1;i<=n;i++) // to store different connected compoents using dfs
33+
{
34+
if(!vis[i])
35+
{
36+
dfs(i,sub);
37+
sub++;
38+
}
39+
}
40+
return 0;
41+
}

‎DynamicProgramming/Java/Knapsack.java‎

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
import java.util.Arrays;
2+
3+
/**
4+
* The knapsack problem or rucksack problem. Given a set of items, each with a weight and a value,
5+
* determine the number of each item to include in a collection so that the total weight is less than
6+
* or equal to a given limit and the total value is as large as possible.
7+
*
8+
* @author Atom
9+
* @see <a href="https://en.wikipedia.org/wiki/Knapsack_problem">Knapsack problem</a>
10+
*/
11+
public class Knapsack {
12+
13+
public static void maxValue(int maxCapacity, int[] weights, int[] values, int[][] v) {
14+
for (int i = 1; i < maxCapacity + 1; i++) {
15+
for (int j = 1; j < weights.length + 1; j++) {
16+
if (weights[j - 1] > i) {
17+
v[j][i] = v[j -1][i];
18+
} else {
19+
v[j][i] = Math.max(v[j - 1][i], v[j - 1][i - weights[j - 1]] + values[j - 1]);
20+
}
21+
}
22+
}
23+
}
24+
25+
public static boolean[] includedItems(int[] weights, int[][] v) {
26+
boolean[] items = new boolean[weights.length];
27+
int w = v[0].length - 1;
28+
for (int i = weights.length; i > 0; i--) {
29+
if (v[i][w] == v[i - 1][w]) { items[i - 1] = false; }
30+
else {
31+
items[i - 1] = true;
32+
w -= weights[i - 1];
33+
}
34+
}
35+
return items;
36+
}
37+
38+
public static void main(String[] args) {
39+
final int capacity = 8;
40+
final int[] values = {2, 5, 10, 14, 15};
41+
final int[] weights = {1, 3, 4, 5, 7};
42+
final int[][] v = new int[weights.length + 1][capacity + 1];
43+
System.out.println("Knapsack max weight = " + capacity);
44+
System.out.println("Number of distinct items = " + values.length);
45+
System.out.println("Values = " + Arrays.toString(values));
46+
System.out.println("Weights = " + Arrays.toString(weights));
47+
System.out.println();
48+
49+
maxValue(capacity, weights, values, v);
50+
final int b = v[weights.length][capacity];
51+
System.out.println("v:");
52+
for (int i = 0; i < weights.length + 1; i++) { System.out.println(Arrays.toString(v[i])); }
53+
System.out.println();
54+
System.out.println("Maximum value = " + b);
55+
System.out.println("Items included: " + Arrays.toString(includedItems(weights, v)));
56+
}
57+
58+
}

‎FisherYatesShuffle/Ruby/fisher_yates.rb‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
# Shuffles an array with Fisher-Yates algorithm
2+
def fisher_yates(arr)
3+
rng = Random.new()
4+
i = arr.length - 1
5+
while i >= 0
6+
j = rng.rand(i + 1)
7+
temp = arr[i]
8+
arr[i] = arr[j]
9+
arr[j] = temp
10+
i -= 1
11+
end
12+
return arr
13+
end

‎HammingDistance/Ruby/hamming_distance.rb‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
# take two binary strings and returns the Hamming Distance between them
2+
def hamming_distance(string1, string2)
3+
if string1.length != string2.length
4+
return "Strings must be the same length."
5+
else
6+
total = 0
7+
for i in 0...string1.length
8+
if string1[i] != string2[i]
9+
total += 1
10+
end
11+
end
12+
return total
13+
end
14+
end

‎LinearSearch/Rust/linear_search.rs‎

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
/*
2+
* Implementation of Linear Search in Rust
3+
*/
4+
5+
fn linear_search(list: Vec<i32>, target: i32) -> Option<usize> {
6+
for i in 0..list.len() {
7+
if list[i] == target {
8+
return Some(i)
9+
}
10+
}
11+
return None;
12+
}
13+
14+
fn main() {
15+
let mut mylist = Vec::new();
16+
mylist.push(5);
17+
mylist.push(4);
18+
mylist.push(8);
19+
mylist.push(9);
20+
mylist.push(20);
21+
mylist.push(14);
22+
mylist.push(3);
23+
mylist.push(1);
24+
mylist.push(2);
25+
mylist.push(2);
26+
27+
let target = 20;
28+
29+
match linear_search(mylist, target) {
30+
Some(r) => { print!("{}\n", r); },
31+
None => { print!("None found\n"); }
32+
};
33+
}

‎README.md‎

Lines changed: 18 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -6,12 +6,13 @@ This repository contains examples of various algorithms which were written on di
66

77

88
Language| Java | Python | Rust | C | C++ | JavaScript | Go | C# | Ruby | Swift | Racket
9-
--- | --- | --- | --- |--- |--- |--- |--- |--- |--- |--- |--- |
9+
---|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
1010
A*Search | | :+1: | | | :+1: | | | |
1111
BellmanFord | :+1: | | | | :+1: | | | |
1212
BestFirstSearch | :+1: | | | | | | | | :+1: |
1313
BinaryGCD | :+1: | | | | | | | | |
1414
BinarySearch | :+1: | :+1: | | :+1: | :+1: | :+1: | :+1: | | :+1: | :+1:
15+
Binary Search Modified | | | | :+1: | | | | |
1516
Bitap Algorithm | | :+1: | | | :+1: | | | |
1617
BreadthFirstSearch | :+1: | :+1: | | :+1: | | | | |
1718
Borwein's Algorithm | :+1: | | | | :+1: | | | | ||
@@ -20,48 +21,50 @@ Conjugate Gradient | | | | | :+1: | | | | ||
2021
CountingSort | :+1: | :+1: | | | :+1: | | | | |
2122
DepthFirstSearch | :+1: | :+1: | | | :+1: | :+1: | | | |
2223
Dijkstra's | :+1: | :+1: | | | :+1: | | :+1: | | |
24+
Dynamic programming | :+1: | | | | | | | | |
2325
Doomsday | :+1: | :+1: | | | :+1: | :+1: | | | :+1: | :+1: | :+1:
2426
EditDistance | | :+1: | | | :+1: | | | |
2527
Edmonds-Karp | :+1: | | | | | | | |
2628
ElevatorAlgorithm | :+1: | | | | | | | |
2729
Fast Fourier Transform | | | | | :+1: | | | |
2830
Fibonacci | :+1: | :+1: | | :+1: | :+1: | :+1: | | :+1: | :+1: | :+1: | :+1:
29-
FisherYatesShuffle | :+1: | | | | :+1: | :+1: | | :+1: |
31+
FisherYatesShuffle | :+1: | | | | :+1: | :+1: | | :+1: | :+1: |
3032
FloodFill Algorithm | :+1: | | | | | | | |
3133
Floyd'sAlgorithm | :+1: | :+1: | | | :+1: | | | |
32-
GreatestCommonDivisor | :+1: |:+1:| :+1: | :+1: | :+1: | | | |
33-
HammingDistance | :+1: | :+1: | | :+1: | | :+1: | :+1: | |
34+
35+
Greatest Common Divisor | :+1: |:+1:| :+1: | :+1: | :+1: | | | |
36+
Hamming Distance | :+1: | :+1: | | :+1: | | :+1: | :+1: | | :+1:
3437
HeapSort | :+1: | :+1: | | | :+1: | :+1: | :+1: | | :+1:
35-
HistogramEqualization | :+1: | | | | | | | |
38+
Histogram equalization | :+1: | | | | | | | |
3639
InsertionSort | :+1: | :+1: | :+1: | :+1: | :+1: | :+1: | :+1: | :+1: | :+1:
3740
Inverse Fast Fourier Transform | | | | | :+1: | | | |
3841
Johnson algorithm | :+1: | :+1: | | | :+1: | | | |
3942
Kadane's algorithm | :+1: | :+1: | | :+1: | :+1: | :+1: | :+1: | |
4043
Knuth Morris Prath Algorithm | :+1: | :+1: | | | :+1: | | | |
41-
LinearSearch | :+1: | :+1: | | :+1:| :+1: | :+1: | :+1: | | | :+1: |
42-
Longest-Common-Subsequence | :+1: | :+1: | | :+1: | :+1: | | | | :+1:
43-
Longest-Increasing-Subsequence | :+1: | :+1: | | | :+1: | | | |
44+
LinearSearch | :+1: | :+1: | :+1: | :+1:| :+1: | :+1: | :+1: | | | :+1: |
45+
Longest common subsequence | :+1: | :+1: | | :+1: | :+1: | | | | :+1:
46+
Longest increasing subsequence | :+1: | :+1: | | | :+1: | | | |
4447
LongestPath | | | | | :+1: | | | |
4548
MergeSort | :+1: | :+1: | | :+1: | :+1: | :+1: | :+1: | | | :+1:
46-
MiniMaxWithABPruning | :+1: | | | | | | | |
47-
Modified_Binary_Search | | | | :+1: | | | | |
49+
MiniMax with alpha–beta pruning | :+1: | | | | | | | |
4850
Pearson Hashing | :+1: | | | | | | | |
4951
Postman Sort | | | | :+1: | | | | |
5052
Quick Sort | :+1: | :+1: | :+1: | | | :+1: | :+1: | :+1: | :+1: | :+1: |
5153
Quick Select | :+1: | :+1: | | :+1: | | | :+1: | |
5254
Uniform-cost search | :+1: | | | | | :+1: | :+1: | |
5355
RadixSort | :+1: | :+1: | | | :+1: | | | |
5456
RobinCarp | :+1: | | | | | | | |
55-
SelectionSort | :+1: | :+1: | | :+1: | :+1: | :+1: | :+1: | :+1: | :+1:
57+
SelectionSort | :+1: | :+1: | :+1: | :+1: | :+1: | :+1: | :+1: | :+1: | :+1:
5658
ShellSort | :+1: | :+1: | | | :+1: | | | |
57-
SieveofEratosthenes | :+1: | :+1: | | | :+1: | :+1: | :+1: | |
59+
Sieve of Eratosthenes | :+1: | :+1: | | | :+1: | :+1: | :+1: | |
5860
UnaryCoding | :+1: | :+1: | | | | :+1: | | |
5961
VEGAS Algorithm | | | | | :+1: | | | | ||
6062
TernarySearch | :+1: |:+1: | | :+1: | :+1: | | | |
6163
Topological Sort | | | | | :+1: | | | |
6264
Segmented Sieve |:+1:| :+1: | | | :+1: | | | |
6365
Union Find |:+1:|:+1:| | :+1: | | | | |
64-
Xor swap |:+1:| | | | | | | |
66+
Xor swap |:+1:|:+1:| | | |:+1:|:+1:| |
67+
Connected-component labeling | | | | |:+1:| | | |
6568

6669

6770
### List of Algorithms :
@@ -284,7 +287,7 @@ Xor swap |:+1:| | | | | | | |
284287

285288
* Dynamic Markov compression : Compression using predictive arithmetic coding
286289

287-
* Dynamic Programming : problems exhibiting the properties of overlapping subproblems and optimal substructure
290+
* [Dynamic Programming](DynamicProgramming) : problems exhibiting the properties of overlapping subproblems and optimal substructure
288291

289292
* Dynamic time warping : measure similarity between two sequences which may vary in time or speed
290293

@@ -784,7 +787,7 @@ Xor swap |:+1:| | | | | | | |
784787

785788
* Fibonacci Recursive : Fibonacci series printed using Java Recursion
786789

787-
Folder structure should be
790+
Folder structure should be like this
788791
[**Algorithm name**]/[**language**]/**file**
789792

790793
*For example*:

‎SelectionSort/Rust/selection_sort.rs‎

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
/*
2+
* Implementation of selection_sort in Rust
3+
*/
4+
5+
fn selection_sort(mut list: Vec<i32>) -> Vec<i32> {
6+
let n = list.len();
7+
8+
for j in 0..n-1 {
9+
let mut cur_min = j;
10+
11+
for i in j+1..n {
12+
if list[i] < list[cur_min] {
13+
cur_min = i;
14+
}
15+
}
16+
17+
if cur_min != j {
18+
list.swap(j, cur_min);
19+
}
20+
}
21+
22+
return list;
23+
}
24+
25+
26+
27+
fn main() {
28+
let mut mylist = Vec::new();
29+
mylist.push(5);
30+
mylist.push(4);
31+
mylist.push(8);
32+
mylist.push(9);
33+
mylist.push(20);
34+
mylist.push(14);
35+
mylist.push(3);
36+
mylist.push(1);
37+
mylist.push(2);
38+
mylist.push(2);
39+
40+
println!("{:?}", mylist);
41+
42+
let selection_sorted = selection_sort(mylist);
43+
44+
println!("{:?}", selection_sorted);
45+
}
46+

‎XorSwap/C#/XorSwap.cs‎

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
using System;
2+
3+
public class XorSwap
4+
{
5+
void Swap( ref int a, ref int b)
6+
{
7+
a ^= b;
8+
b ^= a;
9+
a ^= b;
10+
}
11+
12+
void Main()
13+
{
14+
int a = 5;
15+
int b = 10;
16+
XorSwap(ref a, ref b);
17+
}
18+
}
19+
20+

‎XorSwap/JavaScript/XorSwap.js‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
/**
2+
* xorSwap
3+
*
4+
* Swaps two variables without using a temporary variable
5+
*
6+
*/
7+
function xorSwap()
8+
{
9+
var a = 5, b = 10;
10+
a = a ^ b;
11+
b = a ^ b;
12+
a = a ^ b;
13+
14+
console.log("a = " + a + ", b = " + b);
15+
}
16+
17+

0 commit comments

Comments
 (0)