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

0
votes
1answer
40 views

Structural Induction Subsets

Consider the set $S \subset \mathbb{N}^2$ of ordered pairs of integers defined by the following recursive definition: • $(3, 2) \in S$ (basis) • If $(x, y) \in S$, then $(3x − 2y, x) \in S$ ...
-1
votes
2answers
59 views

Coloring Graph with some constarints

if Graph G be a Cycle with Length=4. how many ways we can color this graph with at most $\lambda$ different color, in such a way that non of two adjacent vertex has a same color?
3
votes
2answers
97 views

Nice Question in Mathmatics about Times

I ran into a nice question from one book in Discrete Mathematics. I want to someone lean me how solve such a problem, because I prepare for entrance exam. if the time is "Wednesday 4 ...
0
votes
1answer
34 views

Calculating the average degree/valency of vertices

If I were to let T be a tree with n vertices, what would be the average degree/valency of the vertices in T? How would I go about calculating this?
0
votes
0answers
36 views

Prove or Disprove Asymptotic Complexity

Not sure how to prove or disprove this. $$\min\{f(n), g(n)\} \in \Theta\left(\frac{f(n)g(n)}{f(n)+g(n)}\right)$$ Could someone please give me a hint on how to approach this?
2
votes
3answers
56 views

How many numbers can a typical computer represent?

I couldn't find this elsewhere so I thought I'd give it a try to figure out exactly how many numbers a typical desktop computer can represent in memory. I'm thinking about this in the context of ...
1
vote
0answers
34 views

Inference using Proof by contradiction and resolution rule [duplicate]

I get stuck in inference. please help me in step by step inference? By using Resolution Rules, and Proof by contradiction from following Knowledge base, we want to understand how we get the answer of ...
-1
votes
1answer
82 views

Finding a minimum weight spanning tree? [duplicate]

Letting W be the weighted graph created by taking a complete graph K5 on five vertices 1, 2, 3, 4, 5 with the weight of each edge {x,y} given by ({x,y})=x+y, How would I find a minimum weight ...
1
vote
1answer
96 views

When to use weak, strong, or structural induction?

For weak induction, we are wanting to show that a discrete parameter n holds for some property P such that P(n) implies P(n+1). For strong induction, we are wanting to show that a discrete parameter ...
1
vote
0answers
37 views

Constructing a “one-way function” of two variables (a.k.a “stop my friend from hacking my game”)

This might be more of a computer science question than a mathematics one; I thought I'd start here but perhaps people might want to point me to a better forum, if this isn't the right one. ...
0
votes
2answers
36 views

In general, what does the location of the rightmost “1” in a binary number tell you? Is it different for positive and for negative numbers?

In general, what does the location of the rightmost “1” in a binary number tell you? Is it different for positive and for negative numbers?
1
vote
0answers
21 views

Shortest route with a requirements set

Suppose you have a weighted connected graph, $G(V, E)$, with $n$ nodes such that every node has a edge to every other node (a large clique). You are also given a set of sets, $\{l_1, l_2, ... l_n\}$ ...
0
votes
0answers
10 views

Is the set $L =\{ M_ i: M_i$ accepts only one string$\}_{i=1}$ an recursive enumarable set?

I am having trouble with this question "Is the set L = {i such that M_ i accepts only one string} an recursive enumarable set ?" My answear is "No, because we can reduce this set to The K set K={i ...
0
votes
1answer
62 views

How would I find a minimum weight spanning tree for W?

If I were to let $W$ be the weighted graph formed by taking a complete graph $K_5$ on five vertices 1, 2, 3, 4, 5 with the weight of each edge $\{x,y\}$ given by $(\{x,y\}) = x + y$, how would I find ...
1
vote
1answer
66 views

Calculating MIPS [closed]

Been struggling to solve this question. From my notes, you can calculate MIPS through this formula: MIPS = Instruction Count / Execution Time X 10^6 And the question goes like this: Given an ...
0
votes
1answer
41 views

How many bits are needed to encode the following data?

A weather station on Santa Rosa Island sends data about weather conditions once every 15 minutes. The data sent is as follows: Temperature (0..60 degrees Celsius) Wind speed (0..170 kph) Wind ...
1
vote
1answer
70 views

Proof of big-O notation

Prove the following: If f is a polynomial of degree $d$, then $f(n)=O(n^{d})$. For every $d \in N, n^{d} = O(e^{n})$ Intuitively, it makes sense to me that for the first one, growth order depends ...
1
vote
1answer
39 views

