All mathematical questions about Computer Science, including Theoretical Computer Science, Formal Methods, Verification, Logic in Artificial Intelligence, and Numerical Analysis
1
vote
1answer
46 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
52 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
54 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
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
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 ...
1
vote
3answers
69 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
37 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
28 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
82 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
99 views
+200
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
52 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
45 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
38 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
39 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
79 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
16 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
107 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
49 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
43 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
27 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
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 ...
0
votes
1answer
24 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
96 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
179 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
27 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
10 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
37 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
130 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 ...
0
votes
0answers
17 views
Questions about the Bresenham Line Algorithim?
For my AP Computer Science class we had to write a code illustrating the effectiveness of Bresenham Algorithm, an optimization type problem.
I have some questions about the algorithm.
Let us say ...
0
votes
1answer
27 views
Recurrence relations by forward substitution help
My question is to solve the following using recurrence relation forward substitution then verify using mathematical substitution:
$T(n) = 2T(\frac{n}{3})$ for $n > 1$, where $n$ is a power ...
2
votes
1answer
24 views
Help with Recurrence relations forward substitution
Thanks in advance to anybody who can help,
The question: solve by recurrence relation using forward substitution and verify by mathematical induction.
$T(n) = 2T(n/7)$ for $n > 1, n$ is a power ...
0
votes
1answer
167 views
Godel number and expressibility [duplicate]
how to show that these properties of strings of symbols are expressible:
1) being a term,
2) being a formula
3) being a sentence
4) being a proof in PA
and where a property (i.e., predicate) P of ...
11
votes
3answers
170 views
What is necessary to exchange messages between aliens? [closed]
Lets assume that two extreme intelligent species in the universe can exchange morse code messages for the first time. A can send messages to B and B to A, both have unlimited time, but they can not ...
6
votes
1answer
52 views
Can the rank of the homology group of an abstract simplicial complex be computed in polynomial time?
I want to write a function that does the following:
Input:
An integer $n$
A function $f$ that maps nonempty subsets of $\{1, \dots, n\}$ to "yes" or "no" such that (a) every singleton set gets ...
0
votes
0answers
12 views
Is there a formula to get the changes in ship course from wind and current?
Anyone know how to get the changes of degree's in ship course that affected by wind and current?
I thinks it maybe related with the speed and degree of WIND and CURRENT. But I don't know how to ...
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
votes
0answers
17 views
Sub-expressions of an expression using lists as representation in SCHEME [closed]
I have an assignment due today on SCHEME programming
and I am kinda stuck so close to the solution.
I have spent so much time on this assignment it's ridiculous.
So to the point:
Given a list ...
1
vote
1answer
47 views
how discrete mathematics is related to computerscience
I have this basic question for sometime since i came across discrete mathematics, hence this question. How discrete mathematics is related to computer science. How its notions are used in the field of ...
1
vote
1answer
131 views
Expressibility and numbering
A predicate $P$ is expressible (in PA) if there exists a formula $\phi(x_1,\ldots, x_n)$ of $L_A$ such that for all $m_1,\ldots, m_n$ elements of $\mathbb{N}$, we have that $P(m_1,\ldots, m_n)$ holds ...
1
vote
1answer
151 views
Second incompleteness and Model theorey
If we let $T$ be a consistent theory in the language of arithmetic $\mathcal{L}_A$ theory extending Peano Arithmetic — with specified numbering of formulas $\left[\cdot\right]$ and suppose that ...
