# algorithms's questions - English 1answer

6.017 algorithms questions.

### Count all paths between two vertices

1 answers, 22 views algorithms graphs
The problem is we have to count number of paths between a source and a destination in a graph. The brute force approach is using backtracking which is $O(n!)$. Is there any better solution to this ...

### DFS and BFS Time and Space complexities of 'Number of islands' on Leetcode

1 answers, 12 views algorithms graphs asymptotics
Here is the question description. The first 2 suggested solutions involve DFS and BFS. This question refers to the 1st two approaches: DFS and BFS. Apparently, the grid can be viewed as a graph. I ...

### Proving GCD algorithm terminates

2 answers, 41 views algorithms algorithm-analysis
I'm reading this article on a GCD algorithm described by Dijkstra: https://www.cs.utexas.edu/users/EWD/transcriptions/EWD03xx/EWD316.4.html I'm looking at program 1. In particular I'm trying to ...

### 1 Undirected graph find minimal wight sum so every cycle has at least one weighted edge included

1 answers, 47 views algorithms graphs
I am given weighted undirected and non-planar graph G=(V,E). I don't understand much about complex graph and how to work with them. So any tips will help. For example like this I don't know how to ...

### Time complexity of travelling salesman problem

1 answers, 38 views algorithms graphs

### Store array of sequential intervals

1 answers, 39 views algorithms data-structures
I need to store a list of sequential intervals. So for example I would to say:{0-5} = a{6} = b...

### 13 Will this program terminate for every Integer?

3 answers, 3.554 views algorithms recursion pseudocode
In a Part Test for GATE Preparation there was a question :f(n): if n is even: f(n) = n/2 else f(n) = f(f(n-1))I answered "It will terminate for all ...

### 2 Efficient method to compute weighted Jaccard similarity?

I'm looking for pointers for high-performance calculation of the weighted Jaccard similarity between two sparse count vectors. I would like to speed up my code by at least 5x. I have a database of ...

### 6 Proof: “If the list is then k-sorted for some smaller integer k, then the list remains h-sorted”

Shellsort is a generalization of insertion sort that allows the exchange of items that are far apart. The idea is to arrange the list of elements so that, starting anywhere, considering every hth ...

### Is there an $O(n^2)$ or $O(n^3)$ time algorithm to check if a number is a sum of $k$ elements of sorted array?

Let $A$ be a sorted array of $n$ positive integers (sorted in non-decreasing order, that is there can be equal consecutive elements). Can we check whether some positive integer $x$ is a sum of $k$ ...

### Is there an example of Dinitz's algorithm running with the worst time complexity?

I'm trying to find a network, where Dinic's algorithm makes |V|^2*|E| steps. Clearly it cannot be a network with 3 or less vertices, but I am not able to come up ...

### 3 Minimal number of nodes needed to connect a disconnected graph

