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

2
votes
1answer
30 views

Asymptotic Function proof?

I am doing questions from past exams and I stumbled upon this one. I have no idea how to go about solving it.I never had any logarithmic functions in my previous bigOh proofs nor have I had to use ...
-3
votes
0answers
80 views

The Riemann Hypothesis and the P versus NP Problem [on hold]

I am writing an article on the connection between the Riemann Hypothesis and the P versus NP Problem. It appears that if factoring $n=pq$ and checking whether a large integer is prime is fast feasible ...
-2
votes
0answers
28 views

Cant find problem with this C++ code. Please Help [on hold]

include using namespace std; void extra() { int gvalue=10; cout< void main() { extra(); { int gvalue = 20; cout<<gvalue << ' '; } ...
0
votes
1answer
13 views

Proving the correctness of a program

So I have this program below SquareRootRecursion that I need to prove is correct. However i'm not sure what it's pre and post conditions would be and how I would use those to prove it's correctness. ...
1
vote
1answer
23 views

Given 2 colors, how to calculate the mix amount between them?

As an input I have two colors, let's say red (RGB = 1,0,0) and magenta (RGB = 1,0,1). Now I have an image which includes additive mixes between these two colors, for example purple (RGB = 0.5,0,1). ...
0
votes
0answers
15 views

Implement using switches the following logic functions

Implement using switches the following logic functions: F(a,b,c,d)= ab + cd F(a,b,c,d)=(a + bc)d' how can i do it ? Digital System
0
votes
1answer
13 views

Use the power-set construction to find a deterministic automata

Given a nondeterministc automata N, how do you use the power-set construction to find a deterministic automata that recognizes L(N)? Here is my work so far: We can start in state 1, 2. If we get ...
-1
votes
0answers
7 views

Where can I find Assignments solution of the MIT course Mathematics for computer science? [on hold]

I'm studying MIT Course Mathematics for computer Science and I've been looking for the solution of the problems sets of the course in order to grade myself. But I haven't found anything so I'm asking ...
2
votes
0answers
26 views

Prove the big theta

I need to find a $n_0$ and $k$ for Big Oh and an $n_0$ and $k$ for Big Omega, to find a big theta bound for: $5n^2 - 9n = \theta(n^2)$ Can anyone help me and show me how to find these for this ...
0
votes
1answer
16 views

Comparing algorithmic complexities

If an algorithm has a running time $ T(n) = O(n$ log $n)$, would it be possible to show that $T(n) = o(n^2)$?
1
vote
1answer
21 views

Taking the log of both sides to determine big Theta/Omega/O

I've managed to confuse myself over this detail: Obviously: $n^2 \notin \Theta(n)$ Now if we take the $\log$ of both sides, we get: $$\log(n^2) \leq \log(cn)$$ $$2\log(n) \leq \log(c) + \log(n)$$ ...
0
votes
1answer
30 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$ ...
2
votes
2answers
52 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?
4
votes
2answers
90 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
25 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?
-1
votes
0answers
35 views

What suggestions do you have about graph theories I could use for a presentation? [closed]

I'm going to make a presentation for Graph class. I found two theories, but I need your advice which one easier to understand and thus for presentation. 1- Graph Theoretical approaches to the Theory ...
0
votes
0answers
21 views

Help with first principle proof

I am stuck on this proof. I just do these for fun. $n^n \in \omega(n^{20})$ I am stuck on this one. not sure how to show this is bound in little omega.
0
votes
0answers
29 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?
1
vote
3answers
50 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
33 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
71 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 ...
0
votes
0answers
7 views

Use structural induction to prove the following binary tree

Recursive def for Set $X$ (there are two): (1)a single node is in $ X$ and (2) if $x_1$ and $x_2$ are in $X$, then the bigger tree with root r connected to the roots of $x_1$ and $x_2$ is in $X$ use ...
0
votes
0answers
54 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 ...
0
votes
0answers
21 views

Help Representing Python Algorithm Mathematically

For a project I am doing (using rhythm comparisons as an alternative to password authentication), I created an algorithm called "MalKonform", which compares keystroke times between two instances. ...
1
vote
0answers
33 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
34 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
20 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
8 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
58 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
32 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
35 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
34 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
35 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
27 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
42 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
47 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
24 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
33 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
15 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
38 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
55 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
226 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
14 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
24 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
56 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
48 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
28 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
31 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
36 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
36 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 ...