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
1answer
35 views

If is true f(n) = Θ(g(n)) and if f(n) = o(h(n)) then g(n) = o(h(n))?

In asymptotic notation the transivity holds, however what happens when we have small o such as if f(n)= o(h(n)) does that means that also g(n)=o(h(n)) holds? i take as granted that both of f(n)=o(h(n))...
0
votes
0answers
20 views

Find the intersection point between two sorted arrays with unknown lengths in lesser than O(n)

Two sorted arrays of positive integers, X[] and Y[] are given.But, the array sizes are unknown to us. We may assume that accessing any index beyond the last element of the array returns -1. The ...
1
vote
1answer
24 views

Finding loop invariant

I am really new concerning loop invariants and I am currently trying to figure out a loop invariant of an algorithm for prime numbers. I tried a lot of ideas, but I still have problems since there are ...
-1
votes
0answers
16 views

Machine learning, computer vision & image processing algorithms for recognition & detection of computer peripherals images

https://www.google.com/search?sxsrf=ALeKk01imob9GW5QnDE8PEmLvGzh5y0G-Q%3A1604724383855&source=hp&ei=nyamX8vwMaif4-EP096Z0AI&q=computer+peripherals&oq=Computer&gs_lcp=...
1
vote
1answer
29 views

Given permutation $p$, compute $p^{-2}$

I'm now to problem solving, and I need some help and insight on the following problem from HackerRank: Given a sequence $p(1),\ldots,p(n)$ of distinct numbers from $1$ to $n$, find numbers $y_1,\...
2
votes
1answer
43 views

Algorithm for cyclic $n$-string Hamming distance with constant sized language $\Sigma$

Suppose we are given a language $\Sigma$ where, suppose, $|\Sigma| = O(1)$. Consider two fixed strings $A, B \in \Sigma^n$. Define the Hamming metric between these strings as $$d_{H}(A,B) = \sum_{i=1}^...
1
vote
1answer
37 views

Indistinguishability of exponentially close distributions

Let $D_{1}$ and $D_{2}$ be two probability distributions over $n$-bit strings such that the total variation distance between them is $\mathcal{O}\left(1/{2^{n}}\right)$. Given as input a polynomial ...
0
votes
0answers
51 views

How AC-3 (Arc Consistency) with backtracking works

I'm trying to understand the AC-3 algorithm with backtracking to implement a Rat in Maze algorithm via C++. So far I've base on these links I have a basic idea in terms of AC-3 and how to implement ...
0
votes
0answers
78 views

I think I've found a flaw in this paper: On finding a minimal enclosing parallelogram. Can someone verify it for me?

On finding a minimal enclosing parallelogram I think the problem will occur when we only consider the first clockwise antipodal vertex. I think instead we should consider an edge when there are two ...
3
votes
1answer
26 views

Optimise the size of union of sets

We consider a set of sets $S = \{S_1, S_2, \dots, S_n\}$, and we want to find a subset $I$ of $S$ that maximises the size of the union of the set $S_i$ included with a penalty for each set included. ...
0
votes
0answers
30 views

Let M be a k × n random matrix with iid entries such that

$M$ is a $k × n$ random matrix with iid entries such that $P(m_{i,j} = +1) = P(m_{i,j} = −1) = 0.5.$ Let $k = O({1\over \epsilon^l})$ for some constant $l$. $v ∈ R_n$ is a fixed vector. Does a ...
2
votes
1answer
26 views

What is the difference between Hamming Distance and Manhattan Distance for non-binary data?

What is the difference between Hamming Distance and Manhattan Distance for non-binary data (specifically I am comparing points in $\mathbb{R}^2$)? I understand Manhattan sums the absolute difference ...
0
votes
0answers
21 views

The observation of the coreset in K-median clustering problems [duplicate]

I have seen two observations from the paper by Har-Peled but I do not know how to prove them (i) If $C1$ and $C2$ are the $(k, ε)$-coresets for disjoint sets P1 and P2 respectively, then $C1 ∪ C2$ is ...
0
votes
1answer
37 views

About the properties of the coresets in k-median clustering

I have seen two observations from the paper by Har-Peled but I do not know how to prove them (i) If $C1$ and $C2$ are the $(k, ε)$-coresets for disjoint sets P1 and P2 respectively, then $C1 ∪ C2$ is ...
2
votes
1answer
73 views

How to generate a number which is divisible by all numbers in a given range?

Suppose I want to find a number that is divisible by all 3 digit numbers (100-999), how do I write a code for that. I know only "1" can divide all 3 digit numbers, but I just want to know ...
0
votes
1answer
29 views