Given a graph $G = (V, E)$ with $V = U \uplus T$ (let's say the vertices are labelled $U$ or $T$), I am looking for the smallest set $U' \subseteq U$ such that $G[U' \cup T]$ is connected. If we ...

### Steiner tree problem with the known optimal subset of Steiner vertices in approximation algorithms

1 answers, 108 views algorithms approximation
I want to prove that The hardness of the Steiner tree problem lies in determining the optimal subset of Steiner vertices that need to be included in the tree and I need to Show this by proving that if ...

### 1 Find a path that contains specific nodes without back and forward edges

I have a directed graph and and a set of nodes(set = [1,2,5,9,24...]). I want to find a path that contains all the set of nodes and this path dont contain back edges(cycles) and forward edges. For ...

### 2 Given an array of integers and a value k, find the length of the longest subarray with max-gap no more than k

I'm struggling with this problem: you are given an array $A$ of $n$ integers and a number $k \in \mathbb{N} : k \neq 0$. The problem asks to find an algorithm that runs in $\Theta(n)$ that returns the ...

### 2 Water Jug Problem

1 answers, 54 views algorithms recursion
I was reading an article on Water Jug Problem. The problem is -You are given a m litre jug and a n litre jug where 0 < m < n. Both the jugs are initially empty. The jugs don’t have markings to ...

### A path modification problem in directed graphs

1 answers, 121 views algorithms graphs routing social-networks
We start with a given finite directed graph. It could represent transitive relations such as: data transfer paths in social networks, transportation connections, etc. Let us use the notation A->B ...

### 4 Maximizing the sum of selected elements in a matrix

I’m trying to find an efficient algorithm for the following optimization problem: Given a matrix $A$ with elements $a_{ij}$ and dimension $k$, select exactly $n$ elements from $A$ ($n<k$) such ...

### Algorithm to find best combination of datasources (Quality and price)

I have some sources of data, and each one of this sources have a cost per request. I know wich data attributes each one of these sources have, and what are the best sources for each attribute. Given ...

### Clone an Undirected Graph

0 answers, 20 views algorithms graphs
I was reading an article on Clone an Undirected Graph, It says I have do do bfs and have to keep track of visited/cloned nodes. I have another approach- I will initialize an empty adjacency list and ...

### Count nodes within K-distance from all nodes in a set

1 answers, 23 views algorithms graphs
The problem is - Given an undirected tree with some marked nodes in a set and a positive number K. We need to print the count of all such nodes which have distance from all marked nodes less than K. ...

### Find the smallest binary digit multiple of given number

1 answers, 32 views algorithms graphs
I was reading an article on Find the smallest binary digit multiple of given number. The problem is - We are given a decimal number N, we need to find the smallest multiple of N which is binary digit ...

### 1 How can I assign cooks to customers?

1 answers, 229 views algorithms assignment-problem
I haven't done much algorithm writing till now. I have a specific scenario and I am wondering which approach shall I take. Scenario: Let us suppose that we have 4 guys (A,B,C,D) We want to ...

### Troubles understanding this Interval Scheduling question

Can someone explain how to prove what this question is asking? I'm terrible at proofs and the fact that I don't even understand the hint is very troubling. This is a homework question. Consider the ...

### Complexity of Longest Palindromic Subsequence Algorithm

I'm trying to find the longest palindromic subsequence for any string and I've tried two approaches: Recursive Algoritm Dynamic Programming Dynamic programming should be the better option in this ...

### Which one is more suitable for designing an algorithm that produces all the paths between two vertices in a directed graph? [on hold]

Which one is more suitable for designing an algorithm that produces all the paths between two vertices in a directed graph? ...

### 6 Efficiently finding the maximum pairwise GCD of a set of natural numbers

2 answers, 4.707 views algorithms number-theory
Consider the following problem: Let $S = \{ s_1, s_2, ... s_n \}$ be a finite subset of the natural numbers. Let $G = \{$ $gcd(s_i, s_j)$ | $s_i, s_j \in S,$ $s_i \neq s_j \}$ where $gcd(x,y)$ is ...

### 1 Is the outer loop in typical bubble sort algorithm precise?

1 answers, 47 views algorithms sorting
I analized the bubble sort algorithm and I cannot see why they "implemented this way". I wrote down the results as the two loops performed their works and, with my small testing arrays, the outer ...

### Fibonacci Heap / Binomial Heap - Decrease Key

1 answers, 169 views algorithms data-structures heaps
I've been implementing a Fibonacci Heap in C this past week and today I just hit a mental roadblock that I can't figure out. Decrease Key is a function that almost all min heaps have (vice versa with ...

### Time Complexity - Reducing Square Matrix to Diagonal Matrix (using Gaussian Row Elimination)

0 answers, 23 views algorithms complexity-theory
Given: A Square Matrix where each entry is an integer (either positive or negative). The magnitude of each integer entry is at most $m$ bits. The size of the Square matrix is $nXn$. Objective: Reduce ...

### 1 Online set filling with redistributions

Edited: Suppose we have 4 sets $A, B, C, D$ which can can hold a maximum of two elements, each. Now, elements ($E_i$) arrive serially with properties such as: ...

### By what criteria is the base value selected in Rabin Karp algorithm?

2 answers, 21 views algorithms string-matching
In the Rabin Karp algorithm the rolling hash is calculated as follows:H1= c1*a^k-1 + c2*a^k-2+c3*a^k-3+…+ck*a^0where a is a ...

### 1 Cellular automata for 2d cloud simulation

0 answers, 18 views algorithms cellular-automata
I want to build a cellular automata that simulates a behaviour that looks like clouds, that is: infinite and random cycles, pieces can gather or break apart, just like the image below: My question is:...

### 4 Is the isometric path cover problem NP-complete?

2 answers, 54 views algorithms graphs np-complete