What's the parametric equation for the general form of an ellipse rotated by any amount? Thanks.

What's the parametric equation for the general form of an ellipse rotated by any amount? Preferably, as a computer scientist, how can this equation be derived from the three variables: coordinate of ...
0
votes
1answer
35 views

What mathematical structure best entails self-modifying programs?

If a program description can be represented as a sequence, then what is the best structure to entail program descriptions which self-modify? There must exist a relationship between the structure in ...
1
vote
1answer
48 views

Prove using structural induction?

First off: I am not sure if I have posted to the correct site, but I am quite lost with this question. I am in a theory of computation class after taking 1.5 years off school and we are on ...
0
votes
0answers
54 views

Proving that there always exists two opposite points on a circle where the temperature difference is less than 1

You are given $n$ ($n$ is even) integers $a_0,a_1,\ldots,a_{n-1}$ representing temperature measurements, equally spaced around a circle. Since the points are "close", the temperature difference ...
1
vote
1answer
30 views

Show that whether or not an arbitrary Turing machine ever executes a particular one of its instructions is unsolvable

Show that whether or not an arbitrary Turing machine ever executes a particular one of its instructions is unsolvable. (This is the same as the problem of detecting unreachable code in a program.)
2
votes
1answer
35 views

Expected Value on code

I'm trying to figure out the expected number of times this algorithm will print. I'm stuck on how to go about doing so. I used an indicator variable to keep track of the number of print statements ...
0
votes
1answer
17 views

In the loop average computation

I want to compute the average of a set of number, which is constantly increasing. I guess it's simple, but I'm struggling here: Let's say: 1st iteration: m(i)=a+b/2 2nd iteration: m(i+1)=a+b+c/3 ...
0
votes
1answer
41 views

Trouble reading mathematical statements. Need to know I'm on the right track.

Σ = {a, b}. We write #a(x) for the number of occurrences of the letter a in the word x and similarly for #b. note: $\Sigma^*$ refers to the set of all finite strings (words) over Σ. ...
0
votes
1answer
59 views

What is the probability the best case occurs? (Comp Sci Type Question)

I'm having trouble figuring out what's the probability the best case occurs? It's my first time bringing together probabilistic knowledge into computer science. The question goes as such. Consider ...
0
votes
1answer
290 views

Convex n- sided polygon proof writing (homework question)

Would anyone be able to help me with the following problem or give me a push in the right direction? I am not entirely sure where to start and I have been looking at this problem for hours... Any help ...
0
votes
0answers
29 views

Calculating peak achievable performance of a dot product of two vectors from the example

I am trying to get the concept of an example. The example shows me all data but I just wonder where certain numbers come from. Here's the example. Consider a memory system with level 1 cache of 64 ...
0
votes
1answer
33 views

Fibonacci proof with a language

The proof I am working toward achieving is as follows: I know this can be proven using induction, and in doing so, I will need to: show when n = 2, F₂ = G₀; when n = 3, F₃ = G₁; if $F_{n -1} = ...
2
votes
2answers
58 views

Sum of a Series to Infinity

Evaluate the following sums: $\sum\limits_{i=0}^\infty\frac1{4^i}$. $\sum\limits_{i=0}^\infty\frac i{4^i}$. $\sum\limits_{i=0}^\infty\frac {i^2}{4^i}$. $\sum\limits_{i=0}^\infty\frac ...
2
votes
1answer
50 views

Using Big-O to analyze an algorithm's effectiveness

I am in three Computer Science/Math classes that are all dealing with algorithms, Big-O, that jazz. After listening, taking notes, and doing some of my own online searching, I'm pretty damn sure I ...
1
vote
1answer
30 views

Calculating $(\lambda x.(x+y))1$

$(\lambda x.(x+y))1$ returns(I think): $(1+y)$. Is $(1+y)$ another lambda function so I'd write: $\lambda y.(1+y)$ or is it just $(1+y)$ and if so what does that mean?
2
votes
1answer
37 views

Algorithm to determine if integer matrix is similar to symmetric integer matrix with nonnegative entries

Let $A\in M_n(\mathbb{C})$ be a matrix with integer entries (treated as a matrix over the complex numbers). Is there an efficient way to check if $A$ is similar to a symmetric matrix with nonnegative ...
1
vote
2answers
107 views

Most negative number (in octal and hex) of a 16-bit one's complement system?

In a 16-bit one's complement system, how do you represent the most negative number in octal and hex? One's complement: http://en.wikipedia.org/wiki/Ones'_complement The most negative 16-bit number ...
0
votes
1answer
39 views

