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
0 answers
36 views

Is there a method for information transfer without copying the data?

What I mean is, if in real life I had an object and I gave it to you, I would not have it anymore. I did not give you a copy of the object. Is there a way to do that with information?
user avatar
  • 11
3 votes
1 answer
110 views

Is there an efficient algorithm to find GCD of all cycles' lengths in directed multigraph?

I have weighted connected directed graph with cycles which can have multiple edges and loops (edge from vertex back to itself). Weight of each edge is its length (always positive integer). There ...
user avatar
  • 245
-3 votes
1 answer
27 views

Which algorithm would be most suitable for finding a minimum subgraph that connects all vertices in a graph and has the smallest weight?

Which algorithm would be most suitable Kruskal, Prims or Steiner tree algorithm ?
user avatar
  • 1
1 vote
0 answers
20 views

Algorithmic ideas to multiply two tall & skinny matrices into one large square matrix?

This problems comes from AI, and it looks something like this: I am supposed to multiply two floating-point matrices A * B. A ...
user avatar
1 vote
1 answer
41 views

Find a perfect matching with weights as close as possible to each other

Given a set of jobs $J$ and a set of machines $M$, where the link between machine $i\in M$ and job $j\in J$ has a positive weight $w_{ij}$. The problem is to select a perfect matching between the jobs ...
user avatar
  • 1,016
1 vote
1 answer
53 views

Find max of all trees resulting from single edge removal in generic tree in linear time

Given a generic tree with $n$ weighted nodes, there are $n-1$ edges. Removing any of the edges will partition the tree into two distinct trees, hence we can construct $2(n-1)$ possible trees in this ...
user avatar
1 vote
1 answer
26 views

Redistricting algorithm

Here in the USA there is a lot of controversy over the practice of gerrymandering. Every ten years the states are divided up into new congressional districts and whoever is in charge creates bizarrely ...
user avatar
2 votes
1 answer
27 views

finding a hemisphere that contains all points of a given set S

Let $S$ be a finite set of points on the unit sphere $\mathbb{S}^2$. My question would be: is there an easy way to either find a great circle $C$ such that all points in $S$ are inside one of the ...
user avatar
1 vote
1 answer
50 views

Summation of asymptotic notation the

How can we solve summation of asymptotic notations like given below: $$\langle 2^0 + 2^1 + 2^2 + \dots + n^{k}\rangle = \Theta(n\log n)$$
user avatar
0 votes
0 answers
25 views

Where is external sorting used beyond databases?

