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
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?
1
vote
1answer
79 views

Computational complexity of solving linear diophantine equations?

Is there any good complexity upper bound for checking satisfiability of a matrix system $Ax=b$ where $A\in \Bbb Z^{m\times n}$? I found some estimate on computing the Smith Normal Form $N$ such that $...
0
votes
0answers
13 views

conditional in basic arithmetic

So I am creating a CSS Framework (for web), which aim to be very responsive. So here's my problem: Is there a way to get/compute with only using +, -, * and / (basic arithmetic) to replace the if ...
1
vote
1answer
36 views

Boolean Algebra laws of deduction question

I have a question in which I'm a little stuck at answering, could anyone help? ...
0
votes
1answer
48 views

Implementation of Heap (ADT) using Array Vs. LinkedList

In data-structure course , I need to implement a binary heap with the following time - complexity requirements: Find Max - O(1) Insert - O(log n) Delete Max - O(log n) Now I thought to implement ...
3
votes
3answers
45 views

Proving that $\{ww^rx | w,x \in \{a,b\}^{+} \}$ is non regular using the pumping lemma.

I need to prove that $L=\{ww^rx | w,x \in \{a,b\}^{+} \}$ is non regular. First of all I assume that L is regular. Then L satisfies the pumping lemma, so let p be the pumping length. I've tried ...
1
vote
1answer
59 views

Decidable and Recognizable

I'm trying to work on this problem but I cant seem to find an approach to it: For any language L ⊆ Σ∗ define the language PREFIX(L) := {w ∈ Σ∗ | some prefix of w is in L} (a) Show that if L is ...
1
vote
1answer
98 views

Show that the following function is primitive recursive

Let $f$ be a function defined by \begin{array}{l} f(0)=1;\quad f(1)=2;\quad f(2)=3;\quad f(n)=0 \mbox{, for $n>2$} \end{array} How to show that $f$ is primitive recursive?
1
vote
1answer
43 views

Minimum spanning tree of graph? proof by contradiction?

this is not a homework but I need to understand it before my exam tomorrow. How to prove by contradiction that a minimum spanning tree of a graph G is unique if all the edge weights in G are distinct?...
1
vote
0answers
22 views

Disadvantages of particle swarm optimization method

I am using particle swarm optimization method. It has a lot of advantages, but I am looking for disadvantages of this method. Can you help me?
-1
votes
4answers
82 views

How in this world can I simplify this $\sqrt 2\cdot(1/(\sqrt2)-1/(\sqrt2)\cdot i)^{31}$ ????

I have a problem, obviously. I am doing some maths and now I have to simplify this: $\sqrt 2\cdot(1/(\sqrt2)-1/(\sqrt2)\cdot i)^{31}$ ????. But I just don´t know how ???? I´ve started simplifying by ...
1
vote
2answers
68 views

Proof by Induction

I am attempting to prove by induction that the algorithm calculates the cube of a number, I can't for the life of my grasp it. I was wondering if someone could help me please. The question is: A ...
0
votes
0answers
21 views

Prove set L is recursive iff there is an increasing total computable function which it's range is L.

Set L is recursive iff there is an increasing total computable function which it's range is L. The function is on $\Sigma^{*} \rightarrow \Sigma^{*}$. And by increasing it means that if a comes ...
0
votes
0answers
22 views

Prove uncountability of set L that L and L' neither of which is recursively enumerable.

How do I prove that the set of all languages L on alphabet {0,1} that neither L or L' are recursively enumerable, is uncountable? Proving uncountability can be done through diagonalization like the ...
0
votes
0answers
34 views

Convert a PDA to a CFG

My professor doesn't do a very good job at explaining the process of converting a PDA to a CFG. Can someone help explain it? The way I see it (but it produces wrong results) is each production is ...
0
votes
1answer
55 views

Is this a valid representation of real numbers?

I am trying to find the simplest representation of real numbers on the lambda calculus. I've thought about this one, and wonder if this is valid. First, we define a real number in the range ...
1
vote
0answers
37 views

Find a number a using strange computer

IN the $\#1$ slot of the computer memory there is number $a$. The computer is able to sum, multiply, divide and subtract from selected slots, writing the result in to the selected slot. It is also ...
0
votes
1answer
16 views

How to Alphabetically Arrange Nodes in a Huffman Tree

Suppose there is a string of characters helloworld. The frequency of these characters are d1, e1, h1, l3, o2, r1, w1. So, when inserting them into the huffman tree, the root node should contain d1, ...
0
votes
1answer
29 views

Find execution time in DAG of tasks

I have to find the difference between the worst and the best possible execution time in a DAG (directed acyclic graph) of tasks. The DAG of tasks looks like the following: http://i.imgur.com/2LJBGZA....
0
votes
2answers
21 views

