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

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
1 vote
1 answer
76 views

smoothness test

An integer is $k$-smooth if its prime factors are at most $k$. In the case where $k$ is not tiny (say $10^8 < k < 10^{10}$), are there algorithms to test for $k$-smoothness, other than trying ...
Pascal Ochem's user avatar
0 votes
1 answer
25 views

algorithm to categorize courses into academic degree requirements?

In most US universities, undergraduate students must satisfy the requirements of a degree program in order to graduate. The general rules are: The university has a minimum number of total credits ...
Foo Bar's user avatar
  • 536
0 votes
0 answers
19 views

Proving Optimal Greedy Algorithms [duplicate]

How is the best way to go about proving that a greedy algorithm is optimal, inductive vs contradiction, are there parts in the proof that are key to include. I did not feel that the lesson I was ...
James's user avatar
  • 1
1 vote
1 answer
46 views

Bellman Ford algorithm relaxation

In the Bellman-Ford algorithm's relaxation part, I can't seem to understand why we need to use (d[v] = min{ d[v], d[u] + c(u, v) }), the (c(u,v)) part. This uses the original weight. Why can't it use ...
Kevin Tsou's user avatar
3 votes
1 answer
227 views

How to optimize algorithm to solve the following time series problem?

I am working on a project and came across the following problem I have to solve. Imagine we have a time series data Ts which is an array of pair, say each element ...
askyfullofstars's user avatar
0 votes
0 answers
23 views

Decreasing quantity elements in quantities array to get it to be in same ratio as array of ratios

Problem Statement: We want to update(only decrease allowed) elements of array to obtain a new array which is in same ratio as ratio array. Example lets say you have quantity vector as [20, 50, 20] and ...
decentstudent's user avatar
1 vote
2 answers
170 views

What is the Time Complexity of this Slow Sorting Algorithm?

...
Arugo's user avatar
  • 49
0 votes
0 answers
104 views

Algorithm for "Clustering" a directed graph

I have a directed graph with unweighted edges between the vertices, and possible cycles. I want an algorithm that I can pass in the graph and a number N, and have it spit out a set of N clusters each ...
Li Haoyi's user avatar
1 vote
1 answer
52 views

Proof of correctness for Binary Search algorithm to find length of array for unknown length

For the algorithm provided in answer to this question, how would I go about proving the correctness of the algorithm? The referenced question is: “You are given an array $A$ of length $n$. Each value ...
Hugh Mann's user avatar
1 vote
0 answers
111 views

How many comparative sorting algorithms are there?

I've invented an abstract structure to represent a comparison-based sorting algorithm, which I will call a comparison tree (similar to the decision tree of a comparative sorting algorithm). ...
sbh's user avatar
  • 51
2 votes
1 answer
71 views

Sorting with element merging

I'm seeking information about a specific sorting algorithm. This algorithm performs pairwise comparisons and distinguishes between three states: a > b: In this case, standard sorting logic proceeds ...
vakvakvak's user avatar
  • 121
0 votes
0 answers
73 views

Minimum flow in a flow network

Let $G = (V, E)$ be a flow network with a source $s$ and sink $t$. However, the constraints are a bit different: Conservation constraint is as usual. For each edge $e \in E$, we have that the flow $f$ ...
Daniel's user avatar
  • 69
1 vote
0 answers
62 views

Total combinations in DAG with upper bound on node value

There is a directed acyclic graph with M edges. There is only one component (If they were undirected edges all nodes will be reachable will from one to another). An edge from a to b means value of ...
Aryan Agarwal's user avatar
1 vote
1 answer
41 views

Find a pair $a,b$ with a range condition in Hash table

Given an array with the size of $n$ of integer numbers. Our goal will be to analyze the expected running time of an algorithm that uses a hash table to find (if exists) a pair $(a,b)$ subject to $2<...
ErroR's user avatar
  • 1,942
2 votes
0 answers
57 views

Are there $r$ pairwise edge-disjoint $k$-sets of internally disjoint $s$-$t$-paths? Complexity

Given an undirected graph, two vertices $s$ and $t$, and two integers $k$ and $r$, then a $k$-set of internally disjoint $s$-$t$-paths is defined to be a set of exactly $k$ $s$-$t$-paths that share no ...
tgnome's user avatar
  • 153
2 votes
0 answers
68 views

Can a time-optimal algorithm have a time complexity better than its space complexity? [duplicate]

That's what I'm formally asking: Let the algorithm $A$ have the worst-case time complexity $\Theta(f(n))$, such that for any algorithm $B$ with the worst-case time complexity $\Theta(g(n))$ doing the ...
sbh's user avatar
  • 51
1 vote
0 answers
47 views

