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

Questions tagged [algorithms]

An algorithm is a sequence of well-defined steps that defines an abstract solution to a problem. Use this tag when your issue is related to design and analysis of algorithms.

0
votes
0answers
31 views

Minimal hashing function for integers that satisfy specific constraints

I'm looking for a kind of way to create a minimal perfect hash function given a set known integers. More specifically, I have M numbers within the range 0-N with N > M. Does it exist a way to create ...
0
votes
0answers
17 views

How do you determine k in a k-gram index?

In information retrieval theory, k-gram indexes can be used for wildcard queries. I often see 3-gram examples, but if I were to build a system how would I choose $k$?
1
vote
1answer
78 views

Given max-flow determine if edge is in a min-cut

We were given an exam question of: Given a flow network G=(V,E) with integer edge capacities, a max-flow f in G, and a specific edge e in E, design a linear time algorithm that determines whether or ...
2
votes
1answer
24 views

NP-Hard on Complete Graphs

I have a problem (A) on undirected graphs that I wish to show is NP-Hard. I can show that there is a reduction from a well known NP-Hard problem (B) to A by constructing an instance of A with a ...
1
vote
1answer
20 views

Is there any better way to find the closest points' distance?

The problem is: Suppose you're given $n$ points in the coordinate plane, and for convenience assume that no two of their $x$ or $y$ coordinates are the same. Design an algorithm that finds the ...
0
votes
0answers
14 views

Trace (horizontal) lines in grayscale image

I have a grayscale image with some line in it, which I would like to trace. The first image shows a Black&White version of the image, and the send shows the image after a few morphological ...
1
vote
1answer
49 views

Gerrymandering Problem: Variant on Set Partitioning

I was recently helping a friend with homework from a dynamic programming class, and this was the question: Given a set of n precincts P1 ,... Pn , each containing m votes, with <...
0
votes
0answers
10 views

Determine the time complexity of code [duplicate]

I need to determine time complexity of the next code: j1=1 j2=1 for i=1 to n k=j1 while k<=j2 s=s+j k=k+1 j1=j1+2i+1 j2=j2+4i+3 return s ...
2
votes
0answers
24 views

Given a set of point sets, find points from each set with maximum total distance between them while each distance is larger than a threshold

