Newbe Dev Stack

Answer : Bellman-Ford algorithm is a single-source shortest path algorithm, so when you have negative edge weight then it can detect negative cycles in a graph. The only difference between the two is that Bellman-Ford is also capable of handling negative weights whereas Dijkstra Algorithm can only handle positives. From wiki However, Dijkstra's algorithm greedily selects the minimum-weight node that has not yet been processed, and performs this relaxation process on all of its outgoing edges; in contrast, the Bellman–Ford algorithm simply relaxes all the edges, and does this |V | − 1 times, where |V | is the number of vertices in the graph. In each of these repetitions, the number of vertices with correctly calculated distances grows, from which it follows that eventually all vertices will have their correct distances. This method allows the Bellman–Ford algorithm to be applied to a wider class of inputs than Dijkstra. Dijkstra is however generally co...

Answer : I hope this is helpful to anybody having trouble understanding computational time complexity for Breadth First Search a.k.a BFS. Queue graphTraversal.add(firstVertex); // This while loop will run V times, where V is total number of vertices in graph. while(graphTraversal.isEmpty == false) currentVertex = graphTraversal.getVertex(); // This while loop will run Eaj times, where Eaj is number of adjacent edges to current vertex. while(currentVertex.hasAdjacentVertices) graphTraversal.add(adjacentVertex); graphTraversal.remove(currentVertex); Time complexity is as follows: V * (O(1) + O(Eaj) + O(1)) V + V * Eaj + V 2V + E(total number of edges in graph) V + E I have tried to simplify the code and complexity computation but still if you have any questions let me know. Considering the following Graph we see how the time complexity is O(|V|+|E|) but not O(V*E). Adjacency List V E v0:{v1,v2} v1:{v3} v2:{v3} v3:{} Ope...

Answer : You could average the RGB values of random colors with those of a constant color: (example in Java) public Color generateRandomColor(Color mix) { Random random = new Random(); int red = random.nextInt(256); int green = random.nextInt(256); int blue = random.nextInt(256); // mix the color if (mix != null) { red = (red + mix.getRed()) / 2; green = (green + mix.getGreen()) / 2; blue = (blue + mix.getBlue()) / 2; } Color color = new Color(red, green, blue); return color; } Mixing random colors with white (255, 255, 255) creates neutral pastels by increasing the lightness while keeping the hue of the original color. These randomly generated pastels usually go well together, especially in large numbers. Here are some pastel colors generated using the above method: You could also mix the random color with a constant pastel, which results in a tinted set of neutral colors. For example, using a light blue cr...

Answer : It seems like these are the issues in your code: You need to convert lat1 and lon1 to radians before calling your function. You may be scaling radialDistance incorrectly. Testing a floating-point number for equality is dangerous. Two numbers that are equal after exact arithmetic might not be exactly equal after floating-point arithmetic. Thus abs(x-y) < threshold is safer than x == y for testing two floating-point numbers x and y for equality. I think you want to convert lat and lon from radians to degrees. Here is my implementation of your code in Python: #!/usr/bin/env python from math import asin,cos,pi,sin rEarth = 6371.01 # Earth's average radius in km epsilon = 0.000001 # threshold for floating-point equality def deg2rad(angle): return angle*pi/180 def rad2deg(angle): return angle*180/pi def pointRadialDistance(lat1, lon1, bearing, distance): """ Return final coordinates (lat2,lon2) [in degrees] given...

Answer : Here is my version, which works purely in integers (the division by k always produces an integer quotient) and is fast at O(k): function choose(n, k) if k == 0 return 1 return (n * choose(n - 1, k - 1)) / k I wrote it recursively because it's so simple and pretty, but you could transform it to an iterative solution if you like. You could use the Multiplicative formula for this: http://en.wikipedia.org/wiki/Binomial_coefficient#Multiplicative_formula Probably the easiest way to compute binomial coefficients (n choose k) without overflowing is to use Pascal's triangle. No fractions or multiplications are necessary. (n choose k) . The nth row and kth entry of Pascal's triangle gives the value. Take a look at this page. This is an O(n^2) operation with only addition, which you can solve with dynamic programming. It's going to be lightning fast for any number that can fit in a 64-bit integer.

Answer : Let's assume that width of the array is bigger than height, otherwise we will split in another direction. Split the array into three parts: central column, left side and right side. Go through the central column and two neighbour columns and look for maximum. If it's in the central column - this is our peak If it's in the left side, run this algorithm on subarray left_side + central_column If it's in the right side, run this algorithm on subarray right_side + central_column Why this works: For cases where the maximum element is in the central column - obvious. If it's not, we can step from that maximum to increasing elements and will definitely not cross the central row, so a peak will definitely exist in the corresponding half. Why this is O(n): step #3 takes less than or equal to max_dimension iterations and max_dimension at least halves on every two algorithm steps. This gives n+n/2+n/4+... which is O(n) . Important detail: we split...

Answer : This link might be helpful to you, as it details the use of the Haversine formula to calculate the distance. Excerpt: This script [in Javascript] calculates great-circle distances between the two points – that is, the shortest distance over the earth’s surface – using the ‘Haversine’ formula. function getDistanceFromLatLonInKm(lat1,lon1,lat2,lon2) { var R = 6371; // Radius of the earth in km var dLat = deg2rad(lat2-lat1); // deg2rad below var dLon = deg2rad(lon2-lon1); var a = Math.sin(dLat/2) * Math.sin(dLat/2) + Math.cos(deg2rad(lat1)) * Math.cos(deg2rad(lat2)) * Math.sin(dLon/2) * Math.sin(dLon/2) ; var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a)); var d = R * c; // Distance in km return d; } function deg2rad(deg) { return deg * (Math.PI/180) } I needed to calculate a lot of distances between the points for my project, so I went ahead and tried to optimize the code, I have found here. On average in different bro...