What are solutions to the convex hull problem?

I have researched multiple solutions to the convex hull problem, but I am afraid I don't really understand some of them. For example, Graham's scan is a bit confusing as it is not very clear if the n ...
user79644's user avatar
1 vote
1 answer
81 views

NP-hardness of a variation of the bin packing problem

I was wondering if a variation of the bin packing problem where the 'size' of a bin is calculated as the product of item sizes in a bin instead of their sum is NP-hard. It seems like it must be, but I ...
Sharp Edged's user avatar
0 votes
0 answers
26 views

Use case for string matching in a 2 by n grid

In a 2 by n grid there is a character in each cell. A path can start at any cell and then you can move to right or down. This way each path will denote a string written by characters on cells visited ...
Iridescent 53's user avatar
6 votes
0 answers
170 views

Are there $\ell$ edge-disjoint $s$-$t$-paths such that at least $k$ of them are internally disjoint? Complexity

Given an undirected graph, two vertices $s$ and $t$, and two integers $k$,$l$ - what is the complexity of finding $\ell$ edge-disjoint $s$-$t$-paths such that at least $k$ of them are pairwise ...
tgnome's user avatar
  • 153
2 votes
1 answer
44 views

Maximum sum staircase complexity

Given an $n \times n$ matrix of integers, I would like to find the optimal dividing line that maximizes the sum of the integers on the same side as the top left corner. The dividing line should be ...
Simd's user avatar
  • 996
-1 votes
1 answer
34 views

Help with understanding Check Digit Validations

I'm not sure if I'm posting in the correct section, but I wanted to learn about CDVs, how the weightings work, and the computation. I'm reviewing how a system is configured and looking to add a new ...
lewisj74's user avatar
1 vote
0 answers
22 views

In monte-carlo tree search, do you propagate the result from the terminal or just the leaf?

In most descriptions of monte-carlo tree search, I see the simulation step described as: Play out a game from the leaf node until a terminal node is reached and get the result. And the ...
Kyle's user avatar
  • 11
3 votes
1 answer
57 views

Finding Specific Order Statistics with O(n log(n/k)) Complexity

I'm working on a problem where I need to find specific order statistics in a set of numbers. Given n numbers, I want to determine the ...
Iman Mohammadi's user avatar
0 votes
0 answers
56 views

Help understand Z order curve range searching

After "speaking" with ChatGPT, I decided to test Z Order Curve. The code interleaves 2D data, then search for range x: [2..4], y: [2..4] Programming code using C/C++ should be as follows: <...
Nick's user avatar
  • 105
1 vote
1 answer
65 views

Scheduling classes with lower and upper bounds on students and classes

I am struggling to solve the following excercise: Design an assignment of a group of n students to m classes. Student i should take a minimum of $l_i$, and a maximum of $u_i$ within a set C1 of ...
FarsoFracico's user avatar
0 votes
2 answers
21 views

Is there a way to automate solving for coefficients in multivariable systems of equations?

I am trying to find a way to automate solving for all possible numerical values in a large multivariable system of equations. By this I mean equations such as k(90)*g(-3)=434 and k(47)*g(-5)=237 ...
man of many men's user avatar
2 votes
2 answers
112 views

Few lines of code to test whether a student will understand computer science

A couple of years ago, I read a story about a professor of computer science, who showed his first semester students a few lines of code with a simple questions. I think it was something along the ...
Pascal Klein's user avatar
1 vote
1 answer
138 views

Algorithm for efficiently identifying ambiguities in a set of HTTP routes with wildcards/Unix Globs?

So I have a bunch of strings that represent routes in a HTTP web framework. Each string has a leading /, some /-separated path ...
Li Haoyi's user avatar
1 vote
0 answers
96 views

Succint data structure for storing n numbers using a mask-based partition

I've a set $N$ of $n$ distinct numbers of $d$-bits each; call them words ($1\leq n\leq 2^d$, with $d\geq 1$). I want to store $N$ using as least space as possible, by partitioning $N$ and factoring ...
ABu's user avatar
  • 529
0 votes
0 answers
40 views

How to optimally construct queries asking about the class of an object to eventually find it?

Consider the following problem stated formally: You are given $n$ objects $o_1$, $o_2$, ..., $o_n$ and $k$ classes $c_1$, $c_2$, ..., $c_k$, each class containing some objects; an object is chosen. ...
sbh's user avatar
  • 51
0 votes
2 answers
55 views

If mergesort takes 30 sec to sort 64 elements in worst case, how many elements can be sorted at worst case by using it in 6 minutes?

To sort 64 elements Time required is $n*log_2{n}$ units The equivalent posteriori time is 30 sec. In 6 minutes I get 768 elements sorted. But the answer is not 768 and is instead 512, I wonder why?
Team B.I's user avatar
  • 263
