FAQ Database Discussion Community


Update minimum spanning tree if edge is added

algorithm,graph,tree,runtime,big-o
I have a possible solution for the following question, but not sure if correct: Assume we have already found a minimum spanning tree T for a weighted, undirected graph G = (V,E). We would like to be able to efficiently update T should G be altered slightly. An edge is...

Remove values from an array in-place without using extra memory

python,arrays,algorithm,dynamic-arrays
I want to remove value x from an array and I have the following constraints: I can only traverse the array once No extra memory/data structures are allowed so that a = [1, 2, 'x', 3, 4, 5] becomes [1, 2, 3, 4, 5, None] The case with only one...

Greedy algorithm: highest value first vs earliest deadline first

algorithm,language-agnostic,job-scheduling,greedy
Assume we have a set of n jobs to execute, each of which takes unit time. At any time we can serve exactly one job. Job i, 1<=i<=n earns us a profit if and only if it is executed no later than its deadline. We can a set of jobs...

Explain the time complexity of these grouping functions

c++,algorithm,inheritance,time-complexity
Here I have 800 derived classes of Base and a list of 8000000 objects of these types, which can be of any order. The goal is to separate the list into the 800 types as efficiently as possible. Here I have written two functions to do that. The first is...

Rate-limiting python function decorator

python,algorithm,decorator,python-decorators,rate-limiting
I found this rate-limiting python decorator based on redis classes. How can I write a similar decorator that uses only what's available in the standard library that can be used as follows? def ratelimit(limit, every): # 🐍 python magic 🐍 @ratelimit(limit=1, every=2) def printlimited(x): print x # print one number...

Finding number of ways to make a sum in coin changing?

c++,algorithm,dynamic-programming
Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter. For example, for N =...

Different ways of generating the partitions of a number in order

c++,algorithm,number-theory
I have an exercise in my algorithms text book that asks me to generate the partitions of a number in order. I have solved it, but while solving the exercise the traditional way I came up with a new idea of solving that problem. There is the traditional approach: #include...

Solving a complex recurrence relation for the Traveling Salesman

algorithm,math,time-complexity,computer-science,recurrence-relation
I need to solve the exact time complexity for the brute force version of the Traveling Salesman using a recurrence relation. I've worked out the recurrence relation to be as follows: T(n)=T(n-1)*(n-1)+1 But I'm having trouble reducing that that to a closed form of the function, and thus get the...

Given length L find the shortest string formed only of as & bs >= L such that adding some character (Either a or b) doesn't produce a new palindrome

string,algorithm,palindrome
Given length L find the shortest string >= L formed only of as & bs such that adding some character (Either a or b) doesn't produce a new palindrome substring (never seen before palindrome) For example for L = 1 there is the string aabbaba, adding "a" to it to...

to find a prime number in java

java,algorithm,primes
I came accros one of the solutions for finding if a number is prime as below : //checks whether an int is prime or not. boolean isPrime(int n) { if (n == 2){ return true; } //check if n is a multiple of 2 if (n%2==0){ return false; } //if...

How to apply ordering to a Scala Priority Queue?

algorithm,scala,priority-queue
I've defined a priority queue like so import scala.collection.mutable.PriorityQueue ... val queue = new PriorityQueue[(Int,Int)]() I want to use this ordering: If we are comparing two items A and B in the queue, A is bigger than B if the first element of its (Int,Int) tuple is larger than B's....

How to reduce time to find the n-th place from consecutive digits number for less than 1 second

php,algorithm,digits
I'm following the programming test, and there are questions like this From this consecutive digits: 123456789101112131415161718192021.... For example The 10th digit is 1 The 11th digit is 0 and so on What is the 1,000,000th digit? What is the 1,000,000,000th digit? What is the 1,000,000,000,000th digit? Your solution should run...

Having trouble understanding a portion of code

c,algorithm,bit
I have this problem: You have n problems. You have estimated the difficulty of the i-th one as integer ci. Now you want to prepare a problemset for a contest, using some of the problems you've made. A problemset for the contest must consist of at least two problems. You...

