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.
10,497
questions
0
votes
1
answer
4k
views
Inorder Traversal of the Ternary Tree
As per Wikipedia, Algorithm for In-order Traversal of Binary Tree
If the current node is empty/NULL/None return nothing.
Traverse the left subtree by recursively calling the in-order function.
...
- 207
0
votes
0
answers
17
views
Find a set K of k vertices in a graph such that the distance between any vertex to the closest vertex in K is minimized
Given a graph with $V$ vertices and $k$, find a set $K$ of $k$ vertices of $G$. Let $c(v)$ be the distance (in BFS-like) of the vertex $v \in V$ to the closest vertex $u \in K$. How to choose the set $...
- 967
0
votes
1
answer
2k
views
Algorithm for finding the longest common subsequence using hash table. Why is it slow?
I've designed an algorithm to find the longest common subsequence. The steps are:
Start with i = 0
Picks the first letter from the first string start from $i^{th}$ ...
- 207
1
vote
1
answer
20
views
Is there an algorithm that in some cases is an improvement of BFS in the same way A* is an improvement of Dijkstra?
The problem concerns finding shortest paths in graph from a single source to a single destination.
So in a general non-degenerate case of a weighted graph, Dijkstra's algorithm runs in O(E+VlogV). A* ...
- 7,002
2
votes
1
answer
538
views
Find maximum length subarray whose bitwise AND is at least $k$ in $o(n^2)$
Given an array $A$ of unsigned integers, a subarray is a contiguous interval $A[\ell],\ldots,A[r]$. The bitwise AND of the subarray is just the bitwise AND of $A[\ell],\ldots,A[r]$ (what is denoted by ...
CommunityBot
- 1
0
votes
1
answer
343
views
An interesting plane sweep algorithm?
I'd like to devise an algorithm which, given n non-intersecting line segments in
the plane and a point p that does not lie on any of these segments, determines the region of the plane that is “visible”...
- 161
0
votes
1
answer
40
views
Finding a Hamiltonian Cycle in a directed graph - graph problem
$N$ towns are given, which we can get to by passing through the northern and southern gates. If you enter a town through a gate, you have to use another gate to leave the town. The merchant would like ...
0
votes
1
answer
17
views
Is there an algorithm for mapping two ambiguous and unrelated data sets?
I was curious to see whether or not there was a common algorithm for mapping two unrelated data sets.
So for example let's say I wanted to give you a spirit animal based on your name, birthday, zodiac ...
- 3,231
1
vote
1
answer
541
views
Represent unsigned 12-bit octal numbers. Results in octal
I have an HW question where I found an answer that matches mine, but their breakdown confuses me.
Ques: What is 4365 - 3412 when these values represent unsigned 12-bit octal numbers? The result should ...
CommunityBot
- 1
2
votes
0
answers
1k
views
Find worst-time complexity for a problem on matching a simple regular expression? [duplicate]
I am not looking for the complexity of following algorithm but rather how to think about the problem and calculate complexity of a given solution?
One way is to perhaps use The Master Method for ...
- 121
0
votes
1
answer
27
views
Algorithm to calculate the period where cumulative days within a rolling period exceeds a threshold
I'm struggling to think of the algorithm to transform one data set to another.
The problem I'm looking at is creating a dataset of periods of time where cumulative days absent within a period (eg 30 ...
- 1
2
votes
3
answers
2k
views
Given a set of 2D vectors, find the furthest reachable point
Input: a set of 2D vectors $S=\{v_1,v_2,\dots,v_n\mid v_i\in \mathbb{Z}^2 \}$
Question: name $P=\{\sum_{v_i\in S'}v_i\mid S'\subseteq S \}$
for all subsets of $S$ (obviously $|P|=O(2^n)$). In
...
- 161
5
votes
2
answers
180
views
Finding the cheapest buy order with fixed inflation for each product
Let's say we have a set of products $M$, a total of $|M|=n$ that we want to buy. However, we can only buy one product at a time, so that we need a total of $n$ time-units to buy all items.
Each ...
- 163
0
votes
0
answers
34
views
Understanding the Rectilinear Spanning Tree Algorithm
I am required to find a Rectilinear Spanning Tree in $\mathcal{O(n\log(n))}$, where $n$ is the number of vertices to connect.
A Rectilinear Spanning Tree is a spanning tree made of nodes where each ...
D.W.♦
- 140k
1
vote
1
answer
51
views
Is there an algorithm for reducing CNFs further?
I have a Boolean formula in conjunctive normal form (CNF)
$$(a\vee b \vee c) \wedge (a \vee b \vee \neg c) \wedge (x \vee y)$$
I know that this can be simplified to $(a\vee b)\wedge (x \vee y)$.
Is ...
0
votes
0
answers
51
views
Find minimum cost cycle in graph G=(V,E) that visits vertices in required subset V′⊂V exactly once & covers edges in required subset E′⊂E atleast once
I have been researching about general routing problems and came across a problem similar to the Travelling Salesman Problem:
Find a minimum cost cycle in a graph $G = (V, E)$ which visits vertices in ...
D.W.♦
- 140k
2
votes
2
answers
45
views
Delete consecutive characters and add zeros at the end with a restriction
Given an array of characters, I need to delete all the characters that got repeated 3 or more times (consecutively) and add '0' at the end of the array for every deleted character,
The restrictions:
$...
- 1,257
1
vote
1
answer
25
views
Find the largest subset of unpaired elements [duplicate]
I have a large list (around 200k) of element pairs (e.g. A-B, A-C, B-C, ...). How can I find the largest subset of elements amongst which none are paired?
Example ...
- 1,005
0
votes
2
answers
42
views
Is there any open resource to study randomized algotithm?
I am a student want to study randomized algorithm. Someone recommend cs271 to me, but it's restricted now.
Can someone recomend a good resource to study randomized, thank you a lot.
- 113
2
votes
1
answer
70
views
Is $m \log^2 n$ complexity too much?
I have been struggling for a few hours in terms of finding the right solution for the following problem:
Suppose we have a file that contains integers where each represents a user of a service. By ...
- 1,005
0
votes
0
answers
30
views
Special case of single vehicle routing
I have a metric space $(V,d)$ described by a tree $T$. And I have $k$ pair of vertices $\{s_i,t_i\}$ ($i \in [k]$) s.t. each of the vertices $s_i$ and $t_i$ are leaves of $T$. There is a car at one ...
- 2,851
1
vote
1
answer
53
views
Find max of all trees resulting from single edge removal in generic tree in linear time
Given a generic tree with $n$ weighted nodes, there are $n-1$ edges. Removing any of the edges will partition the tree into two distinct trees, hence we can construct $2(n-1)$ possible trees in this ...
CommunityBot
- 1
3
votes
1
answer
2k
views
Run Christofides algorithm by hand with wrong result
I am following this algorithm example: https://en.wikipedia.org/wiki/Christofides_algorithm#example
The graph:
Calculate minimum spanning tree T:
Calculate the set of vertices O with odd degree in T....
- 32.9k
1
vote
1
answer
51
views
Formal Proof on why Greedy isn't working on one Particular Problem
Problem
You are given two integer arrays nums and multipliers of size n and ...
- 1,005
2
votes
2
answers
52
views
What does "index up to $n^c$" mean in this question about CLRS "word size $c \lg n$"?
I don't know where else to ask this. And I don't know when or if I'll get reply at all if I comment on that answer. I was reading this answer on a text of CLRS and in the last line got confused. I ...
- 1,005
1
vote
3
answers
480
views
When would it be optimal to use an Edge List as opposed to an Adjacency List / Matrix when representing a graph?
This seems to be my first ever question :)
Given that adjacency lists store all the necessary information with regards to the endpoints of an edge, we could even store a weight alongside that.
I don't ...
- 1,005
0
votes
2
answers
92
views
About the properties of the coresets in k-median clustering
I have seen two observations from the paper by Har-Peled but I do not know how to prove them
(i) If $C1$ and $C2$ are the $(k, ε)$-coresets for disjoint sets P1 and P2 respectively, then $C1 ∪ C2$ is ...
CommunityBot
- 1
1
vote
1
answer
157
views
How to prove that one problem belongs to class P?
Is there any formal method to prove that one problem belongs to Complexity Class $\mathbb{P}$?
For example, how can we prove that the problem of finding $n^k$ belongs to Class $\mathbb{P}$? We can use ...
- 32.9k
1
vote
1
answer
36
views
Searching a hierarchy for progressive node criteria
In our organization we have various business units that organize their data in different ways. The folder structure can vary, but they abide by business unit practices when making backups etc.
I am ...
CommunityBot
- 1
4
votes
3
answers
6k
views
Spanning tree with chosen leaves
I'm working on the following problem:
Suppose that we're given a connected, undirected graph $G = (V, E)$ with
edge weights $w_e$ and a subset of vertices $U \subset V$. We want to find
the lightest ...
D.W.♦
- 140k
3
votes
1
answer
168
views
Amortized analysis on a dynamic table that grows its size by $\sqrt{size} $
The following problem is based on the section about dynamic table as part of the discussion about amortized analysis in CLRS
Problem: We are given a dynamic table $T$ that supports INSERT operation, ...
- 32.9k
0
votes
0
answers
27
views
Wrong Solution for `Spanning tree with chosen leaves` problem
Suppose that we're given a connected, undirected graph $G = (V, E)$ with
edge weights $w_e$ and a subset of vertices $U \subset V$. We want to find
the lightest spanning tree in which the nodes of $U$ ...
- 1
0
votes
2
answers
44
views
Optimizing an arbitrary function of 10 variables
Let us be given a function $f(x_1,\dots,x_{10})$ of multiple variables $x_1,\dots,x_{10}$ given that $\sum_{i=1}^{10} x_i \leq 7$. How do we solve the following problem?
$$
\begin{equation}
\begin{...
D.W.♦
- 140k
0
votes
2
answers
908
views
CLRS Exercise 24.3-4 - Confirm Output of a Program Claiming to Implement Dijkstra's Algorithm
I'm trying to better understand Question 24.3-4 From CLRS below:
Professor Gaedel has written a program that he claims implements Dijkstra’s algorithm.
The program produces $v.d$ and $v.\pi$ for ...
CommunityBot
- 1
2
votes
1
answer
117
views
Sorted list of counters in constant time
Summary.
A data structure maintains in constant time a sorted list of counter values, for a dynamic set of counters. I am interested in references using this structure, and in possible improvements.
...
- 11k
0
votes
3
answers
266
views
Travelling Salesman Problem Easy Algorithms
I'm looking for a easier algorithm to implement to solve the travelling salesman problem (in javascript).
Unluckily all of the ones i found are really hard to understand/ to implement.
The ones i ...
CommunityBot
- 1
1
vote
2
answers
51
views
Find largest set of players that never played against eachother
I have an interesting problem I need to solve.
I have a list of about 200k two player matches containing about 22k unique players.
I need to find the largest set of players that never played against ...
- 956
2
votes
1
answer
94
views
Computing the partition function
Are there in any relatively efficient known algorithms to compute the partition function $P(n)$ for a given $n$? What's known about the complexity class of this problem as a function of $n$?
...
- 32.9k
1
vote
1
answer
32
views
Sum in counting satisfying assignments
Is there a polynomial-time algorithm that computes the sum of two boolean formulas, such that, (#SUM(F,G) = #F + #G), the output satisfying assignments equals the sum of the satisfying assignments of ...
- 268k
3
votes
2
answers
80
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),...
- 603
0
votes
1
answer
73
views
speed up straightforward solution using dynamic programming
i recently got onto the following problem: we consider the following array:
A = [2, 3, 6, 1, 6, 4, 12, 24]
we need to count the number of times these two ...
CommunityBot
- 1
0
votes
0
answers
19
views
Is this how Interval Partitioning Problem aka interval graph coloring problem works?
You can refer the problem on later part of section 4.1 in "Algorithm Design Book by Jon Kleinberg and Éva Tardos"
Problem: We have "n" lectures and we our job is to assign all of ...
-1
votes
2
answers
749
views
Why is Hamiltonian Path and graph coloring np complete and shortest path p when the former can also be solved using DFS recursively?
NP is a complexity class that represents the set of all decision problems for which the instances where the answer is "yes" have proofs that can be verified in polynomial time. But hamiltonian path ...
- 101
0
votes
1
answer
47
views
Algorithm for generating sorted lists of random floats
More out of curiosity than anything else. I know you can always generate a list of random numbers and then sort it, but I was wondering if there exists a (pseudo)random number generator whose output ...
D.W.♦
- 140k
2
votes
0
answers
25
views
0
votes
0
answers
22
views
What is the best algorithm to flip a triangle?
I'm trying to flip a triangle like this in the following image:
there are two constraints in flipping it:
1- flip it with the minimum circles moves
2- the circles is sliding from a place to another ...
- 1
2
votes
1
answer
209
views
Show all chains per user
Some time ago I had in one of the big tech interviews the following question that I still don't know how to approach it.
You have a chains of reservations from AirBnb:
...
0
votes
1
answer
132
views
Kernelization algorithm for the following problem
We are given an undirected graph $ G $ and a positive parameter
$ k \geq 0 $. The problem is to decide if there exists a set $ S \subseteq V(G) $ of size at most $ k $ such that $ G − S $ does not ...
CommunityBot
- 1
0
votes
2
answers
387
views
Write a pseudo code for a Graph algorithm
Given a DAG $G=(V, E)$ and a function $f(v)$ which maps every vertex to a unique number from 1 to $|V|$, I need to write a pseudo code for an algorithm that finds for every $v\in V$ the minimal value ...
CommunityBot
- 1
0
votes
1
answer
91
views
Algorithm for display nodes of a particular node based on in-degree and out-degree
Suppose we have following directed graph. When I click on say node $e$, it should make in-degree and out-degree of node $e$ and connected nodes red. As shown in Resulting Graph. My purpose is, when I ...
CommunityBot
- 1