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
1answer
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 ...
1
vote
0answers
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$...
0
votes
0answers
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 - ...
3
votes
1answer
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 ...
1
vote
1answer
25 views

Best case for sorting algorithm

Given this sorting algorithm: ...
0
votes
1answer
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. ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
2
votes
1answer
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 ...
0
votes
1answer
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 ...
-1
votes
0answers
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)?
0
votes
0answers
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 ...
1
vote
0answers
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 ...
2
votes
1answer
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 ...
0
votes
0answers
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, ...
0
votes
0answers
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' ".
0
votes
0answers
33 views

Asking for your help with LFSR, linear automaton

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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
7answers
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? ...
1
vote
1answer
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 ...
1
vote
1answer
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: ...
2
votes
2answers
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 ...
-1
votes
1answer
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 ...
2
votes
2answers
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 ...
0
votes
1answer
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....
0
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
-1
votes
1answer
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. ...
0
votes
0answers
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 ...
0
votes
0answers
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, ...
0
votes
1answer
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? ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
2
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
1answer
34 views

How to wiggle sort an array in linear time complexity?

The wiggle sort is nums[0] < nums[1] > nums[2] < nums[3] > nums[4] ... For an input: nums = [1, 5, 1, 1, 6, 4], the expected output is ...
-1
votes
0answers
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 ...
0
votes
2answers
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 ...
0
votes
1answer
36 views

Algorithm Analysis of Three nested loop

I'm trying to figure out Time function and Big O of a nested loop code, ...
1
vote
1answer
23 views

Understanding recursion tree for withdrawal formula

$$ 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 ...
1
vote
1answer
44 views

Problem related to set partitioning

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