All mathematical questions about computer science, including theoretical computer science, formal methods, verification, and artificial intelligence. For questions about Turing computability, please use the (computability) tag instead. For numerical analysis, use the (numerical-methods) tag. For ...

learn more… | top users | synonyms

1
vote
2answers
30 views

equivalent regular expr

Given a regular expression $r_1$, is $(r_1^*)^* = (r_1^*)$. I know that this is true but I do not know how to prove it. Would it be adequate to set $r_1$ to a regular expression such as $(a+b)$ for ...
2
votes
1answer
83 views

Is [a, a[ empty?

Is the segment $[a, a[$ equivalent to the point $\{a\}$ or the empty set $\varnothing$? Can one or other be formally proved? I was wondering because in computer science it is the empty set, as the ...
0
votes
1answer
50 views

b tree least upper bound

Hi I have an university assignment question that I can't fully understand. My tutor doesn't understand some of the terminology and my lecturer in the subject is not particularly forthcoming. The ...
0
votes
1answer
16 views

Is there a Relationship Between Multi-Valued Logic and n-Satisfiability?

Is binary (Boolean) logic related at all to the two-satisfiability problem? And is ternary logic related in some way to the three-satisfiability problem? Would it follow then that if one were to ...
2
votes
0answers
45 views

In a directed graph with $n \geq 2$ nodes, if two different nodes reaches $n$ nodes, then this graph has a directed cycle.

I think this statement is true because if first node can reaches every other node (including second node) and second node can reaches every other nodes (including first node), then first node and ...
1
vote
0answers
20 views

Rightmost derivation word aaaccb

I have got these context free grammar: $S \implies aSA | a \\A \implies Ab|c$ The goal is find rightmost derivation of word $aaaccb$ a draw derivate tree, which corresponding with this derivation. ...
0
votes
1answer
21 views

Context-free grammar and regular expression

I have got these Context-free grammar/regular expression: (1) $abba^{*}$ (2) $abb(a+b)^{*}$ (3) $a^{*}ba^{*}ba^{*}$ (4) $S \implies abA \\ A \implies Aa|b$ (5) $S \implies aS|bA \\ A \implies aA|...
0
votes
1answer
27 views

Is every decidable language accepted by a turing machine? [closed]

I am taking a cs class and the lecture slides are not very complete on this topic. can somebody clarify? thank you
2
votes
3answers
38 views

Naming binary strings

Given a string of 1's and 0's, containing the same number of 1's as 0's, is there a way to uniquely "name" each string with a number such that it is computationally easy to go between this "name" and ...
1
vote
0answers
57 views

How Do You Write Mathematical Proofs | Linear Algebra (I have no idea what I am doing…) [closed]

I am a Computer Science student, and right now I am taking a 15 week Summer class on Linear Algebra. This course will cover proof writing (basic) and I have never written a proof like these in my life!...
1
vote
0answers
25 views

Discrete Mathematics: Prove Expression Is Even

I'm brushing up for my Discrete Math final exam, and would like to know if the following proof is valid... Prove by direct proof that $a^2-5a+8$ is even for any integer $a$. Proof: By ...
2
votes
1answer
36 views

Turing Machine Diagram, one Solved Problem ?!

The following Diagram Gets binary number $x$ and produce $x+1$. complete it: the book solution is says first line is the answer. any hint or idea for completing this TM?
0
votes
1answer
21 views

Number system question

Is it true that if we are given a number system with base 3, mantissa 2, $-1 \le p \le 1$, determined by $$\pm 0.d_1 d_2 \times 3^p$$ where each number is normalized, unless it is zero, then the ...
2
votes
1answer
52 views

Longest Common Prefix among $n$ strings with length $k$

Suppose I have a set of alphabet $\Sigma = \{ A,B,\ldots,Z \}$ with $|\Sigma|=26$. I am generating a set of $n$ random strings $S$, with each string of length $k$ from the alphabet (for the random ...
1
vote
0answers
45 views

Discretizations of Differential, Geometric and Topological Notions

I have noticed a recurring theme in Graph Theory / Theoretical Computer Science (abbreviated GT and TCS throughout this post) in that notions typically belonging to differential calculus / geometry / ...
2
votes
0answers
79 views

What is the relationship between Realizability and the Curry-Howard isomorphism?

I have recently been studying the Curry-Howard isomorphism/correspondence. My sources have primarly been Sørensen [1] and Girard [2]. Realizability is introduced here in the form of Kleene's ...
1
vote
1answer
27 views

Showing equivalence of 2 Big O notations

I have the task to show that the following two big O definitions are equivalent. My first thought was that it has to be equivalent because the set of natural numbers excludes all broken rational ...
0
votes
1answer
22 views

Demonstrate that a language is semi-decidable

I need some help to demonstrate that this set below is decidable, semi-decidable, or undecidable. Here's the set: H = {p| |Images(fp)| >= 10} explanation: an ...
0
votes
0answers
14 views

Show how to construct new AKE protocol

I'd appreciate if someone could help me with this exercise (image is for text and notation): http://i.imgur.com/S6xmkEX.png Could someone give me a hint, what am I supposed to do to show it?
1
vote
0answers
34 views

Find $A^n$ for n=0,1, and 3: Languages and Finite State Machines

The question is: Let $A$={11,00}. Find $A^n$ for n=0,1, and 3. Would i be right in thinking that $A^0$ = {λ} $A^1$ = {11,00} $A^3$ = {111111,111100,110011,110000,000011,000000,001100,001111}. if ...
0
votes
3answers
34 views

What does the algorithm s = s + k * k do?

I just finished an exam in my math class and I did well except for one question that I just can't get out of my head, it seems simple but I just can't figure it out: PROBLEM: ...
2
votes
0answers
20 views

levenshtein distance: iterative vs single calculation

I had a list of 1100 words and sought to cluster them based on a levenshtein distance of 2. This reduced the list to 900 words. Running the calculation again reduced the number to roughly 800, and ...
0
votes
1answer
31 views

Algorithm to find password from hash value

I'm currently trying to solve this exercise (sorry for link to image, but there's a bit text): http://i.imgur.com/ETaCK0H.png But there's a few things in the exercise I don't understand. For example,...
8
votes
1answer
464 views

What is the current state of formalized mathematics?

Russell and Whitehead famously tried to actually create and use a formal system to explicitly develop formal mathematics in their work, "Principia Mathematica." Much more recently, with the aid of ...
0
votes
2answers
42 views

Bit increase when averaging?

I have a given number $N$ of binary numbers, that are stored using a given number $B$ of bits. $B$ is the same for all the numbers. For example, thease values where $N = 4, B = 4$. ...
12
votes
1answer
284 views

How to formulate the P v.s. NP problem as a formal statement inside the language of set theory?

I've read a lot that some computer scientists believe that P v.s. NP could turn out to be independent of ZFC. The thing that puzzled me is how to formulate this inside the language of set theory? I ...
2
votes
0answers
17 views

Find Theta Class of T(n) = T(3n/4) + T(n/6) +5n [duplicate]

I'm not quite sure I can apply the Master Theorem to T(n) = T(3n/4) + T(n/6) + 5n. It is not in the normal form of T(n) = aT(n/b) + f(n). Is it possible to apply the MT to it? If not, can the ...
1
vote
0answers
44 views

Arc length using bisection error - root finding methods.

Apologies if this is poorly formatted - it is my first time posting a question. I'm trying to find evenly spaced arc lengths along a function (in this case a sinusoid) using the bisection method. ...
1
vote
1answer
22 views

Hilberts tenth problem over $\mathbb R$ with coefficients in $\mathbb Q$

Consider the following decision problem: Given: An equation $f(x_1, \dots, x_n) = 0$ where $f(x_1, \dots, x_n)$ is a polynomial with variables $x_1, \dots, x_n$ and coefficients in $\mathbb Z$. To ...
1
vote
2answers
31 views

Find particular pair of values that satisfy equation

I think this is might be a fairly simple problem, but I can't for the life of me think of a way to approach it. In this equation, for a given $x$ and $y$, with $x,y,a,b$ non-negative integers: $x2^a ...
0
votes
1answer
37 views

Course or book - Math Foundations in CS

I want to improve my math skills, now I'm trying to find good route for this purpose. I'm using Khan Academy, and recently found "CS103 - Mathematical Foundations of Computing" course which looks good ...
1
vote
1answer
50 views

What formal systems are various programming paradigms based on?

I heard that functional programming paradigm is based on lambda calculus and combinatory logic. If I am correct, lambda calculus and combinatory logic are formal systems. What formal systems are ...
0
votes
1answer
47 views

Solve $T(n)=16T(n/2)+2n^4$

Solve using the iteration method: $$T(n)=16T(n/2)+2n^4$$ My attempt: $$\begin{align} T(n) &=16\cdot16T(n/2^2)+2(n/2)^4+2n^4 \\ &=16\cdot16\cdot 16T(n/2^3)+2(n/2^2)+2(n/2)^4+2n^4\\ &...
1
vote
0answers
28 views

ternary string that contains only $0's$, $1's$, and $2's$

A string that contains only $0's$, $1's$, and $2's$ is called a ternary string. (a) Find a recurrence relation for the number of ternary strings that do not contain two consecutive $0's$. (b) What ...
0
votes
0answers
24 views

What does “symbolic computation” mean in this context?

From Wikipedia In computational mathematics, computer algebra, also called symbolic computation or algebraic computation is a scientific area that refers to the study and development of algorithms ...
1
vote
0answers
33 views

What is the root of first class object in programming languages?

What is the root of "first class object" of programming languages? (Also see https://en.wikipedia.org/wiki/First-class_function, and http://stackoverflow.com/questions/245192/what-are-first-class-...
0
votes
0answers
23 views

Help with a proof of the computability of the monus function by recursion

Reading a text on computability by a guy called Cutland, and he basically asserts the following, which is suppose to be a proof by recursion that x ∸ 1 is a computable function: (1) 0 ∸ 1 = 0 (2) (x+...
-1
votes
1answer
38 views

If NP-complete, prove another is also NP-complete

I've been trying to work on this problem but I don't really know where to start and can't find any resources online. Would it be possible for someone to guide me through step by step.
0
votes
0answers
12 views

Minimum number of pages in a B-Tree of order n?

How can I calculate the minimum number of pages in a B tree of order n and height 3? 1st level = 1 page 2nd level = 2n+1 pages 3rd level = ? 3rd level is 1? Or how many pages?
0
votes
1answer
23 views

Time complexity for loops

I am having some trouble figuring out the time complexity in big theta notation of the following algorithms. Any help is appreciated. int j = 1; int n = any; ...
0
votes
1answer
53 views

Algorithms - Finding Clique of size n in a Graph

I have the following statements (NOTE: $\bar x$ means the complement of $x$): $(x_1 V \bar x_2 V x_3) ∧ ( \bar x_1 V x_2 V x_3) ∧ (x_1 V \bar x_3) ∧ (x_2 V \bar x_3 V x_4)$ I need to do the ...
1
vote
4answers
56 views

How to check if $n!$ is $ O(2^n)$

How can I check if $n! \in O(2^n)$? The definition of $f$ being $O(g)$ is $f(n) \le c g (n)$, where $c>0$. So it would mean $n! \le c 2^n$. What is the clearest way to solve this? (As I am ...
0
votes
1answer
39 views

Hash functions - show how to find collisions

I'm currently trying to solve this exercise (sorry for image, it's for the notation and I'm not allowed yet to post images directly): I have read the exercise question a lot of times and I think I ...
0
votes
0answers
18 views

Balancing integer bins to have a certain summation

Assume that we have bins $$ B_1, B_2 ..., B_n $$ There exists integer bin values $$ V_1, V_2 ..., V_n $$ Let $$ Total_{V} =\sum_{i=1}^{n} V_i$$ There then exists weights ( $ W $) of each bin to ...
1
vote
0answers
14 views

Is $O(x^2)$ equal to OR a tighter bound for $O(x(x-y))$ if $x, y >0$ and $x>y$ alway hold?

In the question, $O$ is the Big-O notation, please see https://en.wikipedia.org/wiki/Big_O_notation. $x$ and $y$ are variables. Here, let me give you an example showing there exist such questions in ...
0
votes
0answers
20 views

Is the Antikythera Mechanism Turing-Complete?

Is the following Turing-complete? https://en.wikipedia.org/wiki/Antikythera_mechanism As in, it possible to perform all of the operations of a Turing-machine, albeit with finite memory, with this ...
0
votes
1answer
22 views

Encryption - show probability for obtaining specific bit

Assume a person A encrypts a message which consist of the bits m1, ..., mn. The person is using the one-time pad algorithm. Another person B intercepts the ciphertext and we suppose he knows that mi (...
0
votes
0answers
11 views

Does the Method of Compliments also work for (non-integers)?

I have only ever seen Method of Complements applied to integers, never non-integers (most notably in the field of modern programming) However curiosity got the better of me, and I was wondering if ...
0
votes
1answer
37 views

Big O for factorials

Hello I have trouble proving:$$(n+1)!\notin O(n!)$$ My first step is the following: $$(n+1)!-cn!\le0$$ Can you please help me with the next step?