# All Questions

30,177 questions
16k views

### When should I learn artificial intelligence? [closed]

Straight to the point: I would really like to learn AI. But I want some advice from experienced CS guys as to when I should jump into Artificial Intelligence. What prerequisites are needed in order ...
510 views

### Given a fast and a slow computer, at what sizes does the fast computer running a slow algorithm beat the slow computer running a fast algorithm?

The source of this question comes from an undergraduate course I am taking, which covers an introduction to the analysis of algorithms. This is not for homework, but rather a question asked in CLRS. ...
57 views

### Heuristically determine a value f such that a probability d/f approaches 1/2

We have a set X of N elements. We want to get a new set X' having a size M < N. ...
2k views

So we have the following table of processes , where A, B and $\Gamma$ are the resources. Here is a pic that i drew with the processes and the resources. So the exact question is this: Using banker's ...
180 views

### Creating artificial NP-Complete problems

Stephen Cook's proof of the NP-completeness of SAT is constructive. Given a Turing machine $M$, one can create a logical formula that is satisfiable if and only if $M$'s computation halts in an ...
187 views

### Are there grammar classes between Chomsky level 1 and 2?

Are there any grammar classes which are true subsets of Chomsky level 2 but not equal to level 1?
103 views

### Computing the running time of a divide-by-4-and-conquer algorithm

I write this code in python: ...
217 views

### Doubt with a problem of grown functions and recursion tree

I'm confused to conclude the recursion tree method a guess for the next recurrence: $$T(n)=3T\left (\left\lfloor \frac{n}{2}\right \rfloor\right) +n$$ I write some costs for the levels of tree, you ...
5k views

### Why does heapsort run in $\Theta(n \log n)$ instead of $\Theta(n^2 \log n)$ time?

I am reading section 6.4 on Heapsort algorithm in CLRS, page 160. ...
948 views

### What approaches are most useful when proving uncomputability of a given function?

I'd like to understand what approaches should one adopt when deciding/proving that a given function F is uncomputable, by any Turing Machine (TM). The ones I've tried so far are as follows: Reduction,...
816 views

### What is the probability of friendship conditioned on the number of mutual friends

Let Alice and Bob be two users chosen uniformly at random from a social network (e.g. Facebook). What is the probability that they are friends assuming that they share $k$ mutual friends? I am ...
492 views

### Kolmogorov complexity of string concatenation

If $K(s)$ is the Kolmogorov complexity of the string $s \in \{0,1\}^*$, Can we prove (or disprove) the following statement: "Every string $s$ is a prefix of an incompressible string; i.e. for every ...
4k views

### How to prove that DFAs from NFAs can have exponential number of states?

All non-deterministic finite automata can be turned into equivalent deterministic finite automata. However, a deterministic finite automata only allows a single arrow per symbol pointing from a state. ...
632 views

### Why isn't converting from an NFA to a DFA working?

I am just beginning to learn computation theory. I wrote up a non-deterministic finite automata that accepts strings that contain the substring "abba": I tried to convert it to a DFA by putting ...
49 views

### How to generate inputs to evaluate the performance of an implementation?

How can we assert that the performance of an implementation matches the expected performance defined in terms of Big-$\mathcal{O}$ and friends by generating best/worst case inputs? I'm thinking of a ...
841 views

1k views

### Approximating the Kolmogorov complexity

I've studied something about the Kolmogorov Complexity, read some articles and books from Vitanyi and Li and used the concept of Normalized Compression Distance to verify the stilometry of authors (...
203 views

### How can lazy learning systems simultaneously solve multiple problems?

On the english Wikipedia it says about lazy learning systems: Because the target function is approximated locally for each query to the system, lazy learning systems can simultaneously solve ...
293 views

### Complexity inversely propotional to $n$

Is it possible an algorithm complexity decreases by input size? Simply $O(1/n)$ possible?
812 views

### Impossibility condition in the Byzantine Generals problem

I am unable to understand why there is a requirement of 3m+1 generals overall given m traitors. As per my understanding, the steps are as follows: Each general decides a strategy and forwards their ...
2k views

### Using a step-counting function in a Turing Machine construction

I have an question relating to the elementary foundations of Turing Machine theory. I would like to have a clarification of the status of a function $\phi$ (a mapping between TM indexes) I shall ...
1k views

### Length of the certificate in complexity classes

A nondeterministic machine trying to decide membership in a language is presented with a hint (called a "witness" or "certificate") which proves membership (no such witness is provided for ...
663 views

### Minimum vertex-weight directed spanning tree where the weight function depends on the tree

Given a directed graph $G=(V,E)$ and a node $r\in V$, I need to grow a tree $T$ rooted at $r$ that has a minimum weight and spans all reachable nodes in $G$. The weight function assigns a non-...
390 views

### Successful applications of fuzzy logic to reasoning in AI?

I've done some searching and it seems that fuzzy logic is used in (electronic) controllers. I'm interested in seeing how well it fares as a tool for reasoning. Are there any robots or programs that do ...
1k views

### Converting function to bitwise only?

I have a function to count upper bits of a 32 bit value. So if a number is 11100011111..., the result is 3 as there are 3 ones in the most significant place before a 0 is hit. I need to convert the ...
7k views

### Changing variables in recurrence relations

Currently, I am self-studying Intro to Algorithms (CLRS) and there is one particular method they outline in the book to solve recurrence relations. The following method can be illustrated with this ...
112 views

### Algorithm that hashes a collection of sets following their disjointness relation

I wonder whether there is a simple algorithm to do this work: Say I have a collection of objects $C$, and a binary relation $R: C\times C$ that is auto-reflective ($\forall c\in C: c R c$) , and ...
20k views

### What does “dummy argument” mean?

What is does it mean when an argument to a function is called a dummy argument? I have not encountered this term outside Fortran, is it a general term in computer science? What would be examples of ...
In Big Theta notation used for defining the running time of an algorithm, are the constants $c_1$ and $c_2$ different for every value of $n$? Definition: \$\qquad \displaystyle \Theta (g(n)) = \{ f(n)...