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
2
votes
1answer
68 views

Enumerate all valid orders of subset sums

Given an positive integer $n$, we define an order of subset sums (or simply, an order, when there is no ambiguity) to be a sequence of all subsets of $\{1,\ldots,n\}$. For example, when $n=2$, the ...
0
votes
1answer
22 views

“Knapsack problem” with repetition, “lesser or equal” constraint, and recording all valid combinations

In a game I am developing I came across an interesting problem, that seems like it could be solved using some modified variant of the knapsack problem, but it's a bit over my head. Let $x_i$, $ 1\leq ...
1
vote
0answers
41 views

Algorithm suggestion to order data with specific condition

Suppose, we want to rearrange all possible $n$-bit binary strings (i.e., we have $2^{n}-1$ possible strings) in a 1-D array $X$; given that stings with smaller hamming distance should be placed as ...
0
votes
0answers
40 views

Scheduling jobs online on 3 identical machines - a lower bound of 5/3

Consider the Online Scheduling Problem with $3$ identical machines. Jobs, with arbitrary size arrive online one after another and need to be scheduled immediately on one of the $3$ machines without ...
0
votes
0answers
14 views

Global-input-local-output p-time algorithms

Are there polynomial-time algorithms whose input is global but output is local in nature? What I have in mind is a problem instead of an algorithm. It’s the satisfiability (SAT) problem. Each clause ...
-1
votes
0answers
26 views

Finding the k-th baseball card purchased in an array of tuples with year and number of baseballs purchased in that year in O(n) time

Edit: Problem has been solved! Thank you @orlp and only you for actually taking the time to be helpful and giving me the hint that got me to progress!
2
votes
1answer
75 views

Maximization problem on finite collection of finite sets

Problem I am considering the following maximization problem: Input is a finite collection of finite sets $\mathcal{F} = \{ X_1, X_2, \ldots, X_n \}$. Goal is to find a subset $G \subseteq \mathcal{F}$...
1
vote
0answers
31 views

If factor isn't found in P-1 algorithm, should upper bound be increased linearly (i.e. +1)

I have seen some implementations of Pollard's P-1 algorithm where the upper bound is only increased by 1 if no factor is found. Such an implementation is described here. Is it sort of missing the ...
1
vote
1answer
154 views

Can map-reduce speed up the count-min-sketch algorithm?

Is there any possibility of improvement in the result of count-min-sketch algorithm if we will use Map Reduce approach? Improvement in performance can be in terms of accuracy, time complexity or the ...
1
vote
1answer
68 views

Do there exist fast multiplication algorithms for two integers with one of them being static?

Let N and M be arbitrary 1024+ bit integers. The objective is to compute the product of N and M (2048+ bits) There exist various multiplication algorithms for various bit lengths (ex library: GMP). ...
12
votes
5answers
2k views

Efficient algorithm to compute the $n$th Fibonacci number

The $n$th Fibonacci number can be computed in linear time using the following recurrence: ...
1
vote
0answers
31 views

Baum-Welch Algorithm

I was reading the book by Jurafsky and this is written by the author on HMM Although in principle the forward-backward algorithm can do completely unsu- pervised learning of the A and B parameters, ...
0
votes
0answers
20 views

How can I parse a boolean expression to group it based on the conjunction?

I have to design an algorithm to parse an array of terms and conjunctions into a grouped boolean expression. I never studied computer science and don't usually need this for web development, but today ...
0
votes
0answers
24 views

Count Unique Subsequences to Destination?

I am looking at this post: Jamie is walking along a number line that starts at point 0 and ends at point n. She can move either one step to the left or one step to the right of her current location , ...
0
votes
1answer
38 views

algorithm to find shortest path connecting EVERY node

I have received a problem to solve and I am not sure what algorithm to use. TLDR; Find the shortest path to get to every node in a undirected graph The problem states that one must visit every ...
3
votes
1answer
81 views

How to determine the maximum valued play in Rummikub?

This question is meant as a follow-up this question and my answer here. The question asked multiple questions about algorithms for playing Rummikub and my answer provided an algorithm that, given a ...
0
votes
1answer
29 views

Is my recursive algorithm for Equivalent Words correct?

Here is my problem. Problem Given two words and a dictionary, find out whether the words are equivalent. Input: The dictionary, D (a set of words), and two words v and w from the dictionary. Output: A ...
2
votes
2answers
73 views

