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
0answers
17 views

Multi-Interval Discretization of Continuous-Valued Attributes for Classification Learning

I'm trying to figure out Fayyad and Irani (1993) MDLP discretization of continuous variables (here is link to the original paper). I understand how algorithm works, but I have some doubts about first ...
4
votes
1answer
100 views

minimum travel from point to point with incremental steps

It's my first time to make a question here. I have a curious problem about algorithm, in the center of Cartesian plane (0,0) I need to go to another point (x,y) -x and y are belong to Z numbers - but ...
1
vote
0answers
23 views

Recording a histogram in a tree exhibits strange best case

The task is to record a histogram from a streaming data source. One data point is, say, a 16 bit integer. The maximum multiple of one data point before the stream ends, is < 2^32. The main ...
0
votes
0answers
51 views

Cotree Generation

Given a co-graph like the one attached as an input what are the steps that I have to follow in order to generate its co-tree? Is there a step-by-step algorithm to do that?
1
vote
2answers
140 views

Find the length of the longest subarray having sum greater than k

I tried to solve this problem but could not do it better than $O(n^2)$. My Algorithm: ...
1
vote
0answers
45 views

CSES Range Query Question: Index Compression and Updates [closed]

I'm trying to solve this problem: https://cses.fi/problemset/task/1144/ Given an array of up to 200000 elements, my task is to process up to ...
3
votes
0answers
19 views

Algorithm to count number of overlapping rectangles of the same colour?

Say you have a grid of pixels. And there are 20 overlapping red rectangles on a blue background. I want to find an algorithm to count the minimum number of rectangles that are needed to form the image....
1
vote
0answers
14 views

Algorithm for drawing the horizon given the current coordinates, elevation and field of view

I have a large database containing coordinates along with an elevation number. If I am a person looking in some direction (0-360) with an n degree field of view, and located at some coordinate and at ...
-1
votes
1answer
36 views

How to know if time complexity is O(n+m) or O(n*m)

I'm having difficulty understanding when can we know if the time complexity of an algorithm is n+m or n*m Is the time complexity of the following algo O(n+m) or O(n*m) Can you please point me to a ...
2
votes
1answer
62 views

Remove vertices until no edges are left

Given an undirected graph G(V,E), find the minimum number of vertices to remove so that the Edge Set of the graph becomes empty. In other words: If we remove one vertex we remove that vertex along ...
0
votes
0answers
21 views

Extending a solution in backtracking

Steven Skiena's "Algorithm Design Manual" has the following code for the backtracking algorithm: ...
0
votes
0answers
47 views

Potential Example of an algorithm failure

I was looking an algorithm to solve a problem of finding whether and array contains a quadruple with sum = k,(k is input) mentioned at GeeksforGeeks. In one solution the approach mentioned is below,...
1
vote
0answers
22 views

Range Query Question: Removing Items from a List

My task is to input a given list of size N, then process N queries that remove an item from the list and then print it to the ...
0
votes
1answer
40 views

Universal Turing Machine algorithm

First, I learned this based on these facts: Turing machine (TM) will be define with 7-tuple Notation, $M=\langle Q,G,b,S,d,q_0,F\rangle$. Any computation rules that can use to simulate any possible ...
1
vote
0answers
44 views

Algorithm for summation with lowest maximum temporary sum

