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
3answers
68 views

An example of something that cannot be explained by means of posets [on hold]

My professor said this but I do not understand- can you help me? Give me an example of something that cannot be explained by means of posets; that is, a description composed of orderings of times. ...
1
vote
0answers
10 views

Induction Proof Check: For a binary tree T, Prove that the number of full nodes in T is always one less than the number of leaves in T.

This is a slight variant on a very common beginner's problem. I think I've got it figured out, but I wanted to make sure I actually proved what's being asked. We define a binary tree $T$: (a) A tree ...
1
vote
2answers
26 views

Prove that a recurrence relation (containing two recurrences) equals a given closed-form formula.

Prove that $a_n = 3a_{n-1} - 2a_{n-2} = 2^n + 1$ , for all $n \in \mathbb{N}$ , and $a_1 = 3$ , $a_2 = 5$ , and $n \geq 3$ Basis: $a_1 = 2^1 + 1 = 2 + 1 = 3$ $\checkmark$ $a_2 = 2^2 + 1 = 4 + 1 = 5$ ...
1
vote
1answer
14 views

Big O and Big Omega Proof with lg base 2

Hello I am a beginner to this kind of notation and I would greatly appreciate an explanation which is easy to understand. I need to prove $$ \log_2(6 + \frac1x) = O(1) $$ and $$ \log_2(6 + ...
2
votes
0answers
34 views

(Concrete) mathematical aspects of programming

It is often said that progamming is mathematics as it "makes use" of "discrete mathematics". However, I would like to ask a more concrete question: what are the concepts of a programming ...
1
vote
1answer
40 views

Simplifying Circuits

I have a question regarding simplifying a circuit of a function below that has 5 logic gates in original. f = (A + B) * (C + D) + (A + B) * (C + D)' + C = (A + B) * ((C + D) + (C + D)') + C = (A ...
3
votes
3answers
56 views

Proving that two summations are equivalent [duplicate]

Give a constructive proof to show that for all $n \geq 1$ , $\sum\limits_{i=1}^n i^3 = (\sum\limits_{i=1}^n i)^2$ Observe that $(n+1)^4 - n^4 = 4n^3 + 6n^2 + 4n + 1$ . Now, the two following ...
2
votes
2answers
21 views

Power set of a set containing a set

I need some help understanding this concept a little better. I understand the general power sets, but only worked nice and easy examples where only the set consisted of only single elements like ...
1
vote
1answer
13 views

Is there a typo in this runtime analysis of selection sort?

This is from https://courses.cs.washington.edu/courses/cse373/13wi/lectures/02-25/19-sorting2-select-insert-shell.pdf, slide 6. The instructor is doing a runtime analysis of selection sort. Here is ...
0
votes
0answers
39 views

Importance Sampling of 2D constant piecewise function convertible to 1D?

So I have a constant piecewise 2D function (luminance values of pixels of an image) that I am writing an importance sampling algorithm for. I was going to write my algorithm by first sampling the 1D ...
0
votes
0answers
18 views

Math theory behind Semantic search technology

Let's assume that somebody is developing an Information Retrieval application and a semantic search application. The chart below would like to display an abstraction of the two ones. If you think ...
0
votes
1answer
30 views

How can I add the following 32-bit IEEE floating-point numbers?

How can I add the following two 32-bit IEEE floating-point numbers in binary? FEDCBA98(base 16) + 89ABCDEF(base 16) = a 33-bit binary number. How can this be possible?
0
votes
0answers
23 views

Help Solve Recurrence Relation$ T(n) = T(n-1) + O(n)$

This is how far I have gotten: $$T(n) = T(n-1) + O(1)$$ $$T(n-2) = T(T(n-2)) + O(1)) + O(1)$$ $$T(n-2) = T(n-2) + O(2)$$ $$T(n-3) = T(T(n-3) + O(1)) + O(2)$$ $$T(n-3) = T(n-3) + O(3)$$ Finally ...
0
votes
1answer
16 views

How would you convert the following 32-bit IEEE floating-point to decimal form?

I have got -1.101 1100 1011 1010 1001 1000 * 2^(9) How can I convert this to decimal form?
2
votes
1answer
31 views

Convert the following decimal number into 32-bit IEEE floating-point form.

I am given a negative decimal -1234.875. I understand the normal process of solving a question like this, except I am uncertain about handling the negative. What I do is find the binary form of 1234 ...
0
votes
0answers
9 views

Changements that have to be done in order to delete node of red-black tree

According to my lecture notes: Let $x$ be the child of the node that we delete. Let $w$ be its sibling node and $p$ the father of $x$. There are four cases: At the first case, $w$ is red. We ...
0
votes
1answer
24 views

