Questions about the science and art of determining properties of algorithms, often including correctness, runtime and space usage.

learn more… | top users | synonyms

0
votes
0answers
29 views
0
votes
0answers
19 views

How can the Gabow scaling algorithm compute all δ(s,v) values in O(E) time?

I was reading about the Gabow scaling algorithm in CLRS. It says that if for all vertex $v$ we've $\delta(s,v)\leq |E|$ then we can compute all $\delta(s,v)$ values in $O(E)$ time where each edge ...
-1
votes
0answers
30 views

ice (sleet, glaze ice) [on hold]

I must to forecast an ice (sleet, glaze ice). I have base of data with parameters to predict, but this data base have not some parametres. In one day I have three parametres in other day I have four ...
-2
votes
1answer
29 views

Asking for help with this Therac 25 bugged code. I don't understand the explanation

Therac 25 is a radiation therapy machine that lead to 3 deaths and 3 injuries in 1980s. That's the worst accidents in history which are caused by software bugs. In 1993, Leveson and Turner did a ...
0
votes
1answer
90 views

What is the runtime of the following code? [duplicate]

Can you explain to me how you get the Big O notation for the runtime of the following snippet of code? ...
-1
votes
0answers
19 views

About a program that might help the Windows 7 Operating system [closed]

I use the Windows 7 Home Edition and one BIG weakness seems to be the Windows Installer or the M.S.I. Installer. 1,000,001 things seem to be able to go wrong with it and I'm not a programmer or a ...
1
vote
0answers
48 views

Influence of edge number and priority-queue implementation on the runtime of Dijkstra

When we try to find the shortest path of a directed weighted graph using Dijkstra’s algorithm, is there a relation between the number of edges/vertices of the graph and the different implementations ...
0
votes
0answers
61 views

stuck on proving the optimality of a greedy algorithm [closed]

I'm Ph.D. student doing research in wireless networks. My past projects are more oriented to systems than theory. For my current project, I devised a greedy algorithm for an optimization problem. ...
0
votes
0answers
38 views

Ranking in complete binary trees

I have a binary tree, the node has two subtrees, every node except the the leaves, has 2 children and all the leaves are at the same level. I want to know the worst and best case complexities when I ...
0
votes
0answers
24 views

analyzing moving pseudorandom sieve algorithm

the following is a rough simpification or "toy" version/ abstraction/ model (but still quite nontrivial) for/ inspired by a famous open math problem (which for now will remain nameless & may be ...
0
votes
1answer
38 views

Maximum value a variable can hold without documentation [closed]

Suppose we work with some particular programming language (like C++) on some particular computer. Furthermore, we want to know which values are minimum and maximum for some particular numeric data ...
6
votes
1answer
62 views

Etymology of time and space “complexity”

The word choice of "complexity" in analysis of algorithms to describe temporal and spatial resource requirements has always struct me as an odd one. These are certainly useful and meaningful concepts. ...
0
votes
1answer
17 views

Understanding when to count key comparisons

I understand that for something like Linear search, this would be the key comparison: if(itemToFind == a[i]) return i; If I put this method into another ...
0
votes
1answer
26 views

Comparing Big O Complexity [duplicate]

I'm trying to compare two functions, such as f(n)=n^n and g(n)=n^10^10. I'm unsure if f(n) is O(g(n)) or vise-vera where g(n) is O(f(n)). From my understanding, n^n can be worse than n! and although ...
0
votes
2answers
71 views

How to show that this algorithm for evaluating polynomials works?

I'm having trouble showing how to solve this problem in particular the part where it asks "To Show that the following pseudo-code fragment finds the value of the polynomial..." How do I exactly show ...
3
votes
0answers
18 views

Pruned FFT runtime

Pruned fast Fourier transforms compute only a specified subset of the result indices in faster time, although sometimes with a slower implementation constant (because FFT is generally so optimized). ...
0
votes
1answer
42 views

Showing that tournament sort requrires O(n log n) comparisons

I wish I could think of a better way to word my question. Maybe some one here could offer s suggestion for that, as well. On to my question. Before I do, this is a class question that has been asked, ...
2
votes
1answer
35 views

Why is Ibarra Kim for 0/1 knapsack an fully polynomial time approximation scheme (FPTAS)?

According to one of my CS lectures, there is an fully polynomial time approximation scheme for the 0/1 Knapsack problem. A first version was developed by Ibarra and Kim, but there are several improved ...
27
votes
3answers
5k views

Why is binary search faster than ternary search?

Searching an array of $N$ elements using binary search takes, in the worst case $\log_2 N$ iterations because, at each step we trim half of our search space. If, instead, we used 'ternary search', ...
1
vote
1answer
40 views

What Can We Say Complexity of Solving the Weighted Pool Ball Problem with a Variable Scale?

Background: The pool ball weighing problem is a classic CS question thrown at students, typically to demonstrate a binary search (alternative to ripping phonebooks in half). Pool Ball Problem: Given ...
-1
votes
1answer
30 views

Proving number of calls made in cut-rod algorithm [duplicate]

I was reading dynamic programming chapter from famous book Introduction To Algorithm In rod cutting problem it gives simple algorithm as follows: ...
1
vote
1answer
66 views

Creating a binomial heap from an array in Θ(n) time

I'm studying binomial heaps. A book tells me that insertion of a node to a binomial heap take $\Theta(\log n)$ time. So given an array of $n$ elements it would take $\Theta(n \log n)$ time to convert ...
41
votes
11answers
5k views

How to fool the “try some test cases” heuristic: Algorithms that appear correct, but are actually incorrect

To try to test whether an algorithm for some problem is correct, the usual starting point is to try running the algorithm by hand on a number of simple test cases -- try it on a few example problem ...
-2
votes
0answers
30 views

Writing recurrencies for run time? [duplicate]

Given a function; derp( x, n ) if( n == 0 ) return 1; if( n % 2 == 0 ) return derp( x^2, n/2 ); return x * derp( x^2, (n - 1) / 2); a) I ...
-3
votes
1answer
56 views

