Share Your Experience: Take the 2024 Developer Survey

# Questions tagged [algorithm-design]

Questions related to general, high level, techniques for the design of algorithms.

100 questions
Filter by
Sorted by
Tagged with
16 views

### What algorithm should be used to find the closest set of dates?

I have tried to outline my problem as structured as possible, here is a rough overview, I am trying to find the best matching stay for a hotel booking system. If someone inputs check in and checkout ...
13 views

### Datastore supporting TTL with range queries

We have a data access pattern in which we need to get users added in the time range say timestamp-1 to timestamp-2 and we don't want to keep older data say max 1 day, so DB should have an inbuilt ...
35 views

### Greedy solution for minimum weight where all tasks are allocated

I'm trying to solve exercise 13 from Chapter 04 of Algorithms Design (Eva Tardos) books. The problem is the following: The way I solved: was to have a greedy solution, where I always choose, for an i,...
2k views

### Find all rational roots of a polynomial equation

I'm going to try to design an algorithm to find all the rational roots of a polynomial equation in range [a, b]. Can someone please tell me which algorithm currently solves the problem with lowest ...
1 vote
157 views

1 vote
39 views

### How do I optimally fuse nodes in a tree structure?

I am trying to solve the following problem. I've tried to find the name of this problem, but could not really find what I was looking for. I assume there should be some graph-theory that covers it, ...
1 vote
65 views

### longest symmetric sequence

Suppose we are given a $n$-vector $A$ of real numbers. We need to find the longest sequence of symmetrical numbers. The numbers $a_i$ and $a_j$ are symmetrical if they are located at the same distance ...
1 vote
121 views

### Comparing Registers with 16-bits

I am given with this information: "CMP OP1,OP2 will compare registers OP1 and OP2 if they are equal, flag values will be ZF=1, CF=0, if the first operands value is greater flag values will be ZF=...
1 vote
28 views

### How can a fault tolarent Distributed Data Saving Algorithm can be developed?

