Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [algorithm-design]

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
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 ...
Christian Webb's user avatar
0 votes
0 answers
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 ...
tusharRawat's user avatar
0 votes
2 answers
37 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,...
Catarina Nogueira's user avatar
2 votes
1 answer
67 views

Seeking help in designing an algorithm

I am not a computer science nor a math person, but if given a pseudo-code or a English outline of steps. I can probably fumble my way through and write some code. I Apologize for the wall of text/...
Scott Watson's user avatar
1 vote
0 answers
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, ...
RunOrVeith's user avatar
1 vote
1 answer
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 ...
Nick's user avatar
  • 175
1 vote
1 answer
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 ...
Sean's user avatar
  • 155
2 votes
1 answer
100 views

Faster selection algorithm for small order statistics

SELECT(A,p,r,i) is an algorithm that partitions $A[p:r]$ around the $i$ th order statistic ie. in the output, we have $l\in A[p:p+i-2]<A[p+i-1]< h\in A[p+i:...
C.C.'s user avatar
  • 159
1 vote
1 answer
43 views

Algorithm design: Model redundancy in tests

I've run across an interesting problem at work that I'm not quite sure how to grapple. Broadly, there is a suite of of $n$ tests to ensure the quality of a product. However, the tests are both time-...
lyberius's user avatar
2 votes
2 answers
114 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 ...
DannyNiu's user avatar
  • 352
1 vote
2 answers
390 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 ...
111's user avatar
  • 13
1 vote
1 answer
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 ...
Mantas Kandratavičius's user avatar
0 votes
2 answers
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 ...
Each One Chew's user avatar
-2 votes
1 answer
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 ...
chaaru's user avatar
  • 1
0 votes
0 answers
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 ...
chaaru's user avatar
  • 1
1 vote
1 answer
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 ...
Guts's user avatar
  • 49
3 votes
1 answer
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", ...
adamcatto's user avatar
  • 131
1 vote
1 answer
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 ...
zetaprime's user avatar
  • 123
1 vote
1 answer
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. ...
cgo's user avatar
  • 273
0 votes
1 answer
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 ...
sprajagopal's user avatar
1 vote
1 answer
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...": ...
peetonn's user avatar
  • 111
1 vote
0 answers
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 ...
Eduardo Fernandez's user avatar
0 votes
2 answers
1k 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 ...
Anshul Verma's user avatar
1 vote
0 answers
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 ...
Pegi's user avatar
  • 111
0 votes
0 answers
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 ...
ayuken's user avatar
  • 1
0 votes
0 answers
113 views

Counting number of sequences summing to target

This is a problem that I have been struggling to understand in a theoretical computer science book I've been reading: We call a sequence of $n$ integers $x_1, \dots, x_n$ valid if each $x_i$ is in $\{...
Satish Rao's user avatar
0 votes
1 answer
69 views

Algorithm for sorting within windows

I am writing an app which displays speeches on various topics, with each speech having a number of attributes. I want to give the user the choice to sort a list of speeches by an attribute, even ...
Sam's user avatar
  • 133
1 vote
2 answers
122 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=...
Mahmut Salman's user avatar
3 votes
0 answers
38 views

Suggestions for a source of algorithm design problems?

I’m finishing up Roughgarden’s two-part algorithms course on edx, and it was good, but I didn’t actually ‘design and analyze’ many algorithms, the questions mostly tested whether you understood the ...
Adam Tolnay's user avatar
1 vote
0 answers
61 views

Abstract algebra algorithms

Let’s make a big list of algorithms relying on abstract algebra. This will help us see how ubiquitous algebra is in algorithm design. I’ll start with two: one is the General Number Field Sieve, the ...
Zirui Wang's user avatar
1 vote
0 answers
161 views

Intersection of line segments induced by point sets from fixed geometry

I am reading up on algorithms and at the moment looking at the below problem from Jeff Erickson's book Algorithms. I solved (a) by seeing a relationship to the previous problem on computing the ...
spektr's user avatar
  • 453
1 vote
1 answer
529 views

Partition the indices of 2d array to minimize sum of sub-matrices

Given an $n\times n$ Matrix $M$, and the indices $[{1,2,3,4,...,n}]$ are divided into several intervals : $[1,x_1],[x_1,x_2],...[x_k,n]$, which further extract several squared sub-matrices along the $...
Haohan Yang's user avatar
1 vote
1 answer
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 ...
JJJJJJJJJJJJJJJJ's user avatar
1 vote
1 answer
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 ...
superfeen's user avatar
1 vote
2 answers
157 views

Mutli-Path Collision Avoidance

I need an algorithm which can do the following: Given some finite number of particles (circles) each with the same radius, and a list of prescribed points for each particle, find paths in $\mathbb{...
JJJJJJJJJJJJJJJJ's user avatar
1 vote
1 answer
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 ...
KyleCraig's user avatar
2 votes
1 answer
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 ...
Debarun Mukherjee's user avatar
0 votes
0 answers
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-...
bruce_springsteen's user avatar
1 vote
1 answer
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 ...
JensenPang's user avatar
0 votes
0 answers
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 ...
Ley Big's user avatar
1 vote
1 answer
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 ...
bicepjai's user avatar
  • 111
2 votes
1 answer
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 ...
Marzi's user avatar
  • 65
1 vote
2 answers
145 views

Lexicographic permutation list

Does anyone have an algorithm for stepping through all permutations of n given arbitrary objects in lexicographic order? Thanks.
Joselin Jocklingson's user avatar
3 votes
1 answer
625 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 <...
aj14's user avatar
  • 33
2 votes
1 answer
701 views

Greedy algorithm for even item distribution

I have this problem where I need to design a greedy algorithm. The problem is as follows: A chocolate factory owns $n$ stores, which are connected by a single road. Each store has a limited supply $...
Winston Smith's user avatar
4 votes
1 answer
73 views

Finding max value algorithm with subset comparison

I have a set of $N$ different values, and my goal is to find the biggest one in the least number of comparisons. Comparing subsets (using the sum of each) is also allowed, and counts as one comparison....
Iaka Noe's user avatar
8 votes
1 answer
22k views

Implementation of QuickSort to handle duplicates

I have this past year question based on the following scenario: When the list of items to be sorted contains a lot of duplicate values, we can improve QuickSort by grouping all the values that are ...
Prashin Jeevaganth's user avatar
3 votes
1 answer
344 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 ...
ךאמיל's user avatar
1 vote
1 answer
456 views

Algorithm to organize a tournament where the team componentes change each round

So, I was tasked with creating an app that generates the schedule of a doubles tennis tournament (i.e., teams of two) in a way that, by the end of it, everyone would have played against the rest of ...
Pedro Soriano Ruiz's user avatar
0 votes
0 answers
43 views

Trouble Convincing Myself Algorithm Correctness

I'm having a tough time convincing myself right when coming up for some solutions to medium/hard leetcode.com problems. Take the following question for example. ...
Adam Thompson's user avatar