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.

learn more… | top users | synonyms

-1
votes
0answers
17 views

Help with Java coding [on hold]

I've recently started taking an intro java class(I apologize in advance for my lack of knowledge) and I've run into some trouble. I was required to make a program that contains 3 data fields, 2 ...
0
votes
0answers
11 views

Need help to write the algorithm

I want to write an algorithm, that sorts the following list, using the Insertion Sort: 50, 200, 1, 102, 8, 52, 69 Could you explain me how I could do this?
1
vote
2answers
17 views

Pumping Lemma proof

We have a language $$ L = \{\text{w element of } \{a,b\}^* \mid \#(a,w) = \#(b,w)^2 \} $$ where $ \#(a,w) $ means the number of letters $a$ in $w$ I would like to show that this language is not ...
0
votes
2answers
23 views

How to show if a language is infinite, then there is no upper bound on the length of words in L?

L is a language over a finite alphabet. How to show that if L is infinite, then there is no upper bound on the length of the words within L? Can someone help me prove this.
0
votes
0answers
19 views

Can you use chinese remainder theorum to convert hex to dec in your head?

At one time I was able to convert hex to decimal in my head, using a trick I learned in college. I have not used it in years, and forgot how. Does anyone remember how to use the Chinese remainder ...
0
votes
0answers
20 views

How can I retrieve all the results in one go?

Please excuse me for posting this question here, but I'm just not sure where this question properly belongs; moreover, as I'm in search of a funded Masters or PhD in Mathematics abroad, perhaps this ...
1
vote
0answers
36 views

Algorithm to compute wether a stabbing line exists for a set of line segments

Let $S$ be a set of n segments in the plane. A line $L$ that intersects all segments of $S$ is called a traversal or stabber of $S$. Give an $\mathcal{O}(n^2)$ algorithm to decide if a stabber for $S$ ...
5
votes
1answer
39 views

FOL and Conjuctive Normal Form Conversion

I see the CNF from following firs order logic: $ \forall x [ \forall y [ \neg A(y) \vee B(x,y) \Rightarrow [ \neg \forall y B(y,x) ] ] $ is equivalent to : $ (A(f(x)) \vee \neg B(g(x),x)) \wedge ...
0
votes
1answer
19 views

How do I generate regular expression from this deterministic finite state automaton?

I want to create a regular expression from the following deterministic finite automaton: "abb" substring search How do I generate regexp from above dfa and what are the steps for doing so? ...
0
votes
1answer
20 views

The complexity of Depth First Search

Can anyone tell me what's the complexity of Depth First Search? I have no idea about what does mean by the complexity.
0
votes
4answers
56 views

Prove that $G$ has at least $q-p+c$ cycles.

I need your help with this question: Suppose that a graph $G$ has $p$ vertices, $q$ edges, and $c$ components. Prove that $G$ has at least $q-p+c$ cycles. I don't know how to prove that.
1
vote
1answer
27 views

Show that the language is not regular using Myhill-Nerode Theorem

I saw that similar questions have been answered on this site, but I've been unable to translate those answers to my problem. $$L=\{ww^R\mid w \in \{a,b\}^*\}$$ This is what I tried: BWOC, assume ...
0
votes
1answer
10 views

How to properly determine observations related to a Hidden Markov Model alike problem?

I got a an exercise problem which should be seen as a HMM scenario and argument some statements. However I'm quite confused about how to properly solve and argument my solutions. Problem tells: ...
-1
votes
0answers
20 views

if two languages can be recognized by the same nfa, are they the same language? [on hold]

What about a single state nfa that accepts, and has transitions to itself using input alphabet chars?
5
votes
1answer
40 views

Graph DFS, BFS and some inference

Suppose G is a connected, undirected graph with at least 3 vertexes. we know the order or visiting the vertexes in DFS and ...
0
votes
1answer
28 views

Is master theorem applicable to the recurrence relation $T(n) = T(n/2)$?

Is master theorem applicable to the recurrence relation $T(n) = T(n/2)$? I do not think it applies because there no $n$ term and there is no $n^k$ for a $k$ which would equal $0$.
1
vote
1answer
23 views

Base conversion between base r^3 to r^2

The problem asks the following: If $(\alpha2)_{r^3} = (r3\beta)_{r^2},$ find $\alpha, \beta,$ and r. First off, I assume $r^2$ > 3 and $r^3 > 2$. I know that $(r3\beta)_{r^2}$ = (10 _ _ _ _ ...
0
votes
0answers
9 views

Find the point where the greater growth rate surpasses the lesser one without graphing

I have 2 lines: f(x) = 2010x^2 + 1388x and g(x) = x^3 What's the strategy for finding a x1 >= 0 where g(x) becomes greater than f(x) for all x >= x1? If one DNE, how would I know?
0
votes
0answers
20 views

Average Memory Access Time Formula and Main Memory's Miss Penalty [closed]

There is this question regarding solving the AMAT(Average Memory Access Time) given these data: Legends: Cache Level 1 = L1 Cache Level 2 = L2 Main Memory = M L1, L2 and M's Hit Time are 1, 10 and ...
0
votes
1answer
23 views

Converting double precision IEEE 754 hex to base 10 with repeating decimals

The number is 0x4001 8CCC CCCC CCCC. So far I have the stored exponent as 1000000000 which equals ...
-4
votes
0answers
15 views

Solving following recurrences [closed]

Find the asymptotic order of the following recurrence, represented in big-theta notation $$A(n) = 4A\left(\frac{n}{2}+5\right)+n^2$$ $$B(n)= B(n-4)+ \frac{1}{n}+\frac{5}{n^2+6}+\frac{7n^2}{3n^3+8}$$ ...
-2
votes
0answers
22 views

count minimum spanning tree [closed]

if there is no three edges have the same length in a graph (but two edges can have the same length). How many di efferent MSTs can you have in the worst case? Give an example to show that How fast ...
1
vote
1answer
35 views

Applying the master theorem

State the asymptotic runtime found by the master theorem. If the master theorem does not apply state why: 1) $T(n) = $T($n/3)$ 2) $T(n)= $ $5T$($2n/5$) + $n$ 3) $T(n) = 4T(n/2) +15n^3 + 4n^2 +n+4$ ...
0
votes
0answers
39 views

