Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Algorithms for finding an element in some specified data-structure (most commonly, in a tree).

1
vote
0answers
9 views

How to use HITS algorithm to rank pages

I am trying to implement a simple web search engine mechanism with using HITS algorithm. I understand how the algorithm work and produce hubs and authority values for each page. But how can I use this ...
1
vote
0answers
19 views

Complexity of bisection method for finding an interval

Let $f$ be a continuous function and $[a,b]$ be an interval where $f(c)=0$ for some unique number $c \in [a,b]$ and where $f(a) f(b) \leq 0$. Suppose there exists a sub-interval $[a_0,b_0]\subset [a,b]...
0
votes
0answers
13 views

Data structure for fixed sized records that only need to support full scans

Background I'm building a memory-mapped inverted index for document search. The inverted index stores (docId, tokenId) pairs, and the whole memory-mapped file is divided into blocks. A block has a ...
2
votes
0answers
24 views

Find combination of array elements that exceed maximum array element

Say I have an array of integers like so: [2,2,3,5,5,5,5,6,6,7,7,7,7,9,10] I'd like to find all combinations of these values that when summed exceed the maximum (in ...
2
votes
1answer
20 views

Nearest Neighbor Search in Spherical Coordinates

I am familiar with k-d trees being used to find nearest neighbors (NN) in 3-D euclidean space however in my particular case I am given a huge array of spherical coordinates. Due to accuracy ...
1
vote
1answer
38 views

KMP - longest palindromic prefix

I wanted to ask if there is a way to use KMP (Knuth-Morris-Pratt) algorithm to find the longest palindromic prefix of a word. I've seen this algorithm used for determining if a word is rotation of ...
0
votes
1answer
36 views

Visit all vertices of a graph

I need to find the fastest route passing in all vertices Each vertex is a class. I can choose the number of classes for semester. Some classes have prerequisites (A and B need to be done one semester ...
1
vote
1answer
48 views

Algorithmic Design to Undo Rotation of Array

An array $A$ of $n$ distinct, ascending integers is rotated to the right by $k$ positions, resulting in the array $A_{k}$. That is, the element at index $i$ in $A$ is moved to index $(i+k)\mod n$ in $...
3
votes
2answers
48 views

Optimization Problem when calculating fitness is expensive

I need to solve an optimization problem, maximizing fitness in a set of around 1 million solutions. Calculating the fitness of any solution is very time consuming, taking around 5 minutes. Therefore, ...
1
vote
0answers
24 views

Finding non-overlapping combinations of spans/bitarrays

My first post here so please correct me if my terms are off or needs clarification. Suppose I have several sets of lists of spans. I define a span as a pair of indexes: begin and end index in a ...
1
vote
1answer
27 views

Duplicate elements in Queue for BFS Maze Algorithm

I'm fairly new to studying data structures and algorithms. I've implemented a non-recursive BFS on a 2d "maze array" which seems to work well. It finds the position of 2 in an array of 1s (walls) and ...
0
votes
1answer
71 views

Babyface vs Heel

So here's the question: "There are two types of professional wrestlers: "babyfaces"("good guys") and "heels"("bad guys"). Between any pair of professional wrestlers, there may or may not be a rivalry. ...
0
votes
2answers
68 views

A data structure to do a specific lookup fast

I have 30,000 items; each item has 30 parameters that take values from 0 to 5. These parameters are named $p_0$ to $p_{29}$ and their value is an integer between 0 and 5. I want to store these items ...
0
votes
0answers
16 views

Search techniques to find desired output with complex interdependencies

I am trying to generate output consisting of three-tuples (A,B,C), where A,B, and C are three different datatypes representing different values. I also have a collection of functions $f_i \in F$ ...
0
votes
0answers
36 views

Prove lower bound of searching algorithm on Young Tableau

I want to prove the search of an element in a Young tableau of size $n\times n$ is $\Omega(n)$, but I do not have any clue. Any help is appreciated!
2
votes
1answer
38 views

Understanding Alpha Beta Pruning: Why do we ignore the values of a unsearched tree after the first leaf, can they not include acceptable values too?

So this is my question. I am trying to understand this part of the book: At d) why do we stop looking at the other nodes in that branch? There could be a acceptable value next to the 2? I am just ...
4
votes
1answer
44 views

