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
3 votes
1 answer
57 views

Approximation ratio on (1, 2)-metric Travelling Salesman Problem (TSP)

I encountered a problem, where I am given a (fully-connected) graph within a metric space, where each edge weight is either 1 or 2. My task is to prove that the following greedy algorithm gives a $\...
user avatar
  • 149
3 votes
1 answer
83 views

Determine efficiently whether A can get infinitely larger than B by following a walk in the given graph

Person $A$ is chasing person $B$. Both people can only travel between $n$ vertices of a graph by running through one of $m$ one-way pipes labelled $1,2,\cdots, m$. For each pipe we know the starting ...
user avatar
0 votes
0 answers
25 views

Graph algorithm for propagating a feature

I have the following problem: Given a graph of persons and their relationships. Suppose I have a classification of the risk of some of those persons. How can I calculate the classification of the ...
user avatar
1 vote
1 answer
92 views

MST with weights in {1, 2, 3, 4, 5}

I am given an undirected connected graph with $n$ nodes, average degree $\sqrt{\log n}$, and each edge having integer weight in $\{1,..,5\}$. I am asked to describe MST algorithm which is as efficient ...
user avatar
  • 149
1 vote
2 answers
42 views

How do SQL databases query non-indexed columns?

I'm looking for some resources on what happens on the low-level with databases. I've found that indexed data is looked up using b+ trees, but could not find anything on non-indexed columns. Is there ...
user avatar
  • 11
1 vote
1 answer
31 views

Binary matrix optimization problem with element co-dependence

