All Questions

20
votes
3answers
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 ...
8
votes
1answer
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. ...
0
votes
3answers
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. ...
3
votes
2answers
2k views

Banker's Algorithm and deadlocks

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 ...
4
votes
1answer
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 ...
4
votes
1answer
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?
4
votes
1answer
103 views
4
votes
1answer
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 ...
6
votes
2answers
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. ...
4
votes
4answers
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,...
3
votes
1answer
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 ...
7
votes
1answer
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 ...
19
votes
3answers
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. ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
2
votes
1answer
841 views

Is star closure of reverse of language equivalent to reverse of closure of that language

is the following true $ (L^R)^* = (L^*)^R $ I tried the following to prove it true. let u,v belong to L then $ L^* = \{ u,v, uu, vv, uv, vu ... \} $ and $ (L^*)^R = \{ u^R, v^R, u^Ru^R, v^Rv^R, v^...
2
votes
1answer
110 views

What constitutes one operation/cycle/move in the RAM model?

I saw a RAM model diagram that displayed an input tape, output tape, the program (read-only), the instruction pointer, and the memory registers. However, when I look at questions of time complexity, ...
7
votes
1answer
6k views

What is the difference between decidability and computability?

If they are different, what are the typical problems in each that do not fall on the other category? Or are the mutually exclusive or does one completely capture the other?
10
votes
1answer
12k views

What is the difference between halting, accepting, and deciding in the context of Turing machines?

Does accepting mean that the TM will read and recognize a char from the cell it's currently reading from? And is it the case that a TM halts iff the input is decidable?
4
votes
0answers
113 views

Is there any research to indicate programmers are/are not moving to a hybrid of functional and object-oriented?

I am converting the OCaml Format module which does I/O and maintains state in a record with mutable values. As such it is a good candidate for me to convert to pure F#, pure C# and a hybrid. Since ...
13
votes
4answers
867 views

Self-Study of Computer Science

I am a 16 year old male who has recently been gifted a big encyclopedia on computer science by a friend of mine. I am usually not that interested in computers and technology, but computer science has ...
4
votes
2answers
599 views

What if a formal grammar cannot be terminated?

I'm currently in a class on Computability and we just finished looking at formal grammars before moving onto finite automata. We were given an several examples of a formal grammar, and one stuck out ...
3
votes
2answers
228 views

Is a single symbol, not in a set, a language?

I was reading about Turing machines and realized I'm not sure about the difference between the following scenario. Given the alphabet $\Sigma = \{a, b \}$, we have the following assertions: $a \in R $...
2
votes
1answer
2k views

Finding the number of leaves in a imbalanced recursion tree

I'm going through the MIT Online Course Videos on Intro. to Algorithms at here at around 38:00. So we have a recursion formula $\qquad T(n) = T(n/10) + T(9n/10) + O(n)$ If we build a recursion tree ...
9
votes
2answers
2k views

Infinite alphabet Turing Machine

Is a Turing Machine that is allowed to read and write symbols from an infinite alphabet more powerful than a regular TM (that is the only difference, the machine still has a finite number of states)? ...
3
votes
2answers
232 views

Recommended Reading for non-CS undergraduate student doing a research Project on Travelling Salesman Problem

I am an undergraduate student in Industrial Engineering. I have taken the topic of Travelling Salesman Problem as a Research Project for my final year. More specifically, I am focusing on Convex Hulls ...
4
votes
1answer
491 views

Help Finding Loop Invariant From For Loop

I have created the algorithm below... ...
4
votes
1answer
2k views

How does a single-track Turing machine simulate a multi-track Turing machine?

It's easy to see how a multi-track Turing machine can simulate a single-track Turing machine; it does so by ignoring all but the first track. But how does it work the other way? I need a specification ...
39
votes
7answers
3k views

Explaining the relevance of asymptotic complexity of algorithms to practice of designing algorithms

In algorithms and complexity we focus on the asymptotic complexity of algorithms, i.e. the amount of resources an algorithm uses as the size of the input goes to infinity. In practice, what is ...
4
votes
1answer
927 views

On-line simulation of a two-head tape Turing machine using single-head tape(s)

I have a question and I haven't been able to figure out the answer yet. I need to do the on-line simulation of a two-head tape Turing machine using single-head tape(s). I've found some online articles ...
3
votes
2answers
2k views

Finding odd directed circuit

I want to write an algorithm to find whether a directed circuit whose length is odd exists in a strongly connected digraph. Can anyone help me how to proceed with this problem???
22
votes
1answer
37k views

Two definitions of balanced binary trees

I have seen two definitions of balanced binary trees, which look different to me. A binary tree is balanced if for each node it holds that the number of inner nodes in the left subtree and the number ...
2
votes
1answer
1k views

What are the mathematical prerequisites for adaptive machine learning algorithms?

I am a PhD student in Computer Science who switched his PhD a little bit towards ML algorithms combined with something else... I am an expert in that something else, say image processing, but not an ...
7
votes
1answer
3k views

NP-complete proof from Dasgupta problem on Kite

I am trying to understand this problem from Algorithms. by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, chapter8, Pg281. Problem 8.19 A kite is a graph on an even number of vertices, say $2n$, ...
7
votes
1answer
8k views

Solving $T(n)= 3T(\frac{n}{4}) + n\cdot \lg(n)$ using the master theorem

Introduction to Algorithms, 3rd edition (p.95) has an example of how to solve the recurrence $$\displaystyle T(n)= 3T\left(\frac{n}{4}\right) + n\cdot \log(n)$$ by applying the Master Theorem. I am ...
4
votes
0answers
222 views

Reduction from knapsack problem to Integer relation that equals one

My question is related to the Integer Relation Detection Problem which can be formulated as: $\qquad a_1x_1 + a_2x_2 + \cdots + a_nx_n = 0$ Where $\forall i. a_i\in\mathbb{Z} \land a_i<c \land x\...
21
votes
3answers
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 (...
5
votes
3answers
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 ...
5
votes
3answers
293 views

Complexity inversely propotional to $n$

Is it possible an algorithm complexity decreases by input size? Simply $O(1/n)$ possible?
2
votes
1answer
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 ...
1
vote
1answer
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 ...
3
votes
3answers
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 ...
6
votes
0answers
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-...
4
votes
1answer
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 ...
6
votes
3answers
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 ...
19
votes
2answers
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 ...
3
votes
0answers
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 ...
8
votes
4answers
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 ...
16
votes
5answers
5k views

Fixed point, what does it mean in the world of computer science

I keep coming across references to fixed point in questions and answers at stackexchange and I look up the meaning on the web obviously finding reference at sites such as Wikipedia. However none of ...
1
vote
3answers
597 views

Value of constants in Big Theta notation

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)...

15 30 50 per page