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
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. ...
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 $...
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}$ ...
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* ...
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 ...
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”...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 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 ...
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.
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 ...
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 ...
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 ...
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....
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 ...
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 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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
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$ ...
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{...
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 ...
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. ...
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 ...
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 ...
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$? ...
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 ...
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),...
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 ...
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 ...
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 ...
2 votes
0 answers
25 views

Understanding MTD-f

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

1
2 3 4 5
210