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
21 views

time complexity of AA^T

In the context of building of a cocitation weighted adjacency matrix, in terms of A using matrix operations.. what is the time complexity of AA^T?
1
vote
1answer
10 views

Select fixed-size connected induced subgraphs in a graph

I have a connected graph with $nk$ vertices, and would like to select $n$ disjoint induced subgraphs with $k$ vertices such that each subgraph is connected, selecting one out of all possible solutions ...
1
vote
1answer
15 views

Time complexity of finding median in data stream

I was reading a solution to the problem in the title on leetcode and the article says that the time complexity of the following solution is O(n) setup a data structure to hold stream value and insert ...
1
vote
1answer
23 views

Do the following two CFGs describe the same language

Do the following two CFGs describe the same language S → aS | bS | ε S → aS | Sb | ε Would the answer to this be no, because the order can't be switched? bS and Sb are different. I'm a bit confused ...
2
votes
2answers
54 views

Proof of $f(n) + ο(f(n)) = \Theta(f(n))$

Can you please help me prove this? I am trying to set $o(f(n))= g(n)$ and then try to solve the equation $f(n) + g(n) = \Theta(f(n))$ but I don't know if it is the correct way, and if it is I don't ...
1
vote
0answers
18 views

Searching for the underyling affine transformation in a ridge function

Quoting from Wikipedia: A ridge function is any function $f:\mathbb{R}^d\rightarrow\mathbb{R}$ that can be written as the composition of a univariate function with an affine transformation, that is: $...
2
votes
2answers
44 views

Turing machine for $0^{3^k} 1^{p}$

Hey guys so I picked up Introduction to the Theory of Computation and started studying finite automata and Turing machines. I was given the following language as an exercise in class, in which I need ...
1
vote
0answers
17 views

Represent unsigned 12-bit octal numbers. Results in octal

I have an HW question where I found an answer that matches mine, but their breakdown confuses me. Ques: What is 4365 - 3412 when these values represent unsigned 12-bit octal numbers? The result should ...
2
votes
1answer
10 views

Pruning: Outlier Candidate Selection

I am using method 3.3 described in Outlier Detection using Isolation Forest and Local Outlier Factor . It states: Specify a dataset: $𝐷={𝑑_1, 𝑑_2, ..., 𝑑_𝑛}$. Here, 𝑛 is the sample number of 𝐷. ...
1
vote
0answers
26 views
2
votes
0answers
29 views

Online algorithm for compressing multiple SETS?

Algorithms like LZW and others compress data sequences. What I'm looking is an algorithm that compress multiple Sets. if possible online algorithm. For example : ...
1
vote
0answers
23 views

EM algorithm - What happens with the standard deviation?

What have you tried? So I watched this video. According to the video, we've to calculate the variance $\sigma^2$ as follows: $$ \sigma_{k}^{2} = \frac { p_{1} \left(x_{1} -...
1
vote
0answers
18 views

Representation of connected components in the $O(|E|)$ time/space variant of Karger's algorithm

I'm trying to understand the various optimizations given in the original 1992 paper on Karger's algorithm. Specifically, looking at section "3.1 Unweighted Graphs", I don't understand what ...
0
votes
1answer
22 views

How to prove that one problem belongs to class P?

