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

Why can the author just switch the order of the inequality without any reprecussions?

Note: This example is from Discrete Mathematics and Its Applications [7th ed, example 2, page 598]. I understand the idea of a symmetric closure. You add all ...
0
votes
1answer
177 views

Find a div m and a mod m when

Find a div m and a mod m when $a = -111$, $m = 99$ I can't find the formula anywhere in my book.
1
vote
2answers
45 views

Prove that if a|b and b|c then a|c using a column proof that has steps in the first column and the reason for the step in the second column.

Let $a$, $b$, and $c$ be integers, where a $\ne$ 0. Then $$ $$ (i) if $a$ | $b$ and $a$ | $c$, then $a$ | ($b+c$) $$ $$ (ii) if $a$ | $b$ and $a$|$bc$ for all integers $c$; $$ $$ (iii) if $a$ |$b$ and ...
0
votes
0answers
18 views

Formulating and solving box unloading as graph problem

I have a set of boxes as those pictured below. I can only remove boxes that dosen't have any boxes on top of it. In every "move" I can move any box that is currently available, but I have limitations ...
2
votes
1answer
60 views

How to solve this logarithmic inequality?

I've started a data structure course and I need some help with solving these logarithmic inequalities. It would also be helpful because later on these kind of calculation won't pose a problem later ...
1
vote
3answers
42 views

How do I show a function is Big-O of another function using the definition of Big-O?

Definition: A function F(x) is Big-O of g(x) if we can find constant witnesses such that $f(x) <= Cg(x)$ when $x=k$. Use the definition of “$f (x)$ is $O(g(x))$” to show that: $x^4 + 9x^3 + 4x + ...
0
votes
1answer
27 views

Prove that the last process is responsible for $\mathrm\lceil {n\over p} \rceil$ elements

In my parallel computing class, I have this proof in one of my HW problems: Suppose we have chosen a block agglomeration of $\mathrm n$ elements (labeled $\mathrm 0, 1, ... , n - 1$) to $\mathrm p $ ...
1
vote
1answer
34 views

Stuttering Subsequence Problem - Explain the example

I'm reading an article that deals with solving the stuttering subsequence problem in $\Theta (n)$. The article can be found here: http://www.cse.yorku.ca/~andy/pubs/Stutter.pdf Some background on ...
-2
votes
1answer
47 views

Cryptography Combinatorics question [closed]

I 'invented' this encryption device - take a string, and start with the first character. Swap this character with the second with probability $50$%. Move to the (now) second character, and repeat ...
0
votes
2answers
40 views

A question about mathematical algorithm in Digital Systems.

My question is related to math technique that must be used to solve a question in Digital Systems subject. and I know Its not so related to this forum, but I couldn't find another related place in ...
1
vote
2answers
46 views

Why does a set of m elements have 2$^m$ subsets?

Note: This example is from Discrete Mathematics and Its Applications [7th ed, prob 2, pg 576], shout out to @crash. I understand why $A \times A$ has $n^2$ elements(because every member of set $A$ ...
0
votes
1answer
23 views

When is the solution of a matrix inconsistent?

I was doing the exercise on matrices at the end of the book answers are written a few have "inconsistent" in answers. what does this means? please help!
4
votes
1answer
63 views

Is this graph theory problem NP-Complete?

Back in college I was in an introductory Graph Theory (undergrad) class. For one assignment I was creating an algorithm to solve the following problem: Find an odd-length cycle in a directed ...
0
votes
0answers
28 views

Expected tries without replacement

I am calculating the number of blackbox fuzzing test I need to run on a program to find an error. Say there is a 1/100 chance that my program throws an error. It takes in two arguments. What is the ...
0
votes
0answers
41 views

Computability, Continuity and Constructivism

Triggered by an IMO extremely interesting question & Mathematics Stack Exchange, asked by Dal: Computability and continuous real functions And a link in one of the comments that could have ...
0
votes
2answers
48 views

Checking Understanding of DFA Regular Operations - Intersection and Star

I'm currently taking a Logics course, and trying to understand the regular operations, intersection and star. I have a question regarding the work I have done so far. Given the following ...
2
votes
1answer
46 views

Proof of the Computability of Polynomials

In studying properties of polynomial functions I have read that they are computable. The usage of the word read implies that I cannot prove this statement, and withhold using learned for this reason. ...
0
votes
1answer
35 views

Iterative Logarithm in Recurrence Relation?

Anyone Could describe me How we can solve this recurrence relation? $T(n) = T(\log n) + O(1)$ $T(1) = 1$ a) $O(\log n)$ b) $ O (\log^* n) $ c) $ O (\log^2 n) $ d) $ O (n / \log n) $ Our TA ...
1
vote
1answer
19 views

