# 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.

8,522 questions
Filter by
Sorted by
Tagged with
66 views

### How can I improve my algorithm for finding optimally balanced P-way partitioning of array

I have an array of $N$ weights $w_i$, say $w_i=\{4, 5, 12, 16, 3, 10, 1\}$, and I need to divide this array into $P$ partitions such that partitions are optimally balanced, i.e. that maximum sum of ...
11 views

### Intuitive explanation of why a large spread makes scheduling problems harder

The problem of minimizing weighted flow-time (min-WPFT) is defined as follows: We are given a set $J$ of $n$ jobs, each job $j$ having a release time $r_j$, a processing time $p_j$, and a weight $w_j$...
19 views

### Best way to find and store difference between two strings

I want to implement my version of the Codeshare service. Now I'm thinking of an implementation where all users have access to one string that can change (if you already have a better option here - ...
33 views

### How to uniformly sample a sorted simplex

I am looking for an algorithm to uniformly generate a descending array of N random numbers, such that the sum of the N numbers is 1, and all numbers lie within 0 and 1. For example, N=3, the random ...
25 views

### Best case for sorting algorithm

Given this sorting algorithm: ...
12 views

### Estimating users standard deviation given avg, min, max for various tests

Given a series of tests, where we are given one users score, the overall minimum, the overall maximum, and the overall average, how would I estimate the user's standard deviation on total score (ie. ...
16 views

### Powells Method for 2 Variables?

This is my first question here, so if anyone has tips on how to improve it that would be great. I've been studying this youtube on Powells method and it looks like when we have a single variable we ...
28 views

### Merge $k$-sorted arrays - without heaps/AVL tree in $O(n\log(k))$?

Given $k$-sorted arrays in ascending order, is it possible to merge all $k$ arrays to a single sorted array in $O(n\log(k))$ time where $n$ denotes all the elements combined. The question is ...
32 views

### Algorithm to identify rearrangements between two sequences of unique values

I have two sequences, seq1 and seq2, each consisting of unique values. Values can appear in seq1 or seq2 which do not appear in the other, and these values can appear in any order. How do I identify ...
31 views

### Heuristics for maximizing the performance for a given complexity

I often have to balance the computational requirement of each qualitatively different module of my algorithm. So, I'm using this heuristics for maximizing the performance for a given complexity, but I ...
20 views

### Uniquely identifying bits

Query: Given $m$ unique integers smaller than $2^n$, can we keep at most $k$ the same bits of each number to uniquely identify them? Is this problem NP-Hard? For example, given the $4$ unique ...
22 views

### Longest palindrome substring in logarithmic runtime complexity

In a palindrome of size N, the amount of candidates for the longest palindrome is N^2. Therefore, the information theoretic lower bound (IBT) should be lg(N^2), which is equivalent to a runtime ...
14 views

### What data structure/algorithm LinkedIn use to determine the degree of a potential connection?

I have read something about bi-directional BFS in this Quora answer, but is there anyone who can describe more specifically how it works and how much time does it take (complexity)?
8 views

### Analysis of succefull and unsuccefull search in a sorted hash table that resolves collision by chaining

I am trying to solve a problem where we have to analyze the expected time for successful and unsuccessful search in a hash table of $n$ elements and $m$ slots . But the hash table has a property that ...
15 views

### A curious question - an algorithm to determine how a list of vectors is sorted?

Given a list of vectors consisting n integers that has been sorted by their components in certain priority, how do you find the possible sorting keys, i.e. the ...
149 views

### Induction Proof on Independent Set Variation Algorithm

So I am given this blackbox algorithm, in which given a Graph G and a integer k, it returns yes if there is an independent set of size k, no otherwise. My algorithm is suppose to output impossible if ...
8 views

### Minimal t needed in B tree for the lowest reading time

I've got an assignment, which I was asked to calculate the minimal t needed in a B tree, to have the optimal searching time. So here it is: We've been told that in a specific B tree, with unknown t, ...
32 views

### Minimum spanning tree with given edges

So the question is: "Given an undirected graph G=(V,E) with positive edge weights, and E'⊆E, show an algorithm that finds, from all the minimum spanning trees, the one that has more edges from E' ".
33 views

I am a software developer new to the site. I am currently learning about LFSR (linear feedback shift register). Every day I solve a question which is given to me, but today I am lost. I can not solve ...
103 views

### Independent Set Problem Variant, Induction

So the question gives us some mysterious algorithm, that given a graph G and an integer k, it outputs true/false to whether there is an independent set of size k in G. So we have to design an ...
20 views

### What datastructure does google use to store its search engine indexes?

To the best of my knowledge search engines such as Google index the web using MapReduce amongst many other tools. With my limited experience this would make hash tables the most practical option for ...
273 views

### What is the time complexity Big-O of this algorithm?

What is the time complexity Big-O of this algorithm? , The first assumption it's O(N * lg N) but it is not correct, why? ...
112 views

### Approximation algorithm question, clustering on n points

So the algorithm I thought of, is to iterate through the n points, centering a ball at each point, and keeping track of the point where we centered that encapsulated the most points. Then remove the ...
35 views

### check if a binary tree is a binary search tree

I have some doubts about this algorithm which checks if a binary tree is a binary search tree: ...
65 views

### Distance queries on Tree with hotspots

We are given a tree with $n$ vertices and some of the vertices act as a "hotspot". We have to answer multiple queries of type $(a,b,c)$, which means we have to find the distance to the nearest ...
19 views

### Max sum non adjacent and k size subsequence

You are given a number n, representing the count of elements. 2. You are given n numbers, representing n elements. 3. You are given an integer k. 3. You are required to find the maximum sum of a ...
47 views