What ω-language does a Büchi Automaton recognize?

When I'm reading about Büchi Automatons, it says that x is accepted if there are infinitely many occurrences of states from the set of accepting states in the run. But for instance, when I'm being ...
0
votes
1answer
14 views

relations between Lower bound of 2 algorithems

I am given two algorithms A and B, with worst time complexity $$ f_A (n) $$ and $$f_B (n)$$ Respectively.Now it is given that: For each n there exists and input x of size n such that the number ...
0
votes
3answers
38 views

Write a recursive algorithm for locating the max number amongst k integers.

Iteratively, I know how to find the max number: Set Max = List[0], for k in range(len(List)), if List[k] > Max, Max = List[k]. Return Max. Recursively, I'm not quite sure. Here is my idea: I ...
0
votes
2answers
56 views

prove that a polynomial is lower bounded

I need help with this question from Data-Structure course. I need to prove that the following polynomial is lower bounded by $n^k $, meaning I need to show that: $$ p(n) = b_kn^k - b_{k-1}n^{k-1}-...
1
vote
1answer
19 views

Computing (the number) of paths in a directed graph starting from the initial state

(This is related to one of my academic projects) Given a directed graph $G=(V,E)$, and $s_1\in V$ the initial state, Let's call a primitive path a path starting from the initial state and does not ...
0
votes
2answers
35 views

non-deterministic automaton and regular expression

I am a linguistics and I start to read some books about Nlp. I have to design a non-deterministic automaton and regular expression over the alphabet $\{a,b,c\}$ that accept all and only those strings ...
-1
votes
1answer
21 views

Maximum number of strict binary trees that can be made, each having exactly n leaf nodes.

I am trying to evaluate(Mathematical expression) the number of strict binary trees that can be made with n leaf nodes. I already know that a strict binary tree with n leaf nodes would have exactly ...
1
vote
1answer
106 views

Loop invariants in logic

I am working on some questions about hoare calculus/logic. The given program $\pi$ is: $ x:=0; y:=1; WHILE \; \lnot x=n \; DO (y:=2y+x + 1; \; x:= x + 1) $ The hoare-logic rules that I can use are ...
5
votes
1answer
67 views

Minimal Elements with respect to big Oh

