Tagged Questions

The tag has no usage guidance.

144 views

Best approach to write on a database with two webservers

I have an architecture/performance problem. The problem: One voting based application with: 1 loadbalancer, 2 webservers and a database 10 candidates and 200k voting users. There may be more than ...
33 views

What are the methods to accurately test the accuracy of a parts of speech tagger?

I know that most of the pos tagger algorithms measure their accuracy token wise I.e. whether the token is tagged correctly or not Some pos taggers provide sentence accuracy too. How is sentence ...
53 views

String Pattern Matching from Lookup Table - Non-Exponential Solution?

Given the problem... Given a String comprising of non-alhpabetical symbols, and a Lookup Table where a subset of those symbols may equate to a single alphabetical character, output all ...
87 views

Optimizing the exponential smoothing of a big array

I have a large set of values (let's say 1M entries) where I need to apply an exponential smoothing algorithm, but only incrementing one value at a time (all others decay to zero). The trivial ...
38 views

Search list items from other list, better way?

Today I have to search items of list from another list individually. I am just thinking about some better approach. Below is scenario described. Lets say I have two arrays, arr1 having 100 elements (...
528 views

What is Big-O notation for purely functional languages?

Is it still relevant? Instead of var result = new List<int>(); for (var i = 0; i < prev.Count; ++i) { result.Add(prev[i] * 2); } where the result.Add, prev[i], and * 2 instructions ...
95 views

Unable to Solve Dynamic Programming

I had an assignment on dynamic programming due last night, but I had to turn it in unfinished because i could not understand how to solve the last problem: The state wants to monitor traffic on a ...
156 views

How to find complexity of T(n) = 8T(n/2)+n^2.93(log n)^93?

I believe we have to use a variant of master theorem...can someone suggest me how to find complexity of such equation which doesn't directly fit into Masters theorem.
355 views

Time complexity of 2^sqrt(n)

I am solving an algorithm question and my analysis is that it would run on O(2^sqrt(n)). How big is that? Does it equate to O(2^n)? Is it still non-polynomial time?
259 views

Data structure for sorting by multiple attributes

I have a list of integer pairs. The value of this list is the sum of the maximum values of each pair. For (0, 5) (20, 5) (6, 8) the value would be 5 + 20 + 8 = 33 Given a list like this,...
96 views

Are these graph coloring algorithms equivalent?

Suppose you want to color the vertices of a graph in a greedy fashion, given a predetermined order of these vertices. The goal is to avoid giving two adjacent (linked by an edge) vertices the same ...
93 views

Belman-Ford 2d array variation problem

I've got a problem with applying a Bellman-Ford algorithm to 2D Array (not to graph) Input array has m x n dimensions: s[1,1] s[1,2] ... s[1,n] -> Exit s[2,1] s[2,2] ... s[2,...
77 views

Running time of the specified Bubble Sort Algorithm

I have been working on a few algorithm questions the last few days, and one bubble sort problem in particular has been giving me headaches. for (k=1; k <= A.length - 1; k++) { //Line 1 ...
277 views

What's the big-O complexity of this recursive algorithm?

I am following a course of Algorithms and Data Structures. Today, my professor said the complexity of the following algorithm is 2^n. I waited till the lesson was over, approached him and told him ...
230 views

Big O Nested For Loop Breakdown

I understand how to get a general picture of the big O of a nested loop, but what would be the operations for each loop in a nested for loop? If we have: for(int i=0; i<n; i++) { for(int j=i+...
844 views

Is O(log n) + O(log n) = O(n)? [duplicate]

We know that binary search takes O(log n) in Big O notation but if we need to run twice an algorithm of O(log n), would it be the same as O(n) in time complexity? For example, if I have a method to ...
690 views

Is the time complexity of a while loop with three pointers different than 3 nested for loops?

This program (written in ruby) finds the largest 3 numbers in an array (without sorting the array). It has a while loop with three pointers. My fist instinct, since there is only one loop is to say ...
3k views

When speaking, how can I say that the time complexity order of an algorithm is O(N log N)?

What term can I use to describe something with O(N log N) complexity? For example: O(1): Constant O(log N): Logarithmic O(N): Linear O(N log N): ?????? O(N2): Quadratic O(N3): Cubic
393 views

Best algorithm to determine whether two arrays can be the same in a circular queue

I'm trying to figure out an efficient way to determine whether two distinct arrays of the same size can be shifted to form the same circular queue. For example: Array1 = ['A','B','C','D'] Array2 = ['...
232 views

What is the algorithmic time complexity of this program?

I wrote a simple program in java to create and maintain Dynamic Arrays: public class DynamicArrays { private Integer[] input = new Integer[1]; private Integer length = 0; private Integer ...
216 views

Time complexity of this loop [duplicate]

Is the time complexity for this loop O(n) or O(log n)? for(i=0;i<n/2;i++){} I am thinking, the time is proportional with the input size.
417 views

Big O notation of randomness

I was thinking about inefficient algorithms based on randomness and wondered how to categorise them. For instance. Say you wanted to generate all the numbers from 1 to N in a random order but only ...
257 views

Close to knapsack problem?

I think that I am trying to solve a problem somewhat similar to a knapsack problem. I am not sure though. Please see the input given below and my solution. There are three types of items and 4 ...
2k views

Calculate Big-O for nested for loops

I found this nested loop to calculate the Big-O notation. for(i=0;i<n;i++) for(j=0;j<i*i;j++) for(k=0;k<j;k++) I got the time complexity for the algorithm with this polynomial ...
402 views

Check distance between all elements in a list of numbers in O(n*lg(n))

I have an exercise for my algorithms and data structures class, where I basically have to implement a divide and conquer algorithm or function called check_distance to determine whether all numbers in ...
115 views

More efficient alternative that checks if a list can be made a palindrome

I asked this question on Stackoverflow, but they told me this is the best place to ask. For my algorithms and data structures class, I have to write an algorithm that is more efficient in the worst ...
1k views

I was given the following problem: Integer V lies strictly between integers U and W if U < V < W or if U > V > W. A non-empty zero-indexed array A consisting of N integers is given. A ...
500 views

Estimating run time of algorithm

For instance if i have an algorithm that is O(n2) and it will run for 10 seconds for a problem size of 1000. Now if i were to double the problem size to 2000 i want to know the approximate run time in ...
196 views

Algorithm Space and Time Complexity with Consideration for I/O (eg cache)

Is there an expression of performance for an algorithm or data structure that attempts to consider cache and other hardware concerns? Context: in my class we're looking at binary trees and it seems ...
220 views

Connected components of undirected graph

Suppose I have an undirected graph G with vertices v1...vn and edges. Right now it is in adjacency list representation. For every time moment I have as input some subset of vertices that are "active" ...
794 views

worst case comparisons for special case insertion sort [closed]

Consider an Insertion Sort with a Sentinel on n values, where every value occurs exactly twice in the input (so n must be even). So the best case input for comparisons is when the elements are ...
140 views

Time complexity analysis for recurrence relation

I was asked to figure out the time complexity analysis for the following recurrence relation T(n) = 4*T(n-1) + c. Basically, I did a replacement.. T(n-1) = 4 * T(n-2) + c and so on.. T(n) = 4^k T(1) ...
197 views

Time complexity for a recurrence relation using Divide and Conquer Master Theorem [closed]

For the recurrence relation : T(n) = 16T(n/4) + n! I have found that the order is Θ(n!). But I don't understand how it can be deduced using Master Theorem.
270 views

Big-O notation for other cases

I was just reading answers to a question Plain English explanation of Big O From that i came to know that Big-O notation is just an "upper bound" of the complexity of an algorithm? But can we apply ...
2k views

Lower and Upper bound of an algorithm

I am learning about analysis of algorithms. I came across the term "upper bound" and "lower bound" in "worst-case" running time of an algorithm. Are they applicable to only the "worst case" or can ...
462 views

Shortest path to visit all nodes [duplicate]

I am given a set of tourist attractions(nodes identified by x, y) and i need to find the shortest path to visit them. The way i thought of it, is i will ignore if there are streets available and ...
171 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 ...
881 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 ...
151 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 ...
281 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 ...
9k 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; ...
98 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 (...
613 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 ...
879 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 ...
395 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, ...
162 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 if-...
417 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; j++...
342 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 ...