Probabilty that quicksort partition creates an imbalanced partition

I have come across this question: Let 0<α<.5 be some constant (independent of the input array length n). Recall the Partition subroutine employed by the QuickSort algorithm, as explained in ...
-1
votes
1answer
55 views

Quick Sort Algorithm When Partition is Constant Time

I ran into a question about Quick Sort Algorithm. Suppose in Quick Sort, Partition procedure take C times, (need constant time). if we use random data as input, what is the order (time complexity) of ...
0
votes
0answers
20 views

Programming and evaluating sorting algorithms based on its complexity [duplicate]

I need to program and evaluate two sorting algorithms: insertion sort and merge sort I know that the complexity of insertion sort is O(n^2) and for the merge sort is O(n·log n) In this case I have a ...
0
votes
0answers
19 views

How to conduct time complexity analysis for an implemented algorithm [duplicate]

Main task In my bachelor degree's thesis I've developed an algorithm for recommender systems which uses personalized PageRank with some particular features as nodes. In the recommender systems' ...
1
vote
2answers
44 views

Why comparison is dominant time consumption for comparison-based sorting algorithms? [duplicate]

Comparison-based sorting algorithms does a number of different operations to accomplish the sorting, why comparisons are the dominant time consumption? While I understand the standard analyses of ...
0
votes
1answer
40 views

tightest upper bound on binary search tree insertion? [closed]

The upper bound on the runtime of binary search tree insertion algorithm is O(n) which is if it is not balanced What will be the tighter upper bound on this,will it become O(logn) I have read that ...
0
votes
0answers
10 views

How to calculate the complexity of Uniform Binary Search algorithm [duplicate]

I was studying the Uniform Binary Search algorithm authored by Donald Knuth which is an optimization of the classic Binary Search algorithm. Can someone explain the complexity analysis for Uniform ...
-1
votes
4answers
203 views

Proving Quicksort has a worst case of O(n²)

I am sorting the following list of numbers which is in descending order. I am using QuickSort to sort and it is known that the worst case running time of QuickSort is $O(n^2)$ ...
1
vote
1answer
86 views

Space complexity analysis of binary recursive sum algorithm

I was reading page 147 of Goodrich and Tamassia, Data Structures and Algorithms in Java, 3rd Ed. (Google books). It gives example of linear sum algorithm which uses linear recursion to calculate sum ...
-1
votes
1answer
73 views

