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

2
votes
1answer
46 views

Generating elements of a Galois Field using an irreducible polynomial

I am practicing some cryptography problems and I am having problems with one involving Galois Fields and irreducible polynomials. Here is the problem: Using the irreducible polynomial $f(x) = x^5 ...
0
votes
2answers
67 views

Can someone clarify the notation of x $\equiv$ -8 $\equiv$ 6 ($\bmod$ 7)

This is an example from Discrete Mathematics and its Applications This is example 1 that this example references And here's Theorem 1 that the example references Example 1 makes sense. We have ...
2
votes
0answers
60 views

Graph Algorithm and Cycle Detection

In $O(|V|+|E|)$, we can detect whether a Directed Graph has a cycle or not. ---> True In depth-first seach on DAG, there is no Back Edge. ---> True With known Number of Edges, in $O(|V|)$ and not ...
2
votes
1answer
41 views

Theory Of Computation - recognizable and decidable

How to prove that for any language $A$, if $A$ is recognizable and $A \leq_m A^\complement$, then $A$ is decidable. I know this theorem - A language is decidable iff both it and its complement are ...
1
vote
2answers
34 views

Graph with Cycle and Two-Colorable

i think if the graph G has an odd cycle, it's not two-colorable, otherwise it can be two colorable. i read in one notes that the following is True: we couldent two-colorable any graph G that has ...
0
votes
1answer
44 views

Decision Problems and Poly Time

