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
1 vote
2 answers
94 views

Greedy Algorithm and Proof of Correctness for Minimum Denominations of US Coinage System Problem

I've come up with a greedy algorithm proof for the minimum denominations problem, and I'm curious if someone can verify the correctness of the proof for me. I have simplified the problem by ...
5 votes
2 answers
2k views

Time complexity for count-change procedure in SICP

In famous Structure and Interretation of Computer Programs, there is an exercise (1.14), that asks for the time complexity of the following algorithm - in Scheme - for counting change (the problem ...
1 vote
1 answer
24 views

Find the value of return variable based on the value of n?

...
0 votes
0 answers
7 views

How does this partitioning problem map to studied problems?

I have a real-world (see background below) problem wherein a set $S = \{A,B,C,D...\}$ needs to be partitioned into set $P = \{ \{A,B\},\{D\},\{E,F\},\{C,G,H\},...\}$ where $P$ is required to have the ...
0 votes
1 answer
109 views

Suggest good books for Advanced Data Structure and Algorithms

I don't really need hands on coding help, I need to clear my concepts of some of the more complex topics of DS and Algo like NP-Completeness, Computational Geometry, String Matching, Multithreaded ...
0 votes
0 answers
28 views

Find multiple order-statistics of an array

Given array $a$ of size $n$ and array $p$ of size $m$. How we can for every $i < m$ find $p_i$-th order statistics of array $a$ in $O(m log(n) + n)$? We can find order statistics separately, but it ...
1 vote
1 answer
57 views

How do I find time complexity of while loops?

I am designing a simple algorithm to be used at hardware level. And I want to find its time complexity. i=1 while(i<=n) { i=i*2; } How I'd go about finding ...
0 votes
0 answers
7 views

Confusion on the use of the chain-rule for the total derivative of the NLL Loss function

So my question is about when we want to find the total derivative of the NLL Loss function $L$ w.r.t. $w_i$. So the "pipeline" is often expressed as: $$\frac{\partial L}{\partial w_i} = \...
1 vote
1 answer
423 views

Find the smallest subarray with sum larger than a threshold

Given a set of $n$ positive numbers $\{a_1,\ldots,a_n\}$ and a positive target $T$, find a subset $S$ from $\{a_1,\ldots,a_n\}$ of contiguous elements, that is $S=\{a_i,a_{i+1},a_{i+2},\ldots\}$ for ...
2 votes
1 answer
72 views

A version of Bareiss algorithm or similar for symmetric matrices

A linear equation $Ax=b$ can be solved by reducing the matrix $A$ to upper triangular form by using Gaussian elimination or LU decomposition. If $A$ is symmetric and positive definite one can use ...
0 votes
1 answer
37 views

Binary search calculating complexity big o

I'm studying recursion and a i have a doubt about the running time complexity of the binary search. I didnt understand this passage in my book : ...
-1 votes
1 answer
44 views

Mergesort time complexity

Using the regular mergesort algorithm for a list, say $a[1...n]$, we call the merge function to merge, mergesort($a[1...\lfloor \frac{n}{2} \rfloor]$) and mergesort($a[\lfloor{\frac{n}{2}}\rfloor+1......
0 votes
1 answer
44 views

Trying to understand the time complexity of IDDFS

I'm trying to break down the Time complexity algorithm for IDDFS. Acknowledging that in general my understanding of maths is not that great. So I will be trying to talk things out. For BFS it is ...
0 votes
1 answer
32 views

Non-dominated maximal paths (DAG)

Let $D(V, A)$ be a DAG. We call a dominated path in $D$ a path $P$ such that $\quad\quad P$ is maximal and $\exists_{P^{'} \in D}(P^{'} \text{ is maximal } \wedge V(P) \subset V(P^{'}))$ that is, $P$ ...
0 votes
1 answer
69 views

Optimal scheduling order for two queues of jobs

I have two queues of jobs and each job consists of the pair (utilization %, time to complete). I have one machine and its utilization cannot exceed 100%. The first job in a queue must be completed ...
0 votes
1 answer
62 views

Given required total area and capacity, choose an amount for each of three given modules

Suppose you have three modules $m_1,m_2$ and $m_3$, each with a capacity of $c_i$ and area $a_i$. You are also given $A$ and $C$. How can you find some of the solutions to choose an amount of each ...
0 votes
0 answers
19 views

Which one of the problems belong to P? [duplicate]

Suppose $P\neq NP$. Which one of the mentioned problems can be solved in polynomial time? Given natural number $n$ and positive real numbers $a_1,a_2,\dots,a_n$ and $b_1,b_2,\dots,b_n$. The goal is ...
0 votes
2 answers
121 views

How to avoid costly square root operations in A* algorithm?

As a reminder, in an A* algorithm, vertices in the priority queue are sorted according to their priority $f = g + h$, where $g$ is the cost of getting to this vertex from the start vertex, and $h$ is ...
2 votes
1 answer
170 views

Design a data structure with constant insertion and sublinear range maximum query

Suppose we have access to a stream of ordered pairs, where the $i^{\text{th}}$ element in the stream is an ordered pair $(a_i, b_i)$, where $a_i$ is a timestamp and $b_i$ is an arbitrary real. How can ...
0 votes
1 answer
35 views

Finding the mode of a continuous distribution

I need to find the empirical mode of a sample of numbers taken from a continuous distribution (i.e. floating-point data). I can think of using an histogram, but choosing an appropriate bin size does ...
0 votes
0 answers
9 views

Identifying peaks at every cluster

I have a data set showing different clusters of data points and was attempting to find a way to get the peak of at every cluster. Comparing the moving average between a set of points does not work as ...
10 votes
1 answer
610 views

Are there associative cryptographic / collision resistant hashes?

Git uses SHA hashing as a content address key. This relies on their being a vanishingly small probability that two different pieces of content will ever hash to the same key. For content ...
3 votes
2 answers
366 views

Find Minimum Transformation Between Multisets of Lists of Cards

Brief: I have two configurations, a and b, of the same set of Rummikub tiles (a may not be a ...
0 votes
1 answer
51 views

Memory allocation algorithm over a growing storage

I am going to story data in a growable persistent storage. I need to implement allocation/deallocation (like malloc/free and possibly realloc but in Rust) of continuous regions of memory on this ...
0 votes
2 answers
53 views

Clarification of divide-and-conquer recurrence explanation in 'Introduction to Algorithms' (CLRS)

The following excerpt is from page 39 of the 4th edition of 'Introduction to Algorithms' (emphasis added): 2.3.2 Analyzing divide-and-conquer algorithms [...] A recurrence for the running time of a ...
4 votes
1 answer
143 views

Survival algorithm for Network deterministic failures

Consider an undirected network $G = (V,E)$ in which edge $e$ $\in$ $E$ fails after (deterministic) time $t(e) > 0$. Network failure occurs at the first instant in which $G$ is no longer connected. ...
3 votes
1 answer
448 views

Tree traversal with conditional summing values from nodes

Hi all i have algorithmic problem and i struggle with finding optimal solution. I have tree which i want to traverse. Nodes of the tree consist of value and a rank of node (value as well as rank can ...
1 vote
0 answers
36 views

Find maximum sized rectangle on a plane

I'm given a rectangular plane with width, height and a set of rectangles defined by left, <...
1 vote
1 answer
115 views

Comparing variable image to static image

What are Levenshtein distance algorithms, but for images? I will have one static image (the target: what it should look like) and one variable image (actual: what the user has created) For example, ...
20 votes
3 answers
24k views

What is the difference between the fundamental matrix and the essential matrix?

Could someone, in plain english, explain the distinction between the fundamental matrix and the essential matrix in multi-view computer vision? How are they different, and how can each be used in ...
3 votes
1 answer
183 views

Why does a prepare message wants a promise that an acceptor is never to accept a proposal numbered less than its propose sequence value? (Paxos)

I was studying Paxos from: http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf Recall that Paxos is a distributed system algorithm with the goal that the processes ...
0 votes
2 answers
118 views

Why is there no polynomial time verifier for N Queens

The N-Queens in question is referring to the one where it is interested in finding all solutions for some natural number n. I just read about the idea of a verifier being an algorithm that verifies ...
1 vote
1 answer
306 views

Appropriate graph clustering algorithm

I'm looking for an appropriate technique to search for clusters. My underlying data is 70,000 respondents to about 2500 multiple choice questions. Most respondents have not answered most questions. I ...
0 votes
1 answer
27 views

Determine if all the continuous subsequences of an array contain at least one unique element in O(n lgn)

Given an array of length n, how to determine if all the continuous subsequence of this array contains at least one unique element. Any subarray array[start, end] ...
0 votes
0 answers
42 views

The second shortest path on a directed graph

The question asks to write an algorithm using Dijkstra's algorithm with time complexity of $\Theta(|E| \log |V|)$ that find the second shortest path between s∈V and t∈V. The farthest I managed to get ...
1 vote
1 answer
136 views

Sorting O(log n) elements in O(n) time

I am presented with the following problem: In an array of $n$ sorted numbers and $f(n)$ unsorted numbers where $f(n)=O(\log n)$, find an algorithm to sort the entire array in $O(n)$ time. What I am ...
0 votes
0 answers
24 views

Greedy algorithm for trading cryptocurrencies with perfect price information

Assume the following hypothetic scenario: You know the values $v_1^0, \ldots, v_n^0$ of $n$ cryptocurrencies. You know the values this currencies will have for the following $m$ days; this is, $v_0^1,...
1 vote
1 answer
46 views

Time complexity of algorithm with three loops and if statement

Suppose I have this c++ code: ...
-1 votes
1 answer
65 views

The three elevator problem

There are three elevators in a building that has twelve floors. Find an algorithm that needs to find the best possible way for the elevators to stop at any particular floor considering the traffic ...
1 vote
0 answers
37 views

How do i make a 2d array as same as i possibly can with another one?

Say i have an 2d array A of nxn size, int values already given for each item.these values can be the same or different. There's gonna be another nxn array B being input. I can only interchange one row ...
0 votes
1 answer
2k views

Proof that median of an array is the number that minimizes the sum of manhattan distance to all points

Given a sorted array A, the problem is to find a number that minimizes the sum of Manhattan distance to the numbers in the array. I found that the median of A is the solution, but was not able to come ...
0 votes
1 answer
37 views

Find combination of elements, one element from each list, whose average is the closest to a target number

Problem: There are L lists of positive integers, say L_0, L_1, L_2 ... L_|L|-1. The lists have equal length. There is a target number T. Find what is the combination of elements, one element from each ...
-2 votes
2 answers
193 views

Could this novel algorithm be qualified to be published in Nature or Science

I recently designed an algorithm for single-source shortest paths in graph structures, which can limit the number of edges as Bellman-Ford while approaching the performance of SPFA. Of course, it also ...
0 votes
1 answer
36 views

Round-robin tournament scheduling, with teams that may share their home field

I need to implement an algorithm to create schedules for round-robin tournaments (where each team faces each other team exactly once), but with the constraint that up to 2 teams – that may play in ...
3 votes
1 answer
713 views

calculating the string similarity of an optimal alignment

description of the algorithms behavior I have two strings s1 and s2, with $len\_s1 <= len\_s2$. I would like to find the ...
0 votes
0 answers
12 views

Dynamic programming problem for minimum cost tower placement

I have an algorithmic problem in which I have a highway that is a straight line of length n and a set of unique respective costs for construction of a radio tower for each mile on the highway. I am ...
1 vote
1 answer
465 views

Find all polygons from a set that overlap a given polygon (convex case)

Problem: Given a set of $N$ non-overlapping convex polygons $\{S_i | 1\leq i\leq N\}$ defined by their vertex coordinates $(x,y)$ and a convex polygon $P$, also defined by its vertex coordinates, ...
1 vote
0 answers
85 views

Can we compute most significant digit of a binary number in O(1) on RAM model?

Consider we use a RAM model with word length w (or if you really want a more exact model, you can use Knuth's MMIX instructions with w-bit numbers). Given a number n, we want to compute the most ...
0 votes
0 answers
56 views

Necklace Alignment Problem

We are given two cyclic $\{0,1\}$ strings $X$ and $Y$ with both length $n$, containing $k$ 0s and $n-k$ 1s. Suppose positions of 1 in $X$ are $x_0,\dots,x_{k-1}$, for $Y$ are $y_0,\dots,y_{k-1}$. We ...
1 vote
0 answers
53 views

Borůvka's step in linear time

I am trying to understand this Expected linear time MST algorithm, and I have a problem in the implementation of the Borůvka's step. My problem is with the removal of duplicate edges between merged ...

1
2 3 4 5
227