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

Difference Between k-center and k-mean/median

I know that k-mean/median is to find a set $F$ that minimize $$\sum_{i\in C}\min_{j \in F} d(i,j)$$ Where $C$ is set of clients and $F$ set of facilities. (For k-mean you just square the distance). ...
0
votes
0answers
18 views

Question of about Boltzmann machine implementation

I would like to implement Boltzmann machine with two hidden and two visible units. The four possible hidden units configuration are $(0,0), (0,1), (1,0), (1,1)$, and their probability distribution is $...
1
vote
1answer
12 views

Minimal cut of a directed graph such that disjoint elements are strongly connected

Given an arbitrary directed graph $G$ (which may not necessarily be connected) find a minimum set of edges $S\subseteq E$ such that every disjoint component of $G(V,E\cap S')$ is strongly connected. A ...
2
votes
1answer
41 views

Partition of a $k$-partite graph to minimal number of connected sets

Let $G$ be a $k$-partite directed acyclic graph where the edges are only between two adjacent sets of vertices. I'm trying to partition the graph to the minimal number of connected sets. Sets $A_0, ...
0
votes
2answers
27 views

algorithm that determines if a given number n is composite or not on input <n>

Consider the following algorithm that determines if a given number n is composite or not ...
1
vote
1answer
26 views

Counting primitive operations on recursive functions

I'm reading Algorithm Design and Applications, by Michael T. Goodrich and Roberto Tamassia, published by Wiley. They teach the concept of primitive operations and how to count then in a given ...
0
votes
0answers
27 views

Why is $\log n = O(n)$? [duplicate]

Why is $\log n = O(n)$? I faced this before and I remember I understood it at that time. But now I cannot know the logic and could not find understandable explanation. Can anyone explain it?
2
votes
1answer
34 views

Understanding the upper bound proof for quick sort

I'm trying to understand the average run time of quicksort which is $O(n \log n)$. I understand the intuition behind it: if we partition array $A$ to e.g. $\alpha n $ and $(1-\alpha)n$ then we ...
0
votes
1answer
13 views

Find two nodes in a BST such that the root's key is the average of their keys without extra space in $\theta(n)$ worst case time

We can do this in $\theta(n^2)$ time if we calculate the average of all couples of nodes in the tree and compare it to the root, but this is too much time. We can do this in linear time but with extra ...
-1
votes
0answers
25 views

Minimum cost required to cover a line with line segments

We are given a line segment $[1, n]$ with $m$ smaller line segments $[l_{i}, r_{i}]$. An example being $[1, 4]$ and line segments ${[1,2], [2,3], [3,4]}$. We can cover this using first and third ...
1
vote
1answer
15 views

What is the sense of distance in the definition of SSSP Problem?

I was studying about algorithms and came across the SSSP problem which stated: Given connected weighted directed graph G(V,E) and a node S, find the shortest path from S to all nodes of the graph. The ...
0
votes
0answers
18 views

Non Preemptible Kernel

I am trying to understand non preemptible kernel in linux 2.4 and can't find answers for those two questions: Suppose Process A is running in kernel space and a hardware interrupt occurred can it cut ...
1
vote
2answers
34 views

More efficient algorithm for Withdraw/Deposit position in bank statement

I am parsing bank statements where the transaction amount is ambiguous as to the withdraw/deposit nature and the balance is only given periodically. My goal is to more efficiently, than brute force, ...
0
votes
1answer
13 views

Finding the distance from a point to a $R^m$ restricted area in $R^n$

The problem is described below: When m=2 and n=3, it is basically finding the distance between a point and a line segment in $R^3$. But when both m and n are larger, do I have to use a generic ...
2
votes
1answer
25 views

Z-function and the minimum string period

Let $s$ be a string of length $n$. One of the classical solutions to the problem of finding the smallest period $p$ of $s$ (that is, smallest $p$ such that $s$ can be obtained as a concatenation of ...
3
votes
0answers
24 views

Online cycle detection but not quite: the Featherstitch problem

Featherstitch (Frost et al., 2007) is an approach for representing data consistency requirements for disk storage. This question concerns a graph-theoretic problem (§4.1 in the paper) that its ...
1
vote
2answers
34 views

Loop Invariants: Can someone explain this concept?

I am reading Algorithms Unlocked By Tom Cormen and find this concept a little confusing. Why is it that we require loop invariants and how does it help in analyzing algorithms?
0
votes
0answers
17 views

CSES Question - Tower [closed]

Ques Link: https://cses.fi/problemset/task/1073/ Code Link: https://pastebin.com/S9nzVJVa In CSES question : Towers, I know it can be solved using sets with greedy approach but I was trying to do ...
0
votes
1answer
28 views

Iteration Vs Induction Method

I am working on different methods to solve Recurrence Relations. I am using Iteration method and substitution method, which involves Induction, but I feel that sometimes Induction method creates a bit ...
1
vote
1answer
17 views

Is there a way to find the correct element in the array for the given index x?

In quick sort, in each iteration we are able to find correct index for an element (i.e. pivot element). Is there any algorithm to find correct element for a given index ? Here, correct index of an ...
0
votes
0answers
40 views

Given $n$ sets of matrices, find $n$ matrices that have the least number of LCDs among their entries

Let's say I have $n$ sets of matrices $$ A = \left\{\begin{pmatrix} 2 & 4 & 17\\ 5 & 6 & 9\\ \end{pmatrix} \begin{pmatrix} 2 & 4 & 18\\ 5 & 6 & 9\\ \end{pmatrix} \right\...
2
votes
2answers
173 views

What would be the big O notation for a function that attempts to find pairs of users that participate in different discussions?

Recently, I started to think of a problem involving the use of Twitter data that would involve finding pairs of users that participate in the most conversations. For example, with each tweet, you get ...
1
vote
0answers
26 views

How good a center of a BFS tree is?

Consider a graph $G=(V,E)$, and a BFS tree $T$ starting from an arbitrary node $v\in V$. Now consider finding the center node $u_T$ of $T$, i.e., the vertex with the lowest eccentricity in $T$, which ...
-1
votes
1answer
51 views

Does ⌊1/𝑛⌋∈Θ(1/𝑛) or to Ω(log𝑛)

⌊1/𝑛⌋ - represents the floor function Does the floor or ceiling function affect the complexity under which a function falls? ⌊1/𝑛⌋∈Θ(1/𝑛) or to Ω(log𝑛) Found ...
2
votes
1answer
27 views

Optimal online algorithm to guess the tree

I have a tree on $n$ vertices. Your goal is to find the adjacency list for it. $n$ is known to you from the start. You can pick a vertex and ask for the lengths of the shortests paths from it to the ...
1
vote
1answer
78 views

What's the difference between a protocol and a distributed algorithm?

What's the difference between a protocol and a distributed algorithm? My internship supervisor told me they are not exactly alike. A protocol is more communication-oriented (e.g. TCP), whereas a ...
0
votes
0answers
25 views

Finding the solution for day k

There are 25 lights $\{l_1, l_2, \dots , l_{25}\}$ in off mode. On Day 1, every light is on. On the Day 2, every 2nd light. i.e, $l_2, l_4, \dots , l_{24}$, are off. On the 3rd day, every 3rd, i.e., $...
0
votes
0answers
20 views

How to create unique combinations out of provided keys-values?

Let's say I have a struct Product with an unknown and variable amount of attributes-values. The attributes-values come from a user at runtime. One product with a unique combination of attributes and ...
-2
votes
0answers
39 views

Is the approximation of this algorithm bounded?

This is an exercise in approximation algorithm section. For the minimum vertex cover problem, if the point with the highest degree in the graph is picked out and added to the vertex cover set every ...
0
votes
0answers
19 views

An algorithm to find differences between routing paths

I need to come up with an algorithm that finds differences in the sequence of each product's routing (or sequence of processes). There are several processes aligned together and each process's been ...
-3
votes
1answer
57 views

How to design fast/efficient algorithms?

Let's say, if you could travel to the past, what would you teach your younger self? Which key points define efficient algorithms?
1
vote
1answer
32 views

Proof of approximation ratio for approximate triangle inequality version of k-center

Consider the standard $k$-center problem i.e find $k$ disks of radius $r$ that cover all points in a point set $P$. This problem has a well known greedy 2-approximation algorithm where you (...
1
vote
0answers
43 views

Finding an optimal solution for the following problem

This is an intriguing question given by my friend for which I want to find an optimal solution: Each week, you can choose to work ONLINE $(ON)$ or in person $(WR)$ in your department's office. If you ...
1
vote
1answer
22 views

Is this a good way to arrange data in a tree?

I was recently learning about Binary Search Trees(BSTs) and thought it could be made even more efficient by making some changes. As binary search trees have numbers greater than the root node on the ...
-1
votes
0answers
34 views

3-hitting set iterative compression

I have a question which I tried to solve without success. I need to prove that if 3-Hitting Set can be solved in time $2^kn^{O(1)}$,then 4-Hitting Set can be solved in time $3^kn^{O(1)}$. There is a ...
0
votes
0answers
60 views

Claw-free graph - linear kernel

I'm having a hard time solving the problem below: In Claw-free problem, we are given a graph $G$ and $k$, and the objective is to decide whether there exists a subset $S \subseteq V (G)$ of size at ...
0
votes
0answers
27 views

Minimum Number of Refueling Stops with Dynamic Programming

This is a question from Leetcode and I wanted to solve it with Dynamic Programming. upon seeing the solution, I am not able to get the intuition behind the logic. I was able to understand the solution ...
1
vote
2answers
38 views

Sliding window max/min algorithm without dynamic allocations

I'm working on a suite of DSP tools in Rust, and one of the features of the library is a collection of windowed statistics (mean, RMS, min, max, median, etc) on streams of floating-point samples. For ...
2
votes
1answer
27 views

What are the limits of Boolean Algebra?

Any decision problem algorithm can be represented as a boolean expression. The rules of boolean algebra (De Morgan's law, distributivity, etc.) can be used to manipulate and simplify that expression, ...
1
vote
1answer
21 views

Time complexity of the triangle factoring problem

We define the triangle factoring problem as in Triangle Factors in Random Graphs, which is, given a simple undirected graph of $3n$ nodes, find if there's a subset of edges dividing vertices into $n$ ...
2
votes
0answers
23 views

Finishing at rest at a target in 2d space

I asked a similar question here, except I forgot to specify that the final velocity must be 0. I have 2 points in 2D space, start = $s$ and target = $t$, and a starting velocity $v_0$. At each time ...
0
votes
0answers
33 views

Find the magic value from an array of N numbers

I was asked this problem recently in an interview however, I failed to provide an optimal solution to it. Given an array $A$ of $n$ numbers, the magic factor of $i^{th}$ element is equal to the ...
1
vote
1answer
29 views

Precise algorithm for finding higher order derivatives

I'm trying to make an algorithm that finds the first 10 or so terms of a function's Taylor series, which requires finding the nth derivative of the function for the nth term. It's easy to implement ...
1
vote
1answer
26 views

Factor $n$ in RSA if we know $φ(n)$

If we know that $n = 1363$ and $φ(n) = 1288$, how can we factor $n$?
0
votes
2answers
76 views

Minimum number of moves puzzle

Let K players be among N towns in a circular position. On each turn, only one player can move. A player cannot move if he is the one who moved in the previous turn. A player can only move clockwise ...
0
votes
2answers
59 views

Find the largest rectangle inscribed in a region partitionable into rectangles

Given a rectilinear polygon, what is an run-time efficient algorithm that finds the largest inscribed rectangle the sides of which either parallel or perpendicular to the sides of the rectilinear ...
0
votes
0answers
36 views

Minimize the average distance from each cities to the closest hospitals

There are n cities [1, 2, 3, .... n] and k available hospitals. k < n. We need to place hospitals into the cities. How to place these hospitals to minimize the average distance from each cities to ...
0
votes
1answer
53 views

Find non common numbers in two arrays

Given two arrays of integers, please write a function that returns all elements present in one of the two arrays but not both. E.g. f([ 1, 3, 5 ], [ 1, 2, 4, 5 ]) -> [ 2, 3, 4 ] I know I can do ...
1
vote
0answers
35 views

minimising Longest-Path in DAG

Assume we have weighted DAG (directed-acycle-graph), source s and target t. Define the number of edges as $E$. Given $0<\alpha<1$: Choose $\alpha*E$ edges to cut their weight by half so that the ...
3
votes
0answers
41 views

Find the largest interior rectangle composed of partitioning rectangles

Suppose a rectangle $R$ is partitioned into more than one smaller rectangles of positive area. What is the fastest algorithm to find the largest rectangle strictly within the all-enclosing rectangle $...

1
2 3 4 5
194