How to determine if given “complex” time complexity is $O(n^2)$?

If a given time complexity, such as these: $(n + \log n) * \sqrt{n+\log n}$ $n * (200 + \log^2 n)$ $(7+n^3)\log(n^5)$ is not determinable by just looking at it whether is it in class $O(n^2)$ or not,...
3
votes
0answers
63 views

Is minimising the total number of one entries in binary matrices $CA$ and $C^TB$ NP-HARD?

Given a two rectangular binary matrices $A$ and $B$ with dimensions $c\times a$ and $c \times b$ respectively, does there exist an invertible binary matrix C with dimensions $c \times c$ such that the ...
0
votes
1answer
84 views

Travelling Salesman Problem Easy Algorithms

I'm looking for a easier algorithm to implement to solve the travelling salesman problem (in javascript). Unluckily all of the ones i found are really hard to understand/ to implement. The ones i ...
4
votes
1answer
37 views

Solving linear system of nonhomogenous equations that are known to have natural solutions

Any idea is appreciated. A generic approach that works for any system would be best but if you want more info about what I'm looking for, the equations are usually short (having few variables, from 1 ...
-2
votes
1answer
38 views

How to calculate the minimum price required to buy all the stones?

I have shared the question above. My current algorithm does the calculation in O((n^4)*(2^n)). Can someone please help me out to solve this faster?
2
votes
1answer
72 views

Calculate boolean matrix multiplication (BMM) using transitive closure

Let us say I am given an algorithm that calculates the transitive closure of a given graph $G = \{ V, E \}$. How can I use this algorithm in order to perform the Boolean Matrix Multiplication of two ...
1
vote
1answer
25 views

Why do we should not to use simple count instead of cumulative count in Counting Sort?

I have this piece of code for counting sort and it is "counting" sort, because it actually counts occurrences. And it doesn't use cumulative sum. I want to ask why it is bad to not to use ...
1
vote
1answer
25 views

Is there any rich problems that can be solved using several algorithm techniques?

I am wondering if there are some particularly rich problems that have a large intersection with algorithms and data structures. An example could be the travelling salesman problem. Any other ...
0
votes
0answers
20 views

Sorting idea - using little buckets (Not BucketSort)

I am recently been doodling with sorting, thought about writing my own ideas, and what I am about to write here came to my mind, and I am writing it here because I do not know if such sorting idea ...
0
votes
1answer
35 views

Triple nested loop complexity

I'm trying to determine the complexity of the following structure: for (i = 1; i < n; i++) for (j = 1; j < o; j++) for (k = 1; k < p; k++) ...
51
votes
6answers
46k views

Floyd's Cycle detection algorithm | Determining the starting point of cycle

I am seeking help understanding Floyd's cycle detection algorithm. I have gone through the explanation on wikipedia (http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare) I can see how the ...
1
vote
1answer
19 views

Finding the middle point of the “most populated” area in a set of points?

I'm working on a game-related application, and I'm trying to find the middle point of the most populated area in my map. Example: ...
0
votes
1answer
46 views

Trading Auction - Need help with calculating price / quantity of restricted underlying securities for matching

I'm having some difficulty with implementing a non-brute force algorithm for solving the following Problem. If I can get something even close to O(N^3) i'd be happy at this point. Auction: https://...
0
votes
1answer
17 views

The definition of a graph's transitive reduction

I want to determine the transitive reduction of this graph: as of now, I only found the first step of doing this: represent the transitive closure of the graph as an adjacency relation, so this is ...
1
vote
0answers
24 views

Help understanding a theorem Kleinberg proves related to sequence alignment

This is from Kleinberg's Algorithm Design text (Theorem 6.14) Let $M$ be an alignment of $X$ and $Y$. If $(m, n) \notin M$, then either the $m^{\text{th}}$ position of $X$ or the $n^{\text{th}}$ ...
1
vote
0answers
55 views

What is Big O of a loop with square root inside?

Knowing that O(n^2) > O(nlogn) > O(n) > O(sqrt(n)) > O(logn) > O(1) and having below python code: ...
1
vote
0answers
24 views

Find original array from array with pairs of adjacent elements

Given an array composed of pairs, like this: [[3,5],[1,5],[3,2],[1,4]] Each element in the array (call it pair) means that pair[0] and pair[1] are adjacent in the original array. Note, they can come ...
1
vote
0answers
25 views