I am trying to design an algorithm. For now, I am trying to give myself a large overview. Assume I have K (for example, K can ...
113 views

### The awkward status of Mersenne Twister

Random number generators generally fit into 3 categories IMO: ad-hoc designs serving as stub to be replaced by something else if this ever happens, considerate designs aiming at achieving statistical ...
1 vote
388 views

### How can I find 2 median values of an array which is an union of 2 arrays in O(log n)?

So I have 2 sorted arrays which will have the same length and what I need to do is sort the union array (the union of the two sorted arrays) and then find two median values, I need to do this in O(log ...
1 vote
39 views

### Beginning Algorithm Design and Proving

I know this is a general question, so you can address this by giving some examples that are specific to your field. I want to start learning algorithm design and consequently prove its convergence. ...
1 vote
23 views

### An algorithm to evaluate the strength of Quiz Participants

As a side-project, I had the idea to write some kind of an algorithm that would evaluate all participations in our weekly Pub quiz, to then calculate the average strength of the participants. This is ...
66 views

### Are there any guidelines on how to decide algorithm strategy when approaching a problem?

There are many different general strategies when designing algorithms for a problem like divide and conquer, greedy, dynamic programming, etc. I understand that it is not always obvious which to use ...
38 views

### How to design algorithm

I am a newbie to algorithm designing. I am working on user association and load balancing algorithm designing in millimeter wave wireless communications. In this topic I am able to formulate the ...
32 views

### Understanding the step in given algorithm?

I am a newbie to the world of algorithms design and currently working on a algorithm which is related to cell-phone user associating with cell-phone tower. Let $\mathcal{K} = \{1,\dots,K\}$ be set of ...
1 vote
121 views

### 3-colouring with a bounded amount of colors

The topic of 3-colouring is often talked about, but what happens if we limit the amount of times we can use one color? Take a graph $G=(V,E)$ with $k$ being the number of vertices, is it possible for ...
78 views

### Fast algorithm for computing minimal closure of a set of sets under intersection?

A step of an algorithm I’ve designed requires computing the minimal closure under intersection of a set of sets of arbitrary size. By the "minimal closure (of a set $S$) under intersection", ...
1 vote
44 views

### Fingerprint functions for set equality checks?

Given I have two sets of objects $A =\{a, b, c\}$ and $B = \{a, b, c, a\}$ Based on the set equality, I want the fingerprint of these sets to be the same $F(A) = F(B)$. Additionally I want to be able ...
63 views

### Queue for two types using 2 queues?

I'm reading the book Cracking the Code. The answer for this question suggests a solution using timestamps and two separate queues. This is straightforward and involves simply enqueuing into the ...
1 vote
59 views

### What are the reasons for solution assumptions behind the longest subsequence problem?

All O(N^2) solutions that I have seen for the longest increasing subsequence problem, as their first step, state something like this "Let L[i] be the length of the LIS ending at index i...": ...
1 vote
2k views

### Josephus Problem - A faster Solution

I came through Josephus problem a little while ago. Problem is stated as follows : "People are standing in a circle waiting to be executed. Counting begins at a specified point in the circle and ...
1 vote
109 views

### Is the minimum spanning tree a minimum-altitude connected subgraph

I'm not sure if my solution to the following problem (adapted from Exercise 20, Chapter 4 of Algorithm Design by Jon Kleinberg and Éva Tardos) is correct. I would appreciate it if anyone could point ...
999 views

### no of times partion is called in quick sort, assuming array is always halved

In the most even possible split, PARTITION function produces two subarrays, each of size no more than n/2. since one is of size floor(n/2) and one of size ceil(n/2)-1. The recurrence for the running ...
1 vote
120 views

### Sub-matrix with minimum size of $k$ and minimum sum

We have an $n \times m$ matrix whose entries are non-negative integers and we want to find a sub-matrix whose area (number of entries) is at least $k$ such that the sum of the entries in minimal. The ...
223 views

### Algorithm question: Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1

Algorithm question: Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1. Example 1: Input: [0,1] Output: 2 Explanation: [0, 1] is the longest ...
113 views

1 vote
103 views

### Multi-Path Length Minimization

I've been thinking about path planning and am trying to make good heuristics for cases with multiple agents. Suppose there are sets $S_i$ of coordinates in $\mathbb R^2$ or $\mathbb R^3$, each of the ...
1 vote
90 views

### "Searching and sorting" algorithm to find the natural logarithim of a number?

Yeah, this is for a homework assignment, but I hope that you'll humor me anyway. I am asked to design an algorithm that finds the natural logarithm of a number. This would be straightforward, but I'm ...
1 vote
73 views

### Finding lost bottle (algorithm problem)

The question is as follows: A scientist creates a new compound, called compound A, that will explode 10 days after being mixed with compound B. This compound A was stored in a label-less bottle on ...
1k views

### Maximum number of similar groups of a given size that can be made from a given array

I am given an array of numbers, not necessarily unique, and the size of a group. Let the array be denoted by $B$ and the size of the group be $A$. I need to find the maximum number of groups with the ...
72 views

### Doubt on integrality gap and LP relaxation

I have an exercise that tells me that, given a problem P (of which now I omit the description) there is no integrality gap between LP and ILP formulation of this problem, and for every fractional LP-...
1 vote
137 views

### Is it possible to estimate the step size and walking velocity of different person with the x-y-z acceleration data from 6 axial accelerometer sensor?

I have a 6-axial sensing device used to record the acceleration data. There is an algorithm used to count the number of step and walking distance of the user, but I want to further increase the ...
19 views

### How to divide services and capacities in a graph?

Given a graph where some nodes can provide some services with x,y,z... capacities. A node connected to multiple nodes needs to divide these services to the connected nodes and these nodes themselves ...
1 vote
74 views

### design cache system using queuing theory

If we have data from a random population, a 3d histogram of throughput and current cache size of DRAM (intersection of a IOPS & a cache size will have a count). How can one use queuing theory to ...
1 vote
145 views

### Lexicographic permutation list

Does anyone have an algorithm for stepping through all permutations of n given arbitrary objects in lexicographic order? Thanks.
167 views

### Given an array of size n, create a sub array with given conditions using dynamic programming

We are given an array of integers of size n, which is not necessarily sorted, and we want to create a sub array. We are allowed to do one of 3 tasks below in each level: 1. skip the number in original ...
624 views

### Can a greedy algorithm have more than one subproblems to solve after making greedy choice?

For example: s = <s1 s2 s3> is my problem, I make greedy choice s2 and solve s1 and <...