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

How does this algorithm calculate the fractional part of a binary logarithm?

I'm trying to understand a binary logarithm function written by somebody else: ...
1
vote
1answer
28 views

How to determine the max offset of a value, given the range, step size and amount of steps

Given The starting and the end values of X The maximum step (maximum delta) Exact amount of steps I need to determinte the maximum and the minimum possible values that X could become during this ...
2
votes
1answer
98 views

Finding the maximum s-t flow of a graph $G$ in $O(n+m)$ time when $G-t$ is an arborescence

You are given an directed graph $G = (V , E)$ with positive edge capacities, a source vertex $s \in V$, and a target vertex $t \in V \setminus \{s\}$. $G$ is guaranteed to have the following ...
1
vote
1answer
56 views

Divide and conquer algorithm for a gas station problem

I never heard about this variation of the gas station problem. The statement is as follows: There is just one road connecting the n+1 cities c0, …, cn consecutively. You want to go from c0 to cn ...
2
votes
2answers
25 views

Need an adaptive algorithm for participant subgroups that balances repeated pairings

I want to build a utility that helps manage small groups of participants. It is an acting class setting. For each exercise, the facilitator will usually have some number of participants get up to do a ...
2
votes
1answer
19 views

Unification with a list of terms

The problem: we have a list of terms $[t_1, ..., t_n]$ , and a term $t$, and we want to find which of the terms in the list can be unified with $t$. Obviously we can iterate through the list and check ...
2
votes
1answer
52 views

A data structure that supports efficient insertion of arbitrary integers, value lookup, and removal of all integers smaller than a given threshold?

I'm looking for a data structure that supports efficient: Insertion of arbitrary integers. Value lookup (given a particular value needle, return true if it's ...
2
votes
1answer
33 views

k-center problem: proof for Gon algorithm gives a 2-approximation

The $k$-center problem is where we a given a graph $G(V,E)$, an integer $k$, a distance metric $d$ and we want to find a subset $C\subseteq V$ (such that $|C|\leq k$) which minimizes the following ...
1
vote
1answer
40 views

Finding closest line segment intersecting rays