I've got this problem on my last exam, which I struggle to deal with. Let's say we have array of $N$ integers (it can be float too, but let's say integers for sake of simplicity. We need to sum those ...
2
votes
0answers
65 views

Minimum number of nodes to select such that every node is at most k nodes away

I received this problem on an exam a few months ago, and have kept thinking about how to solve it with no luck. Given a binary tree where each node in the tree can either be selected or unselected, ...
0
votes
2answers
42 views

Schedule Optimization With Priority and Weighted Costs

I need an algorithm to determine the best itinerary for a series of events. Each event has a time, location, and reward. Arriving at an event in time yields the reward; too late means no reward. Each ...
0
votes
0answers
29 views

How do we sort the chunk in the first pass of external merge sort?

Referring to the 9th page of a slide, when we use multi-pass multi-way external merge sort on a file with $N$ pages using $B$ buffer pages, in "pass 0" we'll read a chunk of $B$ pages into ...
2
votes
1answer
32 views

Approximation factor preserving reduction

The definition of approximation factor preserving reduction from the book by Vijay V. Vazirani, page 365: Let $\Pi_1$ and $\Pi_2$ be two minimization problems, an approximation factor preserving ...
0
votes
0answers
22 views

What is the most efficient way to turn a list of directory path strings into a tree?

I'm trying to find out the most efficient way of turning a list of path strings into a hierarchical list of hash maps tree using these rules: Node labels are delimited/split by '/' Hash maps have the ...
1
vote
1answer
30 views

Median of distribution with memory constraint

Task I want to approximate the median of a given distribution $D$ that I can sample from. A simple algorithm for this, using $n$ samples, is: ...
0
votes
1answer
48 views

Dynamic Programming - Tiling Question

I came across the following question while practising for my final algorithms exam, but I am unsure how to get a linear time complexity for this problem. I assumed it would require checking which ...
1
vote
0answers
72 views

Minimum vertex cover and odd cycles [closed]

Suppose we have a graph $G$. Consider the minimum vertex cover problem of $G$ formulated as a linear programming problem, that is for each vertex $v_{i}$ we have the variable $x_{i}$, for each edge $...
0
votes
1answer
32 views

Approximate bin-packing?

Let $X_1,...X_n$ denote some bins, and $w_1,...w_m$ some positive real numbers, where $m \in \mathbb{N}$, and the order matters, so e.g. we can't switch the position of $w_n$ and $w_1$. The goal is to ...
0
votes
1answer
53 views

Algorithm to find all connected objects

I'm creating a webapplication in which I render multiple objects using Three.js. These objects are saved in a list and can be connected to each other (but don't have to be), and when they are, they ...
1
vote
1answer
66 views

When and Why do I Rehash?

I am studying hashing and reading the part of universal hashing. I have read that I want to draw a hash function from universal hash families when I rehash. When and why do I rehash? One reason to ...
0
votes
0answers
44 views

Why do we need MinHeap for Meeting Rooms 2 Leetcode problem

I came across this problem online which is a Leetcode premium problem. Most of the people are solving this using Minheap. To me using minHeap for this seems like repetitive way to solve a problem if ...
0
votes
1answer
40 views

social network analysis - relations between people with weights