Subgraph isomorphism on star multi-graphs with labelled edges

My approach to the problem has been to reformulate it into something more recognizable, but I don't know the best way to solve the reformulated problems either. I list the original problem, an example,...
2
votes
2answers
48 views

How to graph search a LTL-generated Buchi automaton to generate valid execution paths

I have a set of tasks, and a LTL specification that describes which orders of the tasks are legal. I want to find a way to enumerate all permutations of the tasks that meet the specification. For ...
1
vote
0answers
32 views

What is the meaning of the “*” in names of various learning/search algorithms?

For example, consider L* algorithm for learning a regular language, or A* search algorithm. What do these names - in particular, the star character - mean? It looks like it might be the case that the ...
1
vote
1answer
23 views

Find an edge that is completely visible from point outside a polygon (Convex Hull)

I want to implement algorithms from this paper: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.56.5609&rep=rep1&type=pdf In particular, I am currently dealing with the one in ...
1
vote
1answer
66 views

Time complexity of transforming one string to another

Here is the problem: Given a dictionary $D$ and two strings $s$ and $t$, write a program to determine if $s$ produces $t$. If it does produce $t$, output the length of of the shortest production ...
1
vote
1answer
38 views

Understanding Binary Search for Kth Smallest element in an Array

The Answer here shows a way to solve the problem with O(1) space. The approach uses Binary Search. I am finding really hard to wrap my head around why it works. I get why we did low + (high-low)/2 ...
2
votes
1answer
18 views

Efficient membership check in multiple ranges

Suppose a program has a set $S$ of $n$ numerical ranges, each described by a pair: (lower bound $l_n$, upper bound $u_n$). The program receives a number $x$; it must return all ranges in $S$ that ...
1
vote
1answer
18 views

Justification behind this heuristic in SMA*+

I'm reading the paper Enhanced Simplified Memory-bounded A Star (SMA*+). In short, the authors propose a limited-memory version of A* where we cull nodes if we are out of memory, to re-expand them ...
4
votes
2answers
34 views

Find the fastest duration for a certain distance in a walk

I apologize in advance if the wording of my problem is inappropriate for this forum. Or if another platform i more suitable for it. I'm new here and typically do not have to solve complex algorithmic ...
1
vote
0answers
114 views

Feeding real-time data and binary search algorithm termination

This question was asked in our exam long a go and I don't remember exact words. The scenario was, Initially you are given a set of finite data to start with, and a key value (which you have to find ...
0
votes
0answers
25 views

Minimal search endpoints?

Assume that for each building in a city there is a known subset of the city's buildings that can be seen from that building (being in a building counts as "seeing a building" as well so for every ...
0
votes
0answers
37 views

Find optimal path in BFS and DFS

In UCS it is clear that we find the cheapest cost path. In BFS and DFS we can get the order of output nodes. But How can we find the optimal path in BFS ans DFS in following cases?
1
vote
1answer
36 views

How many queries does it take to find the best flight?

