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

Given a list of integer rectangle areas, find all integer rectangles that they can tile

Is there an efficient algorithm that takes in a list (multiset) of integer rectangle areas and finds all possible integer rectangle tilings? Every integer rectangle area in the list (multiset) must be ...
0
votes
1answer
28 views

Solve recurrence relation $T(n)=n^{1/5}T(n^{4/5})+5n/4$

I am trying to solve this recurrence relation - $T(n)=n^{1/5}T(n^{4/5})+5n/4$. I can't use the master's method and the recursion tree method because of that $n^{1/5}$ term. We can write $$\frac{T(n)}n=...
-1
votes
0answers
23 views

Find words that are combinations of other words in list

I've been wondering how to solve this algorithm question recently but am not sure. What's the most optimal algorithm to solve this problem? There is a list with words like: pin, pine, apple, pineapple....
1
vote
1answer
31 views

A problem about master theorem and recursion [duplicate]

Prove or disprove the following statement: If $f(n)\in \Omega(n^2)$ and $T(n) = 2T(n/2) + f(n)$ then $T(n) \in O(f(n))$. I think that the statement is false. Do you know any counterexamples?
2
votes
1answer
42 views

Sorting $n^2$ numbers which consist of numbers from 1 to $n$

I wish to sort $n^2$ numbers which all come from the set $\{1,2,3,...,n\}$, i.e duplications are allowed. I know I can just use merge sort which has complexity $\mathcal{O}(n^2\log (n))$, but I was ...
0
votes
0answers
22 views

Comparison between counting and radix sort

Given a list of 100_000 different credit card numbers (16 decimal digits each). Which will be a better way to solve this - counting sort or radix sort ? Thanks
1
vote
1answer
22 views

In a set of sentences, how could I determine the fewest sentences that contains all characters?

So, for the sake of simplicity, I am going to use English characters for this example. Let's say I have a set of strings of characters in English ranked by difficulty: Easy, Intermediate, Advanced. So ...
0
votes
1answer
47 views

How is equation 1 simplified to equation 2 as shown below

In CLRS (Intro to algorithms) on page 362, it says eqn(1) : can be simplified to this equation(2): I would like to know how this simplification was arrived at. It shouldn't necessarily be a formal ...
1
vote
1answer
27 views

Finding the area of a rectangle in python [closed]

Q: Standard input consists of exactly four integers, first x1 and y1, the coordinates of the bottom-left corner of a rectangle, then x2 and y2, the coordinates of the top-right corner. Write a Python ...
0
votes
1answer
22 views

Generating topological sequence from DAG with additional “not appearing before” constraints

DAG specifies the relationship of one node must appear after another. What if I add an additional constraint where one node cannot appear before another on top of the DAG? Is there an algorithm for ...
0
votes
0answers
25 views

Approach / data structure to wait for N tasks to complete in arbitrary order

My system needs to wait for the completion of N tasks and terminate when all are completed. The work items are passed in as an immutable array and the execution of these items are handled externally ...
0
votes
0answers
21 views

Market Research Algorithm

I work at a startup and we're doing a lot of online market research to get data about supermarkets in Germany, their name, address, telephone numbers, emails and so that already exist on their website ...
0
votes
0answers
33 views

How does perlin noise work?