Floyd's Cycle Detection Algorithm Proof In Laymen

I came across the algorithm question of detecting a cycle in a linked list, but the solution has to be constant space O(1). I have looked through various proofs proving that: If there is a cycle, at ...
0
votes
0answers
8 views

What is the currently know fastest algorithms to convert each individual Java primitive and Number types to a Char Array/String

What is the currently know fastest algorithms to convert each individual Java primitive and Number types to a Char Array/String number representation while ...
0
votes
0answers
36 views

Minimum Dominating Set

Consider a graph $G$ with minimum degree $d$, we know through sets cover, it's possible to find the one dominating set $S$ that covers $G$ such that $$S\leq O(\log n)\frac{n}{d} $$ with high ...
0
votes
0answers
15 views

SIMD reordering permute algorithm

The question is about how to schedule the pairwise SIMD instruction to move the data in proper position. Say I n SIMD registers, each SIMD register contains n elements. If each column represent a SIMD ...
0
votes
0answers
13 views

Why we take decreasing order of finishing times and NOT increasing order of discovery times in kosaraju algorithm?

We take decreasing order of finishing times in $G^t$ (transpose of Graph G) to know whther the path exists in other direction as shown below. But why can'nt WE take increasing order of discovery time ...
0
votes
1answer
47 views

Adapt a one-tape turing machine's algorithm that find the center of a string in O(nlog(n)) to find the first third

I have found this answer that finds the center of an input string in nlog(n) complexity. I have tried to use it as a starting point to find an algorithm that finds the character(s) that separate the ...
1
vote
2answers
36 views

Complexity of simulating idle games (pt1)

An idle game (Cookie Clicker is a well-known example) is a game where you set up automatic resource production, and most of reasonable human play is then waiting as resources accumulate. Typical ...
2
votes
0answers
28 views

Minimum Product Weight in a Graph with 2 weight functions

Hello Community, Given an undirected graph G = (V,E) where E has 2 weight functions w1(e) --> {1,2,..9} and w2(e) --> {1,2...9} with given a source vertex s and destination vertex t. we can ...
0
votes
0answers
8 views

tool to insert nodes in a tree with queries

I have a tree where each node has a type. Multiple nodes can have the same type. I want to insert new nodes in this tree at some specific positions specified by queries, such as : ...
0
votes
1answer
36 views

Recursive algorithm to find maximum value in 2D array

Imagine a 2D array of size n x m, where every column is a stack of positive values. I am trying to figure out a recursive pseudo code algorithm, where I have a ...
3
votes
2answers
74 views

Meaning of 'running time is $O(n^2)$'

I have a question from Introduction to Algorithms by CLRS, When we say "the running time is $O(n^2),$" we mean that there is a function $f(n)$ that is $O(n^2)$ such that for any values of $...
0
votes
0answers
29 views

Prove that two vertices are in the same connected component of G if a vertex or his decedent has a step ancestor

Given the forest $G_\pi$ of a DFS run on an undirected graph $G=(V,E)$ and a simple path from a root to a descendant $u_0 \rightarrow ...\rightarrow u_k$. Define $w$ as a step ancestor of $v$ if ...
-3
votes
0answers
27 views

Machine learning algorithms for recognising national anthem song of all countries

https://en.wikipedia.org/wiki/National_anthem Are there machine learning algorithms which will recognise and interpret the national anthem song of all countries? Input dataset : National anthem sound ...
8
votes
1answer
2k views

Are there any functions with Big O (Busy Beaver(n))?

So, I was reading this article by Scott Aaronson on big numbers, and he mentioned that the Busy Beaver sequence increases faster than all sequences computable by Turing Machines. Faster than ...
1
vote
1answer
61 views

Are logarithmic Big-O complexities defined with constant base equal to those defined with variable base?

Example: Deleting from a B-Tree (not to be confused with binary tree) has Big-O complexity of $ O(\log_t n) $ (where $t \in \mathbb{N}$ is the order of the tree). There was one true/false question on ...
1
vote
0answers
22 views

Modify a binary matrix to minimize the sum of values of the rows

I have a matrix of zeros and ones, i.e., $\mathbf{X}=[x_{ij}]$ with $x_{ij}\in\{0,1\}$ for all $i=1,2,\ldots,m$ and $j=1,2,\ldots,n$. Associated with each row $i$ of the matrix $\mathbf{X}$ a set of ...
1
vote
1answer
41 views

Calculating a jackpot winner based on probabilities

Imagine a jackpot where users can bet as much as they want, and each bet increases their winning chance. Given a roll [0-100], how would you calculate the winner? ...
0
votes
1answer
21 views