1 vote
1 answer
183 views

Number of stops during trip - Dynamic programming algorithm

I am attending a course about algorithm design, and I have found an old test which has once been submitted. However, I don't have the solutions to it, and I am having some trouble with one specific ...
FarsoFracico's user avatar
2 votes
1 answer
393 views

Prove that the number of comparisons between elements in binary heap build is at most (2n-2)

Question Prove that the number of comparisons between elements in binary heap build is at most $2n-2$. $n$ is the total number of the nodes. Pseudocode ...
Lior's user avatar
  • 143
5 votes
2 answers
350 views

How to find an example for a case in the metric k-center problem

Given $n$ points in a 2d metric space, the $k$-center problem asks us to find a subset of size $k$ of the points which we will call centers. The task is to pick these centers to minimize the maximum ...
Simd's user avatar
  • 996
0 votes
2 answers
38 views

How to unscramble an RGB image 1024x1024

I have a colored image 1024x1024 whose rows and columns were randomly shifted, how would I unscramble it without having any information about the original image?
kjkjkjkjkj's user avatar
0 votes
0 answers
33 views

A probabilistic data structure based on flipping bits with probability $\frac{1}{2^x}$ for counting

How does this data structure work and what is its application? ...
Mason Rashford's user avatar
1 vote
1 answer
59 views

Finding the pair of nodes with maximum distance in an arbitrary rooted tree

Suppose we are given an arbitrary rooted tree. We want to find two nodes that have the maximum distance among all pairs of nodes. I am looking for an algorithm with time complexity $\mathcal{O}(n)$, ...
Mason Rashford's user avatar
2 votes
1 answer
83 views

Repeated Substring Pattern

I've been working on the following challenge on LeetCode: Problem: Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together....
Ariana's user avatar
  • 123
3 votes
1 answer
82 views

Useful algorithm not primitive recursive

The Ackermann function is the textbook example of a function which is total recursive but not primitive recursive. If we want to implement it in some programming language we will need to use a priori ...
Weier's user avatar
  • 231
1 vote
2 answers
108 views

Memory-efficient representation of keys over a huge domain

I don't know if the title of the question is accurated or not, but I was thinking of the following problem: I have a set of numbers, let's call them identifiers. Each identifier is stored on a 64-bit ...
ABu's user avatar
  • 529
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
3 votes
0 answers
92 views

Proof about Existence of Stable Matching

I've read the stable matching chapter in Kleinberg and Tardos's Algorithm Design and was wondering how one can show whether a stable matching under a given set of constraints exists. K&T introduce ...
entangled_photon's user avatar
0 votes
4 answers
397 views

Find median in a sorted matrix

Suppose we are given a $n\times n$ matrix that is sorted row-wise and column-wise. We want to find the median in $\mathcal{O}(n\log{n})$. This is my approach: We know median is such element that is ...
Mason Rashford's user avatar
3 votes
3 answers
285 views

Maximum circular area sum

Given an $n \times n$ grid of integers, I would like to compute the circular area which gives the maximum sum of integers within the area. For example: In this picture, the integers 1, 0, 1, 2, 3, 1, ...
Simd's user avatar
  • 996
1 vote
1 answer
91 views

Running time of modified BFS algorithm to find shortest path in weighted DAG

While the shortest path can be calculated with $O(V+E)$ time over a weighted directed acyclic graph using topological sort, I wonder about the running time of the following BFS type algorithm I ...
wsz_fantasy's user avatar
1 vote
0 answers
25 views

CHK graph dominance algorithm proof

The algorithm developed by Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy is widely used in industry for building dominator tree, but I cannot follow the proof in the “Engineering the data ...
rand0m_scr1pt_k1dd1e's user avatar
0 votes
1 answer
39 views

Buy two chocolates when want MAXIMUM nonegative spend

This is a self-study inspired by the trivial https://leetcode.com/problems/buy-two-chocolates/. Basically the question is as follows: if you have a value of money m ...
JoeTheShmoe's user avatar
1 vote
1 answer
99 views

Restore the original array after merge Sort based on it's steps

i'm trying to write an algorithm to reconstruct the original array from the sorted one. considering input value is a string of 1s and 2s which 1 means in merging part of merge sort, element from left ...
vhd's user avatar
  • 45
3 votes
1 answer
202 views

is there an efficient algorithm to find the optimal partition of a matrix?

Consider an $n \times n$ matrix of integers. Define a boundary in the matrix to be a sequence of cells, one per x-coordinate, where the y-coordinates of the boundary either stay the same or go up/down ...
Simd's user avatar
  • 996