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.

Filter by
Sorted by
Tagged with
0
votes
0answers
35 views

Job scheduling with minimum makespan

You are given n jobs, m workstations and an n × m two-dimensional task matrix T of the time each job will spend at each workstation. Each job becomes available at a specified time and may be processed ...
4
votes
1answer
100 views

Scheduling algorithm to minimize the number of late jobs

There are $n$ (non-recurring) jobs where each job $i$ has an arrival time $a_i$ and a duration $t_i$. All the jobs share a deadline length $d$ (deadline for each job is $a_i + d$). The problem is to ...
1
vote
1answer
28 views

Number of ways of tiling a 3*N board with 2*1 dominoes problem

I came across this problem, Tiling with Dominoes and initially I faced difficulty in understanding the logic behind recurrence relation, but after reading it from here , I understood it. But I had a ...
2
votes
1answer
36 views

k-enclosing rectangle in two-colored point set

I was asked to write an algorithm for the following problem, and discuss complexity: There are p points of two colours, black and white, in an n*m grid. Any cell in the grid can contain 0 or ...
0
votes
0answers
65 views

Find longest path in minimum spanning tree

Given an undirected MST with positive weights how can the longest path be found? Based on the accepted answer in this question Longest path in an undirected tree with only one traversal I've ...
2
votes
2answers
82 views

Converting a number from N to 0 in binary

Trying to solve this problem since 2 days. Still unable to figure out even a basic approach. Given a number $N$ in binary ($1$ to $10^5$), we need to convert it to $0$ using only 2 operations. ...
1
vote
2answers
39 views

Running time correct with Omega?