We have Two Decision Problem A and B. we know A is NP-Complete, but B can be solved in $O(n^2lg^4n)$, and we know $B \leq_pA $ (i.e each problem of B can be convert to a problem of A in Polynomial ...
1
vote
1answer
52 views

Asymptotic and 3-SAT problem in Algorithm Course

my TA says just one of the following is True, anyone could describe me some detail about following three lines? 1- if $f_i$ be a function of natural numbers to natural numbers and $f_i(n)=O(n)$ then ...
2
votes
4answers
34 views

How did author reach the conclusion tm $\equiv$ 0($\bmod$ m)?

This is a proof of a theorem from my book, Discrete Mathematics and its Applications Here is theorem 6 of Section 4.3 The first part of the proof, "because gcd(a, m) = 1" makes sense because the ...
0
votes
1answer
36 views

How does author reach step of $sa + tm \equiv 1 \pmod m$?

This is a proof of a theorem from my book, Discrete Mathematics and its Applications Theorem 1 If $a$ and $m$ are relatively prime integers and $m>1$, then an inverse of $a$ modulo $m$ ...
0
votes
1answer
36 views

Prove the following context-free language is generated by this grammar.

I would like to prove the context-free language $$ \mathcal{A} = \{ w\#x ~:~ w^R \text{ is a substring of $x$ for } w,x \in \{0,1\}^* \}, $$ has the context free grammar \begin{align*} ...
0
votes
1answer
39 views

Prove the following language is context free

I can find many proofs for how a language is not context free using the pumping lemma. But I am not sure how to definitely prove a language is context free. Consider this language: $$\mathcal{A} = \{ ...
1
vote
1answer
21 views

Language described by inverting accepting states of NFA

What is the formal language described by inverting accepting states of NFA? By inverting, I mean that rejecting states become accepting states and accepting states become rejecting states. Is there a ...
1
vote
4answers
79 views

How to prove this modular multiplication property to be true?

I am watching a youtube video on modular exponentiation https://www.youtube.com/watch?v=sL-YtCqDS90 Here is author's work In this problem, the author was trying to calculate $5^{40}$ He worked ...
1
vote
1answer
39 views

How to get to the next step in the procedure?

This is from https://courses.cs.washington.edu/courses/cse311/14au/slides/lecture12-filled.pdf, This procedure is used to solve a modular exponentiation problem, say Here is the procedure How ...
0
votes
0answers
18 views

How to prove this property for repeated squaring?

This is from https://courses.cs.washington.edu/courses/cse311/14au/slides/lecture12-filled.pdf This property is used for modular exponentiation, that is to do a problem like this (from slide 6) ...
0
votes
0answers
47 views

How are these terms algebraically equivalent?

This is from https://courses.cs.washington.edu/courses/cse311/14au/slides/lecture10-filled.pdf slide 25. This is the definition of a is congruent to b modulo m. (from slide 24) This is an example ...
1
vote
1answer
32 views

First Order Logic and Some Validity Checking

I'm sorry for put an image insted of typing it... infact this is an 2012-exam on Logic. i found the solution of this quiz that wrote by one TA. he wrote just the second line is not valid logically in ...
0
votes
0answers
15 views

Design a non-polynomial time PAC algorithm that learns the class of all boolean circuits?

Setting. Suppose we relaxed the constraint that PAC learner uses polynomially evaluable hypothesis class $\mathcal{H}$. Instead let $\mathcal{H}$ be the class of all Turing machines (not neccessarily ...
1
vote
2answers
69 views

User defined sine function in python using series expansion

Applying a Maclaurin expansion to the sine function gives ...
0
votes
3answers
58 views

Period of a simple pendulum

I'm writing a short program to simulate a simple pendulum. The equations of motion are $$\frac{d\theta}{dt}=\omega$$ $$\frac{d\omega}{dt}=-\frac{g}{r}\sin\theta$$ For some small time step $dt$ the ...
0
votes
1answer
16 views

CompSci Math Proof Contrapositive Method

The question is "Using the contrapositive prove for all integers n, if n^2 is a multiple of 5 then n is a multiple of 5". I know that the contrapositive is "if n is not a multiple of 5 then n^2 is not ...
1
vote
1answer
24 views

What is the meant by node role in Graph Theory?

Suppose that I have a graph with some numbers of nodes, and each node connected to other node with a relation, My question what is the node roles here ? Is the role = the relation type, weighted ...
1
vote
1answer
624 views

Strange behavior with Xor, And, Or on Offsets of Integers

I thought of a problem today: given a range of integers $[a, b]$, for all pairs of integers $(x, y)$ in that range, what is the number of them such that $x$ op $y \in [a, b]$, where op is one of {xor, ...
1
vote
1answer
64 views

Runge Kutta complicated equation

Hi I need some help (Or at least a point in the right direction!) with solving the equation below. I've been at it for a while now and I'm not getting anywhere, as my knowledge of solving differential ...
1
vote
2answers
46 views

What am I doing wrong when multiplying binary numbers together?

This is from Discrete Mathematics and its applications I was able to get sum pretty easy. I am trying to follow this example in the book to get the product of the two binary numbers Here's my ...
0
votes
1answer
34 views

How to give a big O estimate/visualize for these while loop?

This is from Discrete Mathematics and its applications I am currently working on problem 4. I was able to see that for problem 2, that one operation one will run n times for every n(meaning in ...
1
vote
1answer
41 views

Growth faster than polynomial, slower than exponential.

Assume $F(n)$ is a positive function. If $F$ is growing faster than a polynomial then is it growing exponentially fast? Is this statement true? Can we find a function $F(n)$ such that ...
0
votes
1answer
29 views

For the following functions, the domain and codomain is {a,b,c,d} which ones are one to one and which are onto? Give reasons for each

For the following functions, the domain and codomain is {a,b,c,d} which ones are one to one and which are onto? Give reasons for each. a) f(a) = b, f(b) = a , f(c) = c, f(d) = d b) f(a) = b, f(b) = ...
0
votes
1answer
56 views

When drawing a recursion tree, how does b effect the tree if it is given?

So the problem I have is T(n) = T(n/8) + T(7n/8) +5n. I need to draw a recursion tree to prove that T(n) = Ө (n log 8 n ). I also need to show that T(n) = O (n log 8 n ) and T(n) = Ω (n log 8 n ). ...
0
votes
1answer
38 views

Adding/Subtracting in binary and hexadecimal number systems?

I have two numbers(in decimal): M = 3892.74 N = 9341.65 I am trying to add and subtract them in binary numbers and then in hexadecimal numbers. I manage to ...
0
votes
1answer
33 views

Suppose A = {1,3,7,11} and B = {3,7,12} . Calculate the following showing the step-by-step process of your calculations

Suppose A = {1,3,7,11} and B = {3,7,12} . Calculate the following showing the step-by-step process of your calculations a) |A ∪ B| b) |A| + |B| - |A ∩ B| c) A X B Not sure if I'm doing these ...
0
votes
1answer
32 views

In the following problems the universe is R. Determine the following

In the following problems the universe is R. Determine the following. a)[0,3] ∪ [2,6] b)[0,3] - [2,6] c)[0,3] ⊕ [2,6] So I just need someone to confirm if I am correct or not in my solution.. I ...
8
votes
1answer
756 views

Three variable, second-degree symmetric Diophantine equation

Find integers $f,g,h$ such that $3(f^2+g^2+h^2)=14(fg+gh+hf)$. You can do it using a computer or by hand. I tried this problem for ages, got nowhere. Unfortunately I don't know how to program, but I ...
1
vote
2answers
31 views

Induction and Statements

I'm having trouble with induction in my discrete math course. We are given a statement we know (∀k)(P(k)⇒P(k+2)), where k is an element of N. After that we have a series of statements, I'll give one ...
1
vote
3answers
74 views