### Looking for an efficient algorithm quickly find the nearest line (defined by perpendicular distance) to an arbitrary point

I have a large set of lines in 2D with a known start point and end point, and would like to find the nearest (defined by perpendicular distance) of those edges (or the extension of those edges past ...
27 views

### Elements of Programming Interviews - 16.4 Generate Power Set - solution 1 time complexity question

hope you all are doing well. I have a question about the time complexity of solution 1 for question 16.4 - Generate Power Set from the book Elements of Programming Interviews by Adnan and Tsung-Hsien....
55 views

### Maximum profit by two parameters

Suppose we have two markets. Each market has various buy & sell orders that we can sell to or buy from respectively. Each order represents a specific number of a particular item type that someone ...
47 views

### Can radix sort reach exponential time complexity?

For example, assume the input array is $$[121212,212121]$$ Say we are in base 10, so count sort will work in $O(n)$ time. We have 6 iterations which is approximately $n^2$. Is this a worst case ...
171 views

### Given a tournament with $2^n$ vertices, show that there is a sub-tournament with at least $n + 1$ vertices that is acyclic

So a tournament is just a complete directed graph, I believe. I'm having trouble proving this problem. I know it is induction however. I was thinking the base case is $2^1$ vertices, and therefore ...
25 views

### What solution to apply for finding the optimal parameters?

For a study, I have a system (black-box) that requires an input in the form of an array with 4 values (input_array) and depending on their values it produces an ...
32 views

### Counting directed graphs

I am trying to find a computable, injective and bijective function $f: \mathbb{N} \to A$ where $A$ is the set of all (finite) directed graphs up to isomorphism (also with no edge repetitions). Which ...
41 views

### Efficient algorithm to compare arrays problem

I was submitted an interesting problem, but I wasn't able to find a solution. Define a function p(x, y) that takes int x and y, with ...
22 views

### How to solve the bin packing problem with conflicts?

I'm trying to devise an algorithm to solve the bin packing problem with conflicts (sometimes referred to as BPPC, or BPC). The problem is defined as follows: consider a set $V$ of $n$ items, where ...
44 views

### checks if a tree is a full binary tree

I have to write an algorithm that checks if a tree is full binary tree (each node, except the leaves, must have 2 children), but I don't know if this version is correct. ...
20 views

### Linear Partition problem (Dynamic Programming) in a circular array

I am practicing algorithms for the last couple of days and I came across this question, the gist of which is: Given apples and oranges arranged in a circle indexed form 1 to n , where n is an odd ...
18 views

### Graph traversal problem touching every node exactly once

Is there a name for the problem: Suppose you have a connected, undirected graph; find a path that touches every node exactly once. This is basically the complement of the Hamiltonian Path problem, ...
32 views

### Insert a node in a binary search tree

The teacher gave us this code that inserts a node in a binary search tree, but I am not sure what the $z.p = y$ instruction does. wouldn't the algorithm work without it? ...
21 views

### Finding all topological orders

I have to make an algorithm that finds all the topological orders(using predecessor counting) and the highest cost paths and their costs between 2 pairs of vertices. My algorithm looks like this for ...
29 views

### 2D packing in fixed dimensions rectangle

Input: a enclosing rectangle of size $(W, H)$ a family of rectangles $R= (R_1;R_2;\dots;R_n);R_i=(w_i;h_i)$ Output: a scaling factor $s$ a 2D bin packing of $R$ in a rectangle of size $(sW, sH)$ I ...
25 views

### What is the difference in time-complexity for sorting these 2-d arrays?

Let $A$ have $n/10$ rows, $10$ columns and $n$ overall elements Let $B$ have 10 rows, $n/10$ columns and $n$ overall elements. It is given that each row is sorted in ascending order, Can you sort ...
75 views

### Create an algorithm for computing the shortest path in O(m + nlogn)

So I'm trying to write an algorithm for computing the shortest path with constraints on the vertices you can visit in $O(m + n \log n)$ time. In this problem, we are given an indirect weighted (non ...
18 views

### Does amortized algorithm analysis make any assumptions about the sequence of function calls?

I have read that average case analysis makes some assumptions about the inputs to the data structure, and amortized analysis makes no such assumptions. Does amortized analysis make any assumptions ...
34 views

### How to wiggle sort an array in linear time complexity?

The wiggle sort is nums < nums > nums < nums > nums ... For an input: nums = [1, 5, 1, 1, 6, 4], the expected output is ...
44 views

### How do I sort an array by performing a minimum number of right shifts to any three elements? [duplicate]

I have an array of N integers such that 1 ≤ a[i] ≤ N. (a permutation of N integers). ** ie for 5 array can be 5,1,2,3,4. ** I need to sort the array by picking any three indices a[p], a[q], a[r] and ...
25 views

### Buying ingredients for a cake from many different stores and need to minimise the number of stores - algorithm name?

So let's say I'm baking a cake and it has a few ingredients (including multiples): ingredients = {sugar, sugar, baking powder, chocolate, flour, egg, egg} I can ...
36 views

### Algorithm Analysis of Three nested loop

I'm trying to figure out Time function and Big O of a nested loop code, ...
$$T(n) = T(n-a) + T(a) + cn$$ Now the solution says that the height of the tree $(h)$ is: $$h = \left \lfloor n/a \right \rfloor$$ And I don't understand why. Maybe I didn't understand the ...
Let $A_j=\{(a^i_j,b^i_j)~:~ 0 \leq i \leq n,\text{and } a^i_j,b^i_j \in \mathbb{Z}^+\}$ Given sets $A_1,\ldots, A_{p}$ and a positive integer $k$, the problem is to check whether there exists one ...