All mathematical questions about Computer Science, including Theoretical Computer Science, Formal Methods, Verification, Logic in Artificial Intelligence, and Numerical Analysis
0
votes
0answers
3 views
Is there a simpler way to describe this context-free language?
I have the following context-free grammar and want to describe it in language/set notation:
$S \rightarrow {\tt a} \, C \, {\tt b}$
$C \rightarrow {\tt c} \, S \, | \, S \, | \, \varepsilon$
So, a ...
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
22 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 ...
1
vote
1answer
25 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
43 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
15 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
156 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
156 views
What is necessary to exchange messages between aliens?
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
49 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
10 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
28 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
45 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 ...
