All mathematical questions about Computer Science, including Theoretical Computer Science, Formal Methods, Verification, Logic in Artificial Intelligence, and Numerical Analysis
2
votes
1answer
27 views
Books on computational complexity
Can anyone recommend a good book on the subjects of computability and computational complexity? What are the de facto standard texts (say, for graduate students) in this area?
I've heard a thing or ...
1
vote
1answer
33 views
2-colorable belongs to $\mathsf P$
To show that 2-colorable belongs to $\mathsf P$, I have a straightforward mental description in mind that I don't think will be considered as a formal proof. Hence I am interested to know how this ...
6
votes
0answers
58 views
Mathematics of Torrenting
It is more or less common knowledge that a bittorrent network has the potential to be much faster than direct downloads, but I have never seen any real math describing why, or any theoretical bounds ...
-1
votes
2answers
54 views
How to find the amount to added every month or year to get the required amount after certain years?
I want to do a Java application for which after giving the current savings, and the rate of interest and and required amount after specified no of years, it has to show how much a person has to earn ...
4
votes
2answers
144 views
Going back to the basics?
I'm currently in my second year of college majoring in comp sci and I haven't really taken any math courses yet except pre-calc. In high school, I thought of myself as a pretty good math student and ...
0
votes
2answers
43 views
Books for Geometry processing
Please suggest some basic books on geometry processing.
I want to learn this subject for learning algorithms in 3d mesh generation and graphics.
Please suggest me subjects or areas of mathematics i ...
0
votes
0answers
14 views
Computation Tree Logic, Check for Equivalence
I have to find out which of the Computation Tree Logic (CTL) formulas below are equivalent, any ideas ?
A: means along all paths
E: means along at least one path
X: means next state
F: means ...
0
votes
0answers
16 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
59 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 ...
1
vote
1answer
81 views
+50
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)$ ...
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 ...
3
votes
2answers
55 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 ...
3
votes
1answer
59 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 ...
0
votes
1answer
34 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
2answers
59 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 ...
1
vote
3answers
72 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 ...
-6
votes
0answers
44 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
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
2answers
87 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)$
1
vote
2answers
120 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 ...
2
votes
1answer
54 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, ...
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 ...
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
42 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
vote
2answers
83 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 ...
-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
113 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 ...
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
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
1answer
51 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 ...
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.
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
29 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 ...
1
vote
1answer
29 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 ...
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
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
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 ...
-1
votes
0answers
101 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
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
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 ...
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 ...
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 ...
0
votes
0answers
11 views
Number Theoretic Gaps for Shell Sort
Has anyone investigated the efficiency of certain number theoretic gaps for shell sort? I'm thinking the Fibonacci sequence may be interesting, or maybe the prime numbers since small coprime sets ...
1
vote
2answers
41 views
Could graph theory aid in the understanding of comparison sorting algorithms?
I am interested in computing the exact number of comparisons that are needed to sort a list. See this wikipedia article.
Up to $n=15$, we know how many comparisons between elements one must make to ...
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 ...
2
votes
1answer
46 views
Unique sequences from different sets
I am given $n$ sets with a selection of $m$ elements, such as:
$$S = \{\{0\}, \{1, 2, 3\}, \{1, 2, 3\}, \{3\}\}$$
I am trying to calculate the number of unique sequences that contain all elements ...
