Skip to content

Commit 1f13ba0

Browse files
FernandaOchoaFernandaOchoa
authored
Merge branch 'master' into FernandaOchoa-QuickSort
2 parents a9f0118 + 0eebbaf commit 1f13ba0

10 files changed

Lines changed: 365 additions & 8 deletions

File tree

‎CONTRIBUTING.md‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -137,4 +137,10 @@ Unfortunately, sometimes the bug can be only reproduced in your project or in yo
137137
- [SrGrace](https://github.com/SrGrace)
138138
- [d-grossman](https://github.com/d-grossman)
139139
- [javmonisu](https://github.com/javmonisu)
140+
- [lena15n](https://github.com/lena15n)
141+
- [stripedpajamas](https://github.com/stripedpajamas)
142+
- [Renan Vichetti](https://github.com/rvconessa)
143+
- [pranjalrai](https://github.com/pranjalrai)
144+
- [stuxxnet](https://github.com/stuxxnet42)
145+
- [BurnzZ](https://github.com/BurnzZ)
140146
- [FernandaOchoa](https://github.com/FernandaOchoa)

‎Doomsday/cpp/doomsday.cpp‎

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
#include <iostream>
2+
#include <string>
3+
4+
int dayOfWeek(int y, int m, int d){
5+
int t[]={0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4};
6+
y -= (m<3) ? 1 : 0;
7+
return (y + y/4 - y/100 + y/400 + t[m-1] + d) % 7;
8+
}
9+
10+
int main(int argc, char** argv){
11+
if(argc != 4){
12+
std::cout<<"usage is: program YYYY MM DD"<<std::endl;
13+
return -1;
14+
}
15+
int year=std::stoi(argv[1]);
16+
int month=std::stoi(argv[2]);
17+
int day=std::stoi(argv[3]);
18+
std::string days[7]={"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
19+
std::cout<<days[dayOfWeek(year, month, day)]<<std::endl;
20+
return 0;
21+
}

‎EdmondsKarp/Java/EdmondsKarp.java‎

Lines changed: 199 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,199 @@
1+
import java.util.*;
2+
3+
public class EdmondsKarp {
4+
public static void main(String[] args) {
5+
int verticesCount = 6;
6+
double[][] capacity = initCapacity(verticesCount);
7+
int s = 0;
8+
int t = verticesCount - 1;
9+
Map<Integer, List<Edge>> graphForwardEdges = initForwardGraphEdges();
10+
Map<Integer, List<Edge>> graphReverseEdges = initReverseGraphEdges();
11+
12+
double maxFlow = calculateMaxFlow(graphForwardEdges, graphReverseEdges, s, t, capacity);
13+
System.out.println(maxFlow);
14+
}
15+
16+
private static double calculateMaxFlow(Map<Integer, List<Edge>> graphForwardEdges,
17+
Map<Integer, List<Edge>> graphReverseEdges,
18+
int s, int t, double[][] capacity) {
19+
int verticesCount = graphForwardEdges.size();
20+
double[][] flow = new double[verticesCount][verticesCount];
21+
double maxFlow = 0.0;
22+
boolean isPathExist = true;
23+
Deque<Integer> queue = new ArrayDeque<>();
24+
25+
while (isPathExist) {
26+
Edge[] parent = new Edge[verticesCount];
27+
boolean[] visited = new boolean[verticesCount];
28+
queue.addLast(s);
29+
30+
// choose path from s to t
31+
while (!queue.isEmpty()) {
32+
int currentVertex = queue.pollFirst();
33+
visited[currentVertex] = true;
34+
List<Edge> outEdges = graphForwardEdges.get(currentVertex);
35+
36+
for (Edge edge : outEdges) {
37+
int to = edge.getTo();
38+
if (!visited[to]) {
39+
if (capacity[currentVertex][to] - flow[currentVertex][to] > 0 &&
40+
flow[currentVertex][to] >= 0) {
41+
parent[to] = edge;
42+
queue.addLast(to);
43+
}
44+
}
45+
}
46+
47+
List<Edge> inEdges = graphReverseEdges.get(currentVertex);
48+
for (Edge edge : inEdges) {
49+
int from = edge.getFrom();
50+
if (!visited[from]) {
51+
if (flow[from][currentVertex] > 0) {
52+
parent[from] = edge;
53+
queue.addLast(from);
54+
}
55+
}
56+
}
57+
}
58+
59+
isPathExist = visited[t];
60+
61+
// find max possible flow of the chosen path
62+
if (isPathExist) {
63+
int child = t;
64+
double bottleneck = Double.MAX_VALUE;
65+
66+
while (child != s) {
67+
Edge edge = parent[child];
68+
if (!edge.isReverse()) {
69+
bottleneck = Math.min(bottleneck, capacity[edge.getFrom()][edge.getTo()] -
70+
flow[edge.getFrom()][edge.getTo()]);
71+
} else {
72+
bottleneck = Math.min(bottleneck, flow[edge.getFrom()][edge.getTo()]);
73+
}
74+
75+
child = edge.isReverse() ? edge.getTo() : edge.getFrom();
76+
}
77+
78+
// update flow
79+
maxFlow += bottleneck;
80+
child = t;
81+
while (child != s) {
82+
Edge edge = parent[child];
83+
int from = (!edge.isReverse()) ? edge.getFrom() : edge.getTo();
84+
flow[from][child] += bottleneck;
85+
flow[child][from] -= bottleneck;
86+
child = (!edge.isReverse()) ? edge.getFrom() : edge.getTo();
87+
}
88+
}
89+
}
90+
91+
return maxFlow;
92+
}
93+
94+
private static double[][] initCapacity(int verticesCount) {
95+
double[][] capacity = new double[verticesCount][verticesCount];
96+
capacity[0][1] = 10;
97+
capacity[1][0] = 10;
98+
99+
capacity[0][3] = 10;
100+
capacity[3][0] = 10;
101+
102+
103+
capacity[1][2] = 4;
104+
capacity[2][1] = 4;
105+
106+
capacity[1][3] = 2;
107+
capacity[3][1] = 2;
108+
109+
capacity[1][4] = 8;
110+
capacity[4][1] = 8;
111+
112+
113+
capacity[2][5] = 10;
114+
capacity[5][2] = 10;
115+
116+
117+
capacity[3][4] = 9;
118+
capacity[4][3] = 9;
119+
120+
121+
capacity[4][2] = 6;
122+
capacity[2][4] = 6;
123+
124+
capacity[4][5] = 10;
125+
capacity[5][4] = 10;
126+
127+
return capacity;
128+
}
129+
130+
private static Map<Integer, List<Edge>> initForwardGraphEdges() {
131+
Map<Integer, List<Edge>> graph = new HashMap<>();
132+
graph.put(0, createForwardEdges(0, 1, 3));
133+
graph.put(1, createForwardEdges(1, 2, 3, 4));
134+
graph.put(2, createForwardEdges(2, 5));
135+
graph.put(3, createForwardEdges(3, 4));
136+
graph.put(4, createForwardEdges(4, 2, 5));
137+
graph.put(5, Collections.emptyList());
138+
139+
return graph;
140+
}
141+
142+
private static Map<Integer, List<Edge>> initReverseGraphEdges() {
143+
Map<Integer, List<Edge>> graph = new HashMap<>();
144+
graph.put(0, Collections.emptyList());
145+
graph.put(1, Collections.emptyList());
146+
graph.put(2, createReverseEdges(2, 1, 4));
147+
graph.put(3, createReverseEdges(3, 1));
148+
graph.put(4, createReverseEdges(4, 1, 3));
149+
graph.put(5, Collections.emptyList());
150+
151+
return graph;
152+
}
153+
154+
private static List<Edge> createForwardEdges(int from, Integer... toVertices) {
155+
List<Edge> edges = new ArrayList<>();
156+
157+
for (Integer to : toVertices) {
158+
Edge edge = new Edge(from, to, false);
159+
edges.add(edge);
160+
}
161+
162+
return edges;
163+
}
164+
165+
private static List<Edge> createReverseEdges(int to, Integer... fromVertices) {
166+
List<Edge> edges = new ArrayList<>();
167+
168+
for (Integer from : fromVertices) {
169+
Edge edge = new Edge(from, to, true);
170+
edges.add(edge);
171+
}
172+
173+
return edges;
174+
}
175+
176+
private static class Edge {
177+
private int from;
178+
private int to;
179+
private boolean isReverse;
180+
181+
Edge(int from, int to, boolean isReverse) {
182+
this.from = from;
183+
this.to = to;
184+
this.isReverse = isReverse;
185+
}
186+
187+
int getFrom() {
188+
return from;
189+
}
190+
191+
int getTo() {
192+
return to;
193+
}
194+
195+
boolean isReverse() {
196+
return isReverse;
197+
}
198+
}
199+
}

‎Fibonacci/Python/fibonacci_golden_ratio.py‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
import math
2+
3+
def fibonacci_golden_ratio(num):
4+
"""Returns fibonacci numbers using the Golden Ratio formula"""
5+
6+
golden_ratio = (1 + math.sqrt(5)) / 2
7+
8+
golden_ratio_conjugate = (1 - math.sqrt(5)) / 2
9+
10+
return int(round(
11+
((golden_ratio ** num)
12+
- (golden_ratio_conjugate ** num))
13+
/ math.sqrt(5)))

‎HammingDistance/Go/hammingDistance.go‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
package hammingDistance
2+
3+
func HammingDistance(a, b string) int {
4+
if len(a) != len(b) {
5+
panic("The two strings must have equal length")
6+
}
7+
aRunes := []rune(a)
8+
bRunes := []rune(b)
9+
distance := 0
10+
for i, r := range aRunes {
11+
if r != bRunes[i] {
12+
distance++
13+
}
14+
}
15+
return distance
16+
}

‎HammingDistance/Go/hammingDistance_test.go‎

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
package hammingDistance
2+
3+
import "testing"
4+
5+
func TestHammingDistance(t *testing.T) {
6+
// "karolin" => "kathrin" is 3 according to Wikipedia
7+
if HammingDistance("karolin", "kathrin") != 3 {
8+
t.Fail()
9+
}
10+
}

‎Kadane's/C/Kadanes.c‎

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
2+
long long int inf=-999999999999;
3+
int KadaneAlgo(int ar[] , int size)
4+
{
5+
int maximum=-inf; //maximum contiguous sum of all the segments of array
6+
int max_of_present_segment=0; //maximum contiguous sum of current segment
7+
for (int i = 0; i < size; i++)
8+
{
9+
max_of_present_segment = max_of_present_segment +ar[i];
10+
if(maximum < max_of_present_segment)
11+
{
12+
maximum = max_of_present_segment; //storing the maximum segment sum till now
13+
}
14+
if(max_of_present_segment < 0)
15+
{
16+
max_of_present_segment=0; //setting the current segment sum as 0 if it is negative
17+
}
18+
}
19+
return maximum;
20+
}

‎QuickSelect/JavaScript/quickselect-javascript.js‎

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
//Source: https://stackoverflow.com/questions/38988384/quickselect-into-javascript
2+
function swap(array, idxA, idxB) {
3+
var temp = array[idxA]
4+
array[idxA] = array[idxB]
5+
array[idxB] = temp
6+
}
7+
8+
function partitionStart(arr, left, right) {
9+
var pivotIdx = Math.floor(Math.random() * (right - left + 1)) + left;
10+
var storeIdx = left, pivotVal = arr[pivotIdx]
11+
for (var i = left; i <= right; i++) {
12+
if (arr[i] < pivotVal) {
13+
swap(arr, storeIdx, i)
14+
storeIdx++
15+
}
16+
}
17+
return storeIdx;
18+
}
19+
20+
function quickSelectLoop(arr, k) {
21+
var pivotDist;
22+
var left = 0, right = arr.length - 1;
23+
while(right !== left) {
24+
pivotDist = partitionStart(arr, left, right)
25+
26+
if (k < pivotDist) {
27+
right = pivotDist - 1;
28+
} else {
29+
left = pivotDist;
30+
}
31+
}
32+
return arr[k]
33+
}
34+
35+
//Test
36+
37+
38+
var test2 = [87,32,55,23,389,123,555,657,12378, 12312,3332]
39+
var tmp = [].concat(test2)
40+
41+
tmp.sort(function(a,b) { return a==b ? 0: (a< b? -1: 1)});
42+
43+
for(var x=0;x<test2.length;x++) {
44+
console.log(quickSelectLoop([].concat(test2), x), tmp[x])
45+
}

‎README.md‎

Lines changed: 8 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -19,22 +19,23 @@ Conjugate Gradient | | | | | :+1: | | | | ||
1919
CountingSort | :+1: | :+1: | | | :+1: | | | | |
2020
DepthFirstSearch | :+1: | :+1: | | | :+1: | :+1: | | | |
2121
Dijkstra's | :+1: | :+1: | | | :+1: | | :+1: | | |
22-
Doomsday | :+1: | :+1: | | | | :+1: | | | | :+1: | :+1:
22+
Doomsday | :+1: | :+1: | | | :+1: | :+1: | | | | :+1: | :+1:
2323
EditDistance | | :+1: | | | :+1: | | | |
24+
Edmonds-Karp | :+1: | | | | | | | |
2425
ElevatorAlgorithm | :+1: | | | | | | | |
2526
Fast Fourier Transform | | | | | :+1: | | | |
2627
Fibonacci | :+1: | :+1: | | :+1: | :+1: | :+1: | | :+1: | :+1: | |
2728
FisherYatesShuffle | :+1: | | | | :+1: | :+1: | | :+1: |
2829
FloodFill Algorithm | :+1: | | | | | | | |
2930
Floyd'sAlgorithm | :+1: | :+1: | | | :+1: | | | |
3031
GreatestCommonDivisor | :+1: | | :+1: | :+1: | :+1: | | | |
31-
HammingDistance | :+1: | :+1: | | :+1: | | :+1: | | |
32+
HammingDistance | :+1: | :+1: | | :+1: | | :+1: | :+1: | |
3233
HeapSort | :+1: | :+1: | | | :+1: | :+1: | :+1: | | :+1:
3334
HistogramEqualization | :+1: | | | | | | | |
3435
InsertionSort | :+1: | :+1: | :+1: | :+1: | :+1: | | :+1: | :+1: |
3536
Inverse Fast Fourier Transform | | | | | :+1: | | | |
3637
Johnson algorithm | :+1: | :+1: | | | :+1: | | | |
37-
Kadane's algorithm | :+1: | :+1: | | | :+1: | :+1: | :+1: | |
38+
Kadane's algorithm | :+1: | :+1: | | :+1: | :+1: | :+1: | :+1: | |
3839
Knuth Morris Prath Algorithm | :+1: | :+1: | | | :+1: | | | |
3940
LinearSearch | :+1: | :+1: | | :+1:| :+1: | :+1: | | | | |
4041
Longest-Common-Subsequence | :+1: | :+1: | | | :+1: | | | | :+1:
@@ -46,7 +47,7 @@ Modified_Binary_Search | | | | :+1: | | | | |
4647
Pearson Hashing | :+1: | | | | | | | |
4748
Postman Sort | | | | :+1: | | | | |
4849
Quick Sort | :+1: | :+1: | | | | :+1: | :+1: | :+1: | :+1: | :+1: |
49-
Quick Select | :+1: | :+1: | | | | | :+1: | |
50+
Quick Select | :+1: | :+1: | | :+1: | | | :+1: | |
5051
Uniform-cost search | :+1: | | | | | :+1: | :+1: | |
5152
RadixSort | :+1: | :+1: | | | :+1: | | | |
5253
RobinCarp | :+1: | | | | | | | |
@@ -55,13 +56,12 @@ ShellSort | :+1: | :+1: | | | :+1: | | | |
5556
SieveofEratosthenes | :+1: | :+1: | | | :+1: | :+1: | :+1: | |
5657
UnaryCoding | :+1: | :+1: | | | | :+1: | | |
5758
VEGAS Algorithm | | | | | :+1: | | | | ||
58-
TernarySearch | :+1: |:+1: | | | :+1: | | | |
59-
Topological Sort | | | | | :+1: | | | |
60-
Segmented Sieve |:+1:| :+1: | | | :+1: | | | |
59+
TernarySearch | :+1: |:+1: | | :+1: | :+1: | | | |
60+
Topological Sort | | | | | :+1: | | | |
61+
Segmented Sieve |:+1:| :+1: | | | :+1: | | | |
6162
Union Find |:+1:|:+1:| | | | | | |
6263

6364

64-
6565
### List of Algorithms :
6666

6767
* 3Dc : a lossy data compression algorithm for normal maps

0 commit comments

Comments
 (0)