Understand a Maple output

My goal is to solve for $L$ in $\frac{(2k)!}{2^kk!}{2nL - L^2 \choose 2k} = \sum_{s=0}^k{L \choose s}{n-L \choose s}s!\frac{(2k-2s)!}{2^{k-s}(k-s)!)}{L-s \choose 2k-2s}.$ I tried to use the solve ...
2
votes
2answers
46 views

Why is the invariant of the following state machine (2 mod 5) OR (3 mod 5)?

Consider a state machine with tuple of numbers describing its state, i.e. $(i,j)$ such that $i \geq 0$ and $j \geq 0$. The initial state is $q_0 =(i,j) = (15, 12)$ There are only two transitions ...
1
vote
2answers
25 views

Prove that the binary representation of a number n will use floor(lg(n)) + 1 bits.

I'm taking Computer Algorithms class and one of my problems is from Skiena's Algorithm Design Manual, 2-41: Prove that the binary representation of $n \ge 1$ has $\lfloor \lg n \rfloor +1$ bits ...
2
votes
0answers
35 views

Computer program to simplify formulas

What is the computer program that attempts to simplify sums of binomial coefficients, factorials, etc.? Possibly Zeilberger wrote it, but I'm unsure. If so, possibly it was talked about in his A=B ...
0
votes
1answer
21 views

Find base of numbers in a sum?

is there an easier way to find the base A in the following without essentially brute-forcing it with different conversions until I get the result? Again, trying to find base A such that the following ...
0
votes
1answer
33 views

Constructing a while loop in R for Newton's method

I'm very, very new to R, and my instructor's example seemed like a special case (or I just don't know how to extrapolate his syntax to my problem). Here's the example we used: Approximate the square ...
5
votes
3answers
281 views

How to encode matrices uniquely

Given a square matrix $A=[a_{ij}]_{n \times n}$, an operation $swap(A, i, j)$ is defined to swap row $i$ and $j$ of $A$ and do the same thing with the corresponding columns. For example, in the ...
0
votes
0answers
52 views

Tilde approximation for $\frac{N^{100}}{2^N}$?

I am having some trouble getting the tilde approximation for a computer algorithms class. Here is what I have so far: $\frac{N^{100}}{2^N} \rightarrow \lg\left(\frac{N^{100}}{2^N}\right) = ...
0
votes
0answers
10 views

Computationaly Simulating Brownian motion and entry times in sets

What would be some good books to help me program Brownian motion? I want to simulate Brownian paths in a bounded domain and ,ideally, get estimates on the hitting probability of sets in that domain. ...
1
vote
1answer
42 views

Limit of a recursive function

I have a recursive functoin: $$\log^{'}(n) = \begin{cases} & 1 \text{ if } n \leqslant 1 \\ & 1 + log^{'}(\log(n))\text{ otherwise} \end{cases}$$ This function grows VERY slowly. Is this ...
2
votes
3answers
103 views

Show that the language is not regular using the pumping lemma.

I have to show that the language $L = \{ a^k b^k \mid k > 0 \}$ is not regular using the pumping lemma. I have done the following: Let $i \geq 1$ $$x = a^i b^i \in L$$ $$|x| = 2i \geq i $$ ...
3
votes
3answers
132 views

$2x_1 + 2x_2 + \cdots + 2x_6 + x_7 = N$

How do I find the number of integral solutions to the equation - $$2x_1 + 2x_2 + \cdots + 2x_6 + x_7 = N$$ $$x_1,x_2,\ldots,x_7 \ge 1$$ I just thought that I should reduce this a bit more, so I ...
1
vote
0answers
55 views

operator vs operation vs function vs procedure vs algorithm

I have a vague understanding of what operator, operation, function, procedure, algorithm mean in general. I am heavily biased towards computer science. Do you agree with them? What are the generally ...
1
vote
1answer
34 views

What's wrong with this “proof” of time complexity? Traversing a $n \times n$ matrix in $O(n)$

Claim: I can traverse an $n \times n$ matrix in $O(n)$. "Proof": Clearly, this is true for $n=1$. Now suppose this is true for $n-1$. Then given an $n \times n$ matrix, traverse the upper left ...
0
votes
1answer
50 views

Preorder Traversal

For Each Preorder Traversal, we have multiple Inorder Traversal. this is True or False Conclusion? every one would help me and add some detail.
0
votes
1answer
40 views

Time Complexity of one Example Code

i see an example on my note for calculating Time Complexity, but i couldn't understand. anyone could help me.