Skip to content

Commit bca4558

Browse files
thuva4thuva4
authored
Merge branch 'master' into master
2 parents d084c3a + c130346 commit bca4558

File tree

22 files changed

+677
-45
lines changed

22 files changed

+677
-45
lines changed

‎BellmanFord/C++/bellmanford.cpp‎

Lines changed: 133 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,133 @@
1+
#include <iostream>
2+
#include <stdlib.h>
3+
#include <string.h>
4+
#include <limits.h>
5+
6+
using namespace std;
7+
8+
struct Edge
9+
{
10+
// This structure is equal to an edge. Edge contains two end points. These edges are directed edges so they
11+
//contain source and destination and some weight. These 3 are elements in this structure
12+
int source, destination, weight;
13+
};
14+
15+
// a structure to represent a connected, directed and weighted graph
16+
struct Graph
17+
{
18+
int V, E;
19+
// V is number of vertices and E is number of edges
20+
21+
struct Edge* edge;
22+
// This structure contain another structure which we already created edge.
23+
};
24+
25+
struct Graph* createGraph(int V, int E)
26+
{
27+
struct Graph* graph = (struct Graph*) malloc( sizeof(struct Graph));
28+
//Allocating space to structure graph
29+
30+
graph->V = V; //assigning values to structure elements that taken form user.
31+
32+
graph->E = E;
33+
34+
graph->edge = (struct Edge*) malloc( graph->E * sizeof( struct Edge ) );
35+
//Creating "Edge" type structures inside "Graph" structure, the number of edge type structures are equal to number of edges
36+
37+
return graph;
38+
}
39+
40+
void FinalSolution(int dist[], int n)
41+
{
42+
// This function prints the final solution
43+
cout<<"\nVertex\tDistance from Source Vertex\n";
44+
int i;
45+
46+
for (i = 0; i < n; ++i){
47+
cout<<i<<"\t\t"<<dist[i]<<"\n";
48+
}
49+
}
50+
51+
void BellmanFord(struct Graph* graph, int source)
52+
{
53+
int V = graph->V;
54+
55+
int E = graph->E;
56+
57+
int StoreDistance[V];
58+
59+
int i,j;
60+
61+
// This is initial step that we know , we initialize all distance to infinity except source.
62+
// We assign source distance as 0(zero)
63+
64+
for (i = 0; i < V; i++)
65+
StoreDistance[i] = INT_MAX;
66+
67+
StoreDistance[source] = 0;
68+
69+
//The shortest path of graph that contain V vertices, never contain "V-1" edges. So we do here "V-1" relaxations
70+
for (i = 1; i <= V-1; i++)
71+
{
72+
for (j = 0; j < E; j++)
73+
{
74+
int u = graph->edge[j].source;
75+
76+
int v = graph->edge[j].destination;
77+
78+
int weight = graph->edge[j].weight;
79+
80+
if (StoreDistance[u] + weight < StoreDistance[v])
81+
StoreDistance[v] = StoreDistance[u] + weight;
82+
}
83+
}
84+
85+
// Actually upto now shortest path found. But BellmanFord checks for negative edge cycle. In this step we check for that
86+
// shortest distances if graph doesn't contain negative weight cycle.
87+
88+
// If we get a shorter path, then there is a negative edge cycle.
89+
for (i = 0; i < E; i++)
90+
{
91+
int u = graph->edge[i].source;
92+
93+
int v = graph->edge[i].destination;
94+
95+
int weight = graph->edge[i].weight;
96+
97+
if (StoreDistance[u] + weight < StoreDistance[v])
98+
cout<<"\nThis graph contains negative edge cycle\n";
99+
}
100+
101+
FinalSolution(StoreDistance, V);
102+
103+
return;
104+
}
105+
106+
int main()
107+
{
108+
int V,E,S; //V = no.of Vertices, E = no.of Edges, S is source vertex
109+
110+
cout<<"Enter number of vertices in graph\n";
111+
cin>>V;
112+
113+
cout<<"Enter number of edges in graph\n";
114+
cin>>E;
115+
116+
cout<<"Enter your source vertex number\n";
117+
cin>>S;
118+
119+
struct Graph* graph = createGraph(V, E); //calling the function to allocate space to these many vertices and edges
120+
121+
int i;
122+
for(i=0;i<E;i++){
123+
cout<<"\nEnter edge "<<i+1<<" properties Source, destination, weight respectively\n";
124+
cin>>graph->edge[i].source;
125+
cin>>graph->edge[i].destination;
126+
cin>>graph->edge[i].weight;
127+
}
128+
129+
BellmanFord(graph, S);
130+
//passing created graph and source vertex to BellmanFord Algorithm function
131+
132+
return 0;
133+
}

‎BellmanFord/C/bellman-ford.c‎

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
vector <int> graph [100005]; // graph is a vector to store the graph
2+
int distance [100005];
3+
4+
for(int i = 0; i < m + 2; i++){ // initializing the distance as infinite
5+
6+
graph[i].clear();
7+
distance[i] = INT_MAX;
8+
}
9+
10+
for(int i = 0; i < m; i++){
11+
12+
cin>>from>>next>>weight; //from and next are the vertices and weight is the edge weiht betwenn the pair of vertices
13+
14+
graph[i].push_back(from);
15+
graph[i].push_back(next);
16+
graph[i].push_back(weight);
17+
}
18+
19+
distance[0] = 0;
20+
for(int i = 0; i < n - 1; i++){
21+
int j = 0;
22+
while(graph[j].size() != 0){
23+
24+
if(distance[ graph[j][0] ] + graph[j][2] < distance[ graph[j][1] ] ){ //comparing the current and new distances between the pair of vertices
25+
distance[ v[j][1] ] = distance[ graph[j][0] ] + graph[j][2]; //updating the minimum distance
26+
}
27+
j++;
28+
}
29+
}