asymptotic tight bounds for quadratic functions

In Introduction to Algorithms by CLRS, it's said For any quadratic function $f(n)=an^2+bn+c$, where $a$, $b$ and $c$ are constants and $a>0$, $f(n)=\Theta (n^2).$ Formally, to show the same thing, ...
1
vote
1answer
22 views

Unconstrained subset sum vs constrained subset sum?

In class, we discussed two question types: constrained subset-sum and unconstrained subset-sum. Let me define the question specifically and then I will mention what I am confused by. Question 1: ...
0
votes
1answer
33 views

Is “backward substitution” and “backtracking” the same thing?

From my limited knowledge, they both are related to solving recurrence relation. Solving recurrence relation using backward substitution Solving recurrence relation using backtracking Can the terms ...
1
vote
0answers
19 views

Solving multiple pathfinding problems efficiently

Let $V$ be a set of nodes, $c : V \times V \rightarrow \mathbb{R} \cup \{\infty\}$ be an edge cost function, and $h : V \times V \rightarrow \mathbb{R}$ be an admissible heuristic. Suppose we want to ...
0
votes
0answers
27 views

Big O of my backtracking solution

I have a problem and I've been struggling with my solution time and space complexity: Given an array of integers (possible duplicates) A and ...
2
votes
0answers
108 views

Is there a linear sorting algorithm given an oracle that finds kth smallest item?

Given a machine that can compute the kth smallest item of an Array A in $O(\sqrt n)$ time. Find a recursive function that can sort A in linear time corresponding to $n$ which is the length of A. First ...
2
votes
2answers
64 views

How to iterate the Hardy-Ramanujan integers quickly

The Hardy-Ramanujan integers, A025487 - OEIS, are integers which when factorized, have their exponents for all the primes starting from 2, in decreasing (not strictly) order. The first few terms are: $...
0
votes
1answer
62 views

How can I prove the correctness of this exponentiation algorithm using induction?

I have the following algorithm. How could I prove it using induction that for every $n\ge 0$, Exp(n)${}= 2 ^ n$? ...
0
votes
0answers
21 views

Filtering Messages

I saw this question posted and can't seem to find it for some reason, so I'm posting it again. There's a leetcode problem that's asking for the number of possible strings that are alphabetically ...
0
votes
1answer
47 views

Question about complexity of algorithms

I came across this symbol $2^{\mathcal{O} (n)}$ and I can't figure out what is means. What complexity class is this?
1
vote
1answer
42 views

Serving $k$ customers with bounded time window

A person provides a service and he/she can serve $k$ clients each minute. Now, client number $i$ comes at the beginning of minute $a_{i}$ and waits $w_{i}$ minutes to receive the service and if they ...
0
votes
0answers
9 views

How to combine multiple Boolean Functions in CDNF efficiently for implementation on a CPU?

I am trying to see how fast I can implement a 6-bits to 6-bites lookup table. Generally, I am attempting to do this by using the common method mentioned in CS textbooks of using the Quine-McCluskey ...
0
votes
1answer
28 views

Algorithm to find pairs

Task: There are N persons. Some of the persons were meet before. I need to find pairs of persons, that were not meet before. Example: 4 persons - A, B, C, D. A and B were meet before. Good solutions: (...
0
votes
0answers
29 views

constants in asymptotic notations

I've question from CLRS that's about constants and functions in asymptotic notations. $\Theta (g(n)) = \{f(n) :there\;exist\; positive\;constants\;c_1, c_2, n_0\;such\;that$ $0 \leqslant c_1g(n)\...
1
vote
0answers
38 views

Asymptotic running time function's domain

I am reading CLRS and have uncertainty in asymptotic running time of algorithms. In CLRS, it is said, The notations we use to describe the asymptotic running time of an algorithm are defined in terms ...
-2
votes
1answer
29 views

Solution to T(n) = 2T(n/2) + log n

So my recursive equation is T(n) = 2T(n/2) + log n I used the master theorem and I find that a = 2, b =2 and d = 1. which is case 2. So the solution should be O(n^1 log n) which is O(n log n) I looked ...
1
vote
0answers
17 views

“Close” Graph Coloring?

I haven't been able to find whether this problem has been studied: we are given a graph $G$ and an ordered list of $k$ colors $L = [\ell_1, \cdots, \ell_k]$. Additionally, we are given a positive ...
0
votes
1answer
34 views

Ordering the tasks to minimize penalties

So I just started learning greedy algorithms and I have a problem that I want to solve. The statement is as follows: In your calendar you have an $L$ list of all the tasks you need to complete today. ...