The tag has no wiki summary.

learn more… | top users | synonyms

-2
votes
0answers
25 views

Find the number of increasing Sequence of length K

Let we are giving a Array we have to find the number of increasing sequence of length K. 1 2 3 1 1 For the first window of [1, 2, 3], there are 3 non-decreasing subranges so the answer is 3. For ...
0
votes
0answers
29 views

Algorithm for intersection of two convex polygons among set of m convex polygons in a plane

There are set of m convex polygons(p1, p2, p3…pm) in a plane. Pi contains ni number of vertices. All total n1+n2+…+nm=n vertices. Two convex polygons intersect if either their boundaries intersect or ...
4
votes
3answers
110 views

Algorithm Analysis: In practice, do coefficients of higher order terms matter?

Consider an^2 + bn + c. I understand that for large n, bn and c become insignificant. I also understand that for large n, the differences between 2n^2 and n^2 are pretty insignificant compared to the ...
4
votes
2answers
238 views

Loop runtime question

I had an exam today and I feel that I did pretty well, except I could not for the life of me figure out what appears to be an unbelievably simple question. We were asked to give theta notation run ...
0
votes
2answers
95 views

What's the professional name for the software planning diagrams, those with ellipses and rhombuses?

What's the official name for a diagram like this one, used to structure a conditional plan. The shapes of the objects are by convention ellipse for an action, rhombus for a question, rectangle for a ...
0
votes
0answers
16 views

A heuristic approach to Clique problem over undirected Graph

I'm trying to get all complete subgraph given a graph G. Needless to say it is an NP-problem complete: Clique_problem. I understand getting the full set is not possible in real time(since it'll take ...
1
vote
1answer
90 views

Check word density within a document

Here is the situation: I have a Document(d) and a set of keywords (Set<String> keywords). I like to check the density of each words from set keywords with d. I have few solution but not really ...
16
votes
5answers
4k views

Algorithms: How do I sum O(n) and O(nlog(n)) together?

