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

Using Subset Sum algorithm $O(n)$ times to find the subset

Subset Sum is a well-known dynamic programming problem, which states that given a succession of numbers and a number, the algorithm determines if exists a subset that its sum is equal to the given ...
0
votes
0answers
9 views

What kinds of questions are asked by the interviewers of IIT Guwahati for M.Tech in CSE? [closed]

What are the particular subjects related to which the interviewers of IIT Guwahati ask the candidates applying for M.Tech course in Computer Science and Engineering during the interview? Are there any ...
0
votes
1answer
49 views

$O(\log n)$ search algorithm for a sorted natural number array with block of 0s on right

Assume A is an m sized array containing n ($m \ge n$) natural numbers (excluding $0$), sorted on the left of it. All remaining cells on right are filled with zeros. For example, $m=10, n=4$: $$A = \{...
-3
votes
0answers
22 views

Subarray with given sum

What are they asking and how can I solve it? https://practice.geeksforgeeks.org/problems/subarray-with-given-sum/0 Given an unsorted array A of size N of non-negative integers, find a continuous ...
1
vote
2answers
34 views

Given a list of integers and a target integer, return the number of triplets whose product is the target integer and two adjacent triplets

Question: Given a list of integers (possibly negative) and a target integer, return the number of triplets whose product is the target integer and two of the triplets must be adjacent. More ...
0
votes
1answer
33 views

How to remove 'skip' edges from a DAG? (How to find only the longest path from each node to each of its sinks?)

In two separate projects, I have come across this problem and I still don't have a good solution for it, so I thought it was worth describing here. Consider the following problem: I have a set of ...
2
votes
1answer
934 views

What is an algorithm that maps back and forth from (x,y) coordinates to the index of that point in a space filling curve over a rectangle?

Suppose that I have a space filling curve over a rectangle of width W and height H. For example, for the rectangle: ...
1
vote
1answer
66 views

Find the power of 2

Assume $n=2^k$, write an algorithm that can find $k$. **log function is not allowed. Is there an efficient way to find the power instead of multiplying by 2 until it equals $n$? What is the ...
1
vote
1answer
30 views

How to connect line segments to form the least number of paths

I have a list of unordered line segments, some of whose endpoints lie on the same point. How do I connect these segments efficiently to form a minimal amount of paths? For example, if I have the ...
1
vote
2answers
46 views

Algorithm for optimal rule-based arrangements?

I am trying to plant a row in a garden. Certain plants are good for some plants and bad for others, and I am trying to find the best order of plants: most adjacent friends and no adjacent foes, as ...
2
votes
1answer
63 views

Dynamic Programming, Counting Independent Sets

My first thought is to make OPT(i, j), where i is n, and j is some condition on the column. But my experience with DP is from knapsack and weighted interval scheduling, but I'm unsure of how to ...
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 ...
6
votes
1answer
462 views

Finding Shortest Paths of weighted graph using stacks

I will be given some kind of this graph as in the picture below. I've searched some algorithms but it seams as if it is something impossible for me to figure them out. In fact using Floyd–Warshall ...
0
votes
1answer
124 views

How to teach random number generator algorithms?

How can I teach random number generator algorithms? I'd like to show how seeding makes randomization closer to truly random. Details of the task to be given are as follows: Code should read a text ...
1
vote
1answer
65 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 ...
0
votes
2answers
137 views

Is there a better-than-brute-force algorithm to generate a graph whose relation is string edit distance=1?

I'm interested in creating a graphs whose vertices are strings, and whose edges represent the relation of having an edit distance of 1 under a given string metric. An obvious approach is to make all $...
3
votes
1answer
51 views

Beginner Question Concerning the Logic of a Very Simple Correctness Proof

I'm trying to familiarize myself with correctness proofs and need some help. In the proof for SimpleSelect (P.25), why do we assume both $A'[i] < A'[k]$ and $1 \leq i \leq k$? I'm not quite sure ...
0
votes
1answer
17 views

Where does the base come from in a subsequence count?

If sequence X has m symbols, then X has 2m possible subsequences. Where does the base (<...
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
0answers
29 views

What is the appropriate term for the “string splitting” problem?

To be clear, I didn't hear of this in any particular venue, and so can't point you to one. Two variants that I can bring you: String spitting Given a string (sequence of elements), and a function ...
4
votes
1answer
180 views

How to extend Bellman-Ford to solve the $k$ shortest path routing?

Browsing the wikipedia I got to this page where it is said: Finding k shortest paths is possible by extending Dijkstra algorithm or Bellman-Ford algorithm and extend them to find more than one ...
0
votes
1answer
25 views

Find Best N Points From a Graph

I've given a task and wonder if there are any better solutions. Inputs of task are: Distance of district pairs Population of pairs Goal is: Find n districts at which its population and districts ...
0
votes
0answers
19 views

Need help with a specific distribution algorithm

Here is the problem: We have an ordered To-Do list with n tasks. The duration of every task is given and tasks need to be completed in order. We need to distribute the tasks to m days. Individual ...
0
votes
1answer
16 views

An almost surly fine-time game of coin toss where you win with probability $p$

Given a fair coin and a number $p\in(0,1)$. How do you Design a game that finishes in finite number of tosses with probability $1$. And further, with probability $p$ you win the game. I thought about ...
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$...
2
votes
1answer
148 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
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 - ...
4
votes
3answers
1k views

Big O Notation of $n^{0.999999}\log(n)$

I'm taking the MIT Open Courseware for Introduction to Algorithms and I'm having trouble understanding the first homework problem/solution. We are supposed to compare the asymptotic complexity (big-O)...
1
vote
1answer
24 views

Best case for sorting algorithm

Given this sorting algorithm: ...
1
vote
2answers
296 views

What is the Space Complexity of Tail Recursive Quicksort?

Looking at the following tail recursive quicksort pseudocode ...
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 ...
0
votes
1answer
18 views

reordering a max heap that the values of one of her subtrees has been changed

Let $H$ be a max binary heap with $n$ elements (vertexes). Pick a vertex $z$ in the heap with height of $k$ ($0<k<\lg n$) To every element in the sub heap of $z$ we add the constant value $c &...
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
1answer
20 views

Comparing the efficiecy of 2 run times

I have a heap with $n$ elements. $k$ represent a number that is the height of one of the elements in the tree. I need to compare two run times and prove what i claim. The 2 run times are: $$ (1)O(...
2
votes
1answer
39 views

In determining whether any segments intersect, why there must be some sweep where segments $a$ and $b$ are consecutive?

In CLRS, Section 33.1, we are given the any-two-segments-intersect algorithm. It's a cool algorithm for sure but going through the correctness proof, I don't know how they arrived at the following ...
1
vote
2answers
372 views

Algorithm for scheduling unit time tasks with arrival times and deadlines

Suppose we have $n$ tasks to order over $n$ days. Each tasks takes 1 day to be completed. Each task has a start date when the task becomes available and a deadline when the task must be delivered. ...
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 ...
0
votes
1answer
37 views

Binary Search Symbol Table

Hi I'm attempting to self teach myself from Algorithms (Sedgewick) and ran across the following problem: ...
2
votes
1answer
284 views

Merging rectangles into rectilinear polygon

Having a set of adjacent rectangles, what would be the algorithm that gets the rectilinear polygon wrapping around them?
4
votes
4answers
516 views

Do all recursive problems have optimal substructure?

I am reading about dynamic programming and I understand the overlapping subproblem requirement but not sure why optimal substructure is explicitly stated. Are there problems that can be solved ...
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 ...
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 ...
2
votes
1answer
52 views

Max sum cyclic path of fixed length in matrix

Given a matrix NxM of positive integer values and a starting position (that has value 0), determine the maximum sum path of length K that starts and ends at the aforementioned position. Legal moves ...
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 ...
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 ...
2
votes
1answer
286 views

one-to-many matching in bipartite graphs?

Consider having two sets $L$ (left) and $R$ (right). $R$ nodes have a capacity limit. Each edge $e$ has a cost $w(e)$. I want to map each of the $L$ vertices to one node from $R$ (one-to-many ...
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
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 ...