I have the following problem as homework: Write a O(N^2) algorithm to determine whether the string can be broken into a list of words. You can start by writing an exponential algorithm and then using dynamic programming to improve the runtime complexity. The naive exponential algorithm which I started out wit…
Tag: algorithm
A* search algorithm implementation in python
I am trying to build a very simple A* Search Algorithm in Python 3. Given the following distances for each node (considering S is the starting node and G the end one) I want to write a function that finds the best path based on total cost (i.e., f(n) for those familiar with the terminology) for the following …
Longest common substring in a text that is inside a list of strings
I’ve come across a problem that similar to the Longest Common Substring problem but with a modification. It’s as follows: A list of strings lst and a string text are provided. The string may or may not contain substrings that are present in the list. I need the first longest substring of text that…
Length of the intersections between a list an list of list
Note : almost duplicate of Numpy vectorization: Find intersection between list and list of lists Differences : I am focused on efficiently when the lists are large I’m searching for the largest intersections. Here are some assumptions: y is a list of ~500,000 sublist of ~500 elements each sublist in y i…
Python: Not being able to compare radians with pi values
I am writing an algorithm which should be able to determine in which quadrant a radian is based on two values that the user inputs. I think that the code is calculating the radian but I know that those values are not being compared to the pi values that I gave since I am not getting any output. Code below:
How to write a text parser logic which identifies keywords from a dictionary?
How to make a simple text parser that finds keywords and categorizes them accordingly. Example: I have two dictionaries Now I want to pick out if the keywords from A are present in B and the result should be something like this. I’m a beginner and the logic to get this is very confusing. Answer You can …
Select n items from a set of subsets [closed]
Closed. This question needs details or clarity. It is not currently accepting answers. Want to improve this question? Add details and clarify the problem by editing this post. Closed 1 year ago. Improve this question I’m wondering if there exists an algorithm that can solve this problem: Suppose you hav…
How can I efficiently find distances from each value to the next lower/higher value?
I’ll tell you what structures I am using, please feel free to recommend any changes like numpy arrays or something. Anyways what I have is a list of 5 million sequential entries that correspond to a stock price. I then have 2 more lists, each of these is the same length – 5 million entries. These …
The most efficient way to sum all possible pairs (x_ik, y_j) for a given k?
I have two numpy array x with shape (n,m) and y with shape (p,). I would like to sum all possible pairs x[k, i] and y[j] to create a new numpy array z with shape (n, m*p). A naïve algorithm would be : This algorithm has a polynomial complexity : O(n*m*p) Knowing I am working on array with $n ~
For Dijkstra’s algorithm, what would be a way to keep track of and store the vertices that each shortest path contains?
I have it coded it out to update all the costs of the edges and such to complete Dijkstra’s main goal of finding the shortest path from the source vertex to all other vertices. But I what I need help on is figuring out a way to store the vertices that each shortest path contains into an array that conta…