# 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,130 questions
Filter by
Sorted by
Tagged with
13 views

### How do i delete one single unequal element from an array of equal elements without using hashing?

the rules of the question states that: Only one element is different Rest are all same. Array A size is 8. I need to find the different element and remove it (Hashing cannot be used). I have not ...
14 views

### How to efficiently see if a value is in a set

I was curious is there a really efficient way to see if a value is in a set? This question comes from me thinking about youtube views. As far as I understand youtube view count goes up for every ...
13 views

### Modifying the probability of sucess of an algorithm

This is motivated from a homework question. Let $A$ be an algorithm with probability of success equal to $q$ for solving a given problem. Let $p \in (0, 1)$. Find an algorithm that has a probability ...
14 views

### Largest rectangle covering set bits in a bitmap

I have a 2D bitmap with various shapes (each pixel is either 1 or 0). How can I find the largest axis-aligned rectangle that covers only set pixels?
33 views

### Storing a file by converting it into $n$ files, some of which can be lost

Let's say that I have a file that I really don't want to lose. I want to convert the original file into $n$ files in the way that will allow me to recover the original file if I have any $m$ of the ...
10 views

### Split-Ordered Lists: Lock-Free Extensible Hash Tables

I am reading the research paper "Split-Ordered Lists: Lock-Free Extensible Hash Tables" by Nir Shavit and Ori Shalev. https://dl.acm.org/doi/10.1145/1147954.1147958 I was just wandering if ...
212 views

### Changing a relation to become transitive

Given a binary relation $R$ on a finite set $S$, is there an efficient algorithm to transform $R$ to a transitive relation $R'$ by minimum number of addition or deletion of pairs $(x,y)$ to or from $R$...
37 views

2k views

### Real life examples of negative weight edges in graphs

I am unable to relate to any real life examples of negative weight edges in graphs. Distances between cities cannot be negative. Time taken to travel from one point to another cannot be negative. ...
13 views

### Resources to self-study counting/sorting networks

I am reading The Art of Multiprocessor Programming. I was able to grasp almost everything up to Counting Networks in chapter 12 - Counting Sorting and Distributed Coordination. However I am having ...
25 views

### What Graph Algorithm can determine ideal distribution of items to travel the least amount of distance from any node?

I have a problem that's been bugging me, but I'm not sure what algorithm can solve it. Alice has medicine that she needs to use as quickly as possible in case of an allergy attack. She wants to ...
17 views

### Treap use cases

I am trying to develop an appreciation for the treap data structure; my goal is not to implement one but use boost when the problem calls for this construct. Some use cases, or small problems showing ...
70 views

### prove that a problem is np-complete using sat [closed]

How can I prove that a problem is NP-complete using a version of SAT? I have a set S of element that make some subsets (B1, B2,..., Bn) and I have another sets T1, T2,...,Tk. I need to find some set G(...
20 views

### Algorithm for homogenization of non-equidistant 1-D grid

I am looking for proper algorithm for so called "delta-homogenization" of 1-D non-equidistant grid. Definition: The sorted monotonically changing vector $x = x_{homogeneous}$ is $\delta$-...
14 views

### Are there any quick and non-branching algorithms for following a point graph?

I'm moving a heavy-duty part of my code to be computed with opencl on a gpu. Its been a while since I did anything on a GPU but from what I remember, any kind of branching is bad so I'm thinking of ...
42 views

### Minimize number of operations to compute thousands of expressions over hundreds of variables

I have an expensive operation; I'll use the symbol + and the word "concatenation" to represent it. This operation is: Binary: ...
69 views

### Having a lot of trouble trying to reason the formal definition of Big O

My professor recently brushed over the formal definition of Big O: To be completely honest even after him explaining it to a few different students we all seem to still not understand it at its core. ...
19 views

### How do video games like Age of Empires code how a soldier spots an enemy soldier and decides to attack?

I was just curious how do RTS games actually implement this. There are usually thousands of units on the whole map. They all have usually unique range of sight and then there's also settings for ...
34 views

### Why does the exact string matching brute force algorithm not compare index 1 of P with index 1 of S in the first round of the for?

In my ADS course we were given this pseudo code for the "exact string matching brute force" algorithm: ...
22 views

### Complexity of insertion into a linked list, single vs double

At https://www.javatpoint.com/singly-linked-list-vs-doubly-linked-list, it says: In a singly linked list, the time complexity for inserting and deleting an element from the list is O(n). And: In a ...
16 views

### Determine whether the system of equations is underdetermined or overdetermined

Suppose I have a set of $n$ equations (each equation can be linear or quadratic). I want to determine whether the system is underdetermined or overdetermined. For example, $a_1=2,a_1=3$ is ...
40 views

### Streaming interval cover algorithm

I'm given a target integer range $[x, y]$ which needs to be covered $n$ times, and a stream of integer ranges $[x_i, y_i]$. I need an algorithm which consumes integer ranges from the stream and ...
52 views

### All possible sum of each array combination

Is there a name for this algorithm? I have an array {1,2,3} and all my possible sums are {1},{2},{3},{1+2},{1+3},{2+3}, {1+2+3} = {1},{2},{3},{4},{5},{6} {1,1,2} => {1}, {2}, {3}, {4} I tried to ...
18 views

### Time complexity analysis of shannon-feno and huffman coding technique

what is the worst case analysis of Huffman coding and Shannon–Fano coding in generalized form is any better explanation plz suggest me.
1k views

### Find shortest path between two vertices that uses at most one negative edge

Given a directed graph $G = \langle V,E \rangle$ with $n$ vertices and $m$ edges and a weight function $w:E \rightarrow \mathbb{R}$, together with two vertices $s$ and $t$ in $V$: Describe an ...
21 views

### Shamos algorithm , cannot understand the Area part

I wanted to find shortest time algorithm for finding the diameter of a convex hull, so I found Shamos algorithm on wikipedia: ...
33 views

### modify dfs to find longest path

Let $G = (V, E)$ be a directed acyclic graph. Let every node $v \in V$ have an additional field $v_d$. For each vertex $v \in V$, we need to store in $v_d$ the length of the longest path in $G$ that ...
22 views

### Searching for sorting algorithm taking into account all possible solution of similar numbers

I need a reference for sorting algorithm where all possible orders are considered. example: if we have four values of n, and we do know there values n1(3) n2(5) n3(5) n4(10) and want to order them in ...
20 views

### Handwritten sources of first inventors

When I was undergrad student, wondering how the inventor of the algorithm thinks like that. What was he/she writing out/drafting on papers/boards? I still cannot throw the thougt out the window, even ...
30 views

### Compute intersection points of n circles

Let $S$ be a set of $n$ circles in the plane. I need to describe a algorithm which computes all the intersection points of the circles. The algorithm should run in $O((n + k)\log n)$ time, where $k$ ...