theory behind semantics, RDF, OWL

What are the fields of mathematics related with semantics technologies and their specifications as RDF, OWL, SPARQL? If somebody working as a programmer with those technologies (using them with a ...
0
votes
1answer
21 views

Big Omega problem : is $n^2\in\Omega (2n^2)$?

Is $n^2\in\Omega (2n^2)$? If we find the limit we can see $\frac{1}{2}>0$, which means it is true, but I haven't learned the limit method. I need to figure out using this definition $\exists ...
2
votes
0answers
23 views

Red-Black tree - “Insert-Delete” [on hold]

I am looking at red-black trees. Unfortunately in my lecture notes, the operations "Insert" and "Delete" are not well explained. Could you explain to me steps that we have to do for these two ...
1
vote
1answer
24 views

Determine if there is a node in a binary postorder anti-sorted tree with key $k$

A binary postorder anti-sorted tree is a binary tree for which the post-order traversal gives the keys that are saved at the nodes of the tree in descending order. Present a pseudocode for the most ...
0
votes
0answers
19 views

Practicing mathematical proofs in preparation for another course and could use some help [closed]

I'm starting a course on Algorithms and the professor wants to test our induction and proof knowledge. Problem is, our prerequisite courses never focused on such material. I'm hoping someone could ...
0
votes
0answers
15 views

How to calculate recurrence $F(n) = F(n/u) + \Theta(n^k)$ where $u,k \in \mathbb{N}$

$\Theta$ is used as in Bachmann-Landau notation (often called as Big-O notation convention). How does one in general the recurrence relation of the following from: $$F(n) = F(n/u) + \Theta(n^k) ...
0
votes
0answers
13 views

Create a list with elements from an other list with specific display order

Consider a singly-linked list $L$ each element of which is a struct with two fields, an integer num and a pointer next to the ...
0
votes
1answer
30 views

Construct an automata for this language

Let $\mathcal{L}_1$ be the language over alphabet $\{0,1\}^*$. Define language $\mathcal{L}_2$, call even-$\mathcal{L}_1$, as: $$\mathcal{L}_2 = \{ w_2 w_4 \ldots w_{k} ~:~ w_1 w_2 w_3 w_4 \ldots ...
0
votes
1answer
25 views

Draw a 2-3 tree, insert and delete a key

Assume that at the nodes of a 2-3 tree, the following keys are saved (in an increasing order): $3,6,9,12,15,18,21,24, 27, 30, 33, 36$. It is also given that the root is a 2-node that contains the ...
2
votes
0answers
30 views

Decidability of given languages

Given are the following languages: $L_1 = \{0\}\\ L_2 = \{w \in \{0,1\}^{*} | L(M_w) = \{0\}\}\\ L_3 = \{w \in \{0,1\}^{*} | M_w \text{ stops at all entries }\} \\ L_4 = \{w \in \{0,1\}^{*} | ...
0
votes
2answers
60 views

Can someone verify my assertion from this english sentence? [duplicate]

This is from Discrete Mathematics and its Applications This is the book means when mentions a list of common ways to express conditional statements After going through the list, I immediately ...
1
vote
0answers
48 views

What is the name of a graph structure with 'ports'?

I am wondering what the name of the following structure is. I might call it the madeup name "graph with ports" but most likely it already has a name that i am not aware of. The interesting thing to me ...
2
votes
0answers
60 views

Is a “network topology'” a topological space?

Is there any connection between the computer science phrase "network topology" and the mathematical notion of a topological space (or, is there any other way to connect "network topologies" with ...
1
vote
1answer
21 views

Rotations after inserting element in AVL-tree

We want to insert $58$ at the following AVL-tree and then we have to make rotations so that the tree is balanced. According to my notes, we are at the case RL (The first edge leads to the right and ...
1
vote
1answer
23 views

Turing machine recognizing language $L=\{a^ib^{i-j}c^j|i>j\ge1\}$

I am having some trouble with designing a Turing machine that recognizes the language: $L=\{a^ib^{i-j}c^j\big|i>j\ge1\}$ For example, word accepted by TM: $w=aaaaabbccc$ To be more precise, I ...
2
votes
0answers
53 views

What computations would advance math knowledge a lot?

Suppose we where given a super computer that would be capable of computing anything, but only for one day. We could for instance compute many of the Ramsey numbers. What would be some computations ...
1
vote
1answer
21 views

Show that: $ L:= \{a^nwb^n: m,n \in \mathbb N, m\geqslant n, w\in\sum^m\} $ is not regular.

$\ \sum= \{a,b\} $ Show that: $ L:= \{a^nwb^n: m,n \in \mathbb N, m\geqslant n, w\in\sum^m\} $ is not regular. I'm trying to proof this with the Pumping Lemma, but I'm kind of confused because of the ...
2
votes
0answers
38 views

Delete nodes that satisfy a property

I want to write a function that takes as argument a pointer A to the root of a binary tree that simulates a (not necessarily binary) ordered tree. We consider that each node of the tree saves apart ...
4
votes
0answers
37 views

Elementary proof of compact space = exhaustible space?

(This is a repost of a question I asked last year on cs.stackexchange.) The work of Martín Escardó has demonstrated close parallels between classical topology on one hand and computability on the ...
0
votes
1answer
58 views

Context free grammar for AN

I need to write Context free grammar for describing moves in a game of chess using the Algebric Notation. Can anyone help me get started. f.ex. how do I write this for this move: Bb5 Bd7.
0
votes
2answers
27 views

Big-O math Question

I'm having trouble with this question: Suppose that $f(x), g(x)$ and $h(x)$ are functions such that $f(x)$ is $O(g(x))$ and $g(x)$ is $O(h(x))$. Prove that $f(x)$ is $O(h(x))$. I have tried ...
2
votes
3answers
75 views

Proving with Big O Notations

Is there a way I can prove that $O(3^{2n})$ does NOT equal $10^n$? How would that be done? Also, is it okay to simplify $O(3^{2n})$ to $O(9^n)$ to do so?
-1
votes
2answers
51 views

Regular vs Nonregular language [closed]

Let S be a language that is not regular? Suppose that T is a language such that T C S. Is T nonregular? This question is from textbook, can someone help me?
0
votes
1answer
36 views

Proving language as regular

Suppose that A and B are languages such that A o B is regular. Suppose that B is regular. Prove or disprove that A is regular. I am having a tough time with questions relating to proving a language ...
0
votes
2answers
49 views

Proving L is a regular language?

I am having tough with problems like this. Can someone help me. Let L be the set of all strings that are not in the English language. Is L regular?
0
votes
1answer
22 views

Using exchange argument in proving greedy algorithm

Here's a problem solvable by greedy algorithm: You are a company and you have list of tasks that still need to be done (but you're late with them already). For a given task we have information about ...
0
votes
0answers
31 views

I'm needing help understanding this coding theory assignment

I'm needing help understanding how to approach this assignment. Create a code consisting of binary codewords. The code must meet three requirements -- Contain at least 20 codewords -- Have a minimum ...
0
votes
1answer
23 views

Computing time-complexity of DP recursion

I've written an algorithm which uses 3-dimensional DP table and it goes as follows: $DP[i][j][0]$ can be computed in $O(1)$ for any $i,j$ and $DP[i][j][k]=\max(DP[i][m][0]+DP[m+1][j][k-1]) $ for all ...
0
votes
0answers
16 views

Topological sort of a graph- how can we find a contradiction?

The topological sort of a graph can be considered as an order of its nodes along a horizontal line so that all the directed edges go from the left to the right. How could we show that all the ...
-1
votes
0answers
20 views

Show that the Dijkstra's algorithm computes correctly the shortest paths

Suppose that we are given a weighted, directed graph $G=(V,E)$ at which the edges that begin from the initial node $s$ could also have negative weights, but the weights of all the ther edges are ...
4
votes
1answer
51 views

How could we prove the correctness of the algorithm?

Consider two sets $D=\{ d_1, d_2, \dots, d_n\}$ and $E=\{ e_1, e_2, \dots, e_m \}$ and consider an other variable $K \geq 0$. Show that we can answer in time $O((n+m) \lg (n+m))$ the following ...
2
votes
1answer
107 views

An endless loop in a program that search for mathematical theorems and proofs − a milestone? [closed]

I don't know if there exist computer programs working on its own, trying to find and prove theorems, delivering proofs and go on searching for new theorems. But if (when) there are such programs, ...
0
votes
1answer
23 views

Proving or demonstrating that an adjacency matrix of a directed graph represents a cycle(s)

I'm currently struggling with this concept for my master's thesis in a computing discipline. If we have an adjacency matrix for a directed graph, $G$, where $A[i, j] = 1$ indicates a directed edge ...
1
vote
0answers
47 views

Proving a greedy algorithm - find minimum number of terms in expression $n=a_1!+\cdots+a_k!$

Given a number $n$ (integer) I should find $a_1,\ldots,a_k$ such that $k$ is minimal and $n=a_1!+\cdots+a_k!$. I think that the following greedy algorithm should give the solution - iterating over ...