How the below program is taking O(n!) time? [closed]

The complexity of the below program is given to be O(n!) ...
5
votes
2answers
78 views

Choosing error rates for probabilistic algorithms

Probabilistic algorithms often have a parameter that allows one to tune the error rate, typically by running the algorithm repeatedly. This often gives an error rate of something like $2^{-k}$ for $k$ ...
3
votes
0answers
30 views

Monograph or survey paper on smoothed analysis of algorithms

The paper by Spielman and Teng, Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time (JACM 51(3):385–463, 2004), won a Gödel award in 2008. Since then, has ...
1
vote
0answers
49 views

How come computer science books are so relaxed about specifying which set variables/values belong too? [closed]

How come computer science books are so relaxed about specifying which set variables/values belong too ? I've read several books on algorithms like CLRS's Introduction to Algorithms, Sedgewick's ...
0
votes
1answer
40 views

If x operations cost O(x) amortized then how much xy operations cost?

True or False? Say some data structure can perform $x$ operations in amortized $O(x)$ time. Then for a big enough $y$ it can perform $xy$ operations in worst case $O(xy)$ time. My attempt: $x$ ...
3
votes
1answer
114 views

How to sort using $\texttt{SQRTSORT}$ as a subroutine which sorts $\sqrt{n}$ of consecutive elements?

I am teaching myself algorithms with the online lecture notes by Jeff Erickson and fails to solve the following problem (Problem 21 of Lecture 1). (a) Describe an algorithm that sorts an input ...
4
votes
1answer
48 views

Optimal Algorithm for Finding Maximal Number of Colinear Points

Given a set of $n$ point in a plane, find the maximal number of colinear points (the points residing on the same straight line). The crudest algorithm is to compute the slope and intercept of each ...
3
votes
0answers
104 views

Complexity of a naive algorithm for finding the longest Fibonacci substring

Given two symbols $\text{a}$ and $\text{b}$, let's define the $k$-th Fibonacci string as follows: $$ F(k) = \begin{cases} \text{b} &\mbox{if } k = 0 \\ \text{a} &\mbox{if } k = 1 \\ F(k-1) ...
0
votes
2answers
96 views

Check if an array is a substring of another array

Given two sequences $A$ and $B$, we want to check if $A$ is a subsequence of $B$ where the elements of $A$ appear in $B$ consecutively and in the same order. Example 1. input: $A = (4 , 6 , -5), B ...
-1
votes
1answer
36 views

difference between multilayer perceptron and linear regression

What is the difference between multilayer perceptron and linear regression classifier. I am trying to learn a model with numerical attributes, and predict a numerical value. Thanks
1
vote
1answer
56 views

Understanding Property Testing with a toy example

I am newbie with this property testing and I am trying to understand it with a few examples. I first dealt with a toy example. I did not understand the first step of the test in the following slide. ...
0
votes
1answer
27 views

Hashing and number of comparisons [duplicate]

Say, I want to put N objects into a hash table. How do I figure out how big the size of the table needs to be to have K comparisons on average when the table is: half full? three quarters full? all ...
2
votes
2answers
114 views

Where does the lg(lg(N)) factor come from in Schönhage–Strassen's run time?

According to page 53 of Modern Computer Arithmetic (pdf), all of the steps in the Schönhage–Strassen Algorithm cost $O(N \cdot lg(N))$ except for the recursion step which ends up costing $O(N\cdot ...
7
votes
2answers
106 views

Why is the transform in Schönhage–Strassen's multiplication algorithm cheap?

The Schönhage–Strassen multiplication algorithm works by turning multiplications of size $N$ into many multiplications of size $lg(N)$ with a number-theoretic transform, and recursing. At least I ...
1
vote
1answer
36 views

Runtime analysis of sorting an array with known number of inversions

I'm having difficulties with analyzing the worst-case runtime of this following case: I'm given an array that has $n$ natural numbers. Out of all $\binom{n}{2} = \frac{n(n-1)}{2}$ possible pairs ...
3
votes
1answer
61 views

Computing the complement of a set

Suppose I have a set $A$ of elements in $\{1, \ldots, n\}$, given as an unordered list. I would like to compute the complement of $A$, i.e., I would like to produce an unordered list of entries in ...