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
2
votes
1answer
32 views

Solving linear system of nonhomogenous equations that are known to have natural solutions

Any idea is appreciated. A generic approach that works for any system would be best but if you want more info about what I'm looking for, the equations are usually short (having few variables, from 1 ...
0
votes
2answers
74 views

Intelligent use of XOR operator to find missing number

I've come across the following problem on leetcode & tried to solve it with the following code however there seems to be an even better solution that takes advantage of XOR. Leetcode has a ...
2
votes
1answer
25 views

Adaptive arithmetic coding confusion

I'm confused about the point of adaptive arithmetic coding. I understand that static arithmetic coding involves using preset probabilities of symbols that remain static during the whole process. I ...
1
vote
1answer
43 views

Fastest algorithm for connectivity problem

Let $G = (V,E)$ be any undirected graph. Let $k$ be some number and $C = |u \longrightarrow v|$ where $u \longrightarrow v$ means there is a path from $u$ to $v$. We want to add $k \subseteq V \times ...
2
votes
2answers
42 views

Algorithm to get the number of iterations needed, if possible, to get an specific 2 element array

I am fairly new to algorithms and I am dealing with a problem I cannot fully translate into mathematical language. So, I am given the array [1,1] and I can only perform one sum between their numbers ...
1
vote
0answers
40 views

Algorithm for intersection point between two vectors

I'm trying to learn Computational Geometry and this formula isn't obvious to me. Hint: cross is related to the cross product of two vectors. ...
-1
votes
0answers
13 views

Algorithm for quadratic voting in anonymous decentralized systems

The question is about voting in decentralized systems. Quadratic voting is a wonderful way to reach consensus without arranging property qualifications. However, quadratic voting requires a KYC: ...
-1
votes
2answers
67 views

What would be the complexity for this relation?