I have the follow algorithm which finds duplicates and removes them: public static int numDuplicatesB(int[] arr) { Sort.mergesort(arr); int numDups = 0; for (int i = 1; i < arr.length; ...
2
votes
3answers
83 views

recalculation model for GUIs

I often come across this problem. Say to have a form with some controls: A B C = A + B D E = C * 2 ONLY IF D==TRUE F G = A - F The user fills A, then B. The system calculates C. The user fills D ...
0
votes
2answers
178 views

How are the tiles in WORDAMENT organized?

I'm trying to create a word game, just like WORDAMENT, in my spare time. In order to present a new round, I need to create a board with 16 letters organized in a 4*4 grid. Currently, I'm generating ...
1
vote
2answers
167 views

How to measure algorithm accuracy?

I have a few optimization algorithms (for finding function minimum) and I'd like to check how good they are. Suppose I build test cases and compare the actual results to theoretical ones. What ...
0
votes
0answers
85 views

Approach for packing 2D shapes while minimizing total enclosing area

Not sure on my tags for this question, but in short .... I need to solve a problem of packing industrial parts into crates while minimizing total containing area. These parts are motors, or pumps, ...
0
votes
2answers
116 views

How to avoid or minimise use of check/conditional statement in my scenario?

I have scenario, where I got stream and I need to check for some value. If I got any new value I have to store it in any of data structure. It seems very easy, I can place conditional statement ...
2
votes
1answer
147 views

Asymptotic running time of for-loops

I have this question which I need answered: What is the asymptotic running time for the following piece of code? if (N < 1000) for (int i = 0; i < N; i++) for (int j = 0; j < N; ...
1
vote
2answers
321 views

How to approach program design with respect to data strucutres and algorimths - is there an equivelant of the OO design process for d.s.'s + algs? [closed]

My applogies for probably the worst written body of text I have produced in my life and many thanks to those willing to plough through it all. I was (and still am) not able to clearly express what I ...
1
vote
1answer
86 views

Confusion in understanding the theorem on Amortization

I was reading a book on Algorithm Analysis by Micheal T Goodrich. I came across amortization technique and I got struck in understanding the proof of theorem. I am putting the theorem and the proof ...
0
votes
0answers
121 views

GSP Algorithm explanation

I've been trying to implement the GSC algorithm in C++, however I need help with clarifying the definition: http://en.wikipedia.org/wiki/GSP_Algorithm GSP Algorithm makes multiple database ...
0
votes
2answers
231 views

calculate complexity of LinkedHashSet

I have an ArrayList<LinkedHashSet<String>> setOfStrings for example this arraylist internally is composed like: positionX[hello,car,three,hotel,beach] positionY[.....] ... I want to ...
0
votes
0answers
98 views

Would Someone explain me this Random Walk Algorithm for Onion Routing?

The Algorithm below is written in pseudocode and for simplicity the storage of the actual route in the Data structure is not included. LengthFromSrc = 0; LengthFromDest = 0; TotalNumberHops = ...
0
votes
0answers
90 views

Algorithm / working approach to get a random list of data

I am working on a android schedule app but that isn't matter , the problem is a algorithm / methodology so you are welcome to just write the pusedo code to answer. The data is like this Place ...
2
votes
1answer
45 views

What is the order analysis of the following (using a list of primes)

I have the following program: Iterate x from 1 to N. Check to see if x is prime. If it is, add it to a list of primes. The way I check to see if it is prime is iterating through the current list ...
1
vote
2answers
270 views

Given two sorted array in ascending order with same length N, calculate the Kth min a[i]+b[j]. Time complexity O(N)

Given two sorted array in ascending order with same length N, calculate the Kth min a[i]+b[j]. Time complexity O(N). Another variant of the question goes like this: given a matrix with sorted rows, ...
0
votes
0answers
32 views

Readers Writers algorithm help - starvation and no starvation

I found this link, as an explanation of r/w problem - http://pages.cs.wisc.edu/~bart/537/lecturenotes/s7.html But, I'm having problems realizing is there any starvation present here and why? Also, if ...
0
votes
1answer
327 views

How to develop an algorithm for brute-forcing / backtracking?

As a beginner programmer, I don't know how to conceptually think about brute-forcing. My mind can't really fathom how to write code that will try every possibility. I have a problem that I want to ...
0
votes
0answers
145 views

what is the meaning of f(n) = O(g(n))? [duplicate]

I am reading 'Algorithm design manual' book by Steven S. Skiena. I would like to know what is f(n) and g(n)? I am a programmer and wanted to gain more knowledge about algorithms but now I am confused ...
3
votes
1answer
357 views

How this Fibonacci exponentiation by squaring algorithm works?

This is one of the best algorithms to calculate the nth Fibonacci sequence. it needs O(log(n)) time to do its job, so it's so efficient. I found it somewhere but don't know how it works! Can anyone ...
1
vote
4answers
263 views

How to trace logical errors in algorithms [closed]

I am beginner in algorithms. Last year I participated in Google Code Jam. One of the major issues I faced during the competition was my code was working fine on my test cases, but when I submitted on ...
3
votes
1answer
185 views

Sentence Tree v/s Words List

I was recently tasked with building a Name Entity Recognizer as part of a project. The objective was to parse a given sentence and come up with all the possible combinations of the entities. One ...
7
votes
3answers
2k views

Why Big Data Needs To Be Functional?

I started working on a new project lately related to Big Data for my internship. My managers recommended to start learning functional programming (They highly recommended Scala). I had a humbled ...
1
vote
1answer
136 views

How to calculate the worst-case runtime of this search-algorithm

I've written a special indexOf function for a list of unsorted unique values. I can search for one or multiple (unsorted) values, passed as array/list, and the function will return me an array/list ...
-4
votes
1answer
1k views

What is the big-O cpu time of Euclid's Algorithm of “Greatest common divisor of two numbers”

Looking at Euclid's algorithm for the "Greatest common divisor of two numbers", I'm trying to divine the big-O cpu time for numbers K, and N. Can anybody help? This is the algorithm as I understand ...
5
votes
2answers
774 views

difference between accounting and potential methods in Amortized Analysis

I was going through the Introduction to Algorithms by Cormen et al.In the chapter titled Amortized Analysis,the difference between accounting and potential methods is given like this The ...
5
votes
1answer
212 views

Bin sorting problem - Please help categorize

I have a problem I am developing a solution for and currently I solve it with a brute force solution that checks all possibilities. It works for small numbers of bins but I'd like to work with a ...
13
votes
2answers
486 views

Trying to understand the 2N lnN compares for quicksort

I was going through the analysis of quicksort in Sedgewick's Algorithms book. He creates the following recurrence relation for number of compares in quicksort while sorting an array of N distinct ...
6
votes
6answers
5k views

Why is binary search,which needs sorted data, considered better than linear search?

I have always heard that linear search is a naive approach and binary search is better than it in performance due to better asymptotic complexity. But I never understood why is it better than linear ...
0
votes
1answer
61 views

clarification about amortized analysis

I was going through an article here In the section named Aggregate Method ,the author says Then summing over the entire sequence, all the 1's sum to O(n), and all the di also sum to O(n). That ...
2
votes
1answer
201 views

Algorithm in undirected BFS graph

I'm trying to put together an algorithm that will display the node degree for every node in a breadth first tree graph (assume BFS was called). Assume it's an undirected graph. I'm not sure how to ...
1
vote
1answer
908 views

Matrix Pattern Recognition Algorithm for a 2D space

I have a picture that I elaborate with my program to obtain a list of coordinates. There is a matrix represented in the image. In an ideal test I would get only the sixteen central points of each ...
5
votes
4answers
638 views

Find the peak of each islands in sparse matrix

I have a sparse matrix that contains several islands of unknown size. I would like to find the highest peak of each islands. Consider this matrix as an example: 0 0 1 0 0 0 0 0 0 1 2 1 0 0 0 0 0 3 2 ...
0
votes
1answer
418 views

Priority queue for Kruskal's algorithm with running time O(E lg V)

I'm reviewing my notes on Kruskal's algorithm and have a question about getting the runtime down to O(E lg V). By using a PQ with edges and a boolean array of which vertices we have added to our tree ...
26
votes
5answers
3k views

Divide and Conquer algorithms – Why not split in more parts than two?

In divide and conquer algorithms such as quicksort and mergesort, the input is usually (at least in introductory texts) split in two, and the two smaller data sets are then dealt with recursively. It ...
2
votes
4answers
347 views

Approach to simplifying an algorithm

For completely random reasons*, I wrote some code that calculates and displays the following expression: P=1*(2+2)(3+3+3)(4+4+4+4)..(n+n...… Which is equivalent to (n!)^2 The version I wrote ...
4
votes
8answers
989 views

How meaningful is the Big-O time complexity of an algorithm?

Programmers often talk about the time complexity of an algorithm, e.g. O(log n) or O(n^2). Time complexity classifications are made as the input size goes to infinity, but ironically infinite input ...
8
votes
1answer
781 views

Possible Damerau-Levenshtein improvement?

I recently implemented the Damerau-Levenshtein distance algorithm from the pseudocode on Wikipedia. I couldn't find any explanation of exactly how it works and the pseudocode uses completely ...
0
votes
2answers
528 views

Does this version of insertion sort have O(n) complexity for best case?

for ( i = 1 ; i <= N ; i++ ) { for ( j = 0 ; j < i ; j++ ) { if ( arr[j] > arr[i] ) { temp = arr[j] ; arr[j] = arr[i] ; for ( k = i ; k > j ; k-- ) ...
5
votes
5answers
680 views

Why interviewers want Optimal Algorithms

In an interview with a software company they asked me some algorithm design questions. Being strong in mathematics I was able to solve it mathematically, but each time when I propose my algorithm ...
3
votes
1answer
909 views

A* Algorithm Completeness Proof

The A* Algorithm is the optimal (provided the heuristic function is underestimated), complete & admissible (provided some conditions). I know the proofs of admissibility & optimality. But how ...
2
votes
1answer
222 views

How to compute amoritized cost for a dynamic array?

I am trying to understand how to do the amortized cost for a dynamic table. Suppose we are using the accounting method. Let A of size m be an array of n elements. When n = m, then we create a new ...
2
votes
1answer
180 views

How much times command executed? Looking for mistake

I have following piece of code: int sum = 0; for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) for (int k = 1; k <= N; k = k*2) for (int h = 1; h <= k; ...
0
votes
4answers
5k views

finding the time complexity of the following program

I need to find the time complexity in terms of Big Oh notation for the following program which computes the factorial of a given number: The program goes like this: public int fact(int n){ if (n ...