Rewriting a function to speed up computation

the purpose of this question is to find the fastest way to calculate a function on a (x,y,z) grid using a programming language. It is more related to maths however, as it concerns recasting a function ...
0
votes
0answers
21 views

yacas factorize polynoms

I want factorize polynoms with yacas but I can do it only with univarial. E.g. I want $x^2-y^2$ factorize to $(x-y)(x+y)$. How can I do it? Or if anybody has any suggestion to another simple, free ...
0
votes
0answers
19 views

An algorithm to find if two sentences are at edit distance $1$

Definition: Two sentences $S_{1}$ and $S_{2}$ they are at edit distance $1$ if $S_{1}$ can be transformed to $S_{2}$ by: adding, removing or substituting a single word. Examples: Consider each ...
2
votes
0answers
29 views

If $L$ is regular, must the language $L_1 = \{w : w^Rw \in L\}$ be regular, or may it be non-regular?

The reverse, $w^{R}$, of a string $w = w_1w_2...w_n$ is the string $w_n...w_2w_1$. Suppose that L is a regular language. Must the language $L_1 = \{w : w^Rw \in L\}$ be regular, or may it be ...
7
votes
2answers
98 views
+50

Graph and in-Degree and Drawing

We have in and out degree of a directed graph G. if G does not includes loop (edge from one vertex to itself) and does not include multiple edge (from each vertex to another vertex at most one ...
5
votes
2answers
43 views

A nice recurrence sequence

I want to find general solution for recurrence: $a_n=7a_{n-1}-10a_{n-2}+4n$ with suppose $c_1, c_2, c_3$ is constant. I need some tutorial or solution on this challenging recurrence.
4
votes
1answer
62 views

How many integers could be in such a way that any digits is not bigger than the left digits?

How many 4-digits integers could be in such a way that any digits is not bigger than it's left digits? I Try it with simulation, i get 714. anyone could describe a formula for me? My try:
0
votes
1answer
35 views

How to calculate the angle between 2 vectors in 3D space given a preset function

In my application, I am attempting to connect 2 points in 3d space with a cylinder via a function taking in 2 vectors. I understand that I need the angle to apply to the cylinder. As I understand, I ...
1
vote
0answers
35 views

Representing $i$ with divergent series

Train of thought In computer science, for representing signed integers, we can use the two's complement representation, so that $11111111_{(2)} = -1$ over 8 bits with $x_{(2)}$ denoting binary ...
0
votes
2answers
54 views

Designing a deterministic finite automata

How would I go about designing a deterministic finite automata to recognize the language L = {λ, ab, abab, ababab, . . . } consisting of strings that start with ‘a’, end with ‘b’, and alternate in ...
-1
votes
1answer
27 views

Proving that CFG generates a language

I need to construct a CFG for the language consisting of even length palindromes with the same number of a's and b's and then prove that it generates that language. This is the CFG I got: S→ abba | ...
0
votes
1answer
16 views

Substitution method for solving recurrences piece wise function

I don't know how to use the substitution method for the following function: piece wise function: $T(n) = c$, if $n=0$ $T(n) = d$, if $n=1$ $T(n)=2T(n-1)-T(n-2)+1$, if $n > 1$
0
votes
1answer
24 views

Triangles incident on a vertex (Graphs)

I have a project that I am doing. The specification requires specific methods on a graph class. Two of the methods requires this: 1.numberOfTrianglesIncidentToVertex, calculates and returns the ...
1
vote
2answers
32 views

Literature and web sources for Computer Aided Geometric Design (CAGD)

Through the Numerical Analysis lecture I came across Bèzier curves, B-Splines and Spline Interpolation and found it very interesting. The title of the chapter was Computer Aided Geometric Design and I ...
2
votes
1answer
31 views

Getting the nth bit of a decimal number

I have a formula for decoding a 3-bit data object: $$T = 68 + 2 \sum_{i=0}^22^iTempA_i$$ where $TempA$ is the 3-bit object and $TempA_i$ is the $i$'th bit from the right. I am trying to rewrite this ...
4
votes
1answer
19 views

Bipartite Graph and Matches of Graph

We know that one match from $G=(V,E)$ be a subset of edges $M \subset_= E $ in such a way non two edges of M hasn't a common vertex. Matches M is Maximal if M not a proper subset of any other matches ...
0
votes
2answers
49 views

Prove that the set of palindromes are not regular languages using the pumping lemma.

Firstly I pick a language $xyz$ where $x = \epsilon$, $y = (abb)^{k}$, $z = (bba)^{k}$ where $|y| \ge$ the number of states in the automaton representing my language. Then $xyz = (abb)^k(bba)^k$ is a ...
0
votes
2answers
52 views

Suppose f : A ---> B and g : B ---> A are functions for which g o f = 1A…

If I were to suppose that $f : A \to B$ and $g : B \to A$ are functions for which $g \circ f = 1_A$, is $f$ always surjective and is $g$ always injective? How would I either prove this or counter it? ...
0
votes
0answers
28 views

String theory - working included [duplicate]

I'm really not too sure if I am correct or even on the right track with regards to the following question - any help is appreciated. Consider strings of five decimal digits. What are the number of ...
0
votes
0answers
30 views

Directed DFS graph - one vertex

I am having trouble trying to figure out the following problem: Give an example of DFS(depth-first-search) on a directed graph where vertex v is the only vertex in some DFS tree despite the fact that ...
0
votes
0answers
12 views

Estimating how many searches will be needed to justify time spent on presorting an array.

Problem Estimate how many searches will be needed to justify time spent on presorting an array of $10^3$ elements if sorting is done by merge sort and searching is done by binary search. (You may ...
0
votes
0answers
20 views

Computing composite functions

This may not be strictly a math question but is related. Whenever there is some function that computes more than two elements, is it possible that all elements are computed at once? Or is computing ...
0
votes
2answers
151 views

the strings of five decimal digitis

My question is : Consider strings of five decimal digits, such as 00147, or 99999. In each case below, what is the number of such strings satisfying the given property? (a) The string has no repeated ...
1
vote
1answer
37 views

Regular language that has a string that cannot be pumped.

This is a question from a past exam. Consider the language $F = \{w | w \in 0^{*}1^{*}\}$ that is kown to be regular. a) Show that if string $w$ is chosen to be $0^p1^p$, that is a member ...
0
votes
2answers
145 views

Invertible functions - proving that $g \circ f$ is invertible

If I were to suppose that $f : A \to B$ and $g : B \to C$ are functions which are both invertible, how would I go about proving that $g\circ f$ is invertible with $(g \circ f)^{-1} = f^{-1} \circ ...
0
votes
0answers
16 views

Big Oh proof. Need help finding c constant

Ok I have the equation . I have compared each term with 2^n and proved that 2^n is greater for some n_0. My problem is how do I gather the terms up and find the c? $ \sqrt[]{2}^{\log n} + \log^2 n + ...
1
vote
0answers
19 views

Nonregular languages that satisfy the pumping lemma at different strengths

There are three versions of the pumping lemma that I've seen, each one stronger than the last (as in it fails on some non-regular languages that pass the weaker ones) The three versions are as ...