The function: for (int i=1; i<n²; i++) for (int j=i; j<n; j++) print(j) Putting it into a relation, I got: $C1 + \sum_{i=1}^{n^2}(C2+...
3
votes
1answer
34 views

“State of the art” algorithms deciding entailment of propositional formulas?

I fail to find much about how to efficiently calculate whether a propositional formula entails another. Considering the following two points... We can check, for each truth assignment which makes the ...
3
votes
0answers
45 views

Minimizing the sum of differences in a pair [duplicate]

You have two arrays, a and b Both contain n elements, all positive and distinct. you have to create a pair, by taking one number from each array, such that the sum of the differences of the pairs ...
0
votes
1answer
10 views

Method to change value in a key for a min heap

How would you write a method to change the value of a min heap where bool changeKey(int oldKey, int newKey). The keys are unique, no duplicate keys are permitted. If there is a key in the heap with ...
-3
votes
1answer
31 views

The number of bits needed to address 64KB

Introduction to computer science Level 109 I don’t understand the question
1
vote
0answers
26 views

Are Online Problems always harder than the Offline equivalent?

I am currently studying Online-Algorithms, and I just asked myself if online Problems are always harder than the offline equivalent. The most probable answer ist yes, but I can't figure the reason ...
1
vote
1answer
27 views

When does a Monte Carlo algorithm solve a problem?

When can we say that a Monte Carlo algorithm solves a problem? To quote from Wikipedia on Monte Carlo algorithms For instance, the Solovay–Strassen primality test is used to determine whether a ...
1
vote
2answers
59 views

How to determine if given “complex” time complexity is $O(n^2)$?

If a given time complexity, such as these: $(n + \log n) * \sqrt{n+\log n}$ $n * (200 + \log^2 n)$ $(7+n^3)\log(n^5)$ is not determinable by just looking at it whether is it in class $O(n^2)$ or not,...
1
vote
0answers
18 views

Understanding proofs Lemma 11 & 10 in this specific Computer Science Scheduling Paper

I'm having a hard time wrapping my head around the proofs Lemma 11 and Lemma 10 (Pages 10 and 11) in this paper called: Preemptive and Non-Preemptive Real-Time UniProcessor Scheduling. Generally the ...
0
votes
0answers
18 views

Recurrence Relations for Perfect Quad Trees (same as binary trees but with 4 children instead of 2)

I have to write and solve a recurrence relation for n(d), showing how I arrive at the formula and solve the recurrence relation, showing how I arrive at the solution. Then prove my answer is correct ...
0
votes
0answers
12 views

Lectures and books for beginner to approach learning simulations

I'm an incoming undergrad with a math background up to single-variable calculus, but reasonably strong programming background through algorithms, data structures, web and mobile app development. ...
0
votes
1answer
23 views

Computation of iterated logarithm function

I recently came across the iterated algorithm function denoted as $\lg^* n$. But I am having a hard time understanding this statement: $\lg^* n = \min \{i \ge 0: \lg^{(i)} n ≤ 1\}$ I could not ...
0
votes
1answer
38 views

Minimization of amount in the change coins problem using the dynamic programing approach

I'm learning the dynamic programming approach to solve the coins change problem, I don't understand the substitution part Given: amount=9, coins = [6,5,1], the ...
1
vote
1answer
30 views

QuickSelect with Median of Medians runtime

I know that Median of medians itself is $O(n)$. With a good pivot, QuickSelect is $O(n)$, too -- but with a bad one, it's $O(n^2)$. But if I now were to use the element gotten through median of ...
1
vote
2answers
66 views

Finding the shortest path in a grid which has walls

The problem is that you want to travel from the top left corner of a grid to the bottom right corner (You are initially at the top left corner). Now, there are some walls in some cells, and you have a ...
1
vote
1answer
25 views

Path uniqueness in undirected graph

Let's consider an undirected graph with two special vertices: start and finish. The graph is relatively sparse. The edge count is expected to be three times or four times higher than the vertex count. ...
0
votes
1answer
36 views

Shortest path in BST

Given a Binary Search Tree and two elements $e1$ and $e2$ which are in the tree, find the length of the shorted path between them. Give the representation of the Binary Search Tree(use a linked ...
2
votes
2answers
45 views

Implementing Queue operations in $\Theta(1)$

We want to implement a Queue which has two special operations besides the regular Queue operations: $getMiddle$(returns the element from the middle of the Queue, for example, if the Queue has 7 ...
1
vote
1answer
23 views

Order notation subtractions in Fibonacci Heap

Can order notation on its own imply: $O(D(n)) + O(t(H)) - t(H) = O(D(n))$ My guess is that you cannot since the constant in the O(t(H)) would still exist after the subtraction if the constant is > 0....
0
votes
1answer
22 views

How to find the square with the highest total sum

I have an integer matrix of size 4n x 4n. I need to select a part of the matrix of size n^2 from which adds up to the most. For ...
0
votes
3answers
48 views

Big O Proof , f(n) = 2n + 1 and I have to prove f(n) is O n^2

If I have $f(n) = 2n + 1$ and I have to prove $f(n) \in O(n^2)$, by proving there exists positive constants $c$ and $n_0$ such that $f(n)<cn^2, \forall n\ge n_0$, can I do this all in one step by ...
2
votes
1answer
39 views

Name of BFS variant with multiple queues with different priorities

Is there a name for the following variant of BFS that operates on trees with non-root starting point?: Instead of a single queue that all neighbor nodes are added to when processing a node, two ...
0
votes
1answer
21 views

How to prove Big-O when $F(N)$ is even or odd

If I'm given a function $f(n)$ which is for example $4n+1$ when even and $3n^2+2$ when odd and I have to prove or disprove $f(n)$ is $\mathcal O( n^2 )$. Do I have to do $f(n) < c n^2$ for all $n &...
1
vote
1answer
32 views

Algorithm to find the intersection of non-convex polyhedra

Context: I have two polyhedra, $A = V_1\times F_1$ and $B=V_2\times F_2$ where $V_i$ is set of vertices (which are just coordonate in $\mathbb R^3$) and $F_i$ is a set of faces (tuples of length $\...
0
votes
2answers
22 views

Doubt regarding strong component in a graph

I know that strong component in a graph means between any 2 vertices there should be bi-directional path. My doubt is cycle is always a strong component. can there be any other subgraph with some ...
0
votes
1answer
24 views

Space and time complexy of operations on 32-bit array vs. binary array

Assume an array a of length $n$. I am wondering how to characterize the difference between time- and space complexity of 32-bit arrays of length $n$ and bit-arrays of length $n$. Normally, you'd just ...
1
vote
0answers
30 views

Butterfly diagram from Cooley-Tukey algorithm

I am trying to understand the logic of this algorithm so I can implement my own but I am not understanding this diagram I see appearing many times in a fair few articles on the topic. I am teaching ...
0
votes
1answer
28 views

Negative cycle detection using Bellman-Ford and its correctness

I recently started studying algorithms on my own using Cormen and MIT algo videos in YouTube. I am going thru Bellman-Ford. I have 2 doubts about the correctness of the algorithm: Why are we ...
1
vote
1answer
45 views

Using a greedy algorithm to find a cut S which at least half of the edges cut

Let $G$ be an undirected graph. Find a greedy algorithm that finds a cut $S$ which at least half of the edges cut. I tried to think about something like choosing the vertex with the highest degree, ...
0
votes
0answers
17 views

Program to Translate Turing Machine to Tableau?

Is a program available to translate a Turing Machine program to Boolean tableau format as used for example in proofs of the Cook-Levin theorem?
2
votes
1answer
88 views

Get every possible (connected) subgraph containing x number of nodes

If I had a graph representing the USA with each node representing a state, and each edge linking adjoining states, is there a graph algorithm that would give me every possible unique group of 4 states ...
0
votes
0answers
15 views

A request for literature on Matching your partner problem

I need reference for a good book (a title and an author will do) or reference on the web which explains the problem of matching procedures of suitable partners between several males and females based ...
1
vote
0answers
95 views

Best algorithm for Renyi–Ulam Game with lies [closed]

Player $A$ thinks of number between 1 and $n$ and ask $B$ to guess the number with minimum number of decision queries (yes or no type). Game : $A$ chooses an element in $\{1,2,\dots,n\}$. $B$ tries ...
1
vote
1answer
26 views

Space optimised versions of Coin Change and Knapsack Problems in Dynamic Programming

I have recently been focussing on DP formulation and space optimization in dynamic programming of some problems. I have gone through the standard questions such as 0-1 Knapsack and Coin Change ...
0
votes
1answer
27 views

What do we mean by polynomially upper bounded and lower bounded

I just came across this asymptotic bound : $(\log n)!= \Theta \left(n^{\log \log n}\right)$ Which had the following remark: Hence, polynomially lower bounded but not upper bounded. I ...
0
votes
0answers
23 views

Scheduling algorithm for overlapping jobs - single resource?

I have a single resource that will need to shared for running multiple parallel jobs. Think of the resource as a straight line numbered from 1 to 100. The jobs occupy part of the line while they are ...
1
vote
2answers
51 views

Theoretical lower bound of finding number of occurrences of a target integer in a sorted array

Given a sorted array of integers and a target integer, find the number of occurrences of the target integer. It is well-known that a binary search has time complexity $O(\lg n) $ where $n$ is the ...
-1
votes
0answers
29 views

Shortest path with exactly k edges in a directed and weighted graph big o

how to calculate the big O of Shortest path with exactly k edges in a directed and weighted graph big O the algorithm is:
0
votes
0answers
26 views

Long Division when dividend and divisor are of same size (same number of digits)

I want to know if there is some optimized method (constant complexity preferred) to obtain the quotient when the dividend and the divisor contain the same number of digits. I know about algorithm D of ...
0
votes
1answer
45 views

Most cost effective way to traverse a set path

I have a set path of $N$ destinations to be visited in order, knowing the distance $D_i$ between each one of them. I can traverse one node $i$ with the cost of $D_i \times r$ or traverse any $5$ nodes ...
1
vote
2answers
24 views

How to find rows of matrix that are zero everywhere except for 1 entry?

I am interested in finding the rows of a matrix where all entries are equal to zeros except for one. Example: Given the following matrix: \begin{bmatrix}0 &0 &3 & 8\\ 0 & 4 & 0 ...
11
votes
6answers
1k views

Find the number using binary search against one possible lie

We all know this classic problem, "there is some hidden number and you have to interactively guess it.", which could be solved using binary search when we know that maximum number that we can guess. ...
0
votes
1answer
46 views

Is there a name of this problem?

There is $n$ lists (of integers) of the same length. I want to find the zeros global intersections of those lists. Example: $A = [4,6,3,0,7,0,0,0,1,0,0]$ $B = [6,6,7,1,7,0,0,0,4,0,0]$ $C = [2,...