Questions related to design and analysis of algorithms
32
votes
3answers
1k views
How does one know which notation of time complexity analysis to use?
In most introductory algorithm classes, notations like $O$ (Big O) and $\Theta$ are introduced, and a student would typically learn to use one of these to find the time complexity.
However, there are ...
12
votes
4answers
4k views
How to convert finite automata to regular expressions?
Converting regular expressions into (minimal) NFA that accept the same language is easy with standard algorithms. The other direction seems to be more tedious, though, and sometimes the resulting ...
20
votes
6answers
586 views
How can we assume comparison, addition, … between numbers is $O(1)$
Normally in algorithms we do not care about comparison, addition, or subtraction of numbers -- we assume they are $O(1)$. For example we assume this when we say that comparison based sorting is ...
15
votes
3answers
399 views
Deciding on Sub-Problems for Dynamic Programming
I have used the technique of dynamic programming multiple times however today a friend asked me how I go about defining my sub-problems, I realized I had no way of providing an objective formal ...
8
votes
1answer
1k views
Which combinations of pre-, post- and in-order sequentialisation are unique?
We know post-order,
post L(x) => [x]
post N(x,l,r) => (post l) ++ (post r) ++ [x]
and pre-order
...
10
votes
7answers
1k views
Generating uniformly distributed random numbers using a coin
You have one coin. You may flip it as many times as you want.
You want to generate a random number $r$ such that $a \leq r < b$ where $r,a,b\in \mathbb{Z}^+$.
Distribution of the numbers should ...
13
votes
1answer
2k views
How hard is counting the number of simple paths between two nodes in a directed graph?
There is an easy polynomial algorithm to decide whether there is a path between two nodes in a directed graph (just do a routine graph traversal with, say, depth-first-search).
However it seems that, ...
6
votes
3answers
459 views
Sorting algorithms which accept a random comparator
Generic sorting algorithms generally take a set of data to sort and a comparator function which can compare two individual elements. If the comparator is an order relation¹, then the output of the ...
7
votes
1answer
456 views
Find shortest paths in a weighed unipathic graph
A directed graph is said to be unipathic if for any two vertices $u$ and $v$ in
the graph $G=(V,E)$, there is at most one simple path from $u$ to $v$.
Suppose I am given a unipathic graph $G$ such ...
1
vote
2answers
798 views
Time complexity formula of nested loops
I've just begun this stage 2 Compsci paper on algorithms, and stuff like this is not my strong point. I've come across this in my lecture slides.
...
36
votes
7answers
2k views
Intuition for logarithmic complexity
I believe I have a reasonable grasp of complexities like $\mathcal{O}(1)$, $\Theta(n)$ and $\Theta(n^2)$.
In terms of a list, $\mathcal{O}(1)$ is a constant lookup, so it's just getting the head of ...
12
votes
3answers
321 views
Dealing with intractability: NP-complete problems
Assume that I am a programmer and I have an NP-complete problem that I need to solve it. What methods are available to deal with NPC problems? Is there a survey or something similar on this topic?
9
votes
5answers
1k views
How to come up with the runtime of algorithms?
I've not gone much deep into CS. So, please forgive me if the question is not good or out of scope for this site.
I've seen in many sites and books, the big-O notations like $O(n)$ which tell the ...
4
votes
2answers
1k views
11
votes
5answers
946 views
When to use recursion?
So we are covering recursion in a C++ class I am taking. I understand what it is, a function that calls itself (a very basic explanation), I am just having trouble coming up with a lot of instances ...
