# Tagged Questions

1k views

### What is an example of a computationally impossible business problem?

I have coworker who refuses to accept the reality that Turing machines (and Von Neuman machines by extension) cannot solve their own halting problem stating: You can do anything with enough time ...
6k views

### How can I make sure that I'm actually learning how to program rather than simply learning the details of a language?

I often hear that a real programmer can easily learn any language within a week. Languages are just tools for getting things done, I'm told. Programming is the ultimate skill that must be learned and ...
2k views

### Why are algorithms and data structures important? [duplicate]

It seems like a lot of university-level computer science programs and programmer job interviews focus heavily on algorithms and data structures. I'm curious as to why universities and employers put so ...
204 views

### Class of problems solvable by sed or stream editors

I've came across a question transform this text with sed [sed only] and it got me wondering what class of problems is solvable by stream editors or programs/computational models with similar ...
1k views

### Time complexity of a nested loop where the inner value is decreased in every step

I have problems to give the right time complexity in O notation for the following loop: k := 0 for i := 0 to N for j := k to M // something k = k + 1 Where N = M. Without the modified ...
339 views

### How many copies are needed to enlarge an array?

I am reading an analysis on dynamic arrays (from the Skiena's algorithm manual). I.e. when we have an array structure and each time we are out of space we allocate a new array of double the size of ...
1k views

### Basic premise on counting sort. How is k related to to Big Oh?

I am reading (Cormen) on counting sort. I understand the structure of the algorithm but the statement: In practice, we usually use counting sort when we have k = O(n), in which case the ...
952 views

### Algorithm refresher. Why is heapsort an insort algorithm?

I can not see why the heapsort is considered an inplace sorting algorithm. I mean an extra data structure populated with the elements of the array to be sorted i.e. a heap, is used to assist in the ...
124 views

### Help on clarification of a formal statement concerning algorithms running time

I am reading the following in a book on algorithms (Cormen's to be specific): That is, we are concerned with how the running time of an algorithm increases with the size of the input in the ...
155 views

### Algorithm analysis refresher help

I haven't touched algorithm complexity stuff in quite a while, so I am trying to do a refresher. I am trying to figure out the number of steps in the following for loop. for(i = 0; i < n; ...
2k views

### Theta notation on constant time. Why we use the 1?

In asymptotic notation when it is stated that if the problem size is small enough (e.g. n<c for some constant c) the solution takes constant time and is writen as Theta(1). Why we write 1 inside ...
3k views

What are the relative pro's and con's of both DFA's and NFA's when compared to each other? I know that DFA's are easier to implement than NFA's and that NFA's are slower to arrive at the accept state ...