Questions tagged [algorithm-design]
Questions related to general, high level, techniques for the design of algorithms.
100 questions
1
vote
1
answer
16
views
Confusing statement about “even-length chain” in Skiena's Algorithm Design Manual
I’m reading Skiena's Algorithm Design Manual 3rd edition, specifically the “Stop and Think: Greedy Movie Stars?” counterexample (Figure 1.7).
The greedy heuristic considered is:
repeatedly pick the ...
- 11
0
votes
0
answers
66
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 ...
- 101
0
votes
2
answers
202
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,...
2
votes
1
answer
103
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/...
- 31
1
vote
0
answers
100
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, ...
- 239
1
vote
1
answer
117
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 ...
- 175
1
vote
1
answer
57
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 ...
- 155
2
votes
1
answer
229
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:...
- 225
1
vote
1
answer
124
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-...
- 11
3
votes
2
answers
279
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 ...
- 448
1
vote
2
answers
573
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 ...
- 13
1
vote
1
answer
61
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 ...
0
votes
2
answers
242
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 ...
-2
votes
1
answer
66
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 ...
- 1
0
votes
0
answers
50
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
1
vote
1
answer
179
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 ...
- 49
3
votes
1
answer
159
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", ...
- 131
1
vote
1
answer
101
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 ...
- 123
1
vote
1
answer
62
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. ...
- 273
0
votes
1
answer
153
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 ...
- 231
1
vote
1
answer
141
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...":
...
- 111
1
vote
0
answers
145
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 ...
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 ...
1
vote
0
answers
176
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 ...
- 111
0
votes
0
answers
248
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 ...
- 1
0
votes
0
answers
171
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 $\{...
0
votes
1
answer
101
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 ...
- 133
1
vote
2
answers
192
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=...
3
votes
0
answers
64
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 ...
- 153
1
vote
0
answers
100
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 ...
- 1,048
1
vote
0
answers
191
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 ...
- 453
1
vote
1
answer
822
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 $...
- 13
1
vote
1
answer
189
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
1
answer
128
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 ...
- 33
2
votes
2
answers
246
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{R}...
1
vote
1
answer
111
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 a ...
- 13
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 ...
0
votes
0
answers
109
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
1
answer
177
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 ...
- 111
0
votes
0
answers
37
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
1
vote
1
answer
111
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 ...
- 111
2
votes
1
answer
235
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 ...
- 65
1
vote
2
answers
202
views
Lexicographic permutation list
Does anyone have an algorithm for stepping through all permutations of n given arbitrary objects in lexicographic order?
Thanks.
3
votes
1
answer
723
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 <...
- 33
2
votes
1
answer
775
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 $...
4
votes
1
answer
176
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....
- 43
9
votes
1
answer
24k
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 ...
3
votes
1
answer
416
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 elements ...
- 33
1
vote
1
answer
528
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 ...
0
votes
0
answers
55
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.
...
- 155