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

Natural Numbers and $A_x=\{y \in A \mid y \leq x\}$ [closed]

Suppose A is a arbitrary subset of Natural Numbers and $A_x=\{y \in A \mid y \leq x\}$ with respect to $ n \in A \Longleftrightarrow n \in A_n $ and $A_n$ is finte, which of them is True? a) A and ...
1
vote
1answer
36 views

Sorting algorithms

How could we show that the algorithm of Mergesort is stable, Quicksort is not stable but it can be implemented as stable, Heapsort is not stable. I have show that the algorithm of Insertion ...
0
votes
1answer
23 views

the minimal deterministic finite automaton recognizing $\{1^n 0^n /n\leq N\}$

Given a language $L$ how can I determine the number of states of the minimal automate which recognizes $L$. I want some examples and to understand the methods that we can use to find a lower bound for ...
0
votes
1answer
28 views

Is the invariant correct?

I want to show that Insetion Sort is stable... Do I have to do that using an invariant?? Is the invariant the following?? At the beginning of each iteration of the for loop, if $A[a]=A[b], a<b ...
1
vote
1answer
49 views

what' is the number of full subtrees of a full binary tree?

I'm looking for the number of full sub-trees of a binary tree; all possible tress of height less than $4$ are: Now my question is: What is $N(h)$ the maximum number of full sub-trees of a ...
0
votes
1answer
20 views

Probability distribution of number of ordered items in a permutation

I have a simple algorithm to check if a series of numbers is sorted: if the first two numbers are sorted, move to the next two. Else, stop and return false. I want to figure out the average case ...
0
votes
0answers
17 views

Time estimation and big-O notation

Let a and m be elements of $\mathbb{Z}$ where m is positive. How can I show that the inverse of $a$ can be computed in $O(log^3m)$ bit operations? I thought that I should find the greatest common ...
1
vote
1answer
16 views

An infinite number of solutions available to the sparse representation problem

I would like to analyze the following problem (different cases leads to which solutions to the problem and such): $$||y-Dx||_2 \leq \epsilon$$ (an overcomplete dictionary matrix $D \in \mathbb{R}^{n ...
2
votes
1answer
37 views

Question about an inequality in a published paper which is yielded from an approximation

I am reading a published paper on K- SVD: An algorithm for designing overcomplete dictionaries for sparse representation In the introduction, it says: Recent years have witnessed a growing ...
0
votes
0answers
20 views

Question about a cycle when doing topological sorting

First off, this is a homework question, but I'm just a bit confused on some of the smaller details of doing a topological sort. The homework question can be seen here (it shows the graph). It says: ...
4
votes
1answer
125 views

Can someone verify my answers to these questions regarding this poset?

Problem: 18. Answer these questions for the poset ({{1}, {2}, {4}, {1,2}, {1,4}, {2,4}, {3,4},{1,3,4}, {2,3,4}}, $\subseteq$) $\quad$a.Find the maximal elements $\quad$b.Find the minimal elements ...
0
votes
2answers
47 views

How to prove what amounts of postage can be formed with normal mathematical induction?

This is similar to my other question Strong induction but it addresses standard mathematical induction. Problem: a) Determine which amounts of postage can be formed using just 4 cent stamps and 11 ...
0
votes
2answers
44 views

How to mathematically show that the relation is transitive?

Problem: Show that the relation $x R y$ iff $x \leq y$ is a poset over the set of integers $\mathbb{Z}$ My work: I know that to show the relation is a poset or a post order, I have to show the ...
0
votes
0answers
46 views

Can linear execution time be achieved [duplicate]

The SELECT algorithm determines the $i$th smallest of an input array of $n>1$ distinct elements by executing the following steps. Divide the $n$ elements of the input array into $\lfloor ...
3
votes
2answers
136 views

De Morgan laws of linear logic

I find it stated, in all the resources I have searched, that the following De Morgan laws$$(A\otimes B)^{\perp}\equiv A^{\perp}\wp B^{\perp}\quad\quad\quad (A\text{&}B)^{\perp}\equiv A^\perp ...
1
vote
2answers
39 views

Dividing the interval in subintervals of equal length

I am asked to describe the operation of the processure BUCKET SORT at the array $$A=\langle 0.75, 0.13, 0.16, 0.64, 0.39, 0.20, 0.89, 0.53, 0.71, 0.42, 0.19 \rangle $$ dividing the interval $[0, 1)$ ...
0
votes
0answers
33 views

Intersection of 2 deterministic finite state automata, but nondeterministically

Starting from 2 simple deterministic finite state automata, I need to construct a non-deterministic automaton that accepts the intersection of the two inputs. Using the algorithm presented at ...
2
votes
0answers
18 views

Compute the coefficients of a Runge-Kutta method

Let $f$ be a Lipschitz continuous function, $(a_{ij})_{1\le i,j\le s}$ and $(b_i)_{1\le i \le s}$ some real numbers, $x_0 \in \mathbb{R}$ and $h$ an arbitrary small positive number. Under some ...
1
vote
0answers
30 views

Can someone verify my work for finding the following closures?

This is the problem I am currently working on Let R be the relation on the set {0, 1, 2, 3} containing the ordered pair (0,1), (1,1), (1,2), (2,0), (2,2), and (3,0). Find the a.reflexive closure of ...
3
votes
0answers
157 views

Execution time of function

At the algorithm SELECT, there is the following step: ...
0
votes
1answer
36 views

Function of pseudocode applying it at an array

The following pseudocode is given: ...
1
vote
2answers
59 views

How to determine which amounts of postage can be formed by using just 4 cent and 11 cent stamps?

Problem: a) Determine which amounts of postage can be formed using just 4 cent stamps and 11 cent stamps. b) Prove your answers to a using strong induction. My work: (I am only working on part a for ...
1
vote
2answers
49 views

Propability of same characters next to each other in words

At the start , I have word of length N(N characters in a word) And each character can only be A,B or C Now the words that i want is words that have 3 or more same character that is next to each ...
3
votes
0answers
71 views

Converting a pushdown automaton (that accepts by final state) to a context-free grammar

Given the following PDA: $$ P = (\{q, p\}, \{0, 1\}, \{Z_0, X\}, \delta, q, Z_0, \{p\}) $$ where the transition function $\delta$ is given by: $$ \delta(q, 0, Z_0) = \{(q, XZ_0)\} \\ \delta(q, 0, ...
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
122 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
38 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
45 views

Cryptography Combinatorics question [on hold]

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
39 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
22 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
62 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
37 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
46 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
33 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
21 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
103 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
48 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 ...