The title may be a bit confusing but the problem is this; Lets assume I have 5 points in 4 groups (in total 20 points). What I want to achieve is; -> Pick one point from each group (we will have 4 ...
2
votes
0answers
37 views

Card dealing problem with constraints (blacklisting),

A friend of mine and I are trying to teach a bot play a card game (bela) We are using monte carlo tree search (MCTS) to estimate the probability of winning hand in regards to multiple possible (!...
0
votes
0answers
11 views

Hit-and-run stucks near edge/corner of polytope

I try to generate random points within a convex polytope. Hit-and-run sampling can get stuck near the edge and corner of a polytope if I use a moderate number of steps. A point at the corner has ...
0
votes
0answers
35 views

Family of graph with Approximation ratio = 2

My question today is about the approximation algorithms. Well, for Approx-Vertex-Cover problems , we know we can get ratio of 2 just by picking an edge and taking 2 endpoints of the same and ...
2
votes
1answer
51 views

Largest rectangle problem

Recently while solving programming challenges for the fun of it, I encountered a challenge which left me kind of puzzled and yearning for a proper solution, other than brute forcing. The problem (...
0
votes
0answers
32 views

Maximizing score of partitioning of table

Consider a table where the cells are Boolean values and rows & columns are positive integers. \begin{array}{|c|c|c|c|c|c|c|} \hline & a_1 & a_2 & a_3 & a_4 & \dots & a_n \\...
0
votes
1answer
26 views

My code works, But how do I make this code run in a deterministic time?

The Problem: Given 3 inputs Bounce, Ball drop height, and ball view height. How do I calculate the number of times the observer can see the ball pass. So my code gives correct output, but it takes ...
2
votes
0answers
20 views

Tail recursion can't work with dynamic programming programs

I am doing some exercises on dynamic programming in order to get familar with this concept. I've noticed that most of the time it's not difficult to calculate the complexity of a program using dynamic ...
3
votes
1answer
60 views

Christofides algorithm (by hand)

I am following this algorithm example: https://en.wikipedia.org/wiki/Christofides_algorithm#example The graph: [![enter image description here][1]][1] ...
0
votes
1answer
39 views

“Ways to make change for a dollar”: How to optimize with constraints

I'm working on an algorithm that takes a number of unit coins ([1, 2, 5, 10] for example) and a certain amount of money (13 in this case), and figures out how many ways there are to provide change for ...
0
votes
0answers
17 views

Misunderstanding of Memoization definition

My professor is saying we will not use memorization for this course See this link at 0:20 https://youtu.be/IuI1RbJ0QuM?t=20 But this Wikipedia page https://en.m.wikipedia.org/wiki/...
1
vote
1answer
22 views

DES encryption - what happens if all sub-keys are the same?

What will happen if we change the DES encryrption algorithm to use the same key in each round ? How will it affect the encryption - will it only make the encryption same as decryption or are the more ...
1
vote
0answers
12 views

Task assignment problem with capabilities and time restrictions

I have the following optimalization problem. I use the notations below because maybe it would be easier to understand that way, but I'm not good at conventions – I'm not sure if I'm using it all the ...
0
votes
1answer
17 views

Lempel-Zilv-Welch Algorithm Decoding Question

Hello i am studying about LZW algorithm by watching this video: https://www.youtube.com/watch?v=j2HSd3HCpDs&t=481s I couldnt fully understand decoding process. At current 258,how does 116 come at ...
1
vote
1answer
26 views

How to check if a given point is inside a polygon with holes?

How to check if a given point lies inside or outside a polygon with holes? Does the below algorithm works for polygon with holes? https://www.geeksforgeeks.org/how-to-check-if-a-given-point-lies-...
2
votes
1answer
49 views

Algorithm to find non-overlapping intervals that minimize standard deviation

I am looking for the name of an algorithm category, or even specific algorithms, that solve the following problem. I have noisy data. For simplicity, let this data be represented by numbers. I have ...
1
vote
0answers
16 views

Expected development of 'fitness histogram' for PSO over time

I'm plotting the fitness histogram of my particle swarm optimizer - i.e. the individual fitness scores for each particle and iteration - during a run. The problem tackled is basically curve fitting/...
1
vote
1answer
46 views

In this implementation of Hoare-partitioning Quicksort, why are additional checks for $i \leq j$ needed?

I am looking at the following implementation of Quicksort that uses Hoare partition scheme (two approaching indices $i$ and $j$ starting from either end of the array). I am having trouble seeing why ...
1
vote
0answers
31 views

How to design a LL(1) grammar for basic regular expression?

I try to design a LL(1) grammar to parse the basic regular expression. Here's the origin grammar.(\| is the escape character, since | is a special character in grammar's pattern). ...
2
votes
2answers
51 views

Can repeated runs of a Las Vegas algorithm equate to a better Las Vegas algorithm?

Let's say I have a Las Vegas algorithm $L$ for some problem $P$, which runs in $n^3$ steps with 50% likelihood. My friend asks me for an algorithm for $P$ that runs in $n^3$ steps with 75% likelihood. ...
0
votes
0answers
30 views

When to use which variant of the loop condition in binary search?

When solving a search problem with binary search, sometimes the loop condition is while low < hi and sometimes it is ...
0
votes
0answers
7 views

Robot Pac-Man algorithm

We're building a "robot pac-man" from Lego - only without ghosts. The robot has "radar", so he sees what's in front of him. The task is to collect the maximum points in a limited time. In more detail,...
1
vote
1answer
18 views

Chinese postman problem, but criteria = visit each vetex at least once

Chinese postman problem, but where the postman have to visit each vetex at least once. Is there a name for this problem? What is the ideal algorithm to solve this problem?
0
votes
0answers
27 views

If you have two recursive calls in a function and one terminates before the second how do you calculate the time complexity? [duplicate]

Suppose you have a function which calls to itself twice. So both go down recusively until they reach some condition. But one of them will go less times than the other. For example one would call ...
2
votes
0answers
13 views

What are some of the simplest applications of heavy hitter problem?

I am learning about stream algorithms and am implementing Count-Min sketch data structure. I am also learning to approximately solve the HH problem with sublinear space complexity. I want to know ...
1
vote
0answers
11 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 ...
0
votes
0answers
10 views

Counting rectangles in one big histogram

Let's say we have given array of $N$ integers which actually represent the height of a histogram, now for each rectangle with lower side at the base of the histogram we need to count how many elements ...
0
votes
0answers
23 views

Solving Recurrence relation using Master Theorem

There is a recurrence relation like $T(n)=mT(n/2)+cn^2$ To solve this recurrence relation I am using Master Theorem. As per master theorem here a = m, b = 2, k=2 ,p=0 So $b^k= 2^2 = 4$ Now, ...
1
vote
1answer
43 views

Checking if the graph provided by a distance matrix is a tree

I came across this problem in an online judge: We are given a distance matrix consisting of $N$ rows and columns. The $i$th line of $j$th row is the distance between node $i$ and $j$ (not necessarily ...
0
votes
0answers
25 views

Scheduling with minimum staffing requirements and preferences

I'm interested in the following scheduling problem: Time is divided in $T$ slots as represented by the left circle below (where $T = 8$). A minimum number of employees $b_t \geq 0$ need to be present ...
2
votes
1answer
45 views

Making a profit as a high-dimensional store owner?

Been thinking about a problem recently and I am wondering if anyone can comment on some ideas to make solutions to this problem more efficient. Let's say that I am some business owner with a set of $...
0
votes
0answers
79 views

Algorithms for elementary operations using other elementary operators

The question asks to provide an algorithm to compute $(i)$ The product of $n$-bit numbers using reciprocation operation and addition operation but not using multiplication and squaring. $(ii)$ The ...
0
votes
2answers
184 views

Quick Sort with first element as pivot

I'm studying Quick-Sort and I am confused as to how it works when the first element is chosen as the pivot point. I am trying to trace the first step in the Quick-Sort algorithm, to move the pivot S[...
0
votes
0answers
60 views

algorithm to find complementary spanning tree in dual graph

I have read from wikipedia, that for every spanning tree in a graph [primal] we have a spanning tree in the dual graph which consists of dual of the complementary set of edges [edges not used in the ...
2
votes
1answer
20 views

Design an algorithm for efficiently computing the k smallest numbers of the form a+b*sqrt(2)

Full question: Numbers of the form $a+b\sqrt{q}$, where $a$ and $b$ are nonnegative integers, and $q$ is an integer which is not he square of another integer, have special properties, e.g. they are ...
1
vote
2answers
163 views

Outputting numbers within a range that are not in a list

How could you design an efficient algorithm that uses the least amount of memory space and outputs, in ascending order, the list of integers in the range 0..255 that are not in a randomly generated ...
3
votes
1answer
155 views

Longest substrings of common length with the same parity

Given two sequences $a$ and $b$, find largest $x$ such that in $a$ there is substring $A$ and substring $B$ in $b$ meeting those conditions: length of both $A$ and $B$ is equal to $x$; sum of ...
0
votes
1answer
32 views

Possible to get the Sum x with maximal two summands? [duplicate]

Suppose we have $n$ different summands. Is it possible to get the sum x with a maximum of two of the $n$ summands (Below the m summands there can be several times the same one). For example you have ...
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]...
2
votes
1answer
14 views

Approximating unique string occurrences using a small, fixed amount of memory

Is there a small-memory way to estimate how many unique strings have been encountered without needing to know the strings themselves? The trick is that we only have a tiny amount of memory to track ...
-1
votes
1answer
65 views

Is there a name for this shuffle algorithm?

Is there a standard name for the following algorithm? At each step, the code picks an index, remove the object at that index, and remember to never pick that index again. See the following ...
1
vote
2answers
84 views

Why are greedy algorithms used to find upper/lower bounds? (when they doesn't guarantee an optimal solution)

Take the nearest neighbor algorithm for the traveling salesman problem as an example. Why is it used to find the upper bound? When can't it guarantee an optimal solution? (Thanks to many comments ...