How to find a function that maps an element to row number in a triangle of integers?

This is a triangle of integers 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ........ Is there some function that could map ...
1
vote
1answer
22 views

Solving a linear program using just one call to a procedure that gives a feasible solution.

Suppose we have some procedure $F$ which takes any set of linear constraints and either returns either infeasible or returns a vector satisfying these constraints. If we now take a linear program ...
2
votes
1answer
104 views

Relax function on Bellman Ford Algorithms

In a Weighted Directed Graph $G$ (with positive weights), with $n$ vertex and $m$ edges, we want to calculate the shortest path from vertex $1$ to other vertexes. we use $1$-dimensional array $D = ...
3
votes
2answers
60 views

n bag of sand and one algorithms

We have $n$ bags of sand, with volume $$v_1,...,v_n, \forall i: \space 0 < v_i < 1$$ but not essentially sorted. we want to place all bag to boxes with volumes 1. We propose one algorithm: ...
0
votes
3answers
50 views

Order of Natural Numbers in Algorithms

Could anyone describe, why this is a True statements? if $f_i$ be a function of natural numbers to natural numbers and $f_i(n)=O(n)$ then $\Sigma_{i=1}^{n} f_i(n)=O(n^2) $
0
votes
0answers
27 views

Conjunctive normal form (~p->r) AND (~p->~r) <-> r

