30 days of code in Go: Day 24 - Djikstra's algorithm

Hi there! Today I implemented Djikstra’s algorithm to find the minimum path between one source vertex and all the other vertices in the graph. This algorithm was devised in 1956 by the Dutch computer scientist Edsger W. Djikstra. It is quite fast having a complexity of $O(n\log n)$ when implemented with an auxiliary heap structure. To implement the heap in Go, I made use of the package heap. The package website also has an example of how to use and mine is basically a copy of it. I just changed one line. The code is available below. The graph structure was made basically with maps. ...

November 6, 2016 · 4 min

30 days of code in Go: Day 23 - Minimum Cut of Graph

Hi there! Today’s program aims to solve the minimum cut problem. It is another one that I learned in Algorithms: Design and Analysis, Part 1 course from Coursera. A cut is partition of a graph and partitioning a graph means dividing it into two disjoint subsets of vertices. The minimum cut then would be such that the number of edges going from one partition to the other is minimal. Below is a simple example of a graph with 4 nodes. There are two minimum cuts for it, namely cutting the node 1 or 4 out. Each one of these cuts has 2 edges going across the partitions. The goal of my program is to show what this number of edges is, not caring what the exact number of minimum cuts is. ...

October 29, 2016 · 5 min

30 days of code in Go: Day 22 - QuickSort

Hi there! Today’s challenge is another algorithm that I learned more in detail in the Algorithms: Design and Analysis, Part 1 course from Coursera: QuickSort. This algorithm chooses a pivot and does a partial sort around that pivot, having all elements less than the pivot to its left and all greater to its right, considering we want the number in increasing order. The main function is qsort which calls the function to choose a pivot and another to partition around the pivot. ...

October 15, 2016 · 4 min

30 days of code in Go: Day 21 - Extra Long Factorials

One of the big limitations of simple number data types is the maximum number they can hold. A 64 bit unsigned long can hold up to the number $2^{64}-1$. This is a pretty huge number, but if you try to compute the factorial of a number like $25!$, it is not enough. The good news is that there are software libraries that allow us to surpass this limitation. The bad is that the computations take longer. Depending on how critical something is, we may wish to avoid costly computations like these. Anyway, that’s the challenge I solved today using the package Big. My solution is given below. ...

October 12, 2016 · 2 min

30 days of code in Go: Day 20 - Count inversions with Merge Sort

Hi there! Today’s post is not from HackerRank. This was an assignment that I solved for the Algorithms: Design and Analysis, Part 1 course from Coursera. The goal is to implement an algorithm presented in the videos. It was explained in high level and not considering edge cases. I first tried to do it in C++ but it was taking me more time than I wanted to spend and then I switched to Go and it was blazing fast to code. What really helped me to solve it fast was the idea of a slice in Go. Slices can be partitioned easily. For instance ...

October 9, 2016 · 4 min

30 days of code in Go: Day 19 - Binomial Distribution II

Hi there! Today’s problem is very similar to the last day, again using a binomial distribution. Question Given that 12% of the pistons of a manufacture are rejected because of incorrect sizing, what is the probability of batch of 10 pistons contain No more than two rejects? At least two rejects? Again, very similar. Now the probability of success for the Bernoulli trial is of the chance of the piston being reject, the same as being incorrectly sized. For the case of no more than two rejects, the probability is given by $$P_{x \le 2} = \sum_{i=0}^2 b(i, 10, 0.12),$$ while for the case of at least two rejects it is $$P_{x \ge 2} = \sum_{i=2}^{10} b(i, 10, 0.12).$$ ...

October 6, 2016 · 2 min

30 days of code in Go: Day 18 - Binomial Distribution I

Hi there! Today’s challenge from HackerRank was a little more involved. The challenge is Given the ratio $1.09 : 1$ of boys to girls for babies born in a certain country, what is the proportion of families with exactly 6 children that will have at least 3 boys?. Before actually solving that, it is important to understand a Bernoulli trial and also the Binomial Distribution. Bernoulli trial According to Wikipedia, a Bernoulli trial is a random experiment with exactly two possible outcomes, “success” and “failure”, in which the probability of success is the same every time the experiment is conducted. ...

October 5, 2016 · 2 min

30 days of code in Go: Day 17 - Standard Deviation

Hi there! Today’s challenge was to compute standard deviation of an array of data given the formula $$\sigma = \sqrt{\frac{\sum_{i=0}^{N-1} (x_i - \mu)^2}{N}},$$ where $$\mu = \frac{\sum_{i=0}^{N-1} x_i}{N}.$$ The first input to the program is N and then N integers are fed to the program in sequence. My solution is given below. package main import ( "fmt" "math" ) func mean(a []int) float64 { n := float64(len(a)) sum := 0.0 for i := 0; i < len(a); i++ { sum += float64(a[i]) } return sum / n } func sigma(a []int) float64 { mu := mean(a) sum := 0.0 n := float64(len(a)) for i := 0; i < len(a); i++ { x := float64(a[i]) sum += (x - mu) * (x - mu) } sigma := math.Sqrt(sum / n) return sigma } func main() { N := 0 fmt.Scanf("%d", &N) // allocate memory X := make([]int, N) // read numbers from stdin for i := 0; i < N; i++ { fmt.Scanf("%d", &X[i]) } y := sigma(X) fmt.Printf("%.1f\n", y) } The problem I had this time was with HackerRank. On my computer I had a result, but their system was saying it had a different result. After that I ran it again on HackerRank using the option custom input, but with the same input that gave me a bad answer error, but this time the answer was ok. Bugs appear everywhere, right? I will submit it with another language, still thinking about it. I wrote something to them, hopefully they will fix this bug. ...

October 4, 2016 · 2 min

30 days of code in Go: Day 16 - Interquartile Range

Hi there! Today’s challenge is quite similar to the last one. Again, there are quartiles, but the input is a little different and the output is the interquartile range: $Q_3 - Q_1$. The first input is $n$ followed by an array $X$ of size $n$ with our data, but the frequencies of each point are included in another array of $n$ elements, $F$, that is the next input. After reading this we need to construct the actual data array $S$. My solution is below. ...

October 3, 2016 · 2 min

30 days of code in Go: Day 15 - Quartiles

Hi there! The problem for today required me to find the quartiles of set of data values. The concept is actually new to me but, once I learned it, it resembled a lot the median of a data set. Actually, the second quartile $Q_2$ is the median itself, while the other two quartiles, $Q_1$ and $Q_2$, are basically medians of sub datasets divided around the second quartile. The three quartiles divide the data in four regions instead of two regions using only the median. ...

October 1, 2016 · 2 min