I would like to write a function that returns a 2D array of floating point numbers representing pixels in an image. I have tried implementing perlin noise 3 times and have followed this (https://www....
4
votes
1answer
63 views

Optimising an exhaustive search for a card game

I'd like to search for a combination of resources that when used, would produce at least up to a threshold of different kinds of materials. For the majority who are not in the know, I'll use an ...
0
votes
1answer
39 views

Group adjacent sections to create groups with biggest value, value is changing in groups

I have sections 1,2,3...44. We can group only adjacent ones and create groups of maximum size S = 4. There are two possible variations of this problem: can not overlap at all (preferred) can overlap ...
1
vote
0answers
34 views

Fastest way to determine constrained sum of an array

I have two $N$-vectors of positive integers, called cost and gain, and I have another integer called ...
0
votes
1answer
31 views

Algorithm for assigning people to groups

Given a list $L = [1, 2, .., n]$ and a list $C = [(L_i, L_j), ....]$ form a group of pairs $G = g_1, ..., g_{n/2}$ such that: every element of $L$ is assigned to exactly one group $g_k = (L_i, L_j) \...
2
votes
1answer
76 views

Finding maximum of $n$ many $m$-bit integers

Suppose you want to determine the largest number in an $n$-element set $X = (x_1, x_2, \dots , x_{n})$, where each element $x_i$ is an integer between $1$ and $2^m − 1$. Describe an algorithm that ...
-2
votes
1answer
138 views

maximum spanning tree in a complete graph

Given a complete graph how do I find maximum weight spanning tree. where $weight(u, v) = \sum_{i=1}^{k} |w_{i,u} - w_{i,v}|$ assuming $k \lt 7$ and $n \le 500000$. $n$ number of nodes $weight(u,v)$ ...
0
votes
0answers
30 views

Optimal partitioning of n-arrays

You're given N integer arrays. Each array can have different size and contains unique values. However same integers can be found in different arrays. The goal is to partition those arrays into K ...
5
votes
1answer
78 views

Word Wrap Algorithm and Datastructure that supports modifications of text and window size

I'm trying to find or create an algorithm for efficiently displaying text that is word wrapped. All the algorithms (if they an even be called that) for word wrapping presume a given lot of text and ...
0
votes
1answer
32 views

how to find all negative weight cycles(elementary circuit) in a strongly connected directed graph?

I can use Bellman-Ford to get some of the elementary negative weight cycles in a graph. It's not guaranteed to always get all of them. (Elementary Cycle: A cycle is elementary if no vertex but the ...
0
votes
0answers
16 views

What should I consider to analyze my proposed ILP in a scientific environment?

I am working on an NP-complete problem and, I have proposed an efficient (as I think) Integer Linear programming to find the solutions in some small instances. My algorithm can work on a greater size ...
1
vote
1answer
37 views

Iterate unique sets of integers

I'm trying to figure out of if there's a way to generate all unique sets of integers of length K, where each member has an upper bound of N, and a lower bound of M, without tracking which sets have ...
-1
votes
0answers
26 views

Partition a sequence of non-negative integers into k parts, minimizing the maximum sum of each part

Given non-negative integers $x_1, \dots, x_n$ and $k > 0$, find $k+1$ integers $0=a_0< a_1 < a_2 < \dots < a_k = n$ such that $$\max_{j=0}^{k-1}\left(\sum_{a_j}^{a_{j+1}-1} x_j \right)$$...
2
votes
1answer
29 views

Better way to decide if a set is a pure simplicial complex

Setup I am trying to write a function that determines if a set of vertices, edges and faces is a pure simplicial complex. A pure simplicial complex is a set where all facets have the same degree, a ...
5
votes
0answers
166 views

Normalization-by-evaluation for untyped lambda calculus which results in 𝛽𝜂-normal form

Usual NbE algorithms for untyped lambda calculus, which use (P)HOAS to embed terms to a host language constructs, results in a beta-normal form of a terms. Is there algorithms to (efficiently) exploit ...
4
votes
2answers
628 views

Sum of series (n/1) + (n/2) + (n/3) + (n/4) +…….+ (n/n)

I wonder if there is a formula to calculate the sum of n/1 + n/2 + n/3 + n/4 + ... + 1. (Integer division) The number n can be as large as 10^12, so a formula or a ...
0
votes
0answers
37 views

offline Bin Packing problem with multiple size bins

As per my research on stack overflow communities, This is probably known as cutting stock problem / multiple Knapsack problem (a variant of the bin packing problem) which is NP hard. here are the ...
1
vote
2answers
65 views

is any faster algorithm to calculate this series? ∑∑ai​/aj

I am wondering if it is possible to calculate the following double sum, where $a_1,\ldots,a_n$ are positive integers, in time faster than the trivial $O(n^2)$: $$ \sum_{i=1}^n \sum_{j=1}^n \left\...
3
votes
1answer
84 views

An algorithm for effecient resource redistribution

For those who think visually, say I've got 5 warehouses with a current stock level of # of fish, and a target level for each. How do I achieve the new target levels in as few truck shipments as ...
3
votes
1answer
42 views

How difficult is this matching-like problem?

Let $A$ and $B$ be two sets of integers with $|A|>|B|$. Given a map $f: A \rightarrow B$ and $i \in A, j \in B$, let us use the shorthand "$i$ is matched to $j$" if $f(i)=j$. I am ...
0
votes
0answers
24 views

Asymptotic Notation sanity check for f(x) and g(x) [duplicate]

For each of the 2 pairs of functions I need to figure out the following: g(n) = Θ(h(n))? g(n) = O(h(n))? g(n) = Ω(h(n))? g(n) = o(h(n))? g(n) = ω(h(n))? Pair one g(n) = (64)(n/4), h(n) = 256(n/8) ...
-2
votes
0answers
26 views

How to solve connecting cities problem?

This problem is from hackerrank seems to be impossible that I can't sleep without knowing the solution. The problem: There are 2 states each contain cities and roads between them. I need to remove ...
0
votes
0answers
15 views

minimum moves to be made to get out of convex hull

Given a convex hull in $XY$ plane. and we have $n$ points sitting inside it. In one move we can move all the points to right by $1$ or move all the points to up by $1$. what are the minimum number of ...
0
votes
0answers
131 views

divide a sorted array into k subarrays with their intervals are same and count integers in the interval without accessing the data

Given a positive integer k and an array A[1..n] that contains n positive integers in ascending order, count the number of integers that its value lie in $(\frac{100(i−1)}{k}, \frac{100i}{k}]$ for ...
7
votes
1answer
197 views

Polynomial time algorithm for finding a maximal monotone subset

Input: Some fixed $k>1$, vectors $x_i,y_i\in\mathbb R^k$ for $1\le i\le n$. Output: A subset $I\subset\{1,\dots,n\}$ of maximal size such that $(x_i-x_j)^T(y_i-y_j) \ge 0$ for all $i,j\in I$. ...
1
vote
1answer
22 views

Determing Big Oh Of Given Data

I'm trying to determine the big O time complexity of the following data set where the first column is the input size, and the second column is the execution time in seconds. Where possible, I should ...
0
votes
1answer
51 views

What is the polynomial time reduction between these two Hamiltonian cycle problems?

Problem 1: Given an undirected graph, return the edges of a Hamiltonian cycle, or correctly decide that the graph has no such cycle. Problem 2: Given an undirected graph, decide whether or not the ...
0
votes
0answers
13 views

Recursive Selection of Pivot from an Array

Suppose we have an array of integers $A$ of length $n$, which is assumed to be multiple of 5 for convenience in the discussion below. Now we try to pick a pivot $x$ from $A$ such that $x$ can divide $...
0
votes
2answers
58 views

Why this problem has such a simple solution? How would you avoid looking for more complex solutions first?

There's a problem whose solution startles me because at first sigh, I wouldn't imagine that it could be solved so easily. The problem is: There are n tasks, each task ...
1
vote
2answers
37 views

Need help with this runtime of algorithm with double loops that results in 0

I know with absolute certainty that this is the wrong runtime, but I just wanted to show you how I got to it. ...
1
vote
1answer
36 views

Cashier Scanning Algorithm Problem

I came across a problem about a cashier scanning goods that I'm stuck on. I paraphrase the question below. A cashier only has x time to scan a person's goods. The ...
0
votes
0answers
44 views

Create a potential function for an abstract queue data structure to show constant amortized-time complexity

Consider a variation of a Queue called MaxQueue, Q, that has the following operations: dequeue(Q): removes and returns the first element of Q enqueue(Q, s): Appends the integer s to the end of Q ...
0
votes
1answer
19 views

Intuition behind the Reversal Algorithm [ Rotation of Array ]

I know that the below program uses Reversal algorithm to rotate an array's elements to k positions to the right. But how does the Reversal algorithm works? It seems kinda magic to see. Can somebody ...
0
votes
1answer
30 views

How to Sort 2D array with out 1D array

Hello I am a new Computer Science student Ok, so I am trying to sort the 2D array I know you can actually sort a 2D array by copying it into a 1D array sort it using any Algorithm, and then place ...
1
vote
0answers
27 views

Is there a way to uniquely map every natural number x < N to another number y < N uniquely and randomly? [duplicate]

Imagine you have a number x, when x ∈ [0, N]. Is there any algorithm that can map x to y, so that y is also y ∈ [0, N] with the mapping being unique, and the distribution of all y is distributed ...
0
votes
1answer
37 views

Is there a way to combine linear equation and inequalities into same equation in order to optimise software calculations?

I’m programming web application which has some tricky calculations and I would need some help with mathematical calculations. What I'm trying to calculate: I have number of items. Lets call items a1, ...
0
votes
0answers
20 views

Expected runtime for hashing with a binary search tree as collision handling

I thought about implementing a data structure with expected runtime of O(1) for insertion, deletion and look-up and a worst case runtime for these operations of O(log(n)). This is under the assumption ...
3
votes
0answers
39 views

Algorithm to cut a sphere in half with a plane and maximize the number of points on the sphere surface on one side of the plane

Consider a sphere with a coordinate system like the earth. There are $N$ points on its surface at random positions. For all the infinite planes that cuts the sphere exactly in half (i.e. the sphere's ...