Assuming we have a fixed set of line segments $S$ such that any two segments are either disjoint or have a common endpoint. A query would look like this; given a query point $q$ shoot 4 rays from $q$ (...
1
vote
1answer
64 views

Algorithm for seeing if there exists a min s-t cut (A,B) in a flow network with node u in A and node v in B

We are given a flow network and two nodes $u$ and $v$. We want to create an algorithm that tells us whether or not there is a minimum s-t cut so that $u$ belongs to the same side of the cut as the ...
0
votes
1answer
34 views

Linear Discriminant Method as Pre-processing for inputs going into a Neural Network?

As the title suggests, I am curious whether Linear Discriminant Method can be performed on a dataset as pre-processing before putting the reduced-dimensional data as input for a neural network for ...
0
votes
0answers
43 views

Bipartite matching using Dinitz's Algorithm

How can we show the size of a matching found using Dinitz's algorithm in terms of the size of the largest matching? So, for example, can we prove that there is some small constant $a$ for which $M \ge ...
2
votes
1answer
116 views

Transitions between lexicographical orders

I have six characters: (,),[,],{,}. They are stored lexicographically: '(' < ')' < '[' < ']' < '{' < '}'. So I can store all balanced parenthesis sequences of length $n$ ...
1
vote
1answer
103 views

Constructing 2-Universal Families

Let H be a class of all functions, mapping M possible keys to N integers. Is it true that H is a 2-universal family? Is it a good idea to use H in applications? I don't even know where and how to ...
0
votes
2answers
46 views

Special case of subset sum in $O(n)$

A sorted array $A[1..n]$ is given. Each element of $A[i]\in \mathbb{N}$, and for each $A[i],A[j]$ we have $A[i]+A[j]\leq n$. Find two elements $A[i], A[j]$ such that $(A[i]-i)+(A[j]-j)=0$. Give a ...
0
votes
1answer
29 views

Prove that in a tree where each node has 0 or 2 children, number of nodes with 0 child is one more than the number of nodes with 2 children

How to prove In a tree where every node has either $0$ or $2$ children, the number of nodes with $0$ child is $1$ more than the number of nodes with $2$ children.
1
vote
1answer
25 views

How to use Runge–Kutta methods in a second order ODE

Consider a second order equation $F=ma=m\ddot{x}$. In the language of Euler's method $\ddot{x}(t+dt)=F(t,x(t),\dot x(t))$ $\dot{x}(t+dt)=\dot x(t)+\ddot x(t)dt$ $x(t+dt)=x(t)+\dot x(t)dt$ Basically, ...
1
vote
0answers
18 views

Finding the two edge-disjoint paths, minimizing the sum of their lengths

Given an undirected graph and a start and end node, I am trying to find two edge-disjoint paths such that the sum of their lengths is minimized. In particular, each path must start at the start node, ...
0
votes
0answers
12 views

Scheduling Repeating, Flexible Intervals with Restrictions on Overlap

I work in 52:17 work:break intervals, as there's some evidence showing it's an effective way to structure the day. However, meetings or planned breaks often require shifting that schedule, moving, ...
1
vote
1answer
48 views

Finding the two node-disjoint paths, minimizing the sum of their lengths

Given an undirected graph and a start and end node, I am trying to find two node-disjoint paths such that the sum of their lengths is minimized. In particular, each path must start at the start node, ...
5
votes
1answer
78 views

what algorithm is used to calculate the exponential function $e^x$?

I am using Matlab daily. But I just realized that I even do not know what algorithm Matlab is using for calculating the exponential function $e^x$. The power series expansion is obviously not ...
0
votes
0answers
36 views

Algorithm question: Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1

Algorithm question: Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1. Example 1: Input: [0,1] Output: 2 Explanation: [0, 1] is the longest ...
0
votes
0answers
35 views

Array algorithm to fill an array in equal but alternate binary choices as close as possible given an already fixed configuration

Stuck on a problem with my roommate and can't seem to find any parallels to this. The problem is simple to understand: you have two possible binary options: T or F. You are given an array which ...
-1
votes
1answer
24 views

Find best value for size of the table in hashing

Given a set of keys $\{i^2|0\leq i\leq 100\}$, and a hash table such that collision resolve by chaining. Our hash function is $ k \mod m$ . What is option is best for $m$ to decrease our search for ...
0
votes
0answers
41 views

Finding height of binary search tree

Suppose given a binary search tree $T$ with $n$ nodes with depth $h$. We did $n$ times search with cost $c_i$ for search $i^{th}$ search on $T$ ,and $\sum_{i=1}^{n}c_i=O(n\log n)$. what we can say ...
2
votes
2answers
53 views

Probabilistic adaptive algorithm that can explore only $k$ bits of input can’t distinguish $k$-independent distribution from uniform

Definition: Distribution $D$ on $\{0,1\}^n$ is called $k$-independent if for every random variable $X$ with distribution $D$ and for all $i_1, \dots, i_k \in \{1,2,\dots,n\}$ random variable $X_{i_1,\...
1
vote
1answer
22 views

How polynomial interpolation of polynomial multiplication algorithm works?

I'm trying to apply the following algorithm from DPV's textbook to an example to see how it works. First, the algorithm is as following: Algorithm [DPV, p. 60] Input: Coefficients of two polynomials. ...
0
votes
1answer
25 views

Search for specific element in sorted array

Given sorted array $A[1..n]$. We want to find an element such that $A[i]=3i+2$ in $O(\log n)$(binary search). I trying to relate to problem finding element in sorted array $A$ such that $A[i]=i$, ...
0
votes
0answers
38 views

A problem in proving with induction

According to asked question in this post. Suppose $T(n,k)=T(n-1,k-1)+T(n-1,k)+1$, now let $C(n,k)=T(n,k)+1$. As a result $C(n,k)=C(n-1,k-1)+C(n-1,k)$. I want to prove $C(n,k)=2\binom{n}{k}$, now on ...
-1
votes
1answer
27 views

Master theorm and epsilon value

I have been reading CLRS and came across a few examples of the Master theorem. I could not follow the reason that epsilon was chosen as 0.8 in the example from page 96 . Can I simply use the ...
0
votes
1answer
36 views

PCA applicability

I understand that PCA takes a data set with input size, with output labels, and reduces the inputs to a set of principal components size r, where r < n. My question is whether or not this can be ...
1
vote
1answer
28 views

How to group thousand of data points for each user

I have thousands of data points associated with users. So a single user can have 2000-10000 data points. These data points are identified by contiguous numbers (e.g. all numbers from 0 to 2000). Each ...
1
vote
1answer
59 views

Solving recurrence relation for running time of combination formula

I'm trying to solve the following Time complexity recurrence relation: $T(n,k)=T(n-1,k-1)+T(n-1,k)+1$ that come from following code: ...
0
votes
1answer
42 views

Check two balanced binary search trees that sub set of each other

Given two balanced binary search trees $T_1,T_2$. We want to check, are $T_1\subseteq T_1$ or not. $T_1$ have $n_1$ nodes, and $T_2$ have $n_2$ nodes. Instructor say it can be done in $O(n_1+n_2)$ ...
0
votes
0answers
45 views

Algo for cash investment in stocks

...
1
vote
1answer
58 views

Greedy algorithm for maintaining drugs

Given $n$ drugs such that each drug $d_i$ should maintain in interval $[c_i,h_i]$.We want to minimize number of containers to maintain medicines in compatible interval. My answer is as follows: I use ...
1
vote
2answers
45 views

How does Command Z work through computer commands?

How does Command Z work through computer commands? What is the step by step computer commands that complete the process?
1
vote
1answer
26 views

Consensus algorithm for imperfect annotators

I'll pose the question in the abstract first and then describe concretely what I'm trying to do. Suppose I have a set of 1000 000 multiple-choice questions and 10 oracles that can answer the questions....
1
vote
2answers
106 views

Sort an array that contain two sorted array in $O(n)$

Given an array $A[1..n]$. $A$ is mixed of two sorted arrays $B$ and $C$ of equal sizes, such that $B$ is in the ascending order and $C$ is in the descending order. Consider the following example: $B=[...
1
vote
0answers
10 views

About the paper Privacy-preserving in association rule mining using an improved discrete binary artificial bee colony

I don't understand two parts in this paper: The min notion on page 4 line 357 (equation 10d): I understand this as to find all the $M_{10}$, $M_{11}$, $M_{01}$ first and then try to minimize the ...
1
vote
0answers
30 views

Cover a surface with disks of various size

I'm trying to find a cover of a surface using disks of variable sizes. In the image, I want to cover the entire blue surface. The disks can go "out" of the blue surface and into the red part,...
4
votes
2answers
62 views

Why is tabulated hashing 3-wise independent but not 4-wise independent?

Tabulated hashing uses tables of random numbers to compute hash values. Suppose $|\mathcal{U}| = 2^w \times 2^w$ and $m = 2^l$, so that the items being hashed are pairs $(x,y)$ where $x$ and $y$ are $...
1
vote
1answer
31 views

Average case analysis by key comparisons of Max Sort

I'm having trouble approaching this average case analysis in terms of key comparisons. The pseudo-code is as follows: ...
0
votes
0answers
12 views

Could you explain this variant of the Preflow Push Algorithm to me?

I am having trouble to understand the FIFO-rule for the Preflow Push Algorithm. In class I learnt the the following version of the FIFO-rule: The active nodes are stored in a queue. Newly active ...
2
votes
1answer
29 views

Median of medians confusion — the “approximate” median part

I'm struggling with the median of medians algorithm, and I think it's perhaps more of a semantics thing rather than a technical thing. I've always thought the median of medians algorithm as finding an ...
1
vote
1answer
68 views

Information-theoretic lower bound for succinct string dictionary of the Unicode Name property

Background The literature on succinct data structures refers often to the “information-theoretic lower bound” of encoding data, i.e., the minimum number of bits needed to store the data – a concept ...
0
votes
1answer
29 views

If possible, use binary search to find an element in sorted array

Given sorted array $A[1..n]$, we want to find an element such that, $A[i]=i^2$,Can we use binary search to find such a element? My Attempt: initially, I read this link, but I can't understand the ...
0
votes
1answer
18 views

“Batch” partial sorting algorithm

I'm looking for an existing algorithm that would ensure that the first k elements after sorting are the top k elements but not ...
1
vote
0answers
17 views

How are virtual nodes placed / calculated to implement consistent hashing

I am reading about consistent hashing for system design and I understand the application of consistent hashing and the use of virtual nodes. I want to understand how to calculate the optimum number of ...
2
votes
1answer
12 views

Scheduling algorithm for a student's study times given assignments, expected time, due dates, and class times

I would like to create an algorithm that advises a student when they should work on certain assignments given the expected time each assignment will take, and the due date of each assignment. Say that ...

1
3 4
5
6 7
192