# 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
Filter by
Sorted by
Tagged with
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. ...
17 views

1 vote
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 ...
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.
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 ...
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 ...
1 vote
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 ...
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....
1 vote
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 ...
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 vote
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 ...
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 ...
1 vote
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 ...
1 vote
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 ...
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 ...
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, ...
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$ ...
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{...
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 ...
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. ...
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 ...
1 vote
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 ...
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$? ...
1 vote
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 ...
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),...
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 ...
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 ...
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 ...
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 ...
25 views

### Understanding MTD-f

In the MTD-f algorithm: ...
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 ...
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: ...
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 ...
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 ...
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 ...