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
55 views

When drawing a recursion tree, how does b effect the tree if it is given?

So the problem I have is T(n) = T(n/8) + T(7n/8) +5n. I need to draw a recursion tree to prove that T(n) = Ө (n log 8 n ). I also need to show that T(n) = O (n log 8 n ) and T(n) = Ω (n log 8 n ). ...
0
votes
1answer
36 views

Adding/Subtracting in binary and hexadecimal number systems?

I have two numbers(in decimal): M = 3892.74 N = 9341.65 I am trying to add and subtract them in binary numbers and then in hexadecimal numbers. I manage to ...
0
votes
1answer
33 views

Suppose A = {1,3,7,11} and B = {3,7,12} . Calculate the following showing the step-by-step process of your calculations

Suppose A = {1,3,7,11} and B = {3,7,12} . Calculate the following showing the step-by-step process of your calculations a) |A ∪ B| b) |A| + |B| - |A ∩ B| c) A X B Not sure if I'm doing these ...
0
votes
1answer
32 views

In the following problems the universe is R. Determine the following

In the following problems the universe is R. Determine the following. a)[0,3] ∪ [2,6] b)[0,3] - [2,6] c)[0,3] ⊕ [2,6] So I just need someone to confirm if I am correct or not in my solution.. I ...
8
votes
1answer
751 views

Three variable, second-degree symmetric Diophantine equation

Find integers $f,g,h$ such that $3(f^2+g^2+h^2)=14(fg+gh+hf)$. You can do it using a computer or by hand. I tried this problem for ages, got nowhere. Unfortunately I don't know how to program, but I ...
1
vote
2answers
31 views

Induction and Statements

I'm having trouble with induction in my discrete math course. We are given a statement we know (∀k)(P(k)⇒P(k+2)), where k is an element of N. After that we have a series of statements, I'll give one ...
1
vote
3answers
73 views

Examples (trivial and non-trivial) of computable functions whose inverse is not computable

Can you give some examples (some trivial and some non-trivial) of computable functions whose inverse is not computable?
0
votes
0answers
41 views

How to show that $2^x$ is not in $O(x^2)$?

This is from Discrete Mathematics and its Applications I am working on 2e. I knew right off the bat from previous computer science courses that 2^x is not in O(x^2). I am having a difficult time ...
0
votes
1answer
49 views

Would the greedy algorithm use the fewest coins for all of those denominations?

This is from Discrete Mathematics and its Applications. Here is the book's section on the greedy alorithm for counting change Here is the problem I am working on, 54(uses 52) Here is what I got ...
0
votes
1answer
31 views

For each of the following set expressions, say what set the expression denotes. In other words if the se…

For each of the following set expressions, say what set the expression denotes. In other words if the set is finite, give an explicit listing of its elements.. Assume A = {2,3,4} a) {x:x ∈ Z, -3.5 ...
0
votes
1answer
28 views

These sets are presented in lists of element form. Write the sets in the form of the set generator

These sets are presented in lists of element form. Write the sets in the form of the set generator a) {0,3,6,9,12} b) {-3,-2,-1,0,1,2,3} So... would the solutions be: a) {n*3: n=0,1,2,3,4} b) ...
0
votes
1answer
41 views

Rewriting statements with quantifiers to full detail

The question i have for an assignment is the following Let P and Q be predicates on the set S, where S has two elements, say, S = {a, b}. Then the statement ∀xP(x) can also be written in full detail ...
4
votes
2answers
94 views

What is the algorithm hiding beneath the complexity in this paper?

So, I am a computer scientist (at least, I'm working to become one..) and I asked a question on here concerning some mathematics behind the Mandelbrot set. A reply I recieved pointed me to this paper. ...
0
votes
1answer
44 views

Summation of harmonic series. [closed]

I'm trying to figure out how to answer this linear algebra question and can't figure it out. Can someone please explain it to me? Thanks a bunch! Here's the questions:
0
votes
1answer
35 views

These sets are written in set generator form. Write the sets in list of elements form.

These sets are written in set generator form. Write the sets in list of elements form. a)$\{\frac{1}{n}: n = 1,2,3,4\}$ b)$\{n^2-n: n = 0,1,2,3,4\}$ I have no idea how to even attempt this...If ...
5
votes
1answer
35 views

Formal Grammar generating $0^p$

Exercise: Find the formal grammar generating the language ${0^p}$ in the binary alphabet for $p$ prime. I have absolutely no clue where to start, nothing of the 'usual' construction strategies seem ...
3
votes
2answers
49 views

Fibonacci recursive algorithm yields interesting result

After writing a program in Java to generate Fibonacci numbers using a recursive algorithm, I noticed the time increase in each iteration is approximately $\Phi$ times greater than the previous. ...
0
votes
1answer
43 views

Can anyone explain the average case in insertion sort?

I am not sure if this question is off topic or not but a question like this has been asked on this site before - Insertion sort proof Here is an example of insertion sort running a on a set of data ...
0
votes
1answer
24 views

Is A+D-C-B really the correct formula to get sum over rectangle in summed area table?

Recently, I was taught about the summed area table (integral image) concept. This table represents a matrix, usually an image, so that every ${SAT}_{ij}$ (I used SAT as summed area table) equals to ...
1
vote
1answer
93 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
30 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
18 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
45 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
52 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
81 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 ...
3
votes
2answers
30 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
18 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
87 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
20 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
36 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
32 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
18 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
65 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
10 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
40 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
29 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 ...
1
vote
1answer
36 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
16 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
34 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
52 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
34 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
1answer
70 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
54 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 ...
3
votes
0answers
85 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
23 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
28 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
60 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
23 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
41 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 ...