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
3
votes
0answers
43 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: ...
1
vote
4answers
76 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
24 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
50 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
32 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
17 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
44 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
60 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 ...
10
votes
2answers
2k 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
27 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
93 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
24 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
21 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
53 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$ ...
1
vote
1answer
66 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) &...
0
votes
3answers
238 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
29 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
34 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
63 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 ...
0
votes
1answer
85 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 ...
1
vote
0answers
16 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
81 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 ...
1
vote
1answer
31 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
63 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 ...
0
votes
0answers
30 views

Algorithm for dividing a polygon into rectangles?

I have a polygon as a set of coordinates (fex [(0,0), (1,0), etc.). I'd like to find a way to divide this into as few rectangles as possible. The background for this is that I wish to have a user ...
0
votes
1answer
20 views

Algorithm to compute a div d and a mod d

I wanted to ask here a question about a simple algoirhtm to compute a div d and a mod d. My doubt specifically depend on ...
1
vote
2answers
62 views

Prove my algorithm that solves ABC String problem in Codeforces is correct

Here's the statements of problem A, "ABC String" in Educational Codeforces Round 105 (Rated for Div. 2) You are given a string a, consisting of n characters, n is even. For each i from 1 to ...
3
votes
0answers
74 views

Deciding whether a given flow is unique in $O(\lvert V \rvert + \lvert E \rvert)$ time

I am stuck with the following exercise: Is it possible to decide whether a given flow $f$ is a unique mamimum flow in $O(\lvert V \rvert + \lvert E \rvert)$ time? I am not sure that this is possible....
0
votes
1answer
55 views

How to reduce clique to Hamiltonian cycle in an undirected graph?

Recently, I studied how to prove a problem is NP-complete. From the book Introduction to Algorithms (CLRS, 3rd edition), there is an example of reducing vertex cover to Hamiltonian cycle. I believe ...
0
votes
1answer
40 views

Lower bound on computing $x^n$

I know that we can compute $x^n$ in $\log n$. Are there any lower bound for computing $x^n$?
1
vote
1answer
42 views

Finishing Time in DFS, is that necessary?

According to DFS algorithm for graph traversing: ...
1
vote
1answer
136 views

Stuck on a possible greedy problem

I am currently dealing with a problem that I believe to be a Greedy releated problem and I'm trying to find some similar problems in order to solve it. I would like to have some hints or resources to ...
0
votes
1answer
40 views

Reduce subset sum to simple path

I have a similar question as this post:Given a complete, weighted and undirected graph $G$, complexity of finding a path with a specific cost My question: Given a weighted and directed graph $G$, it ...
1
vote
1answer
58 views

Algorithm to find shortest distance from source to all other vertices of graph in O(m)?

My question is for (c), as I struggle to find an algorithm that can do this in O(m) time.
0
votes
0answers
13 views

Arranging rectangular textures in square texture atlas and optimize sub texture proximity

I have a mesh consisting of about 100'000 - 200'000 quads. Each quad has a rectangular texture. I'm packing these rectangular textures into a power-of-two atlas. My packing algorithm currently works ...
0
votes
0answers
31 views

How do right contexts work in context-sensitive L-Systems?

I am working on an implementation of context-sensitive 2-L systems as described in The Algorithmic Beauty of Plants by Aristid Lindenmayer, and am in need of clarification regarding context matching ...
2
votes
1answer
37 views

Efficient solution for a particular form of quadratic Diophantine equation

Preface: I know there are a lot of posts already here and elsewhere about algorithms for solving quadratic Diophantine equations in general. I am posting this in the hope that my very particular case ...
0
votes
1answer
12 views

Online binary tree creation via $a\to ax$ and $ab\to a(bx)$

I wish to construct a sequence of unlabeled binary trees $T_n$ satisfying the following properties: $T_n$ has $n$ leaves $T_n$ is well balanced (height $\lg n+O(1)$) $T_n$ is obtained from $T_{n-1}$ ...
2
votes
5answers
331 views

Find two non-overlapping subarrays, with total sum equal to k

Given an array of N non-negative integers, and a number K, we need to find two non-overlapping contiguous subarrays that have a total sum of K. Our algorithm is supposed to find the minimum total ...
4
votes
1answer
69 views

Inverse of Ackermann function and $\log^* n$

Consider inverse of Ackermann function, can we conclude that the growth rate of it as the same as growth rate $\log^*n$?
0
votes
0answers
32 views

decrease weight of edges in graph [duplicate]

Suppose given complete undirected weighted graph $G=(V,E)$ with $n$ vertices, also we have Minimum spanning tree $T$ that obtained from $G$. if we decrease the weight of $n$ arbitrary edges, how we ...
2
votes
1answer
58 views

Why is this equality about the relative translation in the iterative closest point (ICP) algorithm obvious, and how can I derive it?

I'm a computer science bachelor student tasked with understanding On the ICP Algorithm by Esther Ezra, Micha Sharir, and Alon Efrat, and I'm having a lot of difficulty with even supposedly obvious ...
1
vote
2answers
70 views

how do you deal with complex algorithms?

I'm in the first year of computer engineering and I feel completely lost when it comes to solving hard programming exercises. I think it's due to a bad modus operandi. And that is why I'm asking this ...
2
votes
0answers
32 views

Partition columns into m groups to maximize absolute value sums

The Task You are given $n$ columns each of length $m$. All values are either $-1$ or $1$. Find an assignment $s$ of each of columns to 1 of $m$ groups in order to maximize the sum of all the absolute ...
2
votes
1answer
81 views

Prove finding a spanning tree with no more than 50 leaves is NP-hard

This is a homework question. Consider the problem of finding if an undirected graph $G$ can have a spanning tree with no more than 50 leaves. Is this problem NP-hard? I think it is and I'm trying to ...
0
votes
0answers
18 views

Efficient way to do self join with minimum support?

In the apriori algorithm there's the self join step, So, say we have 1 3 2 3 3 5 2 5 If I were to do an exhaustive join I'd end up with a tuple including (1, 3, ...
3
votes
1answer
42 views

A question about hash problems in CLRS book

Consider the following problem 11.2-6 from CLRS book: Suppose we have stored $n$ keys in a hash table of size $m$, with collisions resolved by chaining, and that we know the length of each chain, ...
1
vote
1answer
22 views

Linear programming for prefix of graph

Question: Consider an arbitrary directed graph $G$ with weighted vertices, the weights can be positive, negative or $0$. The prefix of $G$ is a subset of vertices $P$ such that there's no edge $(u \...
0
votes
1answer
23 views

polynomial time approximation algorithm problem

How can we actually define a polynomial-time 4-approximation algorithm for vertex cover or knapsack problem? For say we have 2 approximation problems which less than equal 2C*. But when we have a ...
0
votes
1answer
13 views

Finding permutation of jobs such that each job finishes before deadline

Consider a set of jobs, each having its deadlines and process time. How to find a permutation of them such that if they are executed in that sequence, they all finish before their deadline or figure ...