All mathematical questions about Computer Science, including Theoretical Computer Science, Formal Methods, Verification, Logic in Artificial Intelligence, and Numerical Analysis
0
votes
0answers
12 views
Time complexity of the described DTM
There is a DTM with alphabet $\Sigma = \{∗, 0, 1\}$, that on input $1^n$ outputs $1^n ∗ 1^n$. That is it takes a string of $n$ ones and replaces it by two strings of $n$ ones, separated by a blank ...
3
votes
2answers
56 views
What is the relationship between “recursive” or “recursively enumerable” sets and the concept of recursion?
I understand that "recursive" sets are those that can be completely decided by an algorithm, while "recursively enumerable" sets can be listed by an algorithm (but not necessarily decided). I am ...
4
votes
2answers
3k views
Reduction from Hamiltonian cycle to Hamiltonian path
I'm looking for an explanation on how reducing the Hamiltonian cycle problem to the Hamiltonian path's one (to proof that also the latter is NP-complete). I couldn't find any on the web, can someone ...
-3
votes
0answers
164 views
Is computability theory a joke? [duplicate]
by N.J Wildberger Set Theory: Should You Believe?
I read the book, find some very idea shocking me. The author just destroys everything I had learned from computer science's courses.
Look at last ...
1
vote
1answer
44 views
MATLAB code to find distance and eccentricity in graphs
I was trying to find the distances between vertices in graphs. But as the number of vertices are increasing up to 25 vertices or more, its becoming a tedious job for me to calculate $distance$ and ...
-3
votes
0answers
43 views
Depth-first search of a graph
I need some help...
The exercise is:
You have to implement a data structure to represent graphs, directed or undirected, that tries to avoid the wasted space in the representation of a graph with ...
0
votes
0answers
15 views
Asymptotic recurrences?
$$T(n) = 2T(n/2) + \Theta(n), n > 1$$
$$T(n) = \Theta (1), n \le 1$$
$$G(n) = G(\lfloor n/2 \rfloor) + G (\lceil n/2 \rceil) + \Theta(n), n > 1$$
$$G(n) = \Theta (1), n \le 1$$
Prove $T(n)$ ...
0
votes
0answers
32 views
Expressing functions using Karnaugh map [duplicate]
Using the Karnaugh map, express the following function:
$F(0, 1, 4, 5, 8, 10, 11, 12, 13, 15)$
would this be the answer
I'm a little confuse
($b_1=0$ and $b_0=0$) or ($b_3=0$ and $b_1=0$) or ...
1
vote
2answers
119 views
Decidability and undecidability of a set or language
I want to find out whether the following sets are decidable or not. Generally speaking, what exactly should be done about it? Doing some research, I think a language or set is decidable if a Turing ...
0
votes
1answer
33 views
Is $\{(x, y) \mid y \in \text{Range}(\phi_x)\}$ decidable?
Is the following language decidable? A decidable language must be recursive, right? How should I show that the following is or is not recursive?
$$\{(x, y) \mid y \in \text{Range}(\phi_x)\}$$
1
vote
1answer
47 views
Why is it okay to do this?
I am studying asymptotic recurrences for algorithms, and the book says:
$$T(n) = 2T(n/2) + \Theta (n)$$
is technically
$$T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + \Theta (n)$$
for an ...
2
votes
2answers
86 views
Is the difference of two recursively enumerable sets, reducible to $K$?
Is the difference of two recursively enumerable sets, reducible to $K$?
$W_x/W_y=\{z|z \in W_x \& z \notin W_y\}$
$K=\{x|\Phi_x(x) \downarrow\}$
$W_x= \text{dom}(\Phi_x)$
3
votes
2answers
54 views
complete the table by providing an example of a binary operation $*$ defined on $\{a , b ,c\}$
I have a problem with one of my questions. The question is:
complete the table by providing an example of a binary operation $*$ defined on $\{a , b ,c\}$
such that $*$ is commutative and has the ...
1
vote
3answers
71 views
Is it possible to prove from the definition of big $O$ that $5n^3+7n+1$ is $O(n^3)$?
Is it possible to prove from the definition of big O that $5n^3+7n+1$ is $O(n^3)$? Can this be generalised to any case where you have to (and what is the procedure for working it out?) I guess the ...
1
vote
2answers
499 views
Advice for how to learn more advanced math for audio signal processing?
I am very interested in learning about audio from a signal processing standpoint. However, whenever I try to further my education by reading books, I get extremely frustrated because the books use ...
3
votes
1answer
58 views
Is this language decidable?
Is this language decidable?
$$\{x\mid \text{$x$ is the code of a Turing machine that always halts on $y$
in less than $y^3$ steps}\}$$
I think it is, because it halts in a finite number of ...
1
vote
2answers
58 views
decidability of $\{x|W_x \text{is different from K in only finitely many elements}\}$
Is the following language decidable? Please explain your argument as I want to learn how such problems must be solved to do the rest on my own.
$$\{x \mid W_x \text{ is different from K in only ...
-6
votes
0answers
39 views
Write a Java program on Palindromes [closed]
Write a java program on Palindromes?
How to write a java program on Palindromes without using if statements, loops or Strings.
0
votes
1answer
42 views
Why is it necessary to use sin or cos to determine heading? (dead reckoning)
Here's the problem:
(see pic for problem): https://fbcdn-sphotos-c-a.akamaihd.net/hphotos-ak-ash3/21281_10152793202590262_1804321932_n.jpg
You have a robot that is moving forward at a variable rate ...
1
vote
1answer
111 views
Logical Conjunction of Binary Decision Diagrams
Compute a Binary Decision Diagram for $B1∧B2$. Furthermore, for an arbitrary BDD B you can use the equations $B∧F=F$, $F∧B=F$, $B∧T=B$ and $T∧B=B$.
To construct the BDD i start from the leaves ...
7
votes
2answers
180 views
maximum number of edges to be removed to possess a property
I am working on a problem. We know that on squaring a cycle, degree of every vertex is 4. For squares of cycles, we know if we delete any arbitrary edge then still eccentricity is same for all ...
1
vote
0answers
29 views
Pebble game on graph
Consider the problem whose instance is a directed graph with the selected vertex V and k of 'pebbles'. We can in any order, perform the following elemental steps:
on top of x we can put a pebble, if ...
2
votes
1answer
53 views
An interesting version of the problem “balls into bins”
Consider n people, each has k identical balls. Each people choose k different bins from m bins, constrained by the condition that there are no two people choose exactly the same k bins. For instance, ...
4
votes
1answer
189 views
Matrix Chain Multiplication?
The following are questions about using dynamic programming for matrix chain multiplication. Pseudocode can be found in the Wikipedia article on matrix chain multiplication.
1) Why is the time ...
0
votes
0answers
46 views
write a Java program that asks the user to enter a number and then tells him whether it is a palindrome or not [closed]
I need to write a Java program that asks the user to enter a number and then tells him whether it is a palindrome or not. You may assume the user enters a positive integer that is at most 4 digits ...
1
vote
2answers
82 views
non-recursive function
Give a direct proof that the set $\{x|\Phi_x(1) \downarrow\}$ (which is a set of program numbers that halt on input $1$) is not recursive.
I've got an idea that indirect proof must work. Assuming ...
0
votes
0answers
40 views
Nash equilibria in 3-player game
Consider 3-player game.
Players $x,y,z$, each player has two strategies. $x$: $x_1$ and $x_2$, $y$: $y_1$ and $y_2$, $z:z_1$ and $z_2$.
The outcome of the game are represented by the triple ...
1
vote
1answer
40 views
Rice’s theorem and recursion theorem
Prove Rice’s theorem using recursion theorem.
I need some hints as to what must be done about it. Please use Davis' book notation: Computability, Complexity, and Languages, Second Edition: ...
-1
votes
0answers
17 views
How do you determine the matrix A for my network of pages using Linear Algebra (Google's PageRank algorithm)?
Think of ranking as a vector in R^Z, where Z is the total number of webpages on the web.
For a given network of Z web pages, let A = [a_jk(little)] be the matrix
a_jk(little) = { 1 if page k has a ...
1
vote
1answer
26 views
Binary Decision Diagram of $(A\Rightarrow C)\wedge (B\Rightarrow C)$?
I made a Binary Decision Diagram for $(A\vee B)\Rightarrow C$, which i think is correct.
Know i want o make a Binary Decision Diagram for $(A\Rightarrow C) \wedge (B\Rightarrow C)$ but i can't. I ...
5
votes
2answers
105 views
What are some interesting coding projects (doable in Java) that relates to group theory?
I would like some ideas of possible programs I can write in Java that involves some computational aspects of group theory. My only ideas so far is to write a program that computes the product of two ...
2
votes
1answer
16 views
If $\{w^k|w\in L\}$ regular implies L regular?
If L is a language and the language
$$\tilde{L}:=\{x^k,x\in L, k\in\mathbb{N}\}$$
is regular, does that imply that L is regular? ($|L|<\infty$ gives equivalence)
We came across this question when ...
1
vote
1answer
50 views
to find disconnected graphs
We know that if in a graph $G$, $e$ < $(n -1)$, then the graph is disconnected, where $e$ and $n$ are number of edges and number of vertices resp. Is there any other criteria to find out the ...
2
votes
1answer
53 views
An NFA with $\Sigma = \{1\}$ with $x^2$ accepting runs on strings $1^x$ for all $x \geq 0$ - how to construct?
One of my homework assignments requires us to construct an NFA over the alphabet $\{1\}$ which has exactly $x^2 + 3$ accepting runs over the input string 1^x for all $x \in \mathbb{N}$. Now, the +3 ...
1
vote
1answer
26 views
Are these two context free grammars equivalent?
Let Σ = {a,b}. A CFG for the language {a^nb^m | n > 2m} can be written as:
S-->aaSb
S-->A
A-->aA
A-->a
Would it be equivalent to write this CFG as:
...
1
vote
0answers
45 views
Multivariable asymptotic analysis?
Show that $k \ln k = \Theta (n)$ implies $k = \Theta (n /\ln n)$.
Thanks for the help.
11
votes
1answer
240 views
In how many ways we can place $N$ mutually non-attacking knights on an $M \times M$ chessboard?
Given $N,M$ with $1 \le M \le 6$ and $1\le N \le 36$. In how many ways we can place $N$ knights (mutually non-attacking) on an $M \times M$ chessboard?
For example:
$M = 2, N = 2$, ans $= 6$
$M = 3, ...
0
votes
1answer
46 views
Is the function $\lceil\lg \lg n\rceil!$ polynomially bounded?
I'm totally lost so please be really explicit in your answers. Thanks for the help.
Polynomially Bounded: $f(x)$ is polynomially bounded if for some constants $c$, $a$ and $x_0$, $$f(x) \le cx^a$$, ...
1
vote
0answers
28 views
is the $d$-dimensional arrangement of Trees still $NP$-hard?
The $d$ dimensional Arrangement Problem for general graphs is known to be $NP$-hard since the special case $d=1$ (OLA) already is (Garey et al, [1976]). For Trees however, the one dimensional case can ...
1
vote
2answers
36 views
Decimal Floating Point to Shortest Binary
Might be more of a Comp Sci question so apologies if it's not appropriate.
Basically I have a range bounded by two floating-point decimals <1. I need to find a short binary number lying between ...
0
votes
1answer
26 views
Given a DFA $\mathcal{M} = (S, \Sigma, q_0, \delta, F)$, is there an algorithm that finds the pumping length of $L(\mathcal{M}$)?
This question has been bugging me for a while, and I'm curious what such an algorithm would look like, if it exists. My guess is that it does exist, but I'm not sure how it would look.
2
votes
3answers
39 views
Polynomial bounds?
Q1: Is the function $$\lceil{\lg n}\rceil!$$ polynomial bounded?
Q2: Is the function $$\lceil{\lg\lg n}\rceil!$$ polynomially bounded?
$$\lg = \log_2$$
Polynomially bounded: $f(n)$ is polynomially ...
1
vote
0answers
13 views
Prefix relation on words in $\Sigma^*$ - why does a maximum element imply that the prefix relation is a linear order?
I'm currently preparing for a test, and I'm having trouble understanding one of the preparation questions. The question is as follows:
Let $\Sigma$ be a finite alphabet. The prefix relation on words ...
3
votes
1answer
131 views
diameter and radius of a regular graph
I am trying to find the radius and diameter of a regular graph $G$ with $d(v_i) < (n-1)/2$. I know for $d(v) \geq (n-1)/2$, $\rm{diam}(G) \leq 2$ and $\rm{radius}(G)=\rm{diam}(G).$ If we are not ...
-1
votes
0answers
100 views
C++ Polynomial Multiplication [closed]
\begin{eqnarray} \text{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~} \end{eqnarray}\begin{eqnarray}
\text{IF YOU HAVE A QUESTION, THEN ASK AND I CAN ...
0
votes
1answer
21 views
closest pair in N-Dimensional
I have to find the closest pair in n-dimension, and I have problem in the combine steps.
I use the divide and conquer.I first choose the median x, and split it into left and right part, and then find ...
0
votes
1answer
24 views
How can i bound the largest edge length of an $n$-point metric in $O(n)$?
For a given metric $d$ on a finite (vertex) set $V$, how can I bound the largest edge length in $O(|V|)$? While (wlog) assuming that the smallest edge length is at least $1$.
0
votes
0answers
28 views
Describing a multitape Turing Machine that enumerates the set of $i$ such that $w_i$ is accepted by $M_i$
I am having trouble with this problem. It regards the theory of Turing Machines.
Describe a multitape Turing Machine that enumerates the set of $i$
such that the word $w_i$ is accepted by the ...
2
votes
1answer
126 views
Best and most efficient way to numerically compute $e$?
There are many well-known methods for efficiently numerically computing $\pi$, such as Chudnovsky's Method or perhaps Gauss-Legendre's algorithm.
I was wondering what the best method for computing $e$ ...
0
votes
1answer
31 views
Are these two definition equivalent?
$f(n) = \mathcal{o}(g(n))$ if
for any constant $c$, there exists some constant $n_0$ such that
$0 \le f(n) \le cg(n), n \ge n_0 $
$f(n) = \pi(g(n))$ if
for any constant $c$, there exists ...