I often find flights through a search engine like Google Flights. On input some refined subset of the space of all flights (e.g., non-stop only, departing in the morning, from one of two airports, and ...
0
votes
0answers
25 views

Generation vs expansion BFS

I can not understand the difference between generation and expansion of nodes. How the time and space complexity of BFS are different in each two scenarios? ...
2
votes
1answer
61 views

Variant of nim game with particular rules

Let's say we have the following rule for that particular Nim game: You have multiple heaps, and you have to remove 1,2 or 3 sticks (not more) from a SINGLE choosen heap. The player who pick up the ...
0
votes
1answer
295 views

Find all local minima in a big 2d array

Assume we have a big 2d array. All its elements are either zeros or natural numbers. A local minimum is an element that is less than all its 8 neighbors. Is there an effective algorithm to find all ...
1
vote
1answer
22 views

Better algorithm for aggregating data from various LDAP systems

I have 10 LDAP systems which contain users and groups in the form of objects. Each user / group is identified by a distinguishedName like ...
0
votes
0answers
30 views

Fuzzy, nonsequential string search algorithm?

Is there an algorithm that can find p + stuff within t, where stuff is any set of characters,...
2
votes
0answers
28 views

Avoiding collisions in space and time

Say I have an image, represented as a 2D array of pixel values. Also, say I have a set of points on that image where each has a current (x, y) position and a Destination (x, y) associated with it. I ...
0
votes
1answer
22 views

The optimal way to find leaves in a weighted full binary tree

Let T be a full binary weighted tree. For a node v in T, the cost of going right is a i.e w(v, v.right) = a while w(v, v.left) = b How do I find optimal paths to all leaves from the root. I don't ...
2
votes
1answer
64 views

Average-case analysis of linear search given that the desired element appears $k$ times

The problem below is adapted from CLRS Problem 5-2 "Searching an unsorted array": Consider a deterministic linear search algorithm which searches an array $A$ for $x$ in order, say $A[1], A[2], \...
4
votes
0answers
45 views

Efficient approximation for find all the nodes and edges which match with some sub-tree in a graph

Let's suppose that I have a big digraph D and a small tree T (small w.r.t D), both directed, D can be connected or not, but T is connected. Here an example: Let's say that D is as follow: And T is ...
2
votes
2answers
103 views

Infix search in millions of strings

Let's say we have millions of strings (each of them < 100 characters): alpha allo blah hello world orlando ... I know how a binary search tree or a trie can ...
2
votes
1answer
49 views

Fastest way to search a word in a word list?

I have a word list like "English Open Word List" used to create word games. The list is in txt file with space between words, like; aa aah aahed .........and so on. I want to search it while typing ...
1
vote
0answers
27 views

Do we need visited flags when applying BFS on a tree?

Do we need visited boolean flags when applying BFS on a tree ? ...
2
votes
0answers
190 views

How to traverse a graph in reverse dfs order

For kosaraju's algorithm to traverse the graph in reverse order the naive solution is to reconstruct the original input graph in reverse order and dfs on it. Is there any way I can avoid creating ...
0
votes
1answer
30 views

Algorithm to find a shortest past under a special condition

I am trying to come up with an algorithm that calculates the length of shortest rectangle movement in a given bitmap. For example, let's say we have a 24x24 bitmap where 1 is black pixel and 0 is a ...
2
votes
1answer
53 views

Local search (Hill Climbing) scope and definition

I'm taking an artificial intelligence class and in one of the recent lectures the topic was local search algorithms, more specifically Hill Climbing. At one point the professor showed the classic 8-...
0
votes
1answer
214 views

How to calculate number of nodes opened by BFS?

In the below diagram, each node takes up a space of 2KB. I need to find the total memory consumed to reach the goal : I I know that the equation for BFS is b1 + b2 + ...... + (bd+1 - b) Where b is ...
1
vote
1answer
29 views

data structure admitting top items with prefix

A trie can answer a query for all items with a certain prefix in $O(m + \log n)$ time, where $m$ is the number of matches and $n$ is the number of items. A trie also supports $O(\log n)$ insertion and ...
-1
votes
1answer
16 views

Count points on same distance from set of points

Let's consider finite grid of points with size of $N$ by $M$ and set of $x$ points ($x$ is small number, up to 10, $N$ and $M$ are big numbers, up to 30000 )). Each of the $x$ points is described with ...
1
vote
1answer
31 views

Thompson Regular Expression Search Algorithm 3rd Stage

My professor assigned us to read Thompson' Regular Expression Search Algorithm paper. I am struggling to understand the third stage of the compiler. The first two stages are as follows: Check that ...
4
votes
0answers
32 views

Any elegant approach to search where users have permissions on subset of records?

I work in Search and have seen following problem appear in different forms. There are many users in an enterprise; they have ability to create records. Each user has variable level of access to some ...