Is there any typical proving method when proving that one problem belongs to class P? For example, when proving that The problem of finding n to the kth power is the P problem. (Each multiplication ...
-2
votes
1answer
71 views

Is radix sort in-place or out-place?

Generally, we can implement algorithms in-place and out-of-place. However, I can't say for certain that radix sort can be implemented in both ways.
0
votes
0answers
68 views

Check if graph is regular given adjacency matrix

I have the following problem: Write a function whose input is an adjacency matrix A of a graph G. The function returns true if G is a regular graph and false otherwise. I understand that a graph is ...
1
vote
1answer
64 views

Algorithm for winning solitaire

Is there an algorithm that could check whether it is possible to win in the current situation in solitaire? That is, can we remove all cards from the table in a certain number of moves? Description of ...
1
vote
1answer
151 views

How best to allocate stock buys and sells when using specific id to maximize long term capital gains

Setting aside the fact that tax lots (using specific id) should usually be assigned at the time of the trade (for stocks in the USA), let's assume instead we want an algorithm to optimally allocate ...
-4
votes
0answers
29 views

i am unable to do this question?

Write the Recurrence relation of the following algorithm and solve it usingi iteration method. Use initial value of T as 2. The complexity of swap function is O(1).void Sort(int arrl, int n) { if (n== ...
-2
votes
0answers
16 views

Erase history change history lose information replace information algorithm as a person

We cannot change the history of a person because we cannot travel back in time. Suppose that the person were a computer algorithm. Suppose there were a computer matrix, like a noncommutative math ...
0
votes
0answers
36 views

Implementation of prefix-span algorithm

This is a very elegant implementation of prefix-span algorithm by the maintainer of the prefixspan pip package. However, I am having a hard time understanding the reason behind the implementation. The ...
0
votes
0answers
22 views

Pedestrian Traffic Algorithm Challenge [closed]

Pedestrians are walking on a path of length n that is separated into an upper and lower lane. The upper lane is for people moving to the right and the lower lane is for people moving to the left. ...
0
votes
0answers
22 views

How to know that the substrings 01 and 10 does not require an infinite amount of memory to count the substrings [duplicate]

Why does {w | w has equal number of 01 and 10 substrings} not require an infinite amount of memory to “count” the number of 01 and 10 substrings?
-3
votes
0answers
25 views

Algorithm to find a new spanning tree of G

Here is a problem that I recently encountered and I am having trouble with coming up with an algorithm,. Suppose you are given an undirected weighted graph G and a minimum spanning tree T of G. Now an ...
0
votes
0answers
9 views

Using bloom filters for high speed pattern matching in combination with Aho Corasick

I am implementing a new system for pattern matching in Intrusion Detection Systems for streaming data (network packets). I understand that bloom filters also produce false positives. Is there anyway ...
0
votes
1answer
44 views

Kernelization algorithm for the following problem

We are given an undirected graph $ G $ and a positive parameter $ k \geq 0 $. The problem is to decide if there exists a set $ S \subseteq V(G) $ of size at most $ k $ such that $ G − S $ does not ...
0
votes
1answer
12 views

Multiplication of polynomials in value representation as done for Fast Fourier Transform

I am trying to understand the discrete Fast Fourier Transform. I get the idea of switching between coefficient and value representations to and then back but I am stuck in figuring out how the ...
0
votes
0answers
22 views

Bloom filter variant(using only half of it)

A Bloom filter is an array $B[1..m]$ of bits, together with a collection of $k$ independent ideal random hash functions $h_1,h_2,...,h_k$. To insert an item $x$ into a Bloom filter, we set $B[h_i(x)] ←...
0
votes
1answer
95 views

How to derive max amount of items from DP table of Knapsack problem?

I have a little bit changed algorithm for 1-0 Knapsack problem. It calculates max count (which we can put to the knapsack) as well. I'm using it to find max subset sum which <= target sum. For ...
3
votes
2answers
109 views

Finding all pairs of points with no point in between

Suppose there are $n$ points $p_1,p_2,\dots,p_n$ with color red or blue on a line. We want to find all pairs $(p_i,p_j)$ whose color is distinct and such that there are no points between them. If ...
1
vote
1answer
23 views

Number of paths starting from a given edge using adjacency matrix

I want to write the algorithm that takes the adgacency matrix of a directed connected graph without any cycles, then for each edge computes the number of paths starting from that edge. Also note that ...
1
vote
1answer
45 views

Minimal unsatisfiable core algorithm

Wikipedia says that There are several practical methods of computing minimal unsatisfiable cores. but I cannot find any. I suppose that “practical methods” means polynomial algorithms. Be careful, a ...
0
votes
2answers
38 views

no of times partion is called in quick sort, assuming array is always halved

In the most even possible split, PARTITION function produces two subarrays, each of size no more than n/2. since one is of size floor(n/2) and one of size ceil(n/2)-1. The recurrence for the running ...
1
vote
0answers
25 views

Sub-matrix with minimum size of $k$ and minimum sum

We have an $n \times m$ matrix whose entries are non-negative integers and we want to find a sub-matrix whose area (number of entries) is at least $k$ such that the sum of the entries in minimal. The ...
0
votes
1answer
28 views

A visitor at a political convention with n delegates

So I have been asked to specifically construct a divide and conquer algorithm for the question: "You are a visitor at a political convention with n delegates; each delegate is a ...
5
votes
1answer
29 views

Minimal Path Covering

Consider a connected undirected graph $G = \langle V, E\rangle$, we say that a subset $C$ of vertices is a Path-Cover if the following holds. For every finite path $p$, it holds that $p$ traverses all ...
0
votes
1answer
24 views

Divide and conquer problem:sequence of integers (with possible repetitions)

I was trying to solve this problem. Let $A[1] . . . , A[n]$ an ordered sequence of integers (with possible repetitions) and let $k$ be any integer. A contiguous subsequence $A[i], A[i + 1], . . . A[j]$...
0
votes
0answers
27 views

Spliting in AVL tree in $O(\log n)$ times

Suppose we are given a balanced binary search tree $T$, AVL tree, now we want split $T$ at a arbitrary node. Can it be done in $O(\log n)$? First i read following links: Split in AVL tree with ...
2
votes
1answer
144 views

Weighted binary search tree

Suppose we have binary search tree with $n$ nodes. For each node $u$ we define weight of $u$ is number of nodes in sub tree of $u$ with $u$. if ratio of weight of each internal node $u$ of right sub ...
0
votes
1answer
21 views

Bucket sort has uniformly distributed data

Implementation of bucket sort is mainly useful when input is uniformly distributed over a range. So the ques here is what is the significance of having input data uniformly distributed for applying ...
1
vote
1answer
36 views

How would I prove that the regular expression rejects string?

Prove that the regular expression $\Sigma\Sigma(ab\cup ba)^∗a$ rejects the string $aabaabba$. Would this be because the union of $ab$ and $ba$ would not accept the string $aabaabba$? I'm just confused ...
1
vote
1answer
30 views

Time Complexity of Memoized Solution

I was solving Stone Game II on LeetCode. I was able to come up with a recursive (TLE) solution, which I optimized using memoization. The recursive solution computes a function $u(i,m)$, depending on ...
0
votes
0answers
28 views

How to modify the following Dijkstra/ Uniform-cost search to return the result for all end points?

I know there is a lot of code out there that does this, but in particular, I'm trying to modify the following code to not just return the goal node/ one end point, but all endpoints. How do I go about ...
1
vote
1answer
55 views

How do Kruskal's and Prim's algorithms compare to each other?

I understand that both of them are used to find minimal spanning trees, and I've seen their implementations, but I don't understand how both of them compare to each other, and how they differ in ...
0
votes
0answers
28 views

Dynamic sampling of thermal images

My master’s dissertation subject is to analyze and implement an algorithm that would sample thermal images from camera with different frequency rates to optimize database size and processing power. Is ...
3
votes
1answer
125 views

FPT algorithm for 1-BDD

Given a graph $G = (V,E)$ and an integer $k$, the 1-BDD problem asks if there exists a subset $D$ of at most $k$ vertices such that the degree of any vertex in $G[V \setminus D]$ is at most one. Is ...
2
votes
0answers
21 views

What's an efficient algorithm to check if a binary operator is residuated?

Assume the binary operator is given as a table/matrix, so constant time to compute $xy$. And likewise, assume the (relation giving rise to the) partially ordered set is also given as a table, or in ...
3
votes
1answer
58 views

Minimum-area enclosing equilateral triangle for a point set

We have $n$ points $P$ in $2D$ space. We want to find an enclosing equilateral triangle $\Delta$ with minimum area in $O(n\log n)$. Suppose We know that at least on side of $\Delta$ covers at least ...
1
vote
0answers
30 views

Minimal number of unions of sets such that no union has more than N elements

I have some sets, and can combine them by taking their union. I can take unions of the unions, too. I want to take unions until the total number of sets is as small as possible, with one caveat: that ...
4
votes
0answers
60 views

Number of permutations with satisfactory triangles

We are given $N$ points($N \leq 40$), where no combination of three or more points is colinear. The values of $x$ and $y$ are bounded by [$0$,$10^4$]. The problem is to find the number of permutations(...

1
2 3 4 5
190