# Tagged Questions

All mathematical questions about Computer Science, including Theoretical Computer Science, Formal Methods, Verification, Logic in Artificial Intelligence, and Numerical Analysis

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 ...
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 ...
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 ...
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)\}$$
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 ...
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 ...
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.
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 ...
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 ...
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)$
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 ...
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, ...
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 ...
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 ...
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: ...
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 ...
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 ...
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 ...
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 ...
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: ...
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 ...
0answers
45 views

### Multivariable asymptotic analysis?

Show that $k \ln k = \Theta (n)$ implies $k = \Theta (n /\ln n)$. Thanks for the help.
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$$, ...
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 ...
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 ...
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 ...
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.
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 ...
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 ...
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 ...
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$.
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 104, "mathjax_display_tex": 10, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9138002395629883, "perplexity_flag": "middle"}