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
2answers
55 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 - ...
1
vote
1answer
17 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
34 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
18 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
104 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 } ...
0
votes
0answers
12 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 ...
1
vote
0answers
26 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
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
30 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
51 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
29 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
22 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$. ...
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
25 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 ...
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 ...
2
votes
1answer
26 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
29 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
11 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
35 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 ...
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
17 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
25 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 ...
1
vote
1answer
22 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
33 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 ...
2
votes
1answer
43 views

A book or Source to further study Relations

I have completed a course on Discrete Mathematics and really enjoyed studying the chapter on relations. In fact I went back and finished what we hadn't covered in class. I did basic stuff like n-ary ...
0
votes
2answers
60 views

Writing proposition with connectives and laws of logic

Question 1): Pei Ann has been dealt two cards from a standard 52 card deck. She holds one in her left hand and one in her right. Let $p$ be the proposition "The card in Pei Ann's left hand is an ...
4
votes
3answers
162 views

What exactly are the numbers we use everyday?

Pi can be defined as diameter / circunference of a circle. But what is a circle? You can't tell a computer: "build a circle and divide its diameter by its ...
0
votes
0answers
16 views

Relation between focus and camera intrinsic parameters

Does a focus tuning affect the camera intrinsic parameters? More precisely, if the focus of a camera is changed, does the camera intrinsic parameters matrix remain unchanged? Apparently, since this ...
0
votes
0answers
16 views

principal ideal

I have a homework. I have tried to solve it but I got stuck. Let $P$ be a poset with the Scott topology. If $D$ is any directed subset of $P$ and $G$ is a closed subset of $P$, show that ...
2
votes
1answer
52 views

How can I get better at algorithmic thinking?

I have been practising for a an upcoming algorithmic thinking competition but have always found that when doing the past papers, I have never had enough time left to finish. I can do basically all of ...
1
vote
1answer
20 views

Smallest number of groups to sniff

The question given: The sniffer dog at the airport stops beside a trolley piled high with 60 suitcases. One of the suitcases contains contraband peanuts. The dog can tell whether peanuts are hidden in ...
2
votes
2answers
41 views

Arrange the following:$(1.5)^n, n^{100}, (\log n)^3, \sqrt n\log n, 10^n, (n!)^2, n^{99}+n^{98}, 101^{16}$

Here is the question repeated: Arrange the following in order into increasing order of growth rates. $$(1.5)^n, n^{100}, (\log n)^3, \sqrt n\log n, 10^n, (n!)^2, n^{99}+n^{98}, 101^{16}$$ I graphed ...
1
vote
1answer
22 views

Running Time Analysis

Here is the problem: sum = 0 for i = 1 to n for j = 1 to i^2 for k = 1 to j sum ++ Using three summations, $\sum_{i=1}^{n} \sum_{j=1}^{i^2} ...
0
votes
1answer
12 views

How instances of Automaton(NPDA) read and write the stack

I am reading a text book, Introduction of the theory of computation by Michael Siper. I do not understand the notion of NPDA well. One problem is that the definition of NPDA is not clear on how the ...
4
votes
2answers
51 views

$\prod _{k=2}^{n} {\log k}$ is big-$O$ of what?

$$\prod _{k=2}^{n} {\log k}$$ is a big-$O$ of what? I can see it $O(n!)$ but is there a tighter solution?
-1
votes
1answer
232 views

Show that $\{a^ib^jc^{2j}\mid i\ge 0,j\ge 0\}$ is not regular

How can I show this?I don't know how to start. Show that the set given below is not regular. $$\{a^ib^jc^{2j}\mid i\ge 0,j\ge 0\}$$
2
votes
1answer
40 views

Constructing every spanning tree from addition and deletion of edges

Let $G = (V,E)$ be given (note that this is not necessarily simple), and consider the set of every spanning tree of $G$, $S$. Choose any $G_a, G_b \in S$. Is it possible to construct $G_b$ from $G_a$ ...
0
votes
2answers
44 views

Time Complexity and big-O in CS

Suppose you have 2 algorithms, named A1 and A2 that are designed for solving a problem, with time complexity of $n^2\cdot 2^n$ and $n!$, respectively, where n is the size of the problem instance to ...
0
votes
1answer
38 views

Quintillion bytes to terabytes

I am trying to convert 2.5 quintillion bytes to terabytes (IBM's estimate on the amount of data produced daily), could someone check if my calculations are correct? ...
0
votes
1answer
23 views

Help with Legendre Plot Matlab

I've written a code to change a Chebyshev into a Legendre Polynomial, however it will not plot the graph after and I'm not sure why the graph will not plot? The code i have is: function ...
0
votes
1answer
70 views

Proving that a language is regular and context-free

Let Σ be a finite alphabet and L ⊆ Σ be a language. Let Σ0 ⊆ Σ. For each string w = w1 · · · wn ∈ Σ , define res(w, Σ 0 ) = y1 · · · yn where yi = wi if wi ∈ Σ 0 , and yi =  if wi ∈ Σ \ Σ 0 , for ...
0
votes
0answers
12 views

3CNF is not satisfiable iff CNF is UNQ

I'm trying to come up with a reduction to show that $NOT3SAT \leq_p UNQ$, where NOT3SAT is the non-satisfiability problem for 3CNF and UNQ is unique satisfying assignment for CNF. So, what I'm ...
0
votes
1answer
29 views

Number of fragments into which a fixed triangle is cut in the 3d version of the binary space partitioning algorithm

You can scroll down the question, if you're familiar with the construction of a 3d binary space partition as presented in the book Computational Geometry: Algorithms and Applications by Mark de Berg ...
1
vote
1answer
22 views

Why is no analysis possible for the 3d version of the random binary space partioning algorithm?

Let $S$ be a set of $n$ non-overlapping line segments in the plane $\ell(s)$ be the line which contains $s\in S$ $\ell^+$ and $\ell^-$ be the half-plane above and below of a line $\ell$, ...
0
votes
0answers
13 views

Why FFT algorithm (Cooley-Tukey) takes O(nlogn)?

I was wondering how this algorithm can be formally interpreted with an upper bound n*log(n). There's some formal proof for this? I would appreciate if somebody can help me. Thank you.
1
vote
1answer
17 views

Complement of automata

I know that in order for the complement of the automaton to work, it needs to be deterministic and complete, and if it is not deterministic we can always apply the power set construction, and if is ...