Essence of the cost benifit obtained by using “markings” in Fibonacci Heaps (by using a mathematical approach)

The following excerpts are from the section Fibonacci Heap from the text Introduction to Algorithms by Cormen et. al The authors deal with a notion of marking the nodes of Fibonacci Heaps with the ...
1
vote
0answers
29 views

Intuition behind the entire (amortized) concept of Fibonacci Heap operations

The following excerpts are from the section Fibonacci Heap from the text Introduction to Algorithms by Cormen et. al The potential function for the Fibonacci Heaps $H$ is defined as follows: $$\Phi(H)...
-1
votes
1answer
48 views

Algorithm for display nodes of a particular node based on in-degree and out-degree

Suppose we have following directed graph. When I click on say node $e$, it should make in-degree and out-degree of node $e$ and connected nodes red. As shown in Resulting Graph. My purpose is, when I ...
3
votes
1answer
39 views

“State of the art” algorithms deciding entailment of propositional formulas?

I fail to find much about how to efficiently calculate whether a propositional formula entails another. Considering the following two points... We can check, for each truth assignment which makes the ...
1
vote
1answer
32 views

Solve the online unweighted 0-1 knapsack problem efficiently

I have $n$ items and a bin of size $B$ units. Each item $j$ consumes $w_j$ units of $B$ when placed into the knapsack. The item appears one-by-one in an online fashion. Once item $i$ appears, we must ...
-1
votes
1answer
41 views

Need help with adding elements to hashtable with linear probing

Here is an example problem which I have having trouble figuring out. The red text is the answer. I get how the values are added before the hashtable is resized... that is common sense. (Insert 0 at ...
1
vote
0answers
38 views

Counting one's in a stream of bits

I have to count the number of one's in last $m$ bits in a stream of bits and $m \leq n,$ where $n$ is the window size and it should take polylogarithmic space in $n$. I could only store last $n$ bits ...
0
votes
1answer
38 views

Can we get any subsequence of size $\ge \lfloor \frac{n}{2} \rfloor$ in a sorted order from a sequence in linear time?

Given a sequence $A$ of $N$ distinct integers, does there exist a strategy to get at least one subsequence with size $\geq \lfloor \frac{N}{2} \rfloor$ of the sequence in sorted order in $O(n)$ time? ...
0
votes
1answer
16 views

Method to change value in a key for a min heap

How would you write a method to change the value of a min heap where bool changeKey(int oldKey, int newKey). The keys are unique, no duplicate keys are permitted. If there is a key in the heap with ...
0
votes
0answers
7 views

Community detections in networks using more than one factor?

all community detection algorithms in major python packages are using only edges & edge weights. Is there any algorithm that uses multiple attributes of nodes to detect communities? For ex, in ...
0
votes
1answer
361 views

Merge sort and quicksort recursion tree depth

1) I need to determine recursion tree depth for strings composed of 10, 100 and 1000 elements when using merge sort. For the 10 elements one/I can do it on a paper, just drawing tree, but what about ...
0
votes
0answers
42 views

Get the maximum sum of n items below a threshold

Consider a modified Knapsack Problem where: The number of items to be included is fixed. The value of each item is equal to its weight. Therefore, given a set of numbers, a threshold and the number ...
0
votes
0answers
53 views

Finding index of $p_{k}$ element in the original sorted array if elements were to be removed using a specific condition

Consider a sorted list of numbers $C_{0}=\{0,1,2,3,...,n-1\}$ from where one element will be eliminated at each step. We are also given a value $L$ in $[0, 1)$ and let the indexing start from $0$. ...
9
votes
1answer
2k views

The buckets of water problem

Let's consider the following problem (buckets/pails of water problem) (This problem may be known with different name. If does, please correct me). Let $B=\{b_1,...,b_n\}$ be a set of $n$ buckets. ...
0
votes
1answer
48 views

Proving $\lceil \lg n \rceil -1 = \lfloor \lg n \rfloor$

I recently came across the question: Show that there are at most $\lceil n / 2^{h + 1} \rceil$ nodes of height hh in any nn-element heap. I looked for some solutions and found this one: Binary heap: ...
0
votes
2answers
97 views

How can i solve a recursion equation with square root using recursion tree method?

$T(n) = \sqrt{2}T(\frac{n}{2}) + \sqrt{n}$ I am trying to solve this question by recursion tree method, do we have any way in which we can draw a recursion tree for this eqn. I just don't want to use ...