I asked this question on datascience.stackexchange but they directed me here. I have a social network represented as a set of people S and individual weights for each of person (weight is the cost of ...
2
votes
1answer
90 views

Calculate the area of the shape created by multiple paths

I'm trying to write an algorithm to calculate the area created by multiple paths that can be overlapping or not. Here is an example: Basics 4 separate paths (A,B,C,D) which are a collection of ...
0
votes
1answer
27 views

Latin-1 Supplement Unicode Characters

The unicode characters under the "Basic Latin" unicode block from U+0001 to U+007F are the characters that characters we use in English. However, the "Latin-1 Supplement" block ...
1
vote
1answer
82 views

Minimum number of given operations in order to group letters in a string

Description Suppose we have a string containing letters 'A', 'B', 'C', 'D', and the characters are placed in a stack. We also have an empty stack. Ultimately, we want all of the same letters to be ...
0
votes
1answer
46 views

Find Index In Sorted Array Such That A[i] = C1 * i + C2

I'm already know that there is an algorithm that can solve A[i]=i in O(log(n)) in a sorted array. But I want to know if there is any kind of algorithm that also can solve A[i] = C1 * i + C2 (witch C1 ...
0
votes
1answer
23 views

Remove features with too little variation

I have the following messy chart; As you can see some features are very stable through the time series (post-2011) like Extraversion. Is there an algorithm to remove features that do not have much ...
1
vote
0answers
10 views

Why Burrow's Wheeler Matching (FM-Index) is favored for DNA read matching

I noticed that FM-indexing is a preferred way to match strings in large data sets, and in particular DNA sequencing wiki-article. I know that with this method, it can eliminate space dependencies ...
1
vote
1answer
41 views

How does each element in the output array of a DFT correspond to a specific frequency?

I have a basic understanding of the Fourier Transform, though I'm trying to use it in a program and I'm confused on the specifics. Based on source code I can find online, the DFT takes a set of ...
1
vote
0answers
42 views

2SAT problem testcase does not have any strongly connected components

My task is to solve the 2SAT problem. I have read online that a good method to solve this problem would be to construct an implication graph, where each statement of the form ...
1
vote
0answers
41 views

Understanding the proof of “DFS of undirected graph $G$, yields either tree edge or back edge” better with graph for each statement in proof

I was going through the edge classification section by $\text{DFS}$ algorithm on an undirected graph from the text Introduction to Algorithms by Cormen et. al. where I came across the following proof. ...
0
votes
3answers
413 views

Greedy algorithm for vertex cover

Given a graph $G(V, E)$, consider the following algorithm: Let $d$ be the minimum vertex degree of the graph (ignore vertices with degree 0, so that $d\geq 1$) Let $v$ be one of the vertices with ...
1
vote
1answer
38 views

Why selection sort is a stable sort algorithm?

One of the specifications of sort algorithms is stability, which means items with the same value in different indices are not replaced after applying sort algorithm. Why selection sort is unstable and ...
1
vote
1answer
53 views

Interview q: Small possible length of stick from an array of stick lengths

I was asked this question in a phone interview recently and I bombed it completely. Zero clue how to approach it. I wasn't able to find any similar patterns on google-ing. Thought maybe folks here ...
2
votes
1answer
78 views

what will be space complexity for snippet for(i=1 to n) int x=10;?

The space complexity of the code snippet given below: ...
0
votes
0answers
34 views

'Traders's Route' problem optimization algorithm

I've come up with a problem which we'll call the Trader's Route Problem (If it's an already understood problem that would be great as well, let me know). Say there exist N cities, with some arbitrary ...
1
vote
1answer
41 views

Difficulty in understanding a portion in the proof of the $\text{“white path”}$ theorem as with in CLRS text

I was going through the $\text{DFS}$ section of the Introduction to Algorithms by Cormen et. al. and I faced difficulty in understanding the $\Leftarrow$ direction of the proof of the white path ...
1
vote
1answer
81 views

Distributed predicate computation on event stream

My question is actually a request for papers, articles, texts or books on the problem that I'm trying to solve on my work. I'm working on a program that computes a predicate value (true or false) for ...
0
votes
0answers
24 views

Is this distribution of amount to set by weight a type of Bin Packing Problem and what are names of common algorithms to solve?

Does the following requirement, or subsets of it, have a problem name I can use to explore optimal solutions? I struggled to find a good Question Title. I need to distribute an amount(Freight) to ...
-5
votes
2answers
100 views

solving recurrence T(n) = T(√n) + theta((lg lg n))

My solution: let m = lg n. Then n = 2^m. T(2^m) = T(2^(m/2)) + theta(lgm). Let S(m) = T(2^m). Then S(m) = S(m/2) + theta(lgm). Applying master theorem, I get m^(lg1) = 1 which is asymptotically ...
0
votes
1answer
36 views

Fast query on the number of elements in a quarter plane

I have a scatter of 2D elements on a 2D plane. I would like an efficient algorithm to prepare and query the number of points in a quarter plane (inclusive of boundary). The quarter plane is defined by ...
2
votes
1answer
101 views

Minimum vertex cover algorithm with linear programming

Consider the following algorithm: given a graph $G$ with $n$ vertices, set up a linear programming problem LP where there is a variable $x_i$ for each vertex $v_i$ of $G$, each variable can take value ...
2
votes
2answers
57 views

Algorithm for Estimating Number of Unique Monthly Visitors

Is there a way to estimate the number of unique monthly visitors to a site based on a limited sample of one week of data? I have information about when a given user visited the site. This isn't as ...
0
votes
0answers
36 views

Devising an algorithm to remove “complete” sets of numbers from a list of numbers

Suppose I have a list of numbers consisting of numbers 1 through 5, where some numbers repeat. Define a set of numbers to be "complete" if it consists of each of the numbers 1-5 exactly once....

1
3 4
5
6 7
178