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
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
3
votes
1answer
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?
3
votes
2answers
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 ...
0
votes
0answers
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 ...
3
votes
1answer
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$...
3
votes
1answer
37 views

Shortest possible path between closest pair of specific nodes in a maze

Need to find the shortest distance between the closest pair of 'r' and 'b' nodes. You can traverse along '.' elements, but not 'o' elements. How can we do this in $O(MN)$ time? (M rows, N cols). $O(...
2
votes
1answer
27 views

Optimal order to minimise time until first success

Say you are a salesperson and you want to make a sale; there are $N$ customers on your list; customer $i$ takes $t_i$ time to talk to and there is $p_i$ probability to make the sale to that customer - ...
0
votes
1answer
12 views

Counting all subsequences constrained to a condition

I was trying to find all subsequences constrained to the following conditions: remove element from the end. remove element from the beginning. remove element from both sides. For example, given the ...
0
votes
0answers
19 views

Minimum spanning tree containing specific edges

Given a weighted undirected graph and a list of edges (without cycles), how can I create an MST that contains all those edges (or says that such an MST does not exist)?
1
vote
1answer
24 views

Quicksort for Strings

I am currently trying to study the Quicksort algorithm. I understand how it works for integers but can anyone explain how does Quicksort algorithm work with strings? The reason for my confusion is ...
4
votes
0answers
74 views

Fast and compact data structure for dynamic graphs

Assume a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ is represented as follows in central memory: an associative array (hash table) $V$ gives for any $v\in \mathcal{V}$ the list of its neighbors $V[...
17
votes
6answers
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. ...
0
votes
0answers
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 ...
2
votes
1answer
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 ...
0
votes
0answers
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 ...
-3
votes
1answer
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(...
1
vote
0answers
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$-...
0
votes
0answers
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 ...
3
votes
0answers
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: ...
0
votes
4answers
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. ...
2
votes
0answers
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 ...
3
votes
1answer
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: ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
3
votes
2answers
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 ...
-3
votes
0answers
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.
10
votes
2answers
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 ...
1
vote
1answer
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: ...
0
votes
1answer
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 ...
0
votes
2answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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$ ...
0
votes
1answer
57 views

Shortest walk from $u$ to $v$ through $w$

We have an undirected, weighted graph $G=(V, E)$ with two weight functions $W_1 : E \rightarrow \mathbb{R}^{+}$ and $W_2 : E \rightarrow \mathbb{R}^{+}$ such that for every $e \in E$ we have $W_1(e) &...
-2
votes
0answers
29 views

Try to solve a question from ProjectEuler [closed]

consider the following question from this link. How it possible to slove this question with finding largest path in Dircted Acyclic graph?
0
votes
3answers
201 views

How it's possible decide CNF by having a turing machine that decide SAT?

Suppose we have a Turing machine $M$ as black box that decide $SAT$ problem. Now suppse we have a $CNF$ formula $\phi$ with $n$ variables. How it possible checking satisfiblity of $\phi$ and then ...
-2
votes
1answer
26 views

Need the time complexity of this conditional statement method

My idea of the program is : Input = n sets objective function ObjFn equals to O(n^3) Output = the order of n sets Steps: Applying ObjFn to all n sets Choose the n of the Minimum ObjFn to be ordered ...
0
votes
0answers
28 views

Is there a difference between Heapify and Bottom-Up/Top-Down heap construction, when using array representation of binary tree?

Won't both the methods ultimately give a max/min heap? So if I am given a binary tree, as an array, and am asked to convert it to a max heap, can I just use the bottom up construction of the heap? ...
2
votes
1answer
62 views

Counting number of times we visit vertices of given tree

Suppose we are given a tree $T=(V,E)$ where $|V|=10$. Now, one of the vertices is goal and we want to find it. The structure of the tree is given as input, but which vertex is the goal is unknown. In ...
-1
votes
0answers
11 views

Convert nested Schemas of SQL Columns to Hierarchical naming representation [closed]

Information: In SQL (e.g. Presto/Hive), there exists columns of "Complex" type {ARRAY, STRUCT, MAP} which are higher level structures on top of the basic INTEGER, BOOLEAN, DOUBLE, STRING, ...
-3
votes
0answers
13 views

recurrence equation 2T(n-4) + n^2 solution?

need help solving this equation. the general equation I end up with: 2^k * 2T(n-4k) + [ 2^k-1(n-4(k-1))^2 + 2^k-2(n-4(k-2))^2 + 2^k-3(n-4(k-3))^2....2^k-k(n-4(k-k))^2 ]
0
votes
1answer
81 views

Vertex Cover with minimum degree 1

In Special Vertex Cover, we are given an undirected graph $G$, and an integer $k\in \mathbb{N_0}$. The objective is to decide whether there exists a vertex cover $S$ of $G$ of size at most $k$ such ...
0
votes
0answers
13 views

Relation between time complexity and conditional statement [closed]

I need examples for the types of time complexity for conditional statement
1
vote
0answers
12 views

(Branchless) Bitonic Sorting Network for a Set of Floating Point Numbers

In the past I've implemented a branchless Bitonic Sorting Network on a gpu using CUDA, for integers. I am facing a related problem: In my Order Independent Transparency implementation, I would like to ...
1
vote
1answer
47 views

There are n cities and m possible bidirectional roads and k temple. build roads with minimum cost such that each city has access to at least 1 temple

There are n cities and m possible roads and k temples. The cost of each road is given. Build ...
0
votes
0answers
19 views

Count number of permutation under certain condition [closed]

I am new to this community and don't know well how to ask questions. Please give any comments if I made a mistake The question is how many permutations of input numbers exist under certain. K is any ...
1
vote
1answer
26 views

How can vector angle comparison between lattice points be done without using floating-points? (Convex Hull)

Let's say I have a point $(x_0, y_0)$, and some other points $(x_1, y_1), (x_2, y_2) ... (x_n, y_n)$, such that all of them are lattice points; all have integer coordinates. Let's further assume that ...
1
vote
0answers
57 views

Maximum money that can be made

Came across the following question. All the answers provided there have used brute force, more or less. My hunch was that it could be solved using dynamic programming or perhaps, network flow ...

1
2 3 4 5
203