I need help converting following formula to conjunctive normal form. (~p->r) AND (~p->~r) <-> r By using equivalences i arrive to following result (((~p AND ~r) OR (~p AND r)) OR p) AND (~p OR ...
7
votes
2answers
250 views

Hamiltonian Weighted Graph and Decision Problems

I ran into a question on previous Mid-Exam. anyone could clarify me? Problem A: Given a Complete Weighted Graph G, find a Hamiltonian Tour with minimum weight. Problem B: Given a Complete Weighted ...
1
vote
2answers
49 views

Rooted Tree and Greedy Algorithms

In a Rooted Tree, we have a message on Root. in each step, each node that has a one copy of message, can transfer this message to at most one of it's childeren. we want to use minimum step and send ...
0
votes
1answer
32 views

Maximum Flow and Change it by Edges Capacity Products

Suppose we have a Directed Graph and each edges has a positive capacity. if C is a positive constant, i say, if we add or subtract C to all edges capacity, the maximum flow, changed, (maybe increase ...
-3
votes
1answer
32 views

Digital Circuit Design

Design and implement a digital circuit which will detect a 4 bit number which is less than 3 or greater than 12 or divisible by 3 (if conditions are met, the output is 1, 0 otherwise). Implement the ...
2
votes
1answer
33 views

Complexity class of conditional dependency resolution

I have a problem I am (considering) writing an algorithm for, but which I suspect to be NP-hard. However, I have not been able to prove that it is in fact NP-hard. The problem is stated as so: Given ...
1
vote
1answer
26 views

Using K-Map to simplify functions

I hope this is the right place to ask this. I have the following problems: 1. Using a K-Map technique perform the following: Simplify the following function: f = (A,B,C,D) = ∑ m ...
0
votes
1answer
15 views

Boolean Algebra Manipulation #2

Ok, so I know I just asked a similar question recently, but I have one more. I don't even know how to start this one: (De Morgan's maybe?) (x+y+z)(x'+y+z')(x+y')(y'+z) = x'y'z + xy'z' + xyz Any ...
0
votes
1answer
8 views

Boolean Algebraic Manipulation

so I'm stuck on what seems like the very last steps of the problem. I'll leave out the whole problem and just start from where I got stuck at in the very end. How can I show that c'd' + c is equal to ...
1
vote
1answer
24 views

Clock Frequency and Duty Cycle

A clock has a 1ns clock period with rise and fall time as 0.05ns. The clock signal stays at exact Boolean state 1 for 0.35ns and at state 0 for 0.55ns. The memory used in the design takes 2 clock ...
3
votes
2answers
53 views

NP-Complete and Poly Time Reduction Problems [closed]

I Took Some Priminlairity Learning Method on Complexity Theory. I get trouble with some definition. anyone could help me, Why the mentioned statement is True? if a Problem A can be reducible to ...
0
votes
1answer
74 views

How to evaluate growth of input size from n to 2n in this case?

This is the question I am currently working on What is the effect in time required to solve a problem when you double the size of the input from n to 2n, assuming that the number of milliseconds the ...
3
votes
1answer
35 views

How to give an upper bound for a solution of $T(n) = T(0.25n) + T(0.75n) + O(n)$?

We have an algorithm which can be described the recurrence formula: $T(n) = T(\frac{n}{4}) + T(\frac{3n}{4}) + O(n)$ and for $n\le 100$: $T(n) = O(1)$. How to show that $T(n) = O(n \log n)$? ...
0
votes
1answer
110 views

Amortized Analysis On List

We want to have a set of n linear list to doing following operation: Insert(x,i) : insert new elemets ...
0
votes
0answers
22 views

Excel: Paying off hypothetic loan in 25yrs vs 30yrs?

I am attempting to recreate an Excel Spreadsheet Dynamic Model (Figure 9.4) presented in my Data Warehousing Decision Support System course. I've uploaded a copy at the following link: Excel Link - On ...
0
votes
2answers
27 views

How to come up with an interval for this Big Oh Problem?

This is from Discrete Mathematics and its Applications I'am trying to use the interval method like what was shown in this example Here is my work so far: I noticed that when $x > 5$, $2^x > ...
0
votes
1answer
34 views

What is a signed number?

When is the meaning of "signed number"? A signed number simply means a number that is negative, correct? Sorry if this seems like a stupid question but I'm just starting to get deep into ...
0
votes
1answer
26 views

Compute the distance between two elements in a ring

Given a ring of size $n = 2^m$, starting with element $0$ to element $n-1$, what general formula gives the distance between two arbitrary elements $i$ and $j$? Note that the distance between the ...
0
votes
2answers
57 views

Where does 2525 and 252525 come from in RSA cryptosystem example?

This is an example from Discrete Mathematics and its Applications I understand how to encrypt, the first step is to turn the letters into their numerical equivalents(same thing we had to do for ...
1
vote
2answers
83 views

What mistake am I making when trying to apply Fermat's little theorem?

This is a problem from Discrete Mathematics and its Applications This is Fermat's little theorem from https://www.youtube.com/watch?v=w0ZQvZLx2KA, Here is my work so far First 41 is prime and ...
1
vote
2answers
45 views

Can someone verify the reasoning of why these two congruences are equivalent?

I've wondered why two congruences like $x\equiv81\pmod {53}$ and $x\equiv28\pmod{53}$ were equivalent. I've come up with this proof. I am not sure if this is how you prove it though I know that ...
0
votes
1answer
28 views

K map and simplified circuit

4) Draw the Karnaugh map and the resulting simplified circuit for the following function F(w, x, y, z) = !yz + w!y + !wzy + !w!xy!z + w!xy!z ...
0
votes
3answers
103 views

How to find inverse of 2 modulo 7 by inspection?

This is from Discrete Mathematics and its Applications By inspection, find an inverse of 2 modulo 7 To do this, I first used Euclid's algorithm to make sure that the greatest common divisor ...
2
votes
2answers
138 views

Hash with Chaining Problems

I ran into an example in Computer Science Course. suppose we use Hashing with chanining and use table of size m. the hash function map record with key ...
3
votes
0answers
72 views

A Tricky Quetiones on Creative Algorithm in Graph

an agent is works between n producer and m consumers. i'th producer, generate $s_i$ candy and j'th consumer, consumes $b_j$ candy, in this year. for each candy that sales, agent get 1 dollar payoff. ...
2
votes
1answer
46 views

Generating elements of a Galois Field using an irreducible polynomial

I am practicing some cryptography problems and I am having problems with one involving Galois Fields and irreducible polynomials. Here is the problem: Using the irreducible polynomial $f(x) = x^5 ...
0
votes
2answers
67 views

Can someone clarify the notation of x $\equiv$ -8 $\equiv$ 6 ($\bmod$ 7)

This is an example from Discrete Mathematics and its Applications This is example 1 that this example references And here's Theorem 1 that the example references Example 1 makes sense. We have ...