I am trying to find applications/systems that use external sorting techniques or avoid external sorting by using other methods to achieve a task. I know most relational databases (like PostgreSQL or ...
user avatar
0 votes
1 answer
87 views

Consistent Hashing Algorithm Without Distribution / Load Balancing

I need some help finding or creating a consistent hashing algorithm with the following properties: Given N buckets, only distributes keys to bucket N. When number of buckets are increased from N to N+...
user avatar
0 votes
0 answers
24 views

Algorithm to generate unique suggestions for creating an ID

Let's say I have a service where I provide user registration. The user chooses a ID. Now if I already have someone who is registered against that ID, I will inform the user that this ID is already ...
user avatar
  • 330
-2 votes
1 answer
22 views

An electronic book is made up of 500 pages there are 16 lines of 2400 bits lines of each page. computer space it will ocuppy on a computer in GB

An electronic book is made up of 500 pages and there are 16 lines of 2400 bits lines of each page. compute the space it will ocuppy on a computer in GB
user avatar
2 votes
0 answers
28 views

scheduling with profits and deadlines clrs

The following problem is on page 1104 of the CLRS textbook: I was wondering how to show that the problem is NP-hard (i.e. part b)? Like subset-sum, this problem is weakly NP-complete; it has a ...
user avatar
1 vote
0 answers
23 views

compute shortest distance to a different sink

Given a directed graph G=(V, E) and a sink vertex t. Edge costs may be negative, zero, or positive. consider d(v) contains the length of the shortest path from v to t Given a new sink t2 in the graph, ...
user avatar
2 votes
1 answer
71 views

Longest common subsequence of two permutations

Given two permutations $\pi_1$ and $\pi_2$ of numbers $\{1,2,\dots,n\}$, can we find $\mathrm{LCS}(\pi_1,\pi_2)$ in $O(n\log n)$? I think we can use LIS but I get stuck.
user avatar
  • 1
2 votes
1 answer
22 views

a generalized job assignment problem

The following problem is from a past algorithms course exam and I'm using it to test my knowledge. There are m machines and n jobs. Each machine can doing a subset of jobs. Each machine i has a ...
user avatar
0 votes
0 answers
60 views

How we can solve two lines of this algorithm in $o(n^2)$?

Given $n=2k$ pairs of points $P=\{(p_1,q_1),(p_2,q_2),\dots,(p_k,q_k)\}$ in the plane. Also, let $d(.)$ return distance between two points. Now, our goal is to act as bellow: For each $(p_i,q_i)$ ...
user avatar
  • 1
1 vote
0 answers
38 views

Given T(1)=1 and $T(n) = 3T(n/4) + cn^2$, does it make sense to yield $T(2)=T(1)+c2^2$?

Section 4.4 of "Introduction to Algorithms, 3rd Edition By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein" illustrates how a recursion tree provides a good guess ...
user avatar
  • 576
0 votes
0 answers
43 views

Efficiently finding range from ordered list of ranges with preprocessing

Say we have a list of ranges like so: ranges = [(0, 100), (101, 200), (201, 300)] The ranges will always be ordered, never overlap, and perfectly align. We want to ...
user avatar
1 vote
1 answer
11 views

Finding overlapping time under distance condition

I have a set of records (2 or more for each person) on multiple peoples locations (latitude and longitude) with timestamps. each record has: person ID, latitude, longitude, timeStamp. for each 2 ...
user avatar
  • 11
2 votes
1 answer
25 views

Check if a string can be obtained by a sequences of insertion of "abc"

Let $a$ initially be an empty string. One can transform $a$ into $b$ in the following way: $a$ becomes $a_{left}+$"$abc$"$+a_{right}$, where $a=a_{left}+a_{right}$ in a prior state. $a_{left}...
user avatar
  • 123
2 votes
1 answer
61 views

Find two very frequent items in a given array of comparable items

I am new to this community and I have a question regarding a problem I was trying to solve. Could anyone review my algorithm for solving this problem? I want to emphasize also that the algorithm must ...
user avatar
  • 45
3 votes
1 answer
425 views

Efficient data structure for insertion, deletion and smallest-not-in-range query on an array of integers

I'm trying to make a data structure $A$ that has the following features: insert($a$) operation : insert given integer $a$ to $A$. It is assured that all integers are unique. delete($b$) operation : ...
user avatar
0 votes
0 answers
21 views

Is one set of vectors constructed by another set of vectors?

Let there be given set of vectors $V = \{v_1, v_2, ..., v_n\}$ and set of vectors $S = \{s_1, s_2, ..., s_k\}$ where $n > k$. The set of vectors $V$ can be constructed by $S$ if the vectors in $V$ ...
user avatar
2 votes
1 answer
73 views

Prove a greedy algorithm that obtains the minimum integer with at most k adjacent swaps is correct

This problem is from LeetCode. You're given a string num representing the digits of a very large integer and an integer k. You are allowed to swap any two adjacent digits of the integer at most k ...
user avatar
0 votes
1 answer
53 views

Understanding time complexity of algorithm to determine if parenthesis are matching

Both these algorithms determine if all the parenthesis in a string are balanced and properly nested. The first algorithm uses "a constant amount of memory, regardless of the length of the string.&...
user avatar
0 votes
0 answers
35 views

Partition points into two clusters of equal size, minimizing sum of diameters

Suppose Given $n=2k$ points in the plane. Our goal is to partition points into two clusters $C_1$ and $C_2$ such that $d(C_1)+d(C_2)$ minimized, where $d(\cdot)$ is the diameter function, and $|C_1|=|...
user avatar
  • 1
1 vote
0 answers
35 views

Where does 2^32 come from with bitcoin?

Several months ago I was doing research into calculating mining revenue for several crypto currencies. When trying to calculate BTC revenue I found this value 1/2^32 which was described somewhere ...
user avatar
  • 51
2 votes
1 answer
50 views

How do these Crypto terms relate to each other and what do they all mean?

Alright this is another day of my pursuit to learn about how crypto works. I have several terms that I have found linked together. I was trying to do research on how the Target Hash is determined and ...
user avatar
  • 51
2 votes
3 answers
55 views

Store strings which have same start, but different end

I need to store a list of strings in some files. In this moment, there are too many strings in too many files, which is a problem for me. Here is an example of strings: ...
user avatar
  • 21
0 votes
0 answers
25 views

3-term arithmetic progression

I am a computer science student, I am studying an algorithm course independently. In the course I got stuck with this question: $A$ 3-term arithmetic progression is 3 integers ${a < b < c}$ such ...
user avatar
  • 29
1 vote
1 answer
20 views

K-Modes Clustering with Partially-Overlapping, Variable-Length Data?

I'm working on a project that's attempting to cluster books using machine learning. I'm using the K-Prototypes algorithm for clustering data that has both numerical and class-based data. Under the ...
user avatar
1 vote
0 answers
20 views

Algorithm Complexity Question

this is my first question on this site and I would like to preface this by saying I am not very savvy when it comes to Computer Science. So, I will try to ask this the best I can. I was doing some ...
user avatar
  • 51
0 votes
0 answers
63 views

Binary search with mid index equals to $\frac{(right + left )}{2}$

I have tried to implement traditional binary search on an array. Now, if I set the mid index to be $mid = \frac{(right + left )}{2}$, my code does not run within time quota specified already, however, ...
user avatar
  • 459
1 vote
1 answer
35 views

T(1)=1 is a boundary condition of the recurrence $T(n)=2T(\lfloor{n/2}\rfloor)+n$. Does there exist any other boundary condition of the recurrence?

Section 4.3 of "Introduction to Algorithms, 3rd Edition By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein" uses the following recurrence as an example to ...
user avatar
  • 576
1 vote
1 answer
37 views

Why DFS transversal without the duplicates is a valid cycle?

So I am studying apporiximation algorithms for TSP problem and there is a step that I don't get. Essentially trying to solve TSP means we are looking for a minimum cost Hamiltonian path. The well-...
user avatar
2 votes
0 answers
39 views

Is there an algorithm for determining the identity of an individual, based on their genome and the genome of distant relatives?

I've been thinking recently about the Golden State Killer case, in which a crime was solved by comparing a killer's DNA sample with known samples in a public genetic database. The cousin of the killer ...
user avatar
1 vote
3 answers
54 views

Recursive algorithm for adding numbers from 1 to n with O(1) time complexity

So I have a recursive algorithm which sums up the numbers from 1 to n plus one (hence the return 1): ...
user avatar
  • 13
0 votes
0 answers
19 views

Algorithm to Detect Disjunctive Relationships

I'm working with logic formulas of the form '0 & 2 | 0 & 3'. I was wondering if anyone knew of an algorithm that would take in such a formula, detect existing disjunctive relationships, and ...
user avatar
  • 1
1 vote
1 answer
31 views

How to prove that if Eternal Vertex Cover is Polynomial it's possible to detect its vertices and edges

EVG is defined as EVC = { <G,m,k>| G is an undirected graph and there is as et of m edges in G that are covered by at most k nodes} If EVG was decidable in polynomial time how could we find the ...
user avatar
  • 135
1 vote
2 answers
60 views

How to use the step count method correctly for binary search?

I've tried to use the step counting method to get the worst-case time complexity for binary search. But I seem to mess it up, as my final result would be O(n) and ...
user avatar
  • 13
3 votes
0 answers
21 views

GPU compute parallel radix sort optimizations

I'm looking at this paper that describes a GPU parallel radix sort algorithm. They describe multiple optimizations but in section 3 where the whole algorithm is described some things elude me. First, ...
user avatar
  • 141
1 vote
0 answers
36 views

Text Justification problem of "Introduction to algorithm"

The problem that I currently went through is kind of text justification problem. The problem is given that there is a paragraph and a some blank lines. We want to print this paragraph neatly on the ...
user avatar
1 vote
0 answers
75 views

Why are these two recurrence relations that compute the shortest path equal?

Given a directed graph $G=(V,E)$ with positive weight function $w$, source $s$, destination $t$ and a nonnegative integer $\ell$, we want to find shortest path $\pi$ from $s$ to $t$ such that $\pi$ ...
user avatar
  • 1
1 vote
1 answer
92 views

Given a sequence of strings how can you find the maximum number of strings so that if you concatenate them you have a dominant letter?

The naive approach, which is the first thing that came to my mind, is to use some sort of backtracking to generate all subsets of the given set of strings and then to find the subset with the maximum ...
user avatar
4 votes
1 answer
52 views

Non adjacent sum: Why do we need to include or exclude the current element?

The problem goes like this: Write a function, nonAdjacentSum, that takes in an array of numbers as an argument. The function should return the maximum sum of non-adjacent elements in the array. There ...
user avatar
  • 143
0 votes
1 answer
11 views

How much faster would a semantic segmentation model be with just 2 classes compared to 100 classes?

Let's say I have a semantic segmentation model that distinguishes between 100 classes of objects, and the speed of running the model is 1 image per second. Now let's say I take the same model ...
user avatar
1 vote
1 answer
39 views

Vector of 1s and sum of elements

I stumbled on the following computing issue and would like some help to solve it. Given a vector of size n and filled with 1's, give all the elements obtained by the sum of them. Ignore combinatorial ...
user avatar
1 vote
1 answer
16 views

Algorithm which allows the backend to find compromised data from a 3rd party service

On my backend I use a 3rd party service which provides currency exchange rates. I use this rate for the funds conversion within the customer’s accounts. As far as this rate affects customers’ money, I ...
user avatar
  • 111