‎BinarySearch/Javascript/binarySearch.js‎

Lines changed: 28 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -1,27 +1,31 @@
1-
/*Binary Search-Search a sorted array by repeatedly dividing the search interval
2-
* in half. Begin with an interval covering the whole array. If the value of the
3-
* search key is less than the item in the middle of the interval, narrow the interval
4-
* to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the
5-
* value is found or the interval is empty.
6-
*/
7-
8-
function binarySearch(arr, i) {
9-
var mid = Math.floor(arr.length / 2);
10-
if (arr[mid] === i) {
11-
console.log('match', arr[mid], i);
12-
return arr[mid];
13-
} else if (arr[mid] < i && arr.length > 1) {
14-
binarySearch(arr.splice(mid, Number.MAX_VALUE), i);
15-
} else if (arr[mid] > i && arr.length > 1) {
16-
binarySearch(arr.splice(0, mid), i);
17-
} else {
18-
console.log('not found', i);
19-
return -1;
20-
}
1+
/**
2+
* Search a value into a sorted array by repeatedly dividing the search interval in half.
3+
* @param {Array} arr Array to search into
4+
* @param {Number} k Value to search
5+
* @return {Number} index of found item or -1 for not found
6+
*/
7+
function binarySearch(arr, k) {
8+
let min = 0
9+
let max = arr.length - 1
10+
11+
while (min <= max) {
12+
const cur = Math.floor((min + max) / 2)
13+
if (arr[cur] === k) { return cur }
14+
(arr[cur] > k)
15+
? max = cur - 1
16+
: min = cur + 1
17+
}
2118

19+
return -1
2220
}
2321

24-
var ar=[1,2,3,4,5,6,7,8,9,10];
25-
binarySearch(ar,3);
26-
binarySearch(ar,7);
27-
binarySearch(ar,13);
22+
const arr = [1,2,3,4,5,6,7,8,9,10]
23+
console.log(binarySearch(arr, 6)) // 5
24+
console.log(binarySearch(arr, 9)) // 8
25+
console.log(binarySearch(arr, 2)) // 1
26+
console.log(binarySearch(arr, 7)) // 6
27+
console.log(binarySearch(arr, 11)) // -1
28+
29+
console.log(binarySearch(arr, 3)) // 2
30+
console.log(binarySearch(arr, 3)) // 2
31+
console.log(binarySearch(arr, 3)) // 2

‎BubbleSort/C++/bubble_sort.cpp‎

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
#include <iostream>
2+
using namespace std;
3+
4+
void swap(int *a, int *b)
5+
{
6+
int temp = *a;
7+
*a = *b;
8+
*b = temp;
9+
}
10+
11+
12+
void bubbleSort(int arr[], int n)
13+
{
14+
int i, j;
15+
for (i = 0; i < n-1; i++)
16+
for (j = 0; j < n-i-1; j++)
17+
if (arr[j] > arr[j+1])
18+
swap(&arr[j], &arr[j+1]);
19+
}
20+
21+
void printArray(int arr[], int size)
22+
{
23+
int i;
24+
for (i=0; i < size; i++)
25+
cout<<arr[i]<<" ";
26+
}
27+
28+
int main()
29+
{
30+
int arr[100],n;
31+
cout<<"Enter the size of array : \n";
32+
cin>>n;
33+
cout<<"Enter the elements : \n";
34+
for(int i=0 ; i<n ; i++){
35+
cin>>arr[i];
36+
}
37+
//int n = sizeof(arr)/sizeof(arr[0]);
38+
bubbleSort(arr, n);
39+
cout<<"Sorted Array : \n";
40+
printArray(arr, n);
41+
return 0;
42+
}

‎BubbleSort/Perl/bubble sort.pl‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
#!/usr/bin/perl
2+
use strict;
3+
use warnings;
4+
my @array = ( 5, 6, 3, 1, 7, 3, 2, 9, 10, 4 );
5+
6+
for my $i ( 1 .. $#array ) {
7+
for my $k ( 0 .. $i - 1 ) {
8+
@array[ $k, $k + 1 ] = @array[ $k + 1, $k ]
9+
if $array[$k] > $array[ $k + 1 ];
10+
}
11+
}
12+
13+
print "@array\n";

‎CONTRIBUTING.md‎

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -150,4 +150,14 @@ Unfortunately, sometimes the bug can be only reproduced in your project or in yo
150150
- [Jaernbrand](https://github.com/Jaernbrand)
151151
- [DiegoVicen](https://github.com/DiegoVicen)
152152
- [Ashwin-Kapes](https://github.com/Ashwin-Kapes)
153+
- [Santhosh Kumar](https://github.com/santhoshsamy29)
154+
- [Judar Lima](https://github.com/judarlima)
155+
- [Jhalaa](https://github.com/jhalaa)
156+
- [langlk](https://github.com/langlk)
157+
- [Anat Portnoy](https://github.com/Anat-Port)
158+
- [Leandro Nunes - lnfnunes](https://github.com/lnfnunes)
159+
- [syam3526](https://github.com/syam3526)
160+
- [churrizo](https://github.com/churrizo)
161+
- [Aniket Joshi](https://github.com/aniket7joshi)
162+
- [kuldeepdadhich](https://github.com/kuldeepdadhich)
153163
- [HimanshuAwasthi95](https://github.com/HimanshuAwasthi95)

‎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+
}

0 commit comments

Comments
 (0)