Questions tagged [ds.algorithms]

Questions regarding well-defined instructions for completing a task, and relevant analysis in terms of time/memory/etc.

Filter by
Sorted by
Tagged with
-1
votes
1answer
382 views

linear programming (is this doable?) [closed]

I have the LP formulation at the link below for the following problem: my lp formulation Minimize: $\sum_{i=1}^{N_1} \sum_{j=1}^{N_2} x_{ij}$ Subject to: $\sum_{i=m}^{m+a-1} \sum_{j=n}^{n+b-1} x_{...
-1
votes
0answers
33 views

Application of a Poisson inequality in the networks

I know that there are many works where Poisson (https://en.wikipedia.org/wiki/Poisson_distribution) processes are used in the construction of networks models. I am seeking for a model which can be ...
-1
votes
0answers
47 views

What's with input sparsity algorithm?

Recent years a number of Input Sparsity algorithms have emerged in numerical linear algebra community, most in regression and low-rank subspace approximation problem. An input sparsity algorithm $ALG$ ...
-1
votes
1answer
91 views

Required sample size to hit certain subset of a ground set

Suppose $X$ is a set of $n$ points in $\mathbb{R}^d$ and $N_1,\cdots,N_k$ are k disjoint (unknown)subsets of $X$. There is a probability distribution $\phi$ on $X$ defined as $\phi(p) = \frac{\lvert\...
-1
votes
1answer
29 views

Algorithm in logarithmic time that finds a number with the help of a subarray that is not in the array

The question is as follows. Given: A sorted array A of n integers where A[n − 1] − A[0] ≥ n. Asked: Give an algorithm and the invariant of the algorithm that finds a number between A[0] and A[n - 1] ...
-1
votes
1answer
1k views

Time complexity analysis of random forest and k-means?

I am working with random forest for a supervised classification problem, and I am using the k-means clustering algorithm to split the data at each node, where $n$ is the number of points, $K$ is ...
-2
votes
1answer
497 views

Divide and conquer algorithm to sort a list where each element is root(n) away from its sorted position

I'm stuck on a question and I just need a hint/point in the general direction (not asking for the answer) The question asks for the details of a divide and conquer algorithm that given a list that is ...
-2
votes
2answers
706 views

At last P != NP or not [duplicate]

Possible Duplicate: Is the recent proof that P != NP correct? some weeks ago I heard a news that some one proof that P != NP (link1 - link2) andsome days later I heard that he was wrong (I can't ...
-2
votes
1answer
123 views

Deciding CL-IS on graph efficiently

Given an arbitrary graph $G$, could there be a polynomial time algorithm to tell if it has a larger size clique $(\omega(G))$ or larger independence number$(\alpha(G))$?
-2
votes
1answer
332 views

Iterated Prisoner's Dilemma Algorithms

While reading a post on Scott Aaronson's blog about Eigenmorality, I ran across the idea of the iterated prisoner's dilemma tournament. I've studied some TCS on my own, but had never really thought ...
-2
votes
1answer
555 views

Fortunes Algorithm - Beach Line Data Structure [closed]

This is a cross-post from stackoverflow. I did not recieve a good answer, I guess it is because the question is more theoretical. I have to implement Fortunes algorithm for constructing Voronoi ...
-2
votes
1answer
97 views

Proving hardness of approximation with reduction in terms of 1/$\epsilon$

I have a reduction that proves that a problem is NP-hard to approximate to a factor $1 + \epsilon$ for any $0 < \epsilon < 1$. The reduction is polynomial in $n$ (the size of the instance of the ...
-2
votes
1answer
153 views

Is there a mathematical definition of algorithm? [closed]

A friend of mine usually talks to me about Church's thesis. Some days ago I found a proof and talked about it to him. He said that "it's possible to prove the thesis using an arbitrary definition of ...
-2
votes
1answer
609 views

How does this computational method work?

The last computational method example Knuth gives in 1.1 of Vol. 1 of 'The Art of Computer Programming' is defined by the following: Let $A$ be a finite set of letters Let $A^*$ be the set of all ...
-2
votes
1answer
285 views

Sorting : proof for lower bound of Sorting [closed]

I have read the proof of lower bound of Sorting Algorithm that use comparison to know input is NlogN. In this paper, the author use decision tree for this proof. Everything on this proof I have ...
-2
votes
1answer
117 views

An efficient algorithm for maximizing gain by choosing from a set of options

(I hope this is on-topic for this site -- mods feel free to send this to another stack exchange if not ) I've got an optimization problem where I need to choose from one of several options to ...
-2
votes
1answer
161 views

Is it possible to sort by only knowing the sign of pairwise sums?

I am currently thinking of how much structure one actually needs in order to be able to sort things at all. All comparison-based algorithms need a direct comparability, but are we able to remove this ...
-2
votes
1answer
500 views

Algorithm to determine if given algorithm runs in polynomial time [duplicate]

In general, the undecidability of the halting problem prohibits the general determination of an algorithm's complexity. However, I can see no reason why the halting problem prohibits one from deciding ...
-2
votes
1answer
231 views

3-Hitting-Set - maximum flow algorithm [closed]

so i'm currently learning for an exam and got in an exercise the following question (a loose translation): Find an Algorithm that finds the smallest U' ⊆ U that is a solution the 3 HITTING SET ...
-2
votes
2answers
302 views

An algorithm that determines if regular language accepts all string of its alphabet [closed]

Let $L$ be a regular language with the alphabet $\Sigma$. I'm trying to find an algorithm to tell whether $L=\Sigma^{*}$, whether $L$ accepts all strings in its alphabet. I think this algorithm uses ...
-2
votes
1answer
193 views

What are some natural problems that we can quickly find a solution to using massive parallelism but not a canonical solution?

For many problems, more than one output is acceptable. For instance, the problem of finding an assignment that satisfies a boolean formula. If randomness buys us something then it could be that it ...
-2
votes
1answer
271 views

Find all items which are subsets of an item

I have a problem that I think should have been studied. I am looking for algorithms for it. Each item is a set of key-value pairs. Let $x$ be an item and $F$ be a set of items. Each key and each ...
-3
votes
1answer
272 views

How many steps does this recurrence take to get to 2 (or 1)?

$T(2) = T(1) = 1$ $T(n) = T(\frac{n}{\log n}) + \Theta(1)$ Basically, I wanted to know how many steps before the recursion stops? I tried various approaches, but am not getting anywhere. I know for ...
-3
votes
1answer
180 views

Is finding a solution harder than verifying a solution? [closed]

Is there any known problem in Comp science where determinisitically finding a "non-trivial" solution to that problem is asymptotically easier than verifying a solution?
-3
votes
1answer
118 views

What is wrong with this procedure to convert quadratic programming to convex quadratic programming?

Consider the feasibility quadratic program with constraint $$\sum_{i=1}^nc_{i1}x_{i}\leq \ell_1$$ $$\vdots$$ $$\sum_{i=1}^nc_{it}x_{i}\leq \ell_t$$ $$\sum_{i,j=1}^na_{ij}x_{i}x_{j}+\sum_{i=1}^nb_{i}x_{...
-3
votes
1answer
90 views

Choosing 2*n values while evaluating Fast Fourier Transform [closed]

I am going through the Fast Fourier Transform technique mentioned in the Algorithm Design Book by John Kleinberg and Eva Tardos. I have understood why we need to interpret two ...
-3
votes
1answer
93 views

Is this NP-Hard or does a known optimal polynomial time solution exist? [closed]

Suppose we have 10 items, each of a different cost Items: {1,2,3,4,5,6,7,8,9,10} Cost: {2,5,1,1,5,1,1,3,4,10} and 3 customers {A,B,C}. Each customer has a requirement for a set ...
-3
votes
1answer
253 views

Isn't weakly universal hashing even a stronger than truly random? [closed]

So as far as I know the weakly universal hashing is defined as: for any $x, y \subset U, Pr(h(x) = h(y)) \le \frac{1}{m}$ where m is a smaller number than the cardinality of $U$, and h are chosen ...
-3
votes
1answer
98 views

what problem is this? [closed]

I have this instance: Let's say I have two (could be more) friends, one weighing 200 pounds and another weighing 100 pounds; I won a box with 30 chocolates in a contest and I want to divide among ...
-3
votes
1answer
148 views

Find subset of configurations which produces maximum result

Given a set of $n$ configurations $C_1 , C_2 ... C_n$ and a function $f$ such that $f(C_i)$ produces a set of $m$ results $R_1, R_2 ... R_m$ where $R_j=\{0,1\}$ We only care about the $\Sigma f(C_i)$ ...
-3
votes
1answer
861 views

Weighted matching algorithm for minimizing max weight

Consider the following matching problem: Input: a complete weighted bipartite graph with $n+m$ vertices, given by $n$, $m$, and $w_{i}$ a permutation of $[m]$ for each $i \in [n]$. Output: a ...
-3
votes
1answer
50 views

Finding a non-negative solution to an integer system of linear equations

Let $A$ be an $n \times m$ integer matrix and consider the system of equations $Ax = b$ where $b$ is an integer vector. I want to find a solution $x$, assuming one exists, such that the components of $...
-3
votes
1answer
155 views

Continous work distribution algorithm with failover

Imagine there's a system where there's N workers and M units of work, for example, N ≤ 64, M = 256. Is there an algorithm that ...
-4
votes
1answer
236 views

Sweeping a Polygon With Holes

I am looking for a algorithm or an idea for a algorithm for triangulation a polygon with holes (one outer polygon P containing several polygonal holes) via plane sweep. The diagonals should ...
-4
votes
2answers
347 views

Examples of uncommon problems with different asymptotic costs?

I've being studying some topics of Discrete Mathematics, and I found only a few examples of problems with uncommon asymptotic costs, like Θ(sqrt(n)) or Θ(log(n)) beyond the obvious ones (binary search,...
-4
votes
1answer
111 views

How to say “select the largest” when there can be more than one [closed]

Many algorithms include a step such as "select the largest number from a given numeric array", or "select the leftmost point from a given set of points", etc. In many cases, it is possible that the ...
-4
votes
0answers
29 views

Linear Time Sorting Using Density Towers

I was wondering if it was possible to write a linear-time sorting algorithm using a density tower. This is completely theoretical but essentially what I am thinking about is injecting masses into a ...
-4
votes
2answers
91 views

Is it possible to have a sorting algorithm that computes faster than QuickSort? [closed]

Given an unsorted array, QuickSort has to touch each source element it is trying to sort multiple times before it declares an array as sorted. (notice how many times the 2 is touched [circled in red ...
-5
votes
1answer
311 views

Solving a system of linear inequations

Consider the following system of inequalities: $Ax=b$; $x\geq 0$; A is a $m\times n$ (non-square) and sparse matrix in which some part of entries are rational. a) How feasibility of this system can ...
-5
votes
2answers
969 views

Proof of correctness of in-place Quick sort

I have found proof of correctness of Quick sort (not in-place version), Please refer me a proof of correctness of in-place Quick sort, or provide proof here is very appropriated. a typical ...
-5
votes
1answer
985 views

Polynomial time algorithm to solve the TSP on an m by n solid grid

Is there a polynomial algorithm to solve TSP (or Ham Cycle) on an m by n solid grid graph whose points are at unit distance apart? I've heard about Umans and Lenhart research paper but reading such ...
-5
votes
1answer
146 views

Do irrational number contain infinate/every patterns of sequences? [closed]

I guess the question is "does an 'infinite' number of patterns imply 'every' number of patterns?" For instance, if you could quickly calculate the decimal sequence of π, could you not (in ...
-5
votes
0answers
24 views

Is machine learning a thermodynamic cooling process? [closed]

Is there evidence or proof that machine learning is a thermodynamic cooling process and can we interpret machine learning in an information theoretic manner? What is the interpretation of stochastic ...
-6
votes
1answer
2k views

Path of length k in graph [closed]

I was reading NP complete theory just thought. "Is there any path of length k in given graph" Is it polynomial time algorithm?
-8
votes
1answer
581 views

how to swap the value of two variables without an auxilary (helping) variable [closed]

how to swap the value of two variables without an auxilary (helping) variable ? swap(int *x,int *y) { int h = *x; *x = *y; *y = h; } how can we do it without introducing h?
-11
votes
2answers
3k views

Are sorting algorithms approaching linear time? [closed]

I see some algorithms can do sorting in O(nloglogn) time. Is it reasonable to assume that as research progresses, more and more will be done to logarithm the extra time e.g. next research will produce ...

1
29 30 31 32
33