Examples (trivial and non-trivial) of computable functions whose inverse is not computable

Can you give some examples (some trivial and some non-trivial) of computable functions whose inverse is not computable?
0
votes
0answers
41 views

How to show that $2^x$ is not in $O(x^2)$?

This is from Discrete Mathematics and its Applications I am working on 2e. I knew right off the bat from previous computer science courses that 2^x is not in O(x^2). I am having a difficult time ...
0
votes
1answer
53 views

Would the greedy algorithm use the fewest coins for all of those denominations?

This is from Discrete Mathematics and its Applications. Here is the book's section on the greedy alorithm for counting change Here is the problem I am working on, 54(uses 52) Here is what I got ...
0
votes
1answer
31 views

For each of the following set expressions, say what set the expression denotes. In other words if the se…

For each of the following set expressions, say what set the expression denotes. In other words if the set is finite, give an explicit listing of its elements.. Assume A = {2,3,4} a) {x:x ∈ Z, -3.5 ...
0
votes
1answer
28 views

These sets are presented in lists of element form. Write the sets in the form of the set generator

These sets are presented in lists of element form. Write the sets in the form of the set generator a) {0,3,6,9,12} b) {-3,-2,-1,0,1,2,3} So... would the solutions be: a) {n*3: n=0,1,2,3,4} b) ...
0
votes
1answer
41 views

Rewriting statements with quantifiers to full detail

The question i have for an assignment is the following Let P and Q be predicates on the set S, where S has two elements, say, S = {a, b}. Then the statement ∀xP(x) can also be written in full detail ...
4
votes
2answers
97 views

What is the algorithm hiding beneath the complexity in this paper?

So, I am a computer scientist (at least, I'm working to become one..) and I asked a question on here concerning some mathematics behind the Mandelbrot set. A reply I recieved pointed me to this paper. ...
0
votes
1answer
44 views

Summation of harmonic series. [closed]

I'm trying to figure out how to answer this linear algebra question and can't figure it out. Can someone please explain it to me? Thanks a bunch! Here's the questions:
0
votes
1answer
36 views

These sets are written in set generator form. Write the sets in list of elements form.

These sets are written in set generator form. Write the sets in list of elements form. a)$\{\frac{1}{n}: n = 1,2,3,4\}$ b)$\{n^2-n: n = 0,1,2,3,4\}$ I have no idea how to even attempt this...If ...
5
votes
1answer
35 views

Formal Grammar generating $0^p$

Exercise: Find the formal grammar generating the language ${0^p}$ in the binary alphabet for $p$ prime. I have absolutely no clue where to start, nothing of the 'usual' construction strategies seem ...
3
votes
2answers
50 views

Fibonacci recursive algorithm yields interesting result

After writing a program in Java to generate Fibonacci numbers using a recursive algorithm, I noticed the time increase in each iteration is approximately $\Phi$ times greater than the previous. ...
0
votes
1answer
45 views

Can anyone explain the average case in insertion sort?

I am not sure if this question is off topic or not but a question like this has been asked on this site before - Insertion sort proof Here is an example of insertion sort running a on a set of data ...
0
votes
1answer
24 views

Is A+D-C-B really the correct formula to get sum over rectangle in summed area table?

Recently, I was taught about the summed area table (integral image) concept. This table represents a matrix, usually an image, so that every ${SAT}_{ij}$ (I used SAT as summed area table) equals to ...
1
vote
1answer
115 views

Induction Proof Check: For a binary tree T, Prove that the number of full nodes in T is always one less than the number of leaves in T.

This is a slight variant on a very common beginner's problem. I think I've got it figured out, but I wanted to make sure I actually proved what's being asked. We define a binary tree $T$: (a) A tree ...
1
vote
2answers
31 views

Prove that a recurrence relation (containing two recurrences) equals a given closed-form formula.

Prove that $a_n = 3a_{n-1} - 2a_{n-2} = 2^n + 1$ , for all $n \in \mathbb{N}$ , and $a_1 = 3$ , $a_2 = 5$ , and $n \geq 3$ Basis: $a_1 = 2^1 + 1 = 2 + 1 = 3$ $\checkmark$ $a_2 = 2^2 + 1 = 4 + 1 = 5$ ...
1
vote
1answer
18 views

Big O and Big Omega Proof with lg base 2

Hello I am a beginner to this kind of notation and I would greatly appreciate an explanation which is easy to understand. I need to prove $$ \log_2(6 + \frac1x) = O(1) $$ and $$ \log_2(6 + ...