Suppose we have an optimization problem where we want to find a binary matrix $A \in \{0, 1\}^{n \times m}$ that minimizes the score function defined as $$S(A) = \sum^n_i \sum^m_j f_{ij}(a_{i-1j}, a_{...
user avatar
  • 123
3 votes
2 answers
79 views

Sorted degrees and maximal degree in dynamic graphs

Consider a sequence of vertex and edge additions and removals to an initially empty (undirected, simple) graph. Is it possible to update the ordered list of vertex degrees in constant time (and space),...
user avatar
1 vote
0 answers
15 views

What is the draw back of Bag of Words model?

Bag of words model rank words in a particular document in such a way that If it is occurring into that particular document multiple times and it's frequency is low for other documents then it's weight ...
user avatar
1 vote
0 answers
26 views

What is the name of the following problem on sets of strings

Given finite sets $A,B,C$ of finite strings, does there exist some $x,y \in A$ and some $z$ such that $x.z \in B$ and $y.z \in C$ hold (where $x.z$ denotes the concatenation of $x$ and $z$)? That is, ...
user avatar
0 votes
1 answer
46 views

Checking whether a set of points in the plane can be bi-partitioned with a certain diameter

I am working on a problem in geometry and I encounter the following problem. Suppose given $n=2k$ points $P$ in the plane. And we want partition points into two group Is there an algorithm that ...
user avatar
  • 1
1 vote
1 answer
47 views

uniformly distributed edge weights in an MST

Suppose that the edge weights in a graph are uniformly distributed over the halfopen interval [0, 1). The question is, how can one sort the edge weights in linear expected time? I know the ...
user avatar
3 votes
0 answers
38 views

Finding closest points equal in value in a grid

Given a grid of integer values, $G = \{g_{i,j}\mid i<m,j<n\}$ I would like to compute a grid $H = \{\{x_{i,j},y_{i,j}\}\mid i<m,j<n\}$, in which each cell contains the coordinates of the ...
user avatar
  • 131
-1 votes
1 answer
39 views

Are there a Dynamic programming solution that partition number and minimize the sum of absolute difference of each partition?

Suppose given $n=2k$ numbers. We want partition numbers into two group $G_1,G_2$. Let $d_1$ be the largest value of absolute difference between each pair of numbers in $G_1$ and also $d_2$ be the ...
user avatar
  • 1
0 votes
0 answers
41 views

Understanding TAOCP paragraph "Will Keysorting help" in "external" sorting?

Near the end of subsection 5.4.9 Disks and Drums in 5.4. External Sorting, a process is sketched in a paragraph headed Will Keysorting help?: Schematically, the process has the following form: stage ...
user avatar
0 votes
0 answers
18 views

What makes Spectral kmeans clustering better than only Kmeans clustering?

I know that Kmeans clustering is the final step of Spectral clustering. But why is it that the previous steps involved in Spectral clustering make it a more convenient clustering approach? moreover ...
user avatar
  • 157
1 vote
1 answer
60 views

Split a graph before actually creating it

Consider a weighted graph $G=(V,E)$ of vertex set $V = \{v_1, ..., v_n\}$ and weighted edge set $E = \{\langle v_i, v_j, w(i,j)\rangle \mid i, j \in 1, ..., n\}$, where $w$ is the function that assign ...
user avatar
  • 549
2 votes
2 answers
42 views

Programmatically determine if a tie is possible in US elections

Problem 3.5 from book: "Algorithms for interviews". There are 51 states (+ Washington DC), each with different amount of votes. Find the number of votes of each state here Suppose there are ...
user avatar
  • 123
0 votes
0 answers
13 views

Naming the functions for Shaping the data for UI

Context I work as a frontend developer, our main stack is Graphql & React that's relevant for this question. The data I'm requesting can be quite complex and very often combined with several ...
user avatar
  • 1
2 votes
1 answer
53 views

(Algorithm required) How to determine if a point is in one of many rectangles

What I want to achive ist the following: I have a 2D plane and on this plane I will have a potentially large amount of rectangles (these are specified with 2 coordinates spanning it) Whats the most ...
user avatar
1 vote
1 answer
17 views

Find indices of equal cells in a matrix

I am trying to find the indices of all the equal elements in a matrix $\left ( n\times m \right )$. For each pair of matching cell, I will perform a specific function on them. For example: $ \begin{...
user avatar
1 vote
1 answer
34 views

Hints for efficient computation of the maximum length of a binary sequence

Given a positive integer $n$ I would like to compute $f(n)$, the maximum possible length of a binary sequence such that any substring of it (subsequence with consecutive elements), of length $n$, ...
user avatar
  • 113
4 votes
0 answers
141 views

Find a dynamic programming solution that minimize the sum of the diameters of two clusters?

I asked a question at this link, where I suggested a greedy algorithm for this problem: Suppose given $2n$ points in the plane and we want partition points into two clusters $C_1$ , $C_2$ such that ...
user avatar
  • 1
2 votes
1 answer
72 views

Does this greedy algorithm minimize the sum of the diameters of two clusters?

Suppose given $2n$ points in the plane and we want to partition points into two clusters $C_1$ , $C_2$ such that each cluster contains exactly $n$ points and we want to minimize the sum of the ...
user avatar
  • 1
1 vote
2 answers
46 views

Space-efficient way to prove that a data has been processed before

Suppose that I have a stream of data packets in the form of unsigned 64 bit integers. And I want to make sure that I am not processing the same packet content more than once. A way of doing this would ...
user avatar
  • 11
1 vote
0 answers
29 views

Is there an algorithm for generating non comparable boolean vectors?

First some context: A Boolean Network of $n$ components is a function $f$ from the set $\{0,1\}^n$ (set of vectors of $n$ components whose values are 0 or 1) to itself. The dynamical behavior of a ...
user avatar
0 votes
0 answers
16 views

Big O notation References and Resources

I am new to time complexity, and Big O notation. I have this question pertaining to this code in Python 3.X: ...
user avatar
2 votes
3 answers
641 views

Determines if the minimum spanning tree only uses edges with an integer weight, when E, V are in O(n)

Given a undirected graph $G=(V,E)$ with $|V|=n$ and $|E|=2022n$ and some weight function $w\colon E\to \mathbb{R}$, and $0≤ w(e) ≤n$ for all $e∈E$, Describe an algorithm that determines if the MST ...
user avatar
  • 55
4 votes
1 answer
118 views

Maximum sum of values in a square grid (one in each row/ column)

this is my first post here so bare with me :). What i'm looking for is an algorithm that can find the maximum sum of values in a square grid under the restriction, that you can only pick 1 value from ...
user avatar
  • 41
2 votes
1 answer
21 views

How to create tensors at runtime?

I have a small personal CAS project around linear algebra which involves, among other things, manipulating tensors. When I talk about tensors, I mean them according to the physical / mathematical ...
user avatar
  • 255
1 vote
1 answer
49 views

Time complexity of merging two lists while preserving order

I have two lists l1 and l2 of possibly unequal sizes (say, m and ...
user avatar
  • 11
1 vote
1 answer
77 views

How to tell if I know algorithms & I learned it right?

Notes I apologize if the question is not formed well, I tried my best. "Only" means anything else is discarded. A stupid man’s report of what a clever man says can never be accurate, ...
user avatar
1 vote
0 answers
26 views

Hashing for dot products

I've come across this problem that uses hashing to compute dot products (for non-negative vectors). Suppose we are in $d$-dimensional space and $M$ will be our target for our hash. That is we have a ...
user avatar
  • 21
1 vote
1 answer
72 views

Amortized analysis (accounting/banker's method) for tree operations

Suppose we have a tree data structure with root $r$ with two operations: Add($x, y$) - adds the node $y$ as a child to the node $x$ Zip($x$)- this makes the node $x$ and all of $x$'s ancenstors direct ...
user avatar
  • 21
0 votes
0 answers
20 views

Psuedo Code for A* with Adjency Matrix Graph

There are algorithms for A* but the algorithms use a pointer based representation of a graph instead of an adjacency matrix of a graph. I would like to know how to do the algorithm with an adjacency ...
user avatar
0 votes
0 answers
14 views

non-linear lower bounds for polynomial time decision problems [duplicate]

Are there any decision problems that have deterministic polynomial time algorithms and proven non-linear lower bounds?
user avatar
  • 1
1 vote
1 answer
34 views

Order List of Sets so Adjacent Sets are Disjoint

Let $n \in \mathbb{N}$ and $G := \{1,2,...,n\}$. Now let $P_2(G)$ be a power set of $G$ but only with sets of cardinality $2$, e.g. if $n = 3$ then $P_2(G) = \{ \{1, 2\}, \{1, 3\}, \{2, 3\} \}$. Now I'...
user avatar
  • 47
0 votes
0 answers
32 views

How to compute efficiently the winner of a chess match where players are algorithms

This is my problem: The chess match starts with a board where chess pieces are randomly placed. Both players are controlled by the same deterministic algorithm so if two games start with the same ...
user avatar
1 vote
0 answers
21 views

What is "energy" in computer vision

I keep seeing the term "energy" used in computer vision literature, specifically when speaking about Image Segmentation. For example on this page on Graph-Cut. I'm just wondering if someone ...
user avatar
1 vote
0 answers
33 views

Proving the least number of operators required equals $min((x-target)*2, (target*2)-1)$

Here is the source for the problem below: https://leetcode.com/problems/least-operators-to-express-number/discuss/1675169/java-or-recursion-or-greedy-or-math For completeness, below is the problem ...
user avatar
7 votes
3 answers
2k views

What is the fastest algorithm to approximate an irrational number with specified precision?

Problem Background: Let $a\in(0,1)$ to be an irrational number. Suppose there is a black box, the input is a real number in $[0,1]\backslash \{a\}$, denoted as $x$, the black box outputs boolean ...
user avatar
1 vote
1 answer
35 views

Prove an edge that minimizes the Euclidean distance crossing a cut is in the Delaunay triangulation

Let $P$ and $Q$ be two disjoint point sets in the plane. (Think of them as a red point set and a black point set.) Let $p \in P$ and $q \in Q$ be two points from these sets that minimize the Euclidean ...
user avatar
  • 157
-2 votes
3 answers
86 views

Is O(k*n) in this case linear?

Problem: find sum of k element in array and it is biggest? time complexity of my algorithm is O(k*n).Is it linear complexity?
user avatar
1 vote
0 answers
29 views

Are there any algorithms that become much easier to design & implement in reversible computation settings?

If your program can move backwards (even if just for a preset amount like 10,000 atomic steps), then it's easier to do these things: Undo/Redo history (automatically for everything). This can be a ...
user avatar
0 votes
0 answers
27 views

How to find the second most closest pair of points modifying the Divide and Conquer?

I know the Divide and conquer approach for the finding the closest pair of points and the proof of correctness. Can we modify it in such a way so that , we can find the 2nd most closest pair. I am ...
user avatar
  • 157
2 votes
1 answer
87 views

Efficient "radius-search-based averaging" algorithm on a set of 3-D points that lends itself to massive parallelization without locking

I'm looking for a good algorithm for "simple radius-search-based averaging" (or "radius search based sub-sampling") as referred to section 3.4 of the DynamicFusion article. ...
user avatar
0 votes
0 answers
35 views

Fast Algorithm To Compute Gradient Of Gaussian Blur

what is the fastest algorithm to compute the gradient of the Gaussian blur of a (grayscale) image, with a blur radius of around 100 pixels, where smoothness of the result is important to me, i.e. no ...
user avatar
  • 215
0 votes
1 answer
26 views

Bellman Ford may not update distance correctly by termination?

Consider the example shown in the above figure. Let's consider two orders (1) S, A, B and (2) S, B, A for traversing the graph and updating the distance d (numbers in circle are distance d): 1- start ...
user avatar
2 votes
0 answers
85 views

What is ridge in hill climbing algorithm?

I am studying hill climbing algorithm and this topic seems so confusing. What is ridge basically? Can you show an example while searching using hill climbing when ridge occurs? I have researched in ...
user avatar
0 votes
0 answers
32 views

Why is the time complexity of introspective sort O(n log n)?

I understand that intro sorts avoids the running time O(n^2) of quick sort, by changing to heap sort when the algorithm exceeds a certain recursion depth. But what about insertion sort? It kicks in ...
user avatar
0 votes
0 answers
32 views

An introductory book on graph transformation algorithms

I am looking for a preferably modern book on graph transformation algorithms. I am really interested into general approaches not on mathematical proofs and rigor notations. The easier the read, the ...
user avatar
  • 101

1
3 4
5
6 7
210