algorithm to get all combinations of splitting up N items into K bins

algorithm,recursion,permutation
Assuming I have a list of elements [1,2,3,4,] and a number of bins (let's assume 2 bins), I want to come up with a list of all combinations of splitting up items 1-4 into the 2 bins. Solution should look something like this [{{1}, {2,3,4}}, {{2}, {1,3,4}}, {{3}, {1,2,4}}, {{4},...

Disconnect all vertices in a graph - Algorithm

algorithm,graph
I am looking for an algorithm that finds minimal subset of vertices such that by removing this subset (and edges connecting these vertices) from graph all other vertices become unconnected (i.e. the graph won't have any edges). Is there such algorithm? If not: Could you recommend some kind of heuristics...

How to give mathemarical proof or support my answer through reasoning as a general case?

algorithm
You are managing a software project that involves building a computer-assisted instrument for medical surgery. The exact placement of the surgical knife is dependent on a number of different parameters, usually at least 25, sometimes more. Your programmer has developed two algorithms for positioning the cutting tool, and is seeking...

Find the shortest path sum in a matrix. Is Dijkstra not optimal for this case?

algorithm,go
I am trying to solve the following problem from project euler (please take a look at description and the example in the link, but here is the short explanation). in the matrix, find the minimal path sum from the top left to the bottom right, by moving left, right, up,...

How to detect palindrome cycle length in a string?

string,algorithm,palindrome
Suppose a string is like this "abaabaabaabaaba", the palindrome cycle here is 3, because you can find the string aba at every 3rd position and you can augment the palindrome by concatenating any number of "aba"s to the string. I think it's possible to detect this efficiently using Manacher's Algorithm...

Genetic Algorithm - convergence

java,algorithm,function,genetic-programming,convergence
I have a few questions about my genetic algorithm and GAs overall. I have created a GA that when given points to a curve it tries to figure out what function produced this curve. An example is the following Points {{-2, 4},{-1, 1},{0, 0},{1, 1},{2, 4}} Function x^2 Sometimes I...

Longest Non Repeating Substring in c++

c++,algorithm,substring
I am trying to find the longest substring with no repeated characters. I have a boolean vector to keep track of the 256 ascii characters. #include <iostream> #include <cstdio> #include <string> #include <algorithm> using namespace std; int main() { string s = "aaaaaaaaaaaaasadfrhtytbgrbrsvsrhvsg"; vector<bool> v(256, false); int j = 0,...

Find the maximum value of minimum of each subarray of non fixed length x where 1<= x <= N

algorithm,dynamic-programming
Interview Question: You are given N number in an array. A group of a numbers is a non-empty contiguous segment of array.The size of group is the number of numbers in that group. "A" is the minimum number in that group.Task was to find each x such that 1 <=...

Understanding Big-Ω (Big-Omega) notation

algorithm,big-o
I was doing some reading on logarithms and the rate of growth of the running time of algorithms. I have, however, a problem understanding the Big-Ω (Big-Omega) notation. I know that we use it for 'asymptotic lower bounds', and that we can express the idea that an algorithm takes at...

Dynamic programming: how to design algorithm for when there are two factors to consider?

algorithm,optimization,dynamic-programming,frequency
I have the following problem and I only have a slight idea about it: Consider a tape storage problem. Given n files of length l1,...,ln and frequencies with which they are accessed f1,...,fn, where sum of all frequencies is 1 and 0<fi<1. "Optimal" means to minimize the average retrieval time...

One-dimensional binpacking algorithm with relative costs

algorithm,optimization,bin-packing
I'm wondering how to solve "One-dimensional binpacking problem with relative costs". We pack N volumes (with given sizes) into M bins (with given capacities) and have the matrix (NxM) of costs of each volume per each bin. So, the total cost should be minimized. Can you advice any algorithm for...

Spiral traversal of a matrix - recursive solution in JavaScript

javascript,arrays,algorithm,recursion,matrix
I'm trying to come up with a solution that takes in a matrix like this: [[1,2,3,4], [5,6,7,8], [9,10,11,12], [13,14,15,16]] and returns an array traversing the array as a spiral, so in this example: [1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10] I'm having trouble getting this recursive solution to work, in which the result array takes the...

Binary Search - Best and worst case

algorithm,data-structures
In an exam I see a question: Which one of the following is true? For a binary search, the best-case occurs when the target item is in the beginning of the search list. For a binary search, the best-case occurs when the target is at the end of the search...

C: sorted input serials

c,algorithm
I try find out what is wrong with the program that takes n - size of serials and this same number of elements numbers. With n = 4 and numbers 1, 2, 3, 4 I get output: 1, 0, 2293428, 1990567906. Somewhere in the code something is not okey, but...

Calculating completion time of scheduled dependent tasks

python,algorithm
I am trying to calculate least completion time of a project schedule, which has n number of tasks and each task can have a dependency task. example Task ID Duration Days Dependent ID 1 10 0 2 3 0 3 6 1 4 5 2 5 10 1 Task with...

Algorithmic big o order of growth code

algorithm,discrete-mathematics
I'm doing an online course and i'm stuck on this question. I know there are similar questions but they don't help me. What is the order of growth of the worst case running time of the following code fragment as a function of N? int sum = 0; for (int...

Extract nearest point index from a linestring to a given point?

java,algorithm,scala,jts
Let's consider a linestring as a list of points, I named it trail. I need to detect which point is close enough to this trail. I have another linestring called interest points, which I need to return the closest index point from trail linestring. I want to mention that these...

Javascript: Detailed differences between !variable and variable == false?

javascript,algorithm
I accidentally got undefined == true and undefined == false that both of them returns false. But !undefined returns true. And this is the question: What's the algorithmic difference(s) between !someVariable and someVariable == false? If i want to explain it more, type undefined == false ? 't' : 'f'...

Determining if a graph has a cycle without using DFS

algorithm,graph,cycle,dfs
I came around one of those questions in my exams: Topologocial sorting using Kahn's Algorithm requires the graph to be DAG (Directed Acyclic Graph). How can we determine if a graph contains no cycles without using DFS/BFS first? I am trying to answer that for too long now and I...

Best way to extract ODD digits from a binary number

algorithm,bit-manipulation
Given a 64 bit number, I need to extract every other bit from it, and convert it into a number: decimal: 357 binary: 0000 0001 0110 0101 odd bits: 0 0 0 1 1 0 1 1 decimal: 27 Any idea of a good algorithmic way to do it? And...

How to print the right hemisphere of a square matrix

c++,algorithm,matrix
I am trying to print the right hemisphere of a matrix. If we draw the main and the secondary diagonals in a matrix we see that we got 4 equal parts, the right part is called (in my algorithms textbook) the right hemisphere of a square matrix. For example, in...

Identify that a string could be a datetime object

python,regex,algorithm,python-2.7,datetime
If I knew the format in which a string represents date-time information, then I can easily use datetime.datetime.strptime(s, fmt). However, without knowing the format of the string beforehand, would it be possible to determine whether a given string contains something that could be parsed as a datetime object with the...

minimum no of operations to convert an array having zeroes to some other array [closed]

c++,algorithm
i saw the following question which was asked in some company's hiring test. Can some one please help me out with how to proceed with the problem. Find the minimum number of operations to convert an array containing n elements with value 0 to a given desired array of non-negative...

String Pattern Matching Algorithm Used in Different Applications [on hold]

arrays,string,algorithm,file,data-structures
I want to know which algorithm is used by the following Applications or WebSite for String Pattern Matching, I have already search by title but nothing found, i want to learn and understand the real time implementation of String Pattern Matching algorithm used by various Applications. 1.Notepad 2.Adobe Reader...

Recursive solution doesn't iterate correctly

ruby,algorithm,search,recursion
I'm working through a toy problem in Ruby: how to produce all possible 10-digit phone numbers where each successive number is adjacent to the last on the keypad. I've represented the adjacent relationships between numbers, and have a recursive function, but my method isn't iterating through the whole solution space....

Methods to sample a 2-dim curve efficiently

algorithm
I would like to ask for an efficient method / algorithm to sample a 2-dim curve with the following criteria. The curve is guaranteed not to cross itself. The number of points should be minimized; The sample curve, which connects all the sample points together with lines, should resemble the...

Need of backtracking in Knight’s tour

java,algorithm,backtracking
Why we need backtracking for The Knight’s tour problem? Can we do it by using only recursion? i have tried to do it but it give wrong answer and i am not able to figure out where code or logic goes wrong. import java.util.*; public class Solution { public static...

Flatten out a list in java

java,algorithm,list
I was asked this question in an interview Given a hypothetical list in java that, along with holding integer content, may also hold another list of similar type Example: [1,3,5,[6,7],8,9,10,[11,13,15,[16,17,[18,19]]],20] Output should be: [1,3,5,6,7,8,9,10,11,13,15,16,17,18,19,20] Easy I thought! So i came with a recursive solution that solved the problem! Or not?...

Find the number of disjoint sets

c++,algorithm,data-structures,disjoint-sets,disjoint-union
For those not familiar with Disjoint-set data structure. https://en.wikipedia.org/wiki/Disjoint-set_data_structure I'm trying to find the no. of groups of friends from the given sets of friends and their relationships. Of course, there is no doubt that this could easily be implemented using BFS/DFS. But I choose to use disjoint set, I...

How to place 100 different files on 20 file systems?

algorithm
I have 20 file systems of: /fs01 /fs02 /fs03 ... /fs20 in my Unix environment. Each of these file systems, contains some free space, which I can use for saving files. These file systems are independent of each other, and each contain a different amount of free space. I have...

I don't understand the statement of the exercise given at the admission exam at the Faculty of Computer Science from Bucharest [on hold]

c,algorithm
Given the problem: The statement is a bit ambiguous. I don't really understand what they want. I can display the desired result using just a regular for loop: int step = 0 for(int i = 1; i < m + 1; i++) { if(i != p) { printf("(%d, %d)", step,...

testing dynamically created strings

javascript,algorithm,comparison,func
what i have now is a function that return an array of 2 string that were put together using a random number generator. those values will help make up a string like "this is" + v1 + " and this is" + v2. v1 and v2 are the dynamically created...

How to slice or separate integer numbers and assign them to different variables

c#,algorithm
For example, if I have a variable: uint version = 001001020; This version has 9 digits, and I want to divide them up to 3 variables. the first variable will have 001 the second variable will have 001 and the third variable will have 020 I tried using slice like...

partition recurrence relation understanding

algorithm,recurrence,recurrence-relation
Determine if there is a subset of S that sums to floor(N/2) floor. Given S = {3,1,1,2,2,1}, a valid solution to the partition problem is the two sets S1 = {1,1,1,2} and S2 = {2,3}. Let: p(i, j) be True if a subset of {x1, ..., xj} sums to i...

Power by squaring for negative exponents

c,algorithm,math,recursion
I am not sure if power by squaring takes care of negative exponent. I implemented the following code which works for only positive numbers. #include <stdio.h> int powe(int x, int exp) { if (x == 0) return 1; if (x == 1) return x; if (x&1) return powe(x*x, exp/2); else...

When calling a recursive function to order values, it misses one. How do I fix this?

python,algorithm,function,recursion
I have a recursive function that reads a list of scout records from a file, and adds then in order of their ID's to a list box. The function is called with addScouts(1) The function is below: def addScouts(self,I): i = I with open(fileName,"r") as f: lines = f.readlines() for...

top-down community detection in a network

algorithm,social-networking,igraph
I'm trying to find a way to find network communities in a top-down way. Most of the algorithms available (e.g. in the igraph package) are working bottom up - that is they start by assuming all nodes are singlton communities, and then combine them to larger communities. I want to...

Algorithm for [inclusive/exclusive]_scan in parallel proposal N3554

c++,algorithm,parallel-processing,c++14
Proposal N3554 (A Parallel Algorithms Library) for C++14, proposes (among other things), what seem to be parallel versions of the current std::partial_sum, e.g.: template< class ExecutionPolicy, class InputIterator, class OutputIterator, class BinaryOperation> OutputIterator inclusive_scan( ExecutionPolicy &&exec, InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op); With the explanation Effects: For each...

How to find the maximum number of pairs having difference less than a particular value?

c++,algorithm
I am given two arrays (can contain duplicates and of same length) containing positive integers. I have to find the maximum number of pairs that have absolute difference less than equal to a particular value (given) when numbers can be used only once from both the arrays. For example: arr1...

Interview Ques - find the KTHSMALLEST element in an unsorted array

algorithm
This problem asked to find k'th smallest element in an unsorted array of non-negative integers. Here main problem is memory limit :( Here we can use constant extra space. First I tried a O(n^2) method [without any extra memory] which gave me TLE. Then i tried to use priority queue...

Getting Wrong Answer in “Longest non regular parentheses sub-sequence ”codechef june cook off

algorithm
I attended a programming competition(it has ended now). I don't know why my solution is giving WA, I read the editorial, saw other people solution but unable to find a flaw in my solution. Obviously I am missing somewhere. Please help! Question Link My Solution My approach If the pattern...

PHP: how to print $page / $total_pages in each page without knowing $total_pages?

php,algorithm,static-variables
Supposed we have a lengthy report to export, at each page's bottom we print Page: $current_page / $total_pages Problem is $total_pages is not easy to pre-count as more pages can be generated dynamically during file export. What is your approach? Thank you!...

Python algorithm error when trying to find the next largest value

python,algorithm,file,output
I've written an algorithm that scans through a file of "ID's" and compares that value with the value of an integer i (I've converted the integer to a string for comparison, and i've trimmed the "\n" prefix from the line). The algorithm compares these values for each line in the...

Issue with sorting algorithm - VB

vb.net,algorithm,sorting
I've been struggling with this algorithm below. It is supposed to loas the times inputted from eight textboxes into an array (txtTD1, etc). It then sorts them, and assigns each a numeric rank, which is displayed to the user (in txtR1, etc). Dim timeArr(0 To 7) As String timeArr(0) =...

Use Recursion to get Subsets of an array. C++ and Java give me different results

java,c++,algorithm,recursion,dfs
For example, given a set like below - S=[1,3] we want to get the list of list with following values: [[],[1],[3],[1,3]] I used C++ with the following code and it worked perfect for me. However, after I changed it to Java, the code didn't give me right results. Any help?...

Calculating the next higher number which has same number of set bits?

c++,algorithm
A solution is given to this question on geeksforgeeks website. I wish to know does there exist a better and a simpler solution? This is a bit complicated to understand. Just an algorithm will be fine. ...

Update bits error on one testcase

java,algorithm,bit-manipulation
Given two 32-bit numbers, N and M, and two bit positions, i and j. Write a method to set all bits between i and j in N equal to M (e g , M becomes a substring of N located at i and starting at j) Example Given N=(10000000000)2, M=(10101)2,...

Update minimum spanning tree if edge is removed

algorithm,graph,tree,runtime,big-o
I am having trouble with the following question: Assume we have already found a minimum spanning tree T for a weighted, undirected graph G = (V,E). We would like to be able to efficiently update T should G be altered slightly. An edge is removed from G to produce a...

Lengths of cycles in random sequence

c#,arrays,algorithm,random,cycle
The following LINQPad code generates random sequence of unique integers from 0 to N and calculates the length of cycle for every integer starting from 0. In order to calculate cycle length for a given integer, it reads value from boxes array at the index equal to that integer, than...

(Algorithm) find nodes having single path to reach from one node to other

java,algorithm
I wanted to know fastest algorithm for finding nodes have only path from one node to other nodes. these nodes are represented in string like this: String path = "({A,B,C,D,E,F},{(A,C),(B,C),(C,E),(B,E),(B,D),(E,F)})"; Output should be like this: output = {(A,C),(B,D),(E,F)} I tried split() method but its an long procedure I would greatly...

strcmp performance in C

c,string,algorithm,data-structures
int myStrCmp (const char *s1, const char *s2) { const unsigned char *p1 = (const unsigned char *)s1; const unsigned char *p2 = (const unsigned char *)s2; while (*p1 != '\0') { if (*p2 == '\0') return 1; if (*p2 > *p1) return -1; if (*p1 > *p2) return 1;...

An example of finding the longest path in DAG with both positive and negative weights

algorithm,directed-acyclic-graphs
I read that Critical Path Method uses the longest path method with positive weights and it is used for scheduling a set of project activities (time values must be positive). In my case I need to find the longest path in DAG with both positive and negative weights. What can...

Can anyone improve on the below Fuzzyfind function for VBA?

algorithm,vba,function,find,fuzzy-search
This function lets you find similar strings from a range without having to do an exact search. The formula looks like this: =FuzzyFind(A1,B$1:B$20) assuming the string you are performing a search for is in A1 and your reference or options table is B1:B20 The code is here: Function FuzzyFind(lookup_value As...

create specific permutation of a list in python [closed]

python,algorithm,permutation
I'm trying to write a function that would input a list (of pre-determined length) and output the permutation of that list according to my choice of re-ordering. For example, suppose I have the list [1,'a',12,'b','poppy'] and I have the permutation (3,4,5,2,1) Then the function output would be a list with...

Recursive algorithm that returns a bool when checking if array[i] == i (must be O(log n))

c++,arrays,algorithm,recursion
I'm trying to write a recursive algorithm that returns true if at least one array[i] == i. And false if there is no array[i] = i. Also, the parameters needed are (int * arr, int start, int end). So i'll be traversing the array with a pointer. For example: int...

Count of an element in a matrix using Divide & Conquer

c++,algorithm,matrix,divide-and-conquer
I'm starting to learn how to implement divide and conquer algorithms, but I'm having some trouble with this exercise. I have written an algorithm but unfortunately it returns a 0 value. I need to count how many times a number finds in the matrix using D&C. My idea is to...

Given a sorted array and a parameter k, find the count of sum of two numbers greater than or equal to k

c++,arrays,algorithm,sum
I tried to find all pairs in the array with sum equal to k, the solution to that takes O(n*log(n)) time. Here is the code snippet - map<int,int> mymap; map<int,int>::iterator it; cin>>n>>k; for( int i = 0 ; i < n ; i++ ){ cin>>a; if( mymap.find(a) != mymap.end() )...

Vector Merge Algorithm C++

c++,algorithm
Having a hard time designing an efficient algorithm that accomplishes the following. If I start with a 2d vector A, A = [1 2 3; 2 3 4; 5 6] I want to take the rows that contain common elements and combine them (removing duplicates) resulting in 2d vector B:...

3 X 3 magic square recursively

c++,algorithm,math,recursion
I'm trying to find all possible solutions to the 3X3 magic square. There should be exactly 8 solutions. My code gets them all but there are a lot of repeats. I'm having a hard time tracking the recursive steps to see why I'm getting all the repeats. // This program...

Basic Python code not Working

python,algorithm,data-structures
I am newbie to Python. Here is my Code that implements binary search to find the guessed number .I cant figure it out correctly how to make my code work. Any help would be appreciated. Thanks. print"Please think of a number between 0 and 100!" guessed=False while not guessed: lo=0...

Unable to understand the hash function of Rabin Karp Algorithm explained at topcoder

algorithm,hash,rabin-karp
I was reading the Rabin Karp Algorithm at Topcoder. But in that article, I am not able to get the following hash evaluation. // calculate the hash value of the first segment // of the text of length m ht = 0; for(i = 0; i < m; i++) ht...

How to Scatter Elements of a Ruby Array?

arrays,ruby,algorithm
I have an array of elements, which have a common attribute and are sorted by this attribute. Now, I want to achieve the opposite effect: interleave elements with the same attribute value as much as possible. [ {a: 1}, {a: 1}, {a: 2}, {a: 2}, {a: 2}, {a: 3}, {a:...

Using IEnumerable.Except on KeyCollection vs. exploiting Dictionary.ContainsKey for mutual subtractions and intersection in relation to performance

c#,algorithm,dictionary
I have two dictionaries Dictionary<string, object>. I need to find their intersection (I mean only their keys intersection) and A\B and B\A subtractions and make some actions to the objects (in fact my objects are EntityFramework entities and I have to mark their state as Modified, Added and Deleted respectively,...

How to generate all partitions of a set

algorithm,set,combinatorics,backtracking
For a set of the form A = {1, 2, 3, ..., n}. It is called partition of the set A, a set of k<=n elements which respect the following theorems: a) the union of all the partitions of A is A b) the intersection of 2 partitions of A...

How can I declare a counter inside of my recursive function? (Additive Persistence: Coderbyte)

javascript,algorithm,recursion
While working through some Coderbyte challenges, I was able to solve the following problem recursively, but was hoping to get some feedback on how I can improve it. Have the function AdditivePersistence(num) take the num parameter being passed which will always be a positive integer and return its additive persistence...

When adding a random edge to a graph, which bridge edges are not bridge edges any longer?

algorithm,graph,graph-algorithm
A random edge e is added to a graph. It happens to not be a bridge edge. Let C be the connected component of the endpoints of e. Given the list L of all the bridge edges of C (before e was added), which is the fastest algorithm to find...

Using Master theorem to calculate asymptotic time complexity of algorithm

algorithm,time,complexity-theory,master,theorem
Problem: You have an algorithm that divides n size problem to six subproblems with size of one quarter of the original. For dividing the algorithm makes 100 steps and for merging 75n. What's the time asymptotic complexity of an algorithm? So the formula for Master Theorem and for this problem...

Reverse ^ operator for decryption

c,algorithm,security,math,encryption
I'm trying to reverse the following code in order to provide a function which takes the buffer and decrypts it. void crypt_buffer(unsigned char *buffer, size_t size, char *key) { size_t i; int j; j = 0; for(i = 0; i < size; i++) { if(j >= KEY_SIZE) j = 0;...

Longest Increasing Subsequence code in O(N)?

python,algorithm,time-complexity,longest-substring
Someone asked me a question Find the longest alphabetically increasing or equal string composed of those letters. Note that you are allowed to drop unused characters. So ghaaawxyzijbbbklccc returns aaabbbccc. Is an O(n) solution possible? and I implemented it code [in python] s = 'ghaaawxyzijbbbklccc' lst = [[] for i...

Should checking loop conditions be counted towards total number of comparisons?

c++,algorithm,sorting,c++11
I have implemented three different sorting algorithms and now I want to confirm that my approach of counting the total number of comparisons is correct. In my mind, the number of comparisons shouldn't be tied to the conditional branches because if the condition isn't met, the comparison was still made...

Travels using graph

c++,algorithm,graph
Someone can help me to think in the better way to adapt Dijkstra's Algorithm in these conditions? All I thought didn't was good. Example of input: GP4578 MADRID 01:00 PORTO 02:00 IK6587 PORTO 03:00 VALENCIA 05:00 05:30 TENERIFE 08:00 AB5874 VALENCIA 05:40 BERLIM 10:00 "VALENCIA 05:00 05:30" This is a...

What is this algorithm mapping coordinates to numbers called?

algorithm,coordinates,coordinate-systems,coordinate
I'm writing a program for visualizing crystals. As a part of the program, I have to generate all different basic points in a lattice structure. For those that aren't familiar with crystallography, you can find the most general cases of these structures here: https://en.wikipedia.org/wiki/Hermann%E2%80%93Mauguin_notation#Lattice_types The problem was that I wanted...

Find & count occurrences of certain words matching text/string/paragraph (most efficient way)

php,regex,algorithm,compare,pattern-matching
I have a Paragraph that I have to parse for different keywords. For example, Paragraph: "I want to make a change in the world. Want to make it a better place to live. Peace, Love and Harmony. It is all life is all about. We can make our world a...

Remove smallest non-unique value from vector

c++,algorithm,c++11,unique
I have an unsorted vector of doubles (Actually objects with a double member which is used in this case). From this vector I need to remove the smallest non-unique value. However, it is not guaranteed that a non-unique value exists. It is allowed to sort the range. As always I...

Does there exist an algorithm for iterating through all strings that conform to a particular regex?

c#,regex,algorithm
I'm making a script to try and hack into an account whose login password is at least 8 characters long and includes at least 1 number, 1 special character and 1 capital letter. I will use brute force. Is there a compact, elegant and efficient way to iterate through every...

B-Tree deletion in a single pass

algorithm,tree,b-tree
Is it possible to remove an element from a B-Tree in a single pass? Wikipedia says "Do a single pass down the tree, but before entering (visiting) a node, restructure the tree so that once the key to be deleted is encountered, it can be deleted without triggering the need...

Calculating the percent overlap of two polygons in JavaScript

javascript,node.js,algorithm,geojson,topojson
Here's the problem: I have geoJSON and topoJSON files that give me the polygons for Census block groups and voting precincts. I'm trying to see by how much a given Census block group overlaps with a given precinct. I've seen a couple examples of what I'm after in other languages—i.e....

Hungarian algorithm in PHP with multiple assignments

php,algorithm,assign,subgraph,pairing-heap
In the following we are facing the problem of multiple assignments of the hungarian algorithm. Scenario: We have 100 students and 5 courses, which the students can vote with priority. So every student will get assigned for one specific cours. Priority from 1 to 5. 1 lowest 5 highest The...

Looking for a particular algorithm for numerical integration

algorithm,numerical-methods,numerical,numerical-integration
Consider the following differential equation f(x) = g'(x) I have a build a code that spits out values of the function f(x) for the variable x, where x goes from 0 to very large. Now, I'm looking for a scheme that will analyse these values of f(x) in order to...

Knapsack with unbounded items

algorithm,dynamic-programming,knapsack-problem
I am familiar with the 0-1 knapsack problem and when you are given a certain number of copies from each item but I can figure out how to solve it when you are given infinite copies of each item using dynamic programming. I am trying to solve it by hand...

Project Euler # 5; this solution works - but why?

c++,algorithm
The project Euler problem 5 is stated as : "2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?" Here's...

Removing a prior sample while using Welford's method for computing single pass variance

algorithm,math,statistics,variance,standard-deviation
I'm successfully using Welford's method to compute running variance and standard deviation as described many times on Stack Overflow and John D Cook's excellent blog post. However in the stream of samples, sometimes I encounter a "rollback", or "remove sample" order, meaning that a previous sample is no longer valid...

Datastructure related. Find all arrays elements greater than or equal to given input

java,algorithm,data-structures,graph-algorithm
I have a long sequence of order amounts, 1000, 3000, 50000, 1000000, etc. I want to find out all orders whose amount is more than 100000. Simplest solution can be iterate through full list and compare and put matched on into another list which will give you all whose amount...

Heuristic to find the maximum weight independent set in an arbritary graph

algorithm,graph,graph-algorithm,linear-programming,np-complete
The MWIS (Maximum weight independent set) is a NP-complete problem, so if P!=NP we cannot find a solution in a good enough time complexity. I am looking for an algorithm that can find an approximation of the MWIS in an arbitrary graph within a good time complexity. I am currently...

How to check whether the letters of a string exist in the given order within another string?

c++,algorithm
I'm trying to make a program to check whether the word "nadia" is present with this sequence in a string. if you can delete zero or more characters to get this word then you should print "YES" else print "NO". Can anyone help me find what are the test cases...

Ranking with time weighting

python,algorithm,sorting,math
I am looking for a basic algorithm that gives more weigh to the recent reviews. So, the output value of the algorithm is mutable. For example, two reviews with exactly the same score, will have a different ranking based on the timestamp of the creation. Review_1 Score 10 creation 10/5/2014...

Find root of minimal height which is not BST

algorithm,data-structures,tree,binary-tree,binary-search-tree
I'm struggling with following problem: Write function which for given binary tree returns a root of minimal height which is not BST or NIL when tree is BST. I know how to check if tree is BST but don't know how to rewrite it. I would be grateful for an...