Skip to main content

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
2 votes
3 answers
47 views

worst case scenario for sorting an array using insertion sort given that all elements can only be 0,1,2

were given an array of numbers "A" of size n, any given number in the array can be one of the following: 0,1,2. using insertion sort, what is the worst case scenario, and what is the best ...
אקרמי צאלח's user avatar
0 votes
1 answer
14 views

Calculating nth permutation without repetition efficiently, with variable number of elements

I know I can use the factorial number system to calculate ordered permutations of a set efficiently, given a constant length (for example, ...
wjwrpoyob's user avatar
  • 141
0 votes
0 answers
16 views

Boosting probability of Randomized approximation algorithms

Suppose $A$ is a randomized algorithm with following properties: The expected running time of $A$ is at most $\mathrm{poly}(n)$ When Opt$\geq c$, with probability at least $\mathrm{poly}(n)$ ...
Lagranngekmno4's user avatar
0 votes
1 answer
26 views

Finding middle vertex of tree

"Given a graph G, the remoteness of a vertex v is the distance from v to the vertex u that is farthest from v in G. That is, the shortest path from v to u is as long as possible. A vertex of G ...
user438409385's user avatar
2 votes
1 answer
71 views

Minimum number of intervals from a set to cover all intervals of another set

There are two sets of intervals provided to us. target = {{11,13}, {7,10}, {0,3}, {6,6}} space = {{10,12}, {2,6}, {4,8}, {0,4}, {9,10}} I need to find the minimum number of intervals I can pick from ...
Viktor's user avatar
  • 23
-2 votes
2 answers
57 views

Precise definition of a brute force algorithm

What is the precise definition of a brute force algorithm? Is it one that simply has non-polynomial runtime?
Geremia's user avatar
  • 154
3 votes
0 answers
51 views

Algorithm to find minimum number of cuts in DAG based on a rule

I encountered this problem while doing some “graph”ics programming: Take a directed acyclic graph where every vertex is given a non-unique label 1..N You can ‘trim’ the DAG by making a cut that ...
Matt Tytel's user avatar
3 votes
1 answer
203 views

How to find a binary vector with minimized distance with a vector set?

Given a set of vectors $S = \{v_1, v_n, ..., v_n\}$, $v_i \in \mathbb{R}^m $. Now I want to find a binary vector $ t \in \{0, 1\}^m $ to minimize $ \sum_{i=1}^n \text {distance} (t, v_i)$. ...
Jun Yang's user avatar
0 votes
1 answer
25 views

Is this knapsack variant named / studied? "Online algorithm for farthest-from-previous index"

Problem Statement: Given: an ordered list of N items, which we can refer to by index: [0, N). Goal: Write an algorithm to ...
Erotemic's user avatar
  • 123
1 vote
1 answer
98 views

Number of unique paths in a grid

Suppose, I have a nxn grid. Now, I want to move from (1,1) to (1,n). How many unique ways are there possible if I can move in left, right, up and down direction. I am trying to solve it using depth ...
Nakib's user avatar
  • 11
3 votes
1 answer
40 views

Best algorithm to evaluate a function that takes the elements of all possible combinations of N numbers

Consider a set $A$ containing $N$ real numbers. Let $f(X_{r,k})$ represent a function, where $X_{r,k}\subseteq A$ denotes the $k$th combination of $r$ elements from $A$, with $1 \leq k \leq \binom{N}{...
GeoArt's user avatar
  • 31
0 votes
0 answers
16 views

How to get the iterator of the ancestor nodes during DFS or BFS?

I am able to solve this by myself, but somebody may already know the answer, so saving manpower, instead of me probably trying several variants. What is an easy way during either DFS or BFS of a DAG ...
porton's user avatar
  • 493
1 vote
1 answer
75 views

Solving recurrence relation $T(n) = \max\{T(k)+T(n−k)+O(\min\{k, n-k\})\}$

My question arises out of this competitive programming problem. The idea is to find a unique element $u$ and then divide-and-conquer for the subarray to the left and to the right of $u$. Searching for ...
Elucidase's user avatar
1 vote
1 answer
51 views

How to prove a function is a bijection (name mangling)?

I'm writing a compiler for a subset of Java, which does not permit overloading (but it does permit overriding). Static functions outside of main are not allowed. We'...
user129393192's user avatar
0 votes
1 answer
25 views

How to do different cases of Union Find?

Here is the question: I understand that the absolute parents are 1, 3, 0, and 8, respectively, but I'm not sure how to do union here. Could someone help me understand how to do this?
MotherHorse's user avatar
0 votes
1 answer
37 views

Efficient ordered single-writer multi-reader list with "add" and "bring to front" operations

I'm looking to implement a collection that needs to support only two operations: AddOrUpdate: Insert item into collection if it doesn't exist; otherwise, move it from whatever the current position is ...
Bogey's user avatar
  • 133
1 vote
1 answer
34 views

What kind of problem am I trying to solve?

I have 500 locations that have multiple skus with varying quantities and I have 6000 orders requesting multiple skus with varying quantities. I have to minimize the total number of locations I visit(...
Chong's user avatar
  • 13
0 votes
2 answers
32 views

Search times for hash tables using open addressing for collision resolution

With regards to hash tables using open addressing as collision resolution mechanism, Introduction to Algorithms, Chapter 11, page 294 (4th edition, 2022 printing) states the following Deletion from ...
jam's user avatar
  • 13
-2 votes
2 answers
33 views

Color conversions formulas

I need formulas to convert betwen color spaces, is there official color conversion reference or something of this kind? I can't find it with simple google search. rgb -> hex, rgb -> hsl, rgb -&...
Ilia Borisov's user avatar
1 vote
1 answer
36 views

Knuth–Morris–Pratt algorithm - Determine the next position of the proper prefix of the pattern string

When I learn Knuth–Morris–Pratt algorithm, I got a function f from the book Fundamentals of Data Structures in C. ...
user169664's user avatar
0 votes
0 answers
29 views

Algorithm of min copies needed to make up a string

I encountered a coding interview question. The problem is like this, you are given a source string and a target string, you can make arbitrary copies of source string and also delete an arbitrary ...
P Li's user avatar
  • 101
0 votes
0 answers
31 views

Largest Tetrahedra from a set of points

Problem Given a set of k points in 3D Euclidean space with k ≥ 4, find four points from the set that form a tetrahedra such that the volume of the tetrahedra is maximized. Attempted Solution Find ...
WakkaTrout's user avatar
0 votes
0 answers
7 views

Load Balancing with No Overlap

Problem Suppose there are $n$ jobs $J_1, \ldots, J_n$ that need to be completed using $m$ machines $M_1, \ldots, M_m$. Each job $J_i$ consists of a set $S\left(J_i\right)$ of $k_i$ sub-chores $s_1, \...
cuppajoeman's user avatar
1 vote
0 answers
20 views

re-rooting a rooted DAG

A "network" is a DAG with a single source (the "root") and all nodes except the root either have in-degree one or out-degree one. A network is "binary" if all nodes have ...
igel's user avatar
  • 111
0 votes
0 answers
36 views

Algorithm to "reverse" search/match pairs from results

Sorry, I don't know how to title it clearly. There is a game, where players can send their units to attack another player's units (weeell, there is a lot of games like that). Each unit has some value. ...
herhor67's user avatar
0 votes
0 answers
9 views

Shortest path in a graph where edge weights can vary dynamically based on the path taken [duplicate]

I have a directed acyclic graph whith negative edges where edge weights can vary dynamically based on the path taken. ...
user1552545's user avatar
0 votes
1 answer
42 views

Intuition for Using Greedy Approach in Container with Most Water Problem

Link to leetcode problem: https://leetcode.com/problems/container-with-most-water/?envType=study-plan-v2&envId=top-interview-150 if we consider this solution: https://leetcode.com/problems/...
penguin365's user avatar
0 votes
1 answer
26 views

Set partitions and integer partitions

Consider an algorithm that takes the input a finite set $X$ and an integer partition $\sum_{i=1}^k n_i=|X|$ and gives output all the set partitions $\left(S_1,\ldots, S_k\right)$ of $S$ satisfying $|...
rr314's user avatar
  • 101
0 votes
0 answers
18 views

Kernelization For Odd Cycle Transversal Problem on Perfect Graphs

This problem appears as exercise 2.33 in https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf (page 48). A perfect graph $G$ is bipartite if and only if it contains no triangle graphs. ...
Yavuz Bozkurt's user avatar
0 votes
1 answer
61 views

Write an algorithm for finding the duplicated grades

I have an interesting real world problem. My brother is currently in school. The teachers perform the following procedure when giving him his grades. They take his list of grades ...
Pranav Jain's user avatar
2 votes
1 answer
73 views

Conditional Maximization of a Binary Matrix

Given an $L \times N$ matrix $A$ with only binary values, $A_{ij} \in \{0, 1\}$, and a vector $b$ with $b_j = 2^{j-1}$, I want to find a matrix $\tilde{A}$ that maximizes $\tilde{c}=\tilde{A}b$, ...
Dan's user avatar
  • 61
1 vote
1 answer
34 views

Will CSR format store the all 0 column?

In the matrix(3 rows and 7 columns) below with 4 all zero columns 0 4 0 0 0 0 0 2 1 0 0 0 0 0 0 0 3 0 0 0 0 The CSR format of storage is : row_ptr: [0, 1, 3, 4] col_ind: [0, 0, 1, 2] values: [4, 2, ...
san zhang's user avatar
0 votes
1 answer
32 views

Is this depth search correct (DFS) Shouldn't one act according to the LIFO principle?

Shouldn't we actually continue with C after A, thought a depth search, follows the LIFO principle, isn't C the last node added in this case and shouldn't we expand C before B?
test's user avatar
  • 1
5 votes
3 answers
2k views

"Entrance exam" homework assignment for 3rd-year algorithms?

I teach 3rd-year algorithms for CS majors at a Canadian university and it always seems a fair number of students arrive not really understanding basic things like breadth-first search. This year I'm ...
Travis's user avatar
  • 53
1 vote
0 answers
28 views

Datastructures for finding unifiable terms

I am looking for a datastructure that supports the following operations: Add a term Remove a term Return a pair of unifiable terms if one exists. Ideally, 3 would be as close as possible to ...
manzana's user avatar
  • 111
2 votes
1 answer
125 views

Tree algorithm - arrange integer array numbers to form largest number

I have solved leetcode's Largest Number. I am asking another question about it here, more from a theory perspective about "if" I had used a tree for the solution. I have a full functioning ...
ccot's user avatar
  • 123
1 vote
0 answers
21 views

Rectangular region biquadratic Lagrangian interpolation basis to solve dirichlet boundary Poisson equation?

after learning FEM,I try using it to solve a PDE $-\Delta u=f,u=0 on \partial\Omega$,where $\Omega$ is a square with $(0,0),(1,0),(1,1),(0,1)$being its vertex by classical finite elements.Here I use ...
Ye Xiangao's user avatar
0 votes
1 answer
18 views

Assigning classes to nodes in a graph to minimise intra-class distance

I have an complete undirected graph with n vertices, and the edge $(u,v)$ has weight $d(u,v)$ for some distance function. I also have $m<n$ elements, each of which belongs to a category $\{1...i\}...
minnie's user avatar
  • 1
2 votes
1 answer
69 views

Pseudo random permutation of a very large number of elements

Consider a file $\textbf{F}$ containing $n$ distinct elements, located on a hard drive. Given the large size of $n$, it's not feasible to load the entire file $\textbf{F}$ into main memory. Assuming ...
JPF's user avatar
  • 121
1 vote
1 answer
36 views

Weisfeiler-Leman Algorithm

We know that the Weisfeiler-Leman Algorithm will not always distinguish graphs that are not isomorphic but if two graphs are isomorphic are we guaranteed to get a certificate?
IsoCurious's user avatar
0 votes
1 answer
33 views

How can I assign people to groups of 4 and optimize for "strangers" on a week-to-week basis when the group can change?

Let's say I have a group of people that meets every week. I would like to assign them to groups of 4. How can I assign these people such that, week after week, collectively, every group consists ...
squeegene's user avatar
  • 101
1 vote
0 answers
16 views

Algorithm question (Similar to Knapsack but with an order, or Stock Buy Sell with a cost parameter)

Given : Profit[n]: a n item array indicating the profit on a day (may be positive or negative) Cost[n]: a n item array indicating the cost of holding a stock on a day (always positive) Task: Find $1 ...
Chinmay The Math Guy's user avatar
1 vote
1 answer
37 views

Polynomial-Time Solvability Through NP-Completeness Reductions

Let A and B be NP-complete problems. Suppose I have established reductions from problem A to problem B and vice versa. Now, considering a specific instance (or set of instances) of problem A that can ...
Lewis Trem's user avatar
0 votes
1 answer
46 views

Coding the labyrinth solver

The question mathematically has been answered here: https://math.stackexchange.com/questions/4886084/guaranteed-graph-labyrinth-solving-sequence/4887473#4887473 To summarize, in an unknown strongly ...
user555076's user avatar
0 votes
0 answers
16 views

Factoring using Extended difference of squares

Given a composite number $P$ and two integers $x$ and $y$ such that: $x^2 = y^2 \pmod P$ we can factor $P$ using factor = $\mathrm{gcd}(P, x-y)$ or $\mathrm{gcd}(P, x+y)$. Now are there a similar ...
TheoryQuest1's user avatar
0 votes
0 answers
25 views

Linear time Algorithm 2-sum (Sedgewick Textbook)

I am going through the fourth edition of Algorithms by Sedgewick & Wayne. On page 190 there is a discussion of lower bounds for the 2-sum problem, where the 2-sum problem is stated as: find all ...
ClownInTheMoon's user avatar
0 votes
0 answers
30 views

Fastest algorithm for approximate hamming distance

Consider two binary strings of two alphabets of length $l$, to find the hamming distance each corresponding bit needs to be compared. The runtime will be $O(l)$ or simply $l$ many comparisons are ...
Shi's user avatar
  • 35
0 votes
1 answer
25 views

Algorithms for stacking gage blocks

I'm looking for algorithms for stacking gage blocks. For those unaware, gage blocks are used in machine shops for measuring with high precision and come in sets something like this... Mitutoyo's 56 ...
David Carpenter's user avatar
-3 votes
1 answer
101 views

Can every greedy problem be solved using dynamic programming?

Can every problem with a greedy solution be solved using dynamic programming? Why or why not? I'm not completely sure how to formally reason about this, my understanding about the structure of ...
proof-of-correctness's user avatar
0 votes
1 answer
28 views

What is the relationship among the various algorithms?

I'm curious about whether there exists a hierarchical or layered concept within the broad categories of algorithms, where they can be further divided into subcategories based on their characteristics ...
yinfei's user avatar
  • 1