I have the following statement. I would say it's correct as it's either equal or higher than $\Omega(\log^{10}(n))$. Because: I know $\log(2^n) = n$. By that I would guess the same goes for $\log(n^{...
0
votes
1answer
49 views

Help with graph search problem

For the next problem I can not think of how to find a solution with graph searches (I thought it was backtracking but my college professor told me that I should use graph searches, which I do not know ...
2
votes
1answer
46 views

Distributed MST Construction in O(log log n) Rounds in a Clique

I'm reading the paper MST Construction in O(log log n) Communication Rounds in a Clique and trying to understand the correctness analysis, in page 5. It shows by induction on k (phase number), that ...
2
votes
1answer
70 views

Understanding Correctness of Bidirectional Dijkstra

I'm trying to understand the correctness of the bidirectional version of Dijkstras algorithm as mentioned here on slide 10: https://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/EPP%...
1
vote
0answers
29 views

How to justify using available code (in different language) for comparing algorithms [closed]

I have proposed an algorithm for a scheduling problem in a submitting paper. In the revision, the reviewer asked us to compare with another algorithm in the literature. Our algorithm is in MATLAB, and ...
0
votes
1answer
25 views

Proof Big Theta (sum of a geometric)

Here sum of a geometric, where c is a positive real number. $g(n)=1+c+c^2+...+c^n$ $\theta(1)$ if $c<1$ Any idea to solve this?
1
vote
0answers
26 views

Implementing binary arithmetic encoder

I have set integers that are normally distributed, and I'm trying to implement binary arithmetic encoding, as suggested in this post: Compressing normally distributed data I'm running into trouble ...
2
votes
1answer
46 views

Can we find a computable function which cannot be calculated faster for any given time?

Define $T\colon \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$ by: $T(k,n) = 2^{T(k-1,n)}$ $T(0,n) = 1$ $T(1,n) = 2^n$ $T(2,n) = 2^{2^n}$ And denote the W.C. (worst case) time of computing $...
2
votes
1answer
31 views

Minimize shipping cost based on weight and price constraints

I'm trying to determine the least shipping cost when you have a number of items (each with a weight and a price) that can be combined into the same package. The constraints are as follows: There is a ...
3
votes
1answer
59 views

Reductions between LIS and LCS

Given an oracle that returns both the length and the subsequence for the Longest Increasing Subsequence of a given input $A$ of $n$ elements $\text{LIS}(A,n)$, can one use a polynomial number of calls ...
2
votes
0answers
52 views

What algorithm should I use for the following problem?

Suppose we have 2 lists: List $G$: the goal, contains goal items each comes with a specific amount, $$G = \{i_1 \times Item_1, i_2 \times Item_2,\dots, i_n \times Item_n\}$$ List $I$: a list that ...
0
votes
1answer
38 views

Non consant size alphabet

Sometimes I read that an algorithm works on constant size alphabet and it is clear for me but what means that an algorithm works with a non constant size alphabet? I would like to see an example.
3
votes
4answers
110 views

How to select best k fractions out of n fractions (k<=n) so as to have (numerator sum / denominator sum) maximum?

For example, given 4 fractions $\frac{4}{2}$, $\frac{2}{3}$, $\frac{1}{2}$, $\frac{10}{20}$, I have to select 3 fractions out of these 4 so that the value of $\frac{\text{numerator sum}}{\text{...
0
votes
0answers
32 views

Vertices/segments graph to polygons

On a 2D plane there is a set of vertices V and segments S. Each segment has 2 vertices, and each vertex knows segments that use it. That creates a kind of a graph. I would like to find all polygons ...
0
votes
0answers
25 views

Draw lines according to a specific condition

We have an infinitely planar cartesian coordinate system on which $N$ points are plotted. Cartesian coordinates of the point $i$ are represented by $(X_i,Y_i)$. Now we want to draw $(N−1)$ line ...
2
votes
1answer
94 views

Proving NP hardness in Puzzle with SAT reduction

Introduction I have created an algorithm that generates n^2 x n^2 Sudoku Grids. Out of those grids I remove elements to give only one solution. The algorithm follows an infinite language based on ...
1
vote
2answers
106 views

Could all CPU instructions get fundamentally faster if a better multiplication method was developed

I was reading the article Integer multiplication in time O(n log n) by David Harvey and Joris Van Der Hoeven, 2019. Could this discovery increase the throughput of future CPU's? If so could we ...
3
votes
0answers
77 views

How to cover holes with disks of a fixed radius? [closed]

So you have a sheet / area of a given dimension, and within this area are holes (their center point(x,y) and radius are given). The problem is you need to cover these holes with patches. These ...
1
vote
2answers
35 views

Space-efficient representation of potentially very large arbitrary-precision rationals?

I'd like to know if there are good techniques for faithfully and (reasonably) representing rational numbers with forms similar to: 2/3 1/10 4 * 10 ^ 1,000,000,000,000 I know arbitrary precision ...
3
votes
0answers
49 views

Self intersection in a simple polygon

Suppose I have a simple polygon whose vertices are $p_1,\ldots,p_n$ each $p_i \in \mathbb{R}^2$. Suppose now I pick two distincts vertices $p_i,p_j, i\neq j$ Is there some algorithm I can use to test ...
2
votes
1answer
46 views

What is an approximation factor for the Greedy Motif Search algorithm?

What is approximation factor for the Greedy Motif Search algorithm? I couldn't find an answer to my question except for the fact that the algorithm has a unknown aproximation factor. I'm not a native ...
1
vote
0answers
26 views

Grouping numbers so they approximate their total divided by two

Given an array of numbers, I would like to find an algorithm which divides them into two groups, such that the sum of the numbers in each group is as close as possible to half of the sum of all ...
1
vote
1answer
19 views

How to calculate the number of invalid strings given a constraint system on alphabet, word blacklist, and string length

If I have the following system, I am wondering how to calculate the number of valid strings it contains. The system is something like this, which can have arbitrary variations. Only consists of an ...
0
votes
1answer
39 views

Worst Case Scenario for Quicksort algorithm with pivot element n/2

What would the worst case array look like if I decide to always take the element on the position $\frac{n}{2}$ as the pivot element? I know that if I choose the left or rightmost element as pivot ,the ...
2
votes
1answer
96 views

Solve Maze Without Feedback

Suppose that we have the following maze (_ = open, + = blocked), and we can move left,right,up,down: ...
3
votes
1answer
51 views

Using Chebyshev to derive an upper bound for Coupon Collecter's Problem

I'm TA'ing a course and have trouble solving an exercise. Let $X$ be a RV defined to be the number of trials required to collect at least one of each type of coupon (of which there are $n$). Then $E[...
2
votes
2answers
171 views

Formulating the master theorem with Little-O- and Little-Omega notation

In a lecture of Algorithms of Data Structures (based on Cormen et al.), we defined the master theorem like this: Let $a \geq 1$ and $b \gt 1$ be constants, and let $T : \mathbb{N} \rightarrow \...
1
vote
0answers
82 views

MAX-CUT: are there any algorithms or codes for classical computers, that cater to this specific case?

A paper was published recently in Science where the authors minimized the following function: $$E_{\text{Ising}}(s) = -\dfrac{1}{2} \Sigma_{i=1}^{N} \Sigma_{j=1}^{N} J_{i,j} s_i s_j,$$ where $...
0
votes
0answers
15 views

What is the correct way for beta reduction of lambda terms

my answer : (\x.\y.y)(xx) -> (\y.y)x -> y correct answer: (\x.\y.y)(xx) -> (\y.y) I was wondering would it be reduced one by one from left to right ? it seems the correct answer takes the whole (xx) ...
2
votes
1answer
43 views

In which situation do we choose randomized binary search instead of the normal binary search?

Both randomized and normal binary search takes O(log n) time complexity but why does the randomized version exist? In other words what is the advantage of randomized binary search even if it has same ...
0
votes
0answers
15 views

Min Cut Algorithm using Randomly inserted directions

I had a question about a different randomized min cut algorithm (I don't think it is as efficient as Karger's algorithm for larger sizes of min cuts but it is more efficient for smaller ones). My ...
0
votes
1answer
33 views

Is it possible to compute how many iterations this algorithm will take?

I want to know exactly how many iterations it would take this algorithm to terminate. In other words, is there a closed-form solution for the number of iterations? (For my input values, it is always ...
0
votes
0answers
7 views

Linear time addition of binary numerals using only primitive recursion and case analysis

Given binary numerals encoded like (in Haskell for example): data Bin = Z | T Bin | TI Bin With Z being 0, ...
5
votes
3answers
401 views

How do we place $8n$ objects in a grid of size $n \times n$?

How do we place $8n$ objects on a square of size $n\times n$ in a form of grid such that no 4 of them form a rectangle with sides parallel to those of square? Each object occupies exactly one cell in ...
0
votes
2answers
25 views

Don't understand minimax algorithm in terms of chess

I'm new to minimax algorithm, but i understand it's entire concepts as it's easy, my biggest issue is understanding it's implementation to my chess game, no internet solution answers this question ...
1
vote
3answers
87 views

Do all recursive problems have optimal substructure?

I am reading about dynamic programming and I understand the overlapping subproblem requirement but not sure why optimal substructure is explicitly stated. Are there problems that can be solved ...
1
vote
1answer
32 views

Algorithm To Process Purchases Efficiently and Apply Constraint

I am working on a problem where I have to completely scan a large unordered log file which contains purchasing details of customers. The file structure is as follows: ...
2
votes
1answer
184 views

The origin of list data structure

Does anyone know when the list data structure was mentioned in computer programming/algorithms? Who gave birth to this list concept?
2
votes
2answers
53 views

Is purely functional programming in some situations less efficient than imperative programming?

I am used to implementing algorithms in imperative languages. Many of the algorithms I have implemented use hash maps, hash sets, mutable arrays, heaps, doubly linked lists, etc. I understand that ...
1
vote
1answer
32 views

Time complexity of finding subsequences of a string segmented into parts

Let $S$ be a string of length $N$, consisting of digits 0 to 9. For convenience, we assume $N$ to be a multiple of 3. Then, we split $S$ into $N/3$ equal parts, each of length 3. For each equal part,...
3
votes
3answers
81 views

How to check if a list of XY coordinate meet the safety distance to each others?

My background is not CS so sorry for using improper term. But basically I want to check if a point on XY plane is "too close" to any other points, and do so with every points. In another words, if I ...
1
vote
0answers
36 views

Time complexity of an algorithm for finding a cycle of fixed length

I am considering the following algorithm for obtaining a cycle $C_k$ of fixed length $k$ in an undirected graph $G$. Assuming $G$ is in adjacency list form, say $r \in G$ is the root for a truncated ...
4
votes
4answers
262 views

Algorithms for 2-colouring a 2 x N matrix

Our task is to color a given $2 \times N$ matrix with two colours red (R) and blue (B) such that no two adjacent cells are blue. For red, there are no restrictions. An example of all possible ...
0
votes
2answers
80 views

Is this a new sorting algorithm?

I just came up with a simple sorting algorithm that is faster than ShellSort when the range of values is smaller than the number of elements. Is this new? And if so, what should I do with it? https:/...