Let $\mathcal{F}$ be a finite set of functions from the natural numbers to the natural numbers. Consider the set $S_{\mathcal{F}}=\{g:\mathbb{N}\to\mathbb{N}\mid f\in O(g)\text{ for every } f\in\...
0
votes
0answers
17 views

Is there any difference between fixed point and decimal point?

Source: Introduction to Computers' 1999 Ed.1999 Edition Fixed point number 774.3675 is just a decimal number with a decimal point to show a fractional part 3675/10000. I see no difference in the fixed ...
1
vote
0answers
29 views

How do we tell arithemetic addition or subtraction from floating point numbers?

Source: C++ for Engineers and Scientists, Gary J. Bronson Source: Programmable Logic Controllers: The Complete Guide to the Technology by Clarence T. Jones In the table $12345.67_{10}$ = 1.234567+...
1
vote
1answer
38 views

What does leading $0s$ in a number in scientific notation mean?

Source: Computer Organization and Design: The Hardware/software Interface, David A. Patterson,John L. Hennessy It doesn't seem as the author is using leading $0$ like leading $1$ in a matrix. What ...
-2
votes
1answer
32 views

if f and g are monotonically increasing functions, such that f(g(n))=O(n) and f(n)=Ω(n) then g(n)=O(n) [closed]

I have to prove this statement : if $f$ and $g$ are monotonically increasing functions, such that $f(g(n))=O(n)$ and $f(n)=Ω(n)$ then $g(n)=O(n).$
2
votes
0answers
75 views

Optimization of English Braille: Using the fewest dots

Background: The English Braille system is laid out in such a way so that the letters can be referenced by their position in the alphabet. Of the six dots available for each character, the top four ...
3
votes
2answers
31 views

Prove that $(()())\in P$ (the set of balanced paranthesis) and $))(() \notin P$

Given the recursive definition of $P$ (the set of balanced paranthesis): Base: $() \in P $. Recursive step: if $w \in P$ then: $$(w) \in P$$ $$()w \in P$$ $$w() \in P$$ And I have to prove that $...
1
vote
2answers
34 views

(Un)countable set of regular language.

Suppose alphabet Σ={d,e,l,t} and A is the set of all languages "produced" by Σ, which all of them have the property not to include the string "delete". The question is: Is set A countable? I have ...
0
votes
0answers
30 views

Pattern matching algorithm

Given a text $t[1 . . . n, 1 . . . n]$ and $p[1 . . . m, 1 . . . m], n = 2m,$ from alphabet $[0, Σ−1]$, we say $p$ matches $t$ at $[i, j]$ if $t[i + k − 1, j + l − 1] = p[k, l]$ for all $k, l$. Design ...
0
votes
0answers
36 views

How to prove $\forall f,g\in\mathcal{F}: \log{f(n)} \in O(g(n))\implies f(n)\in O(3^{g(n)})$ if $\mathcal{F}=\{f|f:\mathbb{N}\to\mathbb{R}^+\}$?

Let $\mathcal{F}=\{f|f:\mathbb{N}\to\mathbb{R}^+\}$ How to prove or disprove $\forall f,g\in\mathcal{F}: \log{f(n)} \in O(g(n))\implies f(n)\in O(3^{g(n)}).$ I think it can be proved. Equivalently, ...
1
vote
0answers
26 views

If $1/2 ≤ p/q ≤ 2$ , then $p-q$ is representable exactly on the computer

I've found the following affirmation in an article. I've been thinking about it but I don't know the way to prove it: It is not hard to prove that if $p$ and $q$ are two of a computer’s floating–...
0
votes
4answers
41 views

Prove that an upper bound is incorrect

Probably a simple question that I cant figure out from data structure course: I need to disprove the following statement: $$ 8n^3 + 12n + 3\log^3n \ge n^4 $$ Now I know that from some value $n_0\in\...
2
votes
2answers
38 views

Fast Rational Bézier Surface Evaluation Problem

I am currently writing a NURBS ray tracer. What I do is convert the NURBS into rational Bézier patches and then perform the intersection test using Newton's method. To do this fast (the ray tracer ...
1
vote
0answers
30 views

Method of Complements in Base 17 Given a base 10 number.

Given the following table which shows the symbols I am using when representing numbers in base 17. \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline 0_{10} & 1_{10} & 2_{10} & ...
1
vote
0answers
37 views

Finding a function to map from logical to physical addresses

This is sort of an unusual question. For you to understand, you'll need to look at the picture below. The gray background is irrelevant. You can notice there are $4$ discs, splitted to numbered ...
0
votes
0answers
12 views

Does ray tracing have any speed ups in algorithm running time in the frequency domain?

Could ray tracing be Fourier-transformed so that all calculations are done in the frequency domain? I think ray-tracing a set of rays $S$ from the eye into the view frustum might be more efficient ...
1
vote
2answers
37 views

Given a band of $m$ opaque squares arranged in a circle, can we find a viewpoint from which we see exactly $m/2-1$ squares?

Given a band of $m\ge 3$ opaque squares arranged in a circle, can we find a viewpoint (i.e. a point on a sphere centered at the midpoint of the circle with a radius large enough to see the whole band ...
1
vote
1answer
34 views

Weird informatic problem with Fibonacci numbers in which I have some troubles

I don't know what happended to this website but for months I am not able to connect me in it. As I understand it the website is closed. It is in this website I found this problem. Let $L$ be ...
0
votes
0answers
18 views

Visible faces of a polyhedron $P$ on a path of viewpoints on the unit sphere looking at the center of $P$

Let $P$ be an opaque polyhedron. Assuming parallel projection, let's define a viewpoint to be a point on the unit sphere around the center of $P$. Let's say that two viewpoints $v_1$ and $v_2$ are ...
0
votes
0answers
26 views

Computer Vision Models 4.7 - Simplification of Summations

I am reading through the Computer Vision: Models, Learning, and Inference book written by Simon J.D. Prince to get an understanding of computer vision. The author gives some examples in deriving the ...
1
vote
1answer
24 views

How to prove $2^{\sqrt{f(n)}} \in O\ (2^{f(n)})$ if $f:\Bbb{N}\rightarrow \Bbb{R^+}$?

How to prove $2^{\sqrt{f(n)}} \in O\ (2^{f(n)})$ if $f:\Bbb{N}\rightarrow \Bbb{R^+}$? So we want to prove $\exists c\in\Bbb{R^+}:\ [\exists B\in\Bbb{N}:[\ \forall n\in\Bbb{N}:\ n\ge B\rightarrow 2^{\...
1
vote
1answer
23 views

Closed form expression for the number of ordered partitions of a list

Suppose I have a list $L = [e_1, e_2, \dots, e_n]$ and integer $k \geq 2$. I want to compute the number of ways to partition $L$ into $k$ sublists while maintaining the order of the elements. For ...
0
votes
2answers
40 views

How to prove $\frac15 n^2-42n-8\in Ω(n^2)$?

Here is my procedure: So we want to prove $\exists c\in\Bbb{R^+}:\ [\exists B\in\Bbb{N}:[\ \forall n\in\Bbb{N}:\ n\ge B\rightarrow \frac15 n^2-42n-8\ge cn^2]]$ Taking $B=1$. We have $\frac15 n^2-42n-...