texts:
I was reading JeffE's (Prof. Jeffrey Erickson) notes on solving recurrences, and he used Merge[A[1,...n], m] where A is an array(I think) and m is an integer. What does this mean? I thought Merge sort took two arrays as input. He includes psuedo code, but I can't decipher what is means. What is it doing?

Thank you for any help.

Link:
http://jeffe.cs.illinois.edu/teaching/algorithms/notes/99-recurrences.pdf


texts: Does rice theorem applies to languages only or does it apply to machines as well?

texts:
Rice theorem says that any non trivial property of a language recognized by a Turing Machine is undecidable.

Now does this theorem applies to machines as well since we can define a language consisting of strings which are encoding of machines?

For example whether a machine will run more than 100 steps on some input? This is nontrivial but wikipedia says it is decidable.


texts: Calculating the number of unique BST generatable from n keys, why is my number so large

texts:
I want to find the number of distinct BSTs I can get with 3 unique keys (i.e. 1, 2, 3)

Here's my solution:

In case 1, we have each node have possibility, 3, 2, 1, respectively,
so 3*2*1 = 6 ways
In case 2, we have the same situation, the top node can be 1, 2, 3,
three choices, second node two choices, so and so forth, so I get 6
ways
In case 3, it is same to case 2 and I get 6 ways

In the end I have 6 + 6 + 6 number of the beast = 18 different threes.

(Edited!)

Why does this answer from Stackoverflow based on so called Catalan Number only give me 5 trees?


texts: Show that an NP-Complete problem exists that is contained in SPACE(n)

texts:
The problem I am working on is the following:

  Show that there exists an $NP$-Complete problem in $SPACE(n)$.
  Does the existence of such a problem imply that $NP$ is contained in
  $SPACE(n)$. Why or why not?

$SAT$ is contained in $SPACE(n)$. To show that, simply store Boolean formula (takes $O(n)$ space) and try all assignments for the variables.
$NP$-Complete problem is the problem that is in $NP$ and every problem in $NP$ can be reduced to it, therefore, since $SAT$ is in $SPACE(n)$, any other problem in $NP$ would be contained in SPACE(n).

Would that be a correct solution to the problem?
Also, I have come across related question on $NP \neq SPACE(n)$


texts:
Suppose I have a set of images that I will use for training. Just as an example take that I have pics of the same car in many different camera angles. I am required to identify the  important features like the mirrors, the logo,  may be some body features like curves, dents etc. These features have to be extracted from each of the pics (say manually or please suggest a better way) as these will be used for training.
 The task is I am given an arbitrary image of the same car in some unknown angle and I am to identify as many of the above features as possible. (It feels like an unsupervised learning problem)
What procedure/algorithm should I follow?
PS: I am new to the field of computer vision.


texts:
I'm reading the book The Annotated Turing by Charles Petzold. In it he mentions the Diophantine equations - which was a joy to read.

This then lead to Hilbert's 10th problem - finding an algorithm of solving Diophantine in a fixed number of steps to whole numbers. Interestingly enough - Diophantine sets are Turing Machines. (That last one kind of blows my mind).

Now this is what Turing was driving at in his paper in 1936. (On Computable Numbers, with an Application to the Entscheidungsproblem)

Now it seems to me that Macsyma (with some common heritage to Mathematica) is directed at solving Computer Algebra problems.

Now the Entscheidungsproblem (or as we know it the halting problem) has a relationship to Computer Algebra - but was more about the decidability rather than the symbolic mathematics. Can we say Macsyma was directed at both the symbolic mathematics and the halting problem?

My question is: Is there evidence to suggest Macsyma was directed at the Diophantine equations in the Entscheidungsproblem?


texts: Potential method for dynamic binary search

texts:
I'm trying to solve 17-2(b) problem from Cormen(CLRS) using potential method.

Problem from Cormen:

17-2 Making binary search dynamic
Binary search of a sorted array takes logarithmic search time, but the time to insert a new element is linear in the size of the array. We can improve the time for insertion by keeping several sorted arrays.

Specifically, suppose that we wish to support SEARCH and INSERT on a set
of $n$ elements. Let $k = \lceil \log_2(n + 1) \rceil$, and let the binary representation of n be $\langle n_{k-1}, n_{k-2}, \dots , n_0 \rangle$. We have $k$ sorted arrays $A_0, A_1, \dots, A_{k - 1}$, where for $i = 0, 1, \dots, k - 1$, the length of array $A_i$ is $2^i$. Each array is either full or empty,
depending on whether $n_i = 1$ or $n_i = 0$, respectively. The total number of elements held in all $k$ arrays is therefore $\sum^{k-1}_{i=0}n_i 2^i = n$. Although each individual array is sorted, elements in different arrays bear no particular relationship to each other.

Describe how to perform the SEARCH operation for this data structure. Analyze its worst-case running time.
Describe how to perform the INSERT operation. Analyze its worst-case and amortized running times.
Discuss how to implement DELETE.

So I'm trying to solve point b.
Working time: we have $k = \log_2(n)$ sorted arrays $A_i$ and corresponding bits $b_i$. Size of array $A_i$ is $2^i$. If it's full then $b_i = 1$ else $b_i = 0$.

If first $r$ arrays are full then we can place all elements from them to empty array $A_r$. And we need $2^{r+1} - 2$ time(we merge first arrays: $2 \cdot (2^0 + 2^1 + \dots + 2^{r-1}) = 2^{r+1} - 2$).

Let potential function be $\Phi_i = 2^{r+1} - 2$, where r is number of first bits which are 1. For example, if we have bit string 111110110101 then $r=5$. If $r = 0$ then $\Phi_i = 0$.

Now suppose that we want to calculate amortized cost $\hat{c}_i$ when first $r > 0$ bits are 1. Thus, $\hat{c}_i = 2^{r+1} - 2 + (0 - (2^{r+1} - 2)) = 0$

If $r = 0$ then $\hat{c}_i = 3$.

So we can insert $n$ elements for $\mathcal{O}(n)$ time and they will be sorted. But this is contradicts to lower bound of compare-based sorting.

Could you please help me to find a mistake in my reasoning. I know that correct amortized time is $\hat{c}_i = \mathcal{O}(\log_2(n))$ if we use account method(I found the solution).

Thank you very much!


texts: Linear ordering of all subsets of size k

texts:
I was wondering if there is an obvious way to 'name' the ${n \choose k}$ subsets of size $k$ of the integers from $1$ to $n$. So I am looking for a bijection from the subsets of $\{1,\ldots, n\}$ into $\{1, \ldots, {n \choose k}\}$ that can be computed in $O(1)$ at best.

The most trivial way for this would be to use a tree where each leaf node corresponds to such a subset but then I have to save the entire tree and each lookup will cost more than $O(1)$. We could also totally order those subsets such that $\{1, 2, 3\}$ would be the smallest subset for $k=3$ and $\{n, n-1, n-2\}$ the largest one and then use the number of smaller/equal subsets in this ordering as our index. I tried to come up with a closed form solution and it ended in some gnarly sums of binomial coefficients.

So maybe there is a well known solution to this problem and somebody could give me a reference?


texts: Let us consider a specific case of an extended Kakuro puzzle. Given an integer $n$, we must form $n$ as the sum of $k$ distinct positive integers each less than or equal to $r$. From a mathematical standpoint we know that any number including, and between $L=\frac{k(k+1)}{2}$ and $R=k(r+1)-L$ is achievable in such a way. Given a number $n$, which is between those limits, can anyone think of an algorithm to generate a set of $k$ integers which satisfy the above conditions(knowing that there is at least one such set)?


texts: Assign m agents to N points by minimizing the total distance

texts: Suppose we have $N$ fixed points (set $S$ with $|S|=N$) on the plane and $m$ agents with fixed, known initial positions ($m<N$) outside $S$. We should transfer the agents so that in our final configuration they are all positioned to different points of $S$. How could we achieve it by minimizing the total distance covered by the agents?


texts: Succinct data structure for "bookkeeping problem"

texts:
I have a "standard" problem, but I can't remember its "official" name: I have to keep track of the presence of the absence of value in an array.

Currently I use an each bits of an other array to track it.
Let's say I have a byte array of 8k elements if I want to know if a place is taken (without accessing to the array), I need a 1k byte array (8 bits per byte) to track it. So I have more or less these complexities:

Check: $O(1)$
Change: $O(1)$
Memory: $O(n/8)$

I wanted to know if there's a more memory optimized data structure keep the constant check factor because I have the following properties:

The targetted array has a fixed size known at compile-time
Most of the actions performed are Check (maybe 10k-1k checks for one change)
The array is mostly sparsed (5-25% used)
There are only few space freeing
Sometimes a value take more than one byte but I only need to keep track of the first one.

I'm looking for data-structures name or samples. Thanks.


texts:
If I have a list of length 'n' where each element is a successive power of 2 would an algorithm that simply prints each element decremented to 1 be classified as exponential time?

print([2,4,8,16]) #operations:1
print([1,4,8,16]) #operations:2
print([1,3,8,16]) #operations:3
print([1,2,8,16]) #operations:4
print([1,1,8,16])  #operations:5
print([1,1,7,16])  #operations:6
print([1,1,6,16])  #operations:7
print([1,1,..,16]) #operations+=1
print([..])       #operations+=1
print([1,1,1,1])  #operations: 2**(n+1)-2 :: O(2**n)?

Does one add the number of operations or the complexity of each operation?

Is the complexity O(2**n) or is it O(1)*(2**(n+1)-2) reducing to constant time: O(1)?

If the complexity is constant time would I need each operation to be O(2**n) for the algorithm to be classified as exponential time?  O(2**n)*(2**(n+1)-2) reducing to O(2**n) or would it reduce to double exponential time: O(2**(2**n))?

Here is some python code for such a naive algorithm:

orig_lst=[2,4,8,16]
out_lst=orig_lst[:]
ops=0
n=len(out_lst)
for ind,el in enumerate(out_lst):
    for dec in range(el,0,-1):
        ops+=1
        out_lst[ind]=dec
print(orig_lst,"->",out_lst,"number of operations:",2**(n+1)-2,"==",ops)

Which prints: "[2, 4, 8, 16] -> [1, 1, 1, 1] number of operations: 30 == 30"


texts:
I was reading http://barrywatson.se/lsi/lsi_delta_reduction.html, where

((+ 1) 2) →δ 3 is a δ-reduction.
((+ 1) ((+ 1) 1)) is a not a δ-redex.

Wouldn't $((+ 1) ((+ 1) 1)) \rightarrow ((+1) 2)) \rightarrow 3$?


texts: What are the options of head movement for a Turing machine?

texts: I find several contradictory definitions regarding the head movements of the Turing machine. In some places, it is only L / R. While in some other formal definition; it is L / S / R. Which one is correct?


texts:
Let's say that I want to map some string of binary digits to a single binary digit of output, like the below:

$
\begin{array}{l|l}
\text{Input}&\text{Output}\\
\hline
0001&0\\
0011&1\\
0111&0\\
1111&1
\end{array}
$

If inputs besides those listed are given, I don't care what the output is.  I only care about the inputs listed.

I can eyeball the truth table and come up with the below:

$Output = \lnot (Input_0 \oplus Input_1 \oplus Input_2 \oplus Input_3)$

However, that isn't the only solution, and might not be the solution using the fewest number of operations.

Are there any algorithms to figure this out for arbitrary length inputs mapping to a single binary digit of output?

Ultimately I'm trying to solve for mapping $M$ bits of input to $N$ bits of output.  I figure an ok way to do this might be to break it into $N$ problems of mapping $M$ bits of input to a single bit of output so am starting with that.

I'm actually going to be implementing something using a standard modern computer (aka desktop CPU), so I know that there is some extra complexity if I want better efficiency, due to the fact that operations happen not on single binary digits, but on eg. words.  Not only will efficiency depend on minimizing the number of operations done on each bit, there will also be efficiency to be gained by letting "bit programs" share operations where they can, if that makes sense.

One step at a time, but I bring this up in case there is an answer which encompasses my future needs as well.

Edit:
I've found these pages which talk about minterms and karnaugh maps and understand what they are talking about, however I also know that they aren't guaranteed to be the minimal circuit, and they also mention that some other algorithms are used in more complex circuit design (but they don't say what they are)
https://www.facstaff.bucknell.edu/mastascu/eLessonsHTML/Logic/Logic2.html
https://www.facstaff.bucknell.edu/mastascu/eLessonsHTML/Logic/Logic3.html


texts: The maximum number of statements that could be true at the same time

texts:
I've come across a programming question. I can't solve it but I can write the question in mathematical form as follow:

  Receive k equations,and for each equation receive 3 variables a, b, and c in the following form:

  ax + by + cz >= 0

  This is an example input of k = 4:

  1) 2x + 1y + 0z >= 0

  2) 1x - 2y + 0z >= 0

  3) 3x + 3y - 50z >= 0

  4) -1x + 2y - 50z >= 0

  You should find the maximum number of statements that could be true at the same time given that x, y, and z are positive real numbers and x >= y >= z. As for the following example, the answer is 3.

Please help me with the idea or the design paradigm I should use to solve this problem. The algorithm should be relatively fast. It should be able to compute k = 1,000 in 1 seconds.


texts: The Church-Turing Thesis (Hello World tester) contradiction and randomized algorithms

texts:
The Church-Turing thesis proves that there is no algorithm (or program) $H$ that says whether a program $P$ written in a language, say $C$, on an input $I$ outputs the sentence Hello World or not. This is his proof, visit Hopcraft and etc. introduction to automata theory languages and computation, chapter 8.

The prove is by contradiction. Let there is such a program $H$ to do the task. He made several simple changes to $H$ and built a program $H_2$, then showed $H_2$ doesn't exits.

The program $H$ is as follows

On input $P$ and $I$, it outputs yes or no which tells if the output is Hello World or not.

He then build program $H_1$ as follows

$H_1$ takes $P$ and $I$ and runs $H$ on $P$ and $I$, if $H$ prints yes, it prints yes and if $H$ prints no, it prints Hello World. The $H_1$ is as follows

He then built $H_2$ as follows

$H_2$ reads the $P$ and store in an array $A$.
$H_2$ simulates the $H_1$, but whenever $H_1$ would read an input, $H_2$ reads from stored copy in $A$.

Hence $H_2$ prints yes if $P$ prints Hello World when given itself as input and Hello world if doesn't print Hello World.

The contradiction occurs when when the $P$ is actually program $H_2$, the source code of $H_2$ is provided as input to itself. If the $H_2$ prints Yes, then $H_2$ in the box saying $H_2$ on input $H_2$ prints Hello World and the Hello World is the output of no in $H$.

  The basis of contradiction is, $H_2$ on input source code of $H_2$ printed no while we assumed it is yes and a program on the same input can't have different outputs.

If $H$ were a program with randomized algorithm, then on the same input it would have different outputs. The basis of the contradiction is if $H_2$ on input $H_2$ prints something, it can't print something else on $H_2$ again. But if $H$ contains some random process inside it, then on the same input it would print different things and it is not a contradiction at all.

Please explain where I am wring about this.

Thanks in advance.


texts: How to solve recurrence $T(n) = 5T(\frac{n}{2}) + n^2\lg^2 n$

texts:
I have tried solve the recurrence $T(n) = 5T(\frac{n}{2}) + n^2\lg^2 n$ using substitution. Apparently, it is exact for some $n$ and the order of the general solution can be found from this exact solution.
By substitution I got the following (not sure if it is correct):
$$T(n) = 5^kT(1) + \sum_{i = 0}^{k}{5^{i}\left(\frac{n}{2^{i}}\right)^{2}\lg^{2}\left(\frac{n}{2^{i}}\right)}$$
I am not sure how to proceed from this. I don't even know if this approach is correct so far. How do I solve this recurrence?


texts: Can Multiprocessor Systems Implement Both Temporal Multithreading and Simultaneous Multithreading?

texts:
I am aware that multiprocessor systems often implement simultaneous multithreading in order to allow multiple threads to run on different CPUs. I am also aware that uni-core systems often implement temporal multithreading (fine-grained/preemptive or coarse-grained/cooperative) to allow for a more efficient use of the CPU through the use of context switches.

However, I am curious whether it is possible (or logical) to have a simultaneously multithreaded system also allow for the time-sharing between threads on each CPU, which is prevalent in temporal multithreading systems.


texts: If A is decidable and B is decidable, then A is Turing Reducible to B

texts: The statement seems intuitively true but is it? If so, how can I prove this?


texts:
Let's say I needed to render an image at 1920 x 1080 and also at 1024 x 768. Instead of drawing two separate images, it might make sense to draw the scene in a common "virtual" coordinate system and then translate that to the appropriate output coordinate system.

Is there a name for this problem? I'm having a hard time figuring out what to start searching for.


texts: Is it possible that the union of two undecidable languages is decidable?

texts:
I'm trying to find two languages, $L_1, L_2 \in RE \setminus R$, such that $L_1 \cup L_2 \in R$.

I have already proved that if $L_1\cap L_2 \in R$ and $L_1 \cup L_2 \in R$, such $L_1, L_2$ don't exist (because otherwise we'll be able to construct a Turing Machine $M_1$ which will decide $L_1$, for instance).

However, I cannot prove that it's impossible in the case $L_1\cap L_2 \in RE \setminus R$, and I can't find such languages.


texts: Similar questions have occurred quite a number of times (1) (2) (3), but I have, say, a specific instance of one. I'm aware of a bunch of applications of finite automata, but would you provide an academic exposition of applications of finite state machines (like, e.g., Mealy machines) in cryptography and ciphers? There is a mention about things like that in Wikipedia article on Mealy machines (subsection “Applications”). So the links to some academic texts play up on this are very appreciated. Alternatively would you share your thoughts on how to furnish this topic (FSM in cryptography) for students?


texts: Intuition for vertex/set cover approximation algorithms

texts:
The best approximation algorithm for vertex cover is randomly choosing an edge and removing its vertices (picking the largest degree vertex actually is a worse approximation), but the best approximation algorithm for almost the identical problem of set cover does take the largest set.

How can we explain intuitively why picking the largest degree vertex doesn't result in a smaller (and thus better approximation) vertex cover, and why doesn't the same reasoning apply to sets?


texts:
I hope I named this CNF Boolean sentence the correct way. The way I see it, a 2P2N is where each literal appears twice (or at most twice, but we can say twice without loss of generality).

I am trying to prove it is Satisfiable. How do I do this? Do I need to try to reduce it to 3-SAT (might need some help doing that as well). Or is there another method of proving satisfiability?


texts: Decide whether a DFA accepts at least two strings

texts: Is the following language decidable? $$L = \{A : \text{A is a DFA and } |L(A)| \ge 2\}$$


texts: Is there an NFA whose corresponding DFA has lesser number of states than the given NFA? (without unreachable states or epsilon moves)

texts:
I'm stuck with another homework question - "Design an NFA with $n$ states such that the corresponding equivalent DFA constructed using the subset-construction method has less than $n$ states."

What I have learnt is that using subset (or powerset) construction, you can convert a given NFA with $n$ states to it's equivalent DFA with atmost $2^n$ states. I've tried constructing NFA's and tried converting them to check their equivalent DFA's number of states, with multiple attempts, but in vain.

DFA with less states than NFA

The above question tackles the possibility of a DFA having less than equivalent states to it's corresponding NFA. The question, as mentioned in some comments, doesn't take into account the fact that a DFA can have multiple equivalent NFAs, and also suggests the solution of having unreachable states to solve the problem.

Now, this does offer a solution to my homework problem, as the given problem doesn't specify that I shouldn't use unreachable states. Regarding epsilon moves, I believe my professor mentioned not to use them, if not said in the question, or indicated as an option to use, in the given question. Regardless, I can solve my problem by adding unreachable states. But that is not my question, here.

My question is, given an arbitrary NFA with $n$ states, to begin with. (without $\epsilon$ moves or unreachable states). Is there any specific case, where the  NFA (please provide an example) under said conditions is such that I can use subset construction and get a DFA with less than $n$ states?


texts: The 3-Partition problem (wiki) is a $\text{NP}$-complete problem which is to decide whether a given multiset of integers can be partitioned into triples that all have the same sum. It is well-known that the 3SAT problem has a plenty of variants. Are there some variants of the 3-Partition problem discussed in the literature?


texts: Polynomial time counter of solutions of 2SAT expression with pure literals

texts: As per the title, is there any polynomial time algorithm to count the number of satisfying arguments for a 2SAT expression with pure literals? An even shallower case: Is there any such counter when the literals in the expression are either all positive, or all negative?


texts: Number of order 4 B-trees possible with 6 distinct keys

texts:
To avoid any confusion the order of B tree is the maximum number of children it can have.
Suppose we create a B tree of order 4 by inserting 6 distinct keys (1, 2, 3, 4, 5, 6) in any permutation, how many different structure of B trees can we get?
While inserting a new node in a B tree, going by the insertion rules from Wikipedia

A single median is chosen from among the leaf's elements and the new element.

As we can have a maximum 3 keys in a node, plus the new element totalling four keys so we can choose either the 2nd or the 3rd as the median. So the new structure will be dependent on choice of the median along with insertion order.
How do I solve this problem systematically? I've been trying to brute force it and I have found these four structures
    3           4           2,4           3,5
  /  \        /   \        / | \        /   |  \
1,2  4,5,6  1,2,3  5,6    1  3  5,6   1,2   4   6

Are there more?


texts: Book CS:APP, using bit set and bit clear

texts:
Okay so I'm going through a book CS:APP.
I'm in chapter 2. And problem 2.13 talks about how the Digital Equipment VAX computer used bis (bit set) and bic (bit clear) instead of Boolean operations AND and OR.
Both instructions take a data word x and a mask word m. They generate a result z consisting of the bits x modified according to the bits of m. With bis, the modification involves setting z to 1 at each position where m is 1. With bic, the modification involves setting z to 0 at each position where m is 1.
Now you're given x and y. And you're allowed to use bis and bic to recreate x | y. And x ^ y.
Now I have already tried looking at the answers to understand what's going on. But I don't understand it.
If I literally look at explaination for bis and bic I would say bis just copies the mask and leaves x unused. And for bic it goes opposite of m, but also without using x. If I try to interpret it differently I end up with questions like what does bic do (for example) when m is 0?
The answers are for x | y: bis(x, y) where y becomes m... so a relatively simple answer.
And for x ^ y (xor): bis(bic(x, y), bic(y, x)) where y and then x becomes m
So basically anything that could clarify what's going on here would be much appreciated!
And aside from this question, I also would like to ask if this is the right place for questions about a specific CS book? Because I'm teaching myself and don't have a teacher or someone to ask questions to and seeing with the previous exercise I also had a question it's possible that I might get a lot. But I can't find anything when searching on CS:APP (Computer Systems: A Programmer's Perspective) and yeah don't know where else to turn to. The book was recommended through teachyourselfcs.com if anyone was wondering.


texts: What is shell expansion in programming language theory?

texts:
From Bash Reference Manual

  Expansion is performed on the command line after it has been split
  into tokens. There are seven kinds of expansion performed:

  brace expansion
  tilde expansion
  parameter and variable expansion
  command substitution
  arithmetic expansion
  word splitting
  filename expansion

From the programming languages perspective,  are shell expansions of the same kind of pre-defined compiler macros in C?

What is the concept for shell expansions called in programming languages?


texts:
It's well known that linear congruential generators have a full period only if a few properties are fulfilled.

Now I need a LCG that does not generate a full period in 2^32 (easy to find, just violate one requirement) and I need one of those values in the period that's not used.

Is there any clever math trick/algorithm to find such a thing? I can see the obvious bruteforce solution, but that'd take quite some time and tons of memory - also it seems like an interesting math problem. I did check Knuth but he obviously focuses on showing how to get a full period.

PS: For people wondering - I have to trick a compiler into making sure it can't use DCE on some values and this seems like a very performant and hard to figure out way to achieve this.


texts: Is there a difference between computational graphs and neural networks?

texts:
According to this post, "neural networks are a special form [of a computational graph]". I think that one can infer from that that all neural networks are computational graphs.

My question then would be: are there computational graphs that aren't neural networks?


texts: List of scheduling problems and their statuses

texts:
As of 1993, there are 4536 scheduling problems, 3821 were proven to be $NP$-hard, 417 polynomially solvable, and 298 still open.

Where can I find the most up-to-date list of scheduling problems and their statuses (if they are $NP$-hard, polynomially solvable or open)?


texts: Approximation rate for Greedy Set Cover algorithm (RESOLVED)

texts:
Set Cover: Consider a set of points X and Si a subset of X. The goal is to get the minimum number of subsets Si such as all points in X are covered. An example is shown by figure bellow. In this case, optimal solution should be OPT = {S3, S4, S5}.

Greedy Algorithm:

greedy(X, F = {S1, S2, ...})
     G_OPT = {}
     U = X
     while U = empty set
          Pick s in F with greatest coverage in U
          G_OPT = G_OPT + s
          U = U - s
     return G_OPT

Goal: To find approximation rate of greedy set cover algorithm above.

What I have so far: Let t be the size of optimal soltion, $t = |OPT|$.

At the beginning of step k + 1, the number of uncovered items in X is given by $|U_{k+1}| = |U_{k}| -$ # of newly covered items;
By pigeonhole principle, # of newly covered items $\leq \frac{|Uk|}{t}$ and then $|U_{k+1}| \leq |U_{k}| - \frac{|U_{k}|}{t} = |Uk|(1 - \frac{1}{t})$;
Taking the Taylor's Series of $\exp(-\frac{1}{t})$, one can easily see that $exp(-\frac{1}{t}) \geq (1 - \frac{1}{t})$;
So, $|U_{k+1}| <= |U_{k}| \times exp(-\frac{1}{t})$;
$|U_{0}| = |X| = n$ (none item is covered at step 0);
Taking $|U_{1}| = n \times exp(-\frac{1}{t})$, gives $|U_{2}| = |U_{1}| \times exp(-\frac{1}{t}) = n \times exp(-\frac{2}{t})$, $|U_{3}| = |U_{2}| \times exp(-\frac{1}{t}) = n \times exp(-\frac{3}{t})$ so on and so forth. Therefore, $|U_{k}| = n \times exp(-\frac{k}{t})$;
Lets say there is no item uncovered at k-th step. So, $|U_{k}| = 0$ and $n \times exp(-\frac{k}{t}) < 1$ (otherwise, there could be a remaining uncovered item in $U_{k}$, and this would be a contradiction of $|U_{k}| = 0)$;
It is possible to get $\frac{k}{t} > ln(n)$ by taking log over the previous inequality.

The expected answer is $\frac{k}{t} \leq ln(n) + 1$. I have seen some lecture videos and lecture notes on the internet that give raise to the same results as I described above. However, they are all vague while getting from $\frac{k}{t} > ln(n)$ to $\frac{k}{t} \leq ln(n) + 1$.

All I can see about k, t and n is:

$k \geq t$
$t \leq n$

Does anyone know the "trick"?


texts: Difference between sequential and parallel divide and conquer

texts:
In the textbook Introduction to Algorithm, third edition, by Coremen et al. (CLRS), the following introduction has been given about divide and conquer algorithm strategy

  In divide and conquer, we solve a problem recursively, applying three
  steps at each level of recursion:

  Divide the problem into a number of subproblems that are smaller
  instances of the same problem

  Conquer the subproblems by solving them recursively. If the
  subproblems sizes are small enough, however, just solve the problems
  in a straight forward manner.

  Combine the solutions into the solution of the original problem.

This algorithmic strategy is assumed on sequential machines and is a non-parallel divide and conquer strategy.

How is parallel divide and conquer different from the above? Which step among divide, conquer, combine will be different?

My assumption is that the dividing step will not change and combine step will not change, but only the conquer step changes and the change will be that each subproblem will be solved in parallel. Is it true?


texts: Supervised learning with no prior information

texts:
I am now reading two modern books on machine learning theory. Both of them emphasize that, in order to succeed in supervised learning, one must choose a good hypothesis class. "Good" means that it is sufficiently simple (formally, has a low VC dimension) and that it contains the true hypothesis or sufficiently close hypotheses. One also mentions the "no free lunch theorem", which says that, without such prior knowledge, you cannot have meaningful learning.

But what do I do if I have no prior knowledge? I have no idea how the correct hypothesis looks like, I do not know if it will be simple or complex. All I have is the training data. Isn't there anything useful I can do with them?

I am thinking of a newly born child. He has no prior knowledge, all he has are "training samples" given by his parents/teachers, and it is still sufficient for meaningful learning.  You could say that each child is born with some prior knowledge wired into his brain, but then the question is:  where such prior knowledge comes from? And again, what should a person do in a new situation on which his wired prior-knowledge is useless?

To sum, my question is: what is a supervised learning paradigm that can be applied without any prior knowledge on the set of possible hypotheses?


texts: Karp hardness of a vector system allocation

texts:
Given an undirected graph $G(V,E)$, a vector system is a set $S$ of ordered pair (intuitively called vector) $(u,v)$ (we shall call $u$ the initial point, and $v$ the terminal point) that satisfies the following criteria:

For each vector $(u,v)\in S$, we have that $uv \in E(G)$. So, each vector must be an orientation of an edge
No two vectors share the same initial point. Formally, for every two vectors $(u,v),(w,x)\in S$, we have that $u\neq w$
An initial point of a vector cannot be the terminal point of other vector. Formally, for every two vectors $(u,v),(w,x)\in S$, we have that $v\neq w$

Now, our problem is defined as follows:

  Input: An undirected graph $G(V, E)$ and a natural number $k$

  Output: YES if it is possible to allocate a vector system of size $k$ in $G$, otherwise NO

What is the hardness of this problem?


texts:
The following problem seems very similar to the $stCON$ decision problem:

{$G, s,t  |  G = (V, E)$ such as $V$ is a graph, $s,t ∈ V$,
there exists in $G$ a simple path from $s$ to $t$ of length $≥ n/2$}

But from what I've read, it cannot be placed in $NL$. The reason is unclear. Why it cannot be placed in $NL$ using an verifier Turing Mechine like in $stCON$ case and another counter for the path length?


texts: N-ary (NOT binary) Gentle Boost algorithm?

texts: I know Gentle Boost, an adaption of the AdaBoost algorithm, can be used for binary classification. However, I need to do $n$-ary classification. How do I modify or extend the GentleBoost algorithm so it can be used for $n$-ary classification?


texts:
Introduction

For those who did not read my prior question, I have created an algorithm that generates n^2 x n^2 Sudoku Grids. Out of those grids I remove elements to give only one solution. The algorithm follows an infinite language based on circular matrix shift of elements. It does so in such a way that allows valid grids to be formed. Explained Here-1, Here-2, Here-3 and algorithm in python

Decision Problem

Before reading make sure the links are read first.

Given an n^2 x n^2 grid G does there exist a mapping of a puzzle that will allow only one solution?

Here I test to see if my problem is in NP

g = grid

p = mapped puzzle

The certificate (g, p) is accepted by the checker

run backtracker....

print "analyzing puzzle to check possible solutions"

       if p == one solution

       print "valid shift-L puzzle"
else:
       print "false"

Proof that Puzzle completion is NP-Complete

It is already proven by Colborn with a reduction from a NP-complete problem known as Triangle Partition of tripartite graphs. Explained here

Question

With a pre-existing proof that latin square completion is NP-complete, is it safe for me to firmly say my puzzle generation (or puzzles) is at least NP-hard?


texts: Optimally find one of the total orderings for a poset based on some metadata about the elements

texts:
Given a finite, partially ordered set with the following two properties:

Every element in the set has one of two types: "A" or "B". The type does not define the total ordering of the set and is metadata.
Every element in the set is a natural number and the poset can be ranked by the numbers themselves. This means that the sorted elements themselves provide one of the possible total orders of the poset, or in graph theory, one of the topological orderings of the DAG.

What is the most optimal algorithm to find the total ordering of the described poset that groups elements with the same type together?

The posets are represented by describing the type and dependencies of every element such that:

0:{[], A}, 1:{[0], A}, 2:{[], B}, 3:{[2], A} 4:{[0], A}, 5:{[0,1,4], B}, 6:{[1,2], A}, 7:{[3,6], A}

looks like this:

Where the blue dot represents the "B" type and every other element is of type "A". The following are some of the valid total orderings:

[0, 1, 2, 3, 4, 5, 6, 7]
[0, 2, 1, 4, 3, 6, 5, 7]
[0, 2, 1, 4, 3, 6, 7, 5]

However, I have been trying to find the most optimal algorithm that will group elements based on their type, if it is possible, while preserving the total order. For the DAG/poset in the example, one of the possible solutions would be:

[[0, 1, 4], [5, 2], [6, 3, 7]]

Thank you!


texts: is it possible to determine using a single depth-first search, in O(V+E) time, whether a directed graph is singly connected?

texts:
I'm working on exercise 22.3-13 of CLRS (Intro to Algorithms 3rd edition):

  A directed graph $G = (V, E)$ is singly connected if the existence of a path from $u$ to $v$ implies that $G$ contains at most one simple path from $u$ to $v$ for all vertices $u, v\in G$. Give an efficient algorithm to determine whether or not a directed graph is singly connected.

Previous threads on this question are here and here. In that second thread, one of the answers links to a preprint by someone who corresponded with one of the authors of the book, and stated (in the abstract of the preprint) that the solution the authors intended was (if I'm understanding correctly) to call DFS-VISIT(G, u) (from p. 604 of CLRS) on each vertex $u$ of the graph, resetting all vertex colors back to white (to indicate unvisited) in between calls, and return false (for "not singly connected") whenever a forward edge or cross edge is found, and returning true otherwise. This would take O(VE) time.

There seems to be some confusion in the answers and comments section of those threads: the above scheme is referred to as "calling DFS on every vertex". In fact, this is different from the DFS algorithm presented on p. 604 of CLRS, which calls DFS-VISIT on all unvisited nodes in the graph, without resetting the colors in between calls, which takes $O(V + E)$ time.

My question is, instead of doing what is stated in the preprint, which takes O(VE) time, is it sufficient to simply perform the ordinary $O(V + E)$ DFS on the graph, and return false (for "not singly connected") whenever a forward edge or a cross edge that is located entirely within a single DF tree is found? (As correctly pointed out in one of the comments in the second thread linked above, a cross edge within a single DF tree means the graph is certainly not singly connected, but a cross edge between two vertices in different trees does not necessarily mean so).

In other words, is it possible to have a non-singly connected graph, such that for some ordering of the adjacency lists, performing the DFS algorithm from p. 604 of CLRS will not find any forward edges or cross edges within individual trees, but possibly only cross edges between trees, if any?


texts:
I have an exam coming up and my teacher posted a practice exam for it.  Problem is that I solved the question but I am not sure if I am doing it right or getting the right answer as he refuses to give us an answer key to confirm if we got it right or not.  The question goes

Given a simple page table as the figure below.  For each of the following logical address, determine the physical address.  Assume that page size is 1024 bytes.

a) x1E53

b) x3746

Table below

Can someone explain the steps on how to get the answers?  I believe I got something but I am not sure if its right or not.  I got for a 1x8000253 and for b 0xF800346 but once again I am not sure if I did this right.  Sorry and thank you.


texts: Methods, Routines, or Algorithms To Optimize Selection of String Compression Methods

texts:
When encoding a a 2D Datamatrix barcode, I want the smallest output size. There are means to encode a compressed a string using some methods like C40.
Reference:

Here's a reference: https://en.wikipedia.org/wiki/Data_Matrix#Text_modes

Some sections of the string will compress more efficiently than others depending on the encoding method.

To be clear, I'm not trying to make my own compression scheme.

I want to compute the best combination of existing compression schemes. For example, I can individually use Ascii or C40 to encode an entire string. Each scheme has its unique benefits.

BUT I can also compress specific parts of the string with different schemes. So, switching back and forth between Ascii and C40 can result in a more efficient compression than C40 or Ascii alone.

QUESTION:
How do I optimize the selection of compression schemes for section of the input string. I would be comfortable narrowing it down to only combining c40 and ascii.

Are there any algorithms for scanning strings and and optimizing the result?


texts: What is the need for "some constant" times $n$?

texts:
I have a question regarding the following sentence:

So we can make the following expressions:
The best case running time of LINEARSEARCH is a constant function $T(n)=a$ OR $Θ(1)$
The worst case running time of LINEARSEARCH is a linear function of $T(n)=an + b$ OR $Θ(n)$
Merging them together, the running time of LINEARSEARCH is no more than some constant times $n$

There is reference to some constant, what is the point of this constant? Why is not just that the running time is $n$?
What is the some constant and why does it need to be taken into consideration?


texts: How to determine if a database schema violates one of the less known normal forms?

texts:
In database normalization, 1NF (no multivalued attributes), 2NF (all non-PK attributes depending only on PK attributes) and 3NF (all non-PK attributes depending on all of the PK attributes) are widely known. The 4NF (no part of the PK depending on other part of the PK) is less known, but still reasonably known.

Much less known are the 5NF, 6NF and the intermediates EKNF (Elementary Key normal form), BCNF (Boyce-Codd normal form - 3.5) and DKNF (Domain/Key normal form - 5.5). What exactly are that? Given a database schema, how do I determine if any table violates one of these much less knows normal forms?


texts: The complexity of BDD Synchronous Composition

texts:
As shown in Byrant's original paper, the time complexity of (single-variable) composition algorithm is cubic, and it is a tight upper bound. My question is about synchronous composition, written as
$$f' = f(x_{1},\dots,x_{n})|_{x_1=g_1, \dots, x_n=g_n}$$
where you replace all variables of $f$ synchronously with other Boolean functions $G$ over $X$.

However, I couldn't find an explicit reference mentioning time and space complexity of synchronous composition for BDDs. Is anyone of you aware of such results?


texts: Concatenation among different language types

texts:
I am trying to figure out the result of the concatenation among different language types (regular, context free, ...). I think the result strongly depends on the nature of the languages which will be concatenated, but I have some doubts on determining the category the result belongs to. Maybe troughout an example it will be easier to solve all my doubts and let you understand better the nature of my question. For instance, let $L = \left \{ 0^{n}\cdot 1^{n} \mid n \geq 0 \right \}$ and $L^{R} = \left \{ 1^{n}\cdot 0^{n} \mid n \geq 0 \right \}$

Those two languages are obviosly not regular (it's easy to apply the Pumping Lemma here)
but what happens if I define this result language $L{}' = L \cdot \left \{ 0, 1 \right \}^{*} \cdot L^{R}$

I think it should be still not regular, since we can apply again the pumping lemma by letting be $p$ the length of the pumping and $w=0^{p}1^{2p}0^{p}$, w is in $L'$. The contination is easily.

But is it good to consider that w of $L'$?


texts: What is the difference between python list and c++ vector?

texts: I read about the similarities between the python list and c++ vector and it looks as if the only difference is python list is heterogeneous. Are there any other differences? How are they both implemented?


texts: Why we can't have some algorithm to be polynomial if there are generic conditions that make them so?

texts:
I explain it better:
There are some algorithms that is clearly in NP, also NP-complete, but that under certain conditions they can be solved in polynomial time.
An example is Bin Packing, the decision version of the problem is an NP-complete problem and it's defined as follows in the book "Computers and Intractability" by Michael R. Garey and David S. Johnson:

INSTANCE: Finite set $U$ of items, a size $s(u) \in Z$ for each $u \in U$, a positive integer bin capacity $B$, and a positive integer $K$.
QUESTION: Is there a partition of $U$ into disjoint sets $U_1, U_2, ..., U_k$ such that the sum of sizes of the items in each $U_i$ is $B$ or less.

And there is a comment that says "Solvable in polynomial time for any fixed $B$ by exhaustive search."
I have asked in math.stackexchange how it is possible and I get a clearly answer about that:
https://math.stackexchange.com/questions/3804912/bin-packing-problem-with-fixed-size-of-bins
Now I ask you why we can't applicate things like this to all instance of the problems? What is the thing that I don't get that makes this impossible?
For example, in the Bin Packing problem I think that I would can always enumerate the solutions and search into them because the $ B $ is always fixed once I get it, ok the number of the solutions could be a huge number, but it still remains a polynomial time algorithm. Or the "enumerate solutions" meanings that they are precomputated and the algorithm just has to check between them? And in this case, why we can't precomputate always?
I'm not saying something like $ P=NP $ because I'm sure not the first person that think about this thing and if the most accredited opinion is that $ P \not= NP $ it must be why this thought of mine is wrong and I want to understand why this isn't a generic solution for the problem, and where I'm wrong.


texts: Terminologies of "Process calculus" and "Process algebra"

texts:
In the literature, the terms of "process calculus" and "process algebra" are often interchangeable. Meanwhile, it confused me.

My questions are:

  Are there formal, standard, and widely-accepted definitions of "calculus" and "algebra"?
  What are the significant distinctions (maybe informally) between "calculus" and "algebra"?
  What are the features that make a theory kind of "calculus" or "algebra"?


texts: How are the number of bytes less than the number of pixels in an image?

texts:
Lets take, for example this jpeg image here

The image there is 400 x 300, or 120000 pixels and The file size of the image (on my computer) is shown to be 65171 bytes.

This means the computer stores about 2 pixels in every byte. How does it do this? Is it due to the same color pixels repeating in the image, so it only has to save the RGB data once, or is there some other trickery going on here?


texts: Why do admissible functions allow $A^*$ to retain correct shortest path computations?

texts:
I was reading about how to use $A^*$ and was told that:

  A heuristic is admissible if $h(u) \leq \delta(u,t)$, where $\delta(u,t)$ function indicates that the shortest path from $u$ to $t$.

I was wondering why such a condition guarantees that the shortest paths can still be computed.

Its clear to me if the heuristic is defined as with the help of a potential function $\lambda(u)$:

$$ h(u) = \lambda(u) - \lambda(s) $$

and the new weights are defined as (i.e. the potential function is feasible):

$$ w^*(u,v) = w(u,v) + h(u) = w(u,v) + \lambda(u) - \lambda(s) $$

then if we have $w^*(u,v) \geq 0$ with that heuristic then its clear that shortest paths are retained (because of telescoping series).

However, otherwise, I can't see why admissible function would retain shortest paths or what the motivation is to use admissible function with the property $h(u) \leq \delta(u,t)$. Why is that?

Usually heuristics tilt search algorithms to better paths, how do admissible function attain this?


texts: Is the infinite language unrecognizable in a Turing machine?

texts:
This question is building up on an older one, here.

But now let's say we keep $Σ=\{0,1\}$. Is the TM that accept anys ($1^x \mid x \gt 0$) recognizable?
That means 1, 11, 11111, 1111111, and so on are all accepted.

I believe the TM is unrecognizable. This is because for it to be recognizable, we would have to halt. Yet, with no upper limit, we can have $1^\infty$ - meaning we will never halt. Does this work?

The above was an example of a language, didn't think it would be recognizable. A better way to phrase my question is: Is there a language of any number of $1$s over $\Sigma=\{0, 1\}$ that you can make unrecognizable?


texts: Are if statements unnecessary if a program is represented as an explicit state machine?

texts:
This question occurred to me some time ago when I was thinking about whether or not if statements are fundamental in computation.

Consider a program that manages a single bank account (for the sake of simplicity). The bank account could be defined as something like

Account
{
    int balance; // current amount of Money

    boolean withdraw(int n)
    {
       if (balance >= n)
       {
           balance = balance -n;
           return true;
       }
       else
           return false;
    }

    void deposit(int n)
    {
       amount = amount + n;
    }
}

Since the program has no way to known in which state it currently is unless it performs validations using if statements, as in the withdraw operation, if statements are unavoidable.

However, over the course of time, the program will pass through a finite set of states that can be known beforehand. In this particular case, a state is defined solely by the value of the balance variable, hence we would have states: {balance = 0 , balance = 1, balance = 2...}.

If we assign each state a number, say state {0,1,2,....} with a 1-1 correspondence to the above set of states, and assign to each operation a number identifier as well (say deposit = 0 and withdraw = 1), we could model the program as an explicit transition between states and therefore remove every if statement from the code.

Consider that state = 0 is the state where balance = 0 and we want to perform a deposit of 50 dollars, if we coded every single possible execution of the deposit function, we could just define the deposit function as

void deposit (int n)
{
   deposit[state][n]; // índex deposit instance for state = 0, amount = n;
}

deposit[][] would be a matrix of pointers for a set of functions that represent each possible execution of deposit, like

deposit[0][0] -> balance = balance + 0; state = 0;
deposit[0][1] -> balance = balance + 1; state = 1;

....

In the case of withdrawal, it would be like:

boolean withdraw (int n)
{
    // índex withdraw instance for the current state and amount=n
    return withdraw[state][n];
}

withdraw[][] would be a matrix of pointers for a set of functions that represent each possible execution of withdraw, like:

deposit[0][100] -> return false; state = state;
...
deposit[200][100] -> balance = balance - 100; return true; state = 100;

In this situation, the program the managers the single bank account can be written without using a single if statement!

As a consequence however, we have to use A LOT more memory, which may make the solution unreasonable. Also one may put the question of how did we fill the deposit[][] and withdraw[][] matrices? By hand? It somehow implies that a previous computation that used ifs as necessary to determine and possible states and transitions.

All in all, are ifs fundamental or does my example prove that they aren't? If they are, can you provide me an example where this does not work? If they are not, why dont we use solutions like these more often?

Is there some law of computation which states that if statements are unavoidable?


texts:
I think I know how the arithmetic coding works but what I don't understand is the reasoning about efficiency.

I have read in this pdf that the number of bits required to specify a range is greater the smaller is the interval. This is obvious.

Then I read that:

$$2^{-l(x)} \leq \frac{p(x)}{2}$$
so
$$l(x)\geq \log{\frac{1}{p(x)}} + 1$$
and then
$$l(x) = \left \lceil -\log{p(x)} \right \rceil +1$$

Then the arithmetic coding efficiency is:
$$H(X) \leq \overline{l} \leq H(X) + 2$$

where:

$x$ is the symbol emitted by the source
$l(x)$ is the length of that encoded symbol
$p(x)$ is its probability
$\bar{l}$ is the average length of the encoded symbols emitted by source

Some might explain me better these steps?

I tried to understand what $2^{−l(x)}$ means, but I didn't understand so I'm "stalled".
I want to understand why the arithmetic coding is "worst" of the Huffman coding, that is why the upper limit of $\bar{l}$ is $H(X)+2$.
So I would like to understand the steps that lead to determine $H(X)+2$. We are therefore talking about binary coding so I assume that the two of $\bar{l}$ resulting from this. But why $\frac{p(x)}{2}$ and why $2^{−l(x)}$?

I can't find an explanation for $H(X)+2$.

Thank you very much

@PeterShor First of all, thanks for your time. The main book I'm using is Cover & Thomas (pag. 128).

In this book it says that $x$ is encoded with $\bar{F}(x)$.
"But, in general, $\bar{F}(x)$ is a real number expressible only by an infinite number of bits. So it is not efficient to use the exact value of $\bar{F}(x)$ as a code for $x$. If we use an approximate value, what is the required accuracy?
Assume that we truncate $\bar{F}(x)$ to $l(x)$ bits denoted by $\left \lfloor\bar{F}(x)_{l(x)}\right \rfloor$.

Thus, we use the first $l(x)$ bits of $\bar{F}(x)$ as a code for $x$.
By definition of rounding off, we have $\bar{F}(x) - \left \lfloor\bar{F}(x)_{l(x)}\right \rfloor < \frac{1}{2^{l(x)}}$.
If $l(x) = \left \lceil \log \frac{1}{p(x)} \right \rceil + 1$, then:
$\frac{1}{2^{l(x)}} < \frac{p(x)}{2} = \bar{F}(x) - F(x-1)$
..."

There are two things that I didn't understand.

"in general, $\bar{F}(x)$ is a real number expressible only by an infinite number of bits." Why? There may be a finite number of digits, and not infinite, or not?
I don't understand the formula $\bar{F}(x) - \left \lfloor\bar{F}(x)_{l(x)}\right \rfloor < \frac{1}{2^{l(x)}}$.

Since reading this book I didn't undestand these things, I tried another text that could help me (see the pdf in Italian).


texts: How do I verify that a DFA is equivalent to a NFA?

texts: I'm learning how to convert NFAs to DFAs and I want to make sure I'm doing it right. Obviously, going back in the other direction isn't a thing. Does anyone know of an algorithm to check that a DFA is equivalent to a NFA?


texts: Computing set difference between two large sets

texts:
I have two large sets of integers $A$ and $B$.  Each set has about a million entries, and each entry is a positive integer that is at most 10 digits long.

What is the best algorithm to compute $A\setminus B$ and $B\setminus A$? In other words, how can I efficiently compute the list of entries of $A$ that are not in $B$ and vice versa?  What would be the best data structure to represent these two sets, to make these operations efficient?

The best approach I can come up with is storing these two sets as sorted lists, and compare every element of $A$ against every element of $B$, in a linear fashion.  Can we do better?


texts: Space bounded Turing Machine - clarification on Computational Complexity (book: Arora-Barak ) question 4.1

texts:
I have the following question from Computational Complexity - A modern Approach by Sanjeev Arora and Boaz Barak:

  [Q 4.1]
  Prove the existence of a universal TM for space bounded computation (analogously to the deterministic universal TM of Theorem 1.9).

That is, prove that there exists a Turing Machine $SU$ such that for every string $\alpha$ and input $x$, if the TM $M_\alpha$ -- the TM represented by $\alpha$ -- halts on $x$ before using $t$ cells of its work tape, then $SU(\alpha, t, x) = M_\alpha(x)$ and moreover, $SU$ uses at most $C\cdot t$ cells of its work tape, where $C$ is a constant depending only on $M_\alpha$.

After checking theorem 1.9 and the universal TM with time bound, I see that the construct $SU(\alpha, t, x)$ means that the Turing machine SU stops after $t$ steps. However if this is the case, then it means that we can create a Turing Machine equivalent to $M_\alpha$ such that the new Turing Machine stops in $t$ steps where $t$ is the "space" used in the original.

However, this seems a dubious interchange of space and time. If on the other hand, $t$ actually meant that the second machine stops within $t$ space, too, then the second part does not make sense any more because it says $SU$ uses $Ct$ cells, which is not $t$.

So my question is how do I interpret this? Is the first interpretation really possible?


texts:
In the question in this video about quicksort luckily picking the median in each recursive call. Tim Roughgarden, the presenter, says at 11:22

Partition needs really linear time, not just $O(n)$ time.

What does he mean here? I thought linear time is $O(n)$. Does he mean $\Theta(n)$ or something else? I see how partition in quicksort here would be $\Theta(n)$ but I don't get the part that says "not just $O(n)$ time".


texts: Proving undecidability of the language composed of LBAs where their language is empty

texts:
As it is explained in Sipser's book, the following language is undecidable and he proves this using the computation history method.

$\qquad E = \{\langle M \rangle \mid M\ \mathrm{LBA}, L(M)=\emptyset\}$

I wanted to see if we could use the same method used for proving undecidability of the following language in the case of LBAs too (instead of using computation history method).

$\qquad E' = \{\langle M \rangle \mid M\ \mathrm{TM}, L(M)=\emptyset\}$

Is it possible?


texts: What does it mean by "consistent view of memory" in lock-free dequeue implementation?

texts:
I am currently reading this paper by Chales-Lev. This paper explain an implementation of work-stealing dequeue. The part where I don't understand is in the implementation of steal operation.

public Object steal() {
11 long t = this.top;
12 long b = this.bottom;
13 CircularArray a = this.activeArray;
14 long size = b - t;
15 if (size <= 0) return Empty;
16 Object o = a.get(t);
17 if (! casTop(t, t+1))
18 return Abort;
19 return o;
}

I am confused by this sentence on page 3 regarding this implementation:

  Note that because top is read before bottom, it is guaranteed that the
  values read represent a consistent view of the memory. Specifically,
  it implies that bottom and top indeed had their observed values when
  bottom was read at Line 12.

I actually have find an example where loading bottom before top is problematic. Say for example where one thread do steal operation and in between the load bottom and load top operation there is another threads that keep doing pop operation until the queue is empty. Then after that we load top variable. Because we load the bottom variable first, we don't know that the queue is already empty and at that point of time, top variable is up to date so the casTop() will be successful. But if we load the top variable first. There is no way to make the queue empty without modifying the top variable, so the casTop() will fail when there is another thread that try to make the dequeue empty.

But I still don't understand the sentence above. What does it mean by consistent view of memory? Even though I already find the reason why I must load top first before bottom, I afraid there is a concept that I don't understand here.


texts: Non-regularity of the set of primes in unary encoding using Myhill-Nerode

texts:
I have found many proofs for this using pumping lemma, I'm curious of how to proof it via Myhill-Nerode theorem.

Suppose $L= \{a^p \mid p \text{ is prime}\}$ is regular. Then we have congruence such $u ∼ v ⇒ uw ∼ vw$ of finite index $k$, so it has $k$ equivalence classes. $L$ is union of some of its equivalence classes.

Let's choose $aa,aaa,...,a^{p_k},a^{p_{k+1}}$, where $p_k$ is $k$-th prime. Then, there exists $i,j$ from $\{1,...,k+1\}$, that $a^i∼a^j$. Now we should concatenate some word to $a^i$ and $a^j$, that one of the words is in $L$, while the other is not, but in contradiction, they are in the same equivalence class.

Any ideas?


texts: Polynomial Identity Testing $(\mathsf{PIT\text{}})$ in non commutative setting

texts:
Let me define the problems first

Polynomial Identity Testing $(\mathsf{PIT\text{}})$

Given :  A polynomial $p$ over some field $\mathbb{F}$.

Decide : Are all coefficients of the monomials of $p$ are equal to zero ?

Polynomial Identity Testing $(\mathsf{PIT1\text{}})$

Polynomial identity testing defined in non commutative setting i.e. $x.y \neq y.x $

Given :  A polynomial $p$ over some field $\mathbb{F}$.

Decide : Are all coefficients of the monomials of $p$ are equal to zero?

Evaluates to Zero Everywhere $(\mathsf{EZE\text{}})$

Given :  A polynomial $p$ over some field $\mathbb{F}$.

Decide : Is it true that for every choice of numbers $a \in \mathbb{F}$, the value of $p(a)$ is the number $0$.

My question : Are $\mathsf{PIT\text{}}$ and $\mathsf{PIT1\text{}}$ equivalent?

Reference : http://www.cs.ubc.ca/~nickhar/W12/Lecture9Notes.pdf


texts: Complexity of backtracking to find power set given random array of numbers

texts:
Given an array of elements which can contain duplicates, this is an algorithm that solves the problem.
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:

    nums.sort()
    res = [[]]
    self.dfs(nums, res, [], 0)
    return res

def dfs(self, nums, res, path, index):

    if path not in res:
        res.append(path)

    for pos in range(index, len(nums)):
        self.dfs(nums, res, path + [nums[pos]], pos+1)

I think the time complexity of this algorithm is: $n \cdot n! \cdot  2^{n}$,
My logic is as follows, we loop the array once per value i.e., $n$
For each loop the number of calls is $(n-1)!$ which is $n!$ complexity
Then there is a check if value in array in each call which has at most $2^n$ checks since thats when power set is complete but dupes are being checked
Combining them gives $n \cdot n! \cdot 2^n$
Is this correct?


texts: What architectural features will allow this microprocessor to access a separate "I/O space"?

texts:
I'm studying for my final and don't understand this question.  Here is the full question (from Stallings 8th edition):

  Consider a hypothetical microprocessor generating a 16-bit address
  (e.g., assume the program counter and the address registers are 16
  bits wide) and having a 16-bit data bus.

  a. What is the maximum memory address space that the processor can
  access directly if it is connected to a “16-bit memory”?

  b. What is the maximum memory address space that the processor can
  access directly if it is connected to an “8-bit memory”?

  c. What architectural features will allow this microprocessor to
  access a separate “I/O space”?

  d. If an input and an output instruction can specify an 8-bit I/O
  port number, how many 8-bit I/O ports can the microprocessor support?
  How many 16-bit I/O ports? Explain.

If I'm following, the answer to "a" is the processor is generating 2^16 = 64 Kbytes and the bus is 16-bit so the answer it 64 Kbytes.

However, for "b", the answer is 64 Kbytes are being generated but since the bus is only 8-bit, it requires twice as many cycles.

For the answer to "c", I am clueless and I think that carries over into me being clueless on "d". :-\


texts:
As reading the textbook of Introduction to the theory of computation_third edition - Michael Sipser, which have the concept that we call a context-free language L inherently unambiguous if there does not exist an ambiguous CFG that generates L.

Do we have any CFLs are inherently unambiguous? if so, can you please give me an example?


texts: How to prove that Inner product of two $n$ dimensional vectors requires at least $n$ many multiplications?

texts:
Input : Two matrices $A$ and $B$ of size $n$ X $n$.

Compute : Matrix product $A$ X $B$.

Some of the known results about matrix multiplication are given below.

Brute Force : $O(n^3)$.

Nader H. Bshouty : at least $2.5$ $n^2 -$$o( n^2 )$ [over binary field] multiplications. A lower bound for matrix multiplication

A paper by Yijie Han :  Matrix Multiplication Algorithm by Yijie Han

After reading the paper above I come to know that lower bound for matrix multiplication reduces to the problem of finding inner product of two vectors. I know how to compute a inner product of two vector in a brute force way. So my question is

Question  : How to prove that Inner product of two $n$ dimensional vectors requires at least $n$ many multiplications ?.


texts: Alternating Turing Machine: Why one cannot generalize the proof of AL = P?

texts:
In their paper "Alternation" Chandra et al. show how an Alternating Turing Machine can simulate a Deterministic Turing Machine with time-complexity $t(n)$ using only $\log(t(n))$ space what implies $P \subseteq AL$.

I wonder why one cannot use the same (or at least a quite similar) construction in order to simulate a Non-deterministic Turing machine with time complexity $t(n)$ using only $\log(t(n))$ space.


texts:
I have an algorithm which searches a sorted int array for two elements which sum up to a searched value. First I thought that the complexity is $\mathcal{O}(n)$, but the interpolation search algorithm has a similar approach and has a $\mathcal{O}(\log(log(n)))$ complexity with uniform distributed elements.

Which is the right complexity and why?

boolean hasPairWithSum(int[] elements, int sum) {
    int start = 0;
    int end = elements.length-1;
    while (start < end) {
      int tempSum = elements[start] + elements[end];
      if (tempSum == sum) return true;
      if (tempSum > sum) {
          end--;
      } else {
          start++;
      }
  }
  return false;
}


texts: Shortest directed path connecting given subset of vertices

texts:
Given

weighted directed graph $G = (V,E,w)$, where $w : E \to \mathbb R^+$
source vertex $v \in V$
vertex subset $U \subset V$

how to find a shortest directed path from $v$ containing all vertices from $U$? Note that such path may contain vertices that are not in $U$.

Does such problem have a name?
How to find a solution?


texts: Given 2 regular languages and their DFA's, how to construct the DFA of the union?

texts:
Suppose $L1, L2$ are both regular languages and $A1, A2$ are their corresponding DFA's.
How can I construct a new DFA for the regular language $L1 \cup L2$?


texts: Given An Array of Intervals, Find the Supersets

texts:
Suppose we have the following array of pairs representing start and end indices within an array. Think of them as an interval. I'll be using this term from now on.

$[\left\{1,3\right\},\left\{4,9\right\},\left\{2,11\right\},\left\{8,14\right\},\left\{16,21\right\}]$

I want to yield all intervals which contain no other interval and do not overlap with another interval. As an example, $\left\{2,11\right\}$ contains $\left\{4,9\right\}$ (it is a superset). So we would return $\left\{2,11\right\}$ but not $\left\{4,9\right\}$.
If one or more intervals partially overlap, we yield only one of these intervals. We use the following rules to determine which one:

If one of the intervals (among those overlapping) has the largest length, we return that one.
If they all have the same length, we return the interval with the lowest starting index.

So for this example, we would yield:
$[\left\{2,11\right\},\left\{16,21\right\}]$. Why? $\left\{4,9\right\}$ is a subset of $\left\{2,11\right\}$ so it's eliminated. $\left\{1,3\right\}$, $\left\{2,11\right\}$, and $\left\{8,14\right\}$ contain partial overlaps with one another. But $\left\{2,11\right\}$ has the largest length among those intervals so we yield that one. $\left\{16,21\right\}$ overlaps with no other interval partially or in full so it is yielded as well.

Is there a way to achieve a better than $O(n \log n )$ solution to this problem?


texts: Shortest path that visits maximum number of strongly connected components

texts:
Consider a directed graph. I need to find a path that visits maximum number of strongly connected components in that graph. If there are several such paths the desired path is the path that visits minimum number of nodes (shortest path).

I have created a DAG from the directed graph and performed a topological sort on it. Now I can easily find paths that passes maximum number of components by traversing the DAG, but I have problem finding the shortest one of them. Of course you can brute-force over all of these paths and find the shortest one of them but this is not acceptable because my graph has 1000 nodes.


texts: Randomized quicksort expected running time analysis

texts:
I am following the quicksort analysis in CLRS (pp. 181-184, 3rd edition). Let me summarize the setting of the analysis.

Setting in CLRS

First let $Z = \{z_1, ..., z_n\}$ be the set of elements of the input array $A$ in sorted order. $X$ is defined as the number of comparison we make (i.e., between pivot and an element). Because any two elements of the array $A$ is compared at most once, we have $X = \sum_{i=1}^{n-1} \sum_{j = i+1}^{n} X_{ij}$ where $X_{ij} = 1$ if $z_i$ and $z_j$ are compared. So we just need to calculate the expectation, $\mathbb{E} \left[ X \right] = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \mathbb{P} \left(X_{ij} = 1\right)$.

So we just need to calculate $\mathbb{P} \left(X_{ij} = 1\right)$. According to the book, $\mathbb{P} \left(X_{ij} = 2\right) = \frac{1}{j - i + 1}$ and I don't follow this result.

My analysis

Let $k$ be the index of the randomly selected pivot. Conditioning on the event that $k \in Z_{ij}$ where $Z_{ij} = \{z_i, z_{i+1}, ..., z_j\}$,

\begin{equation}
  \begin{aligned}
    \mathbb{P} \left(X_{ij} = 1\right) &= \mathbb{P} \left( \left.X_{ij} = 1 \right| k \in Z_{ij}\right) \mathbb{P} \left(k \in Z_{ij} \right) + \mathbb{P} \left( \left.X_{ij} = 1 \right| k \not\in Z_{ij}\right) \mathbb{P} \left(k \not\in Z_{ij} \right) \\
    &= \frac{2}{j - i + n} \frac{j - i + 1}{n} + \mathbb{P} \left( \left.X_{ij} = 1 \right| k \not\in Z_{ij}\right) \left(1 - \frac{j - i + 1}{n} \right).
  \end{aligned}
\end{equation}

From this, we can see that if $\mathbb{P} \left( \left.X_{ij} = 1 \right| k \not\in Z_{ij}\right) = \mathbb{P} \left(X_{ij} = 1 \right)$, then indeed $\mathbb{P} \left(X_{ij} = 1 \right) = \frac{2}{j-i+n}$ agreeing the book's result. But I don't think that equality holds.

Suppose we choose pivot $k > j$ which is not in $Z_{ij}$. Then, we reduce the problem size to $\{1, ..., k-1\}$. Because $z_i$ and $z_j$ still belong to the same partition, we are given another chance to pick another pivot such that it is either $i$ or $j$. So I would expect that  $\mathbb{P} \left( \left.X_{ij} = 1 \right| k \not\in Z_{ij}\right) = \mathbb{P} \left(X_{ij} = 1 \right)$ does not hold.

Question

Is my analysis correct, i.e., $\mathbb{P} \left( \left.X_{ij} = 1 \right| k \not\in Z_{ij}\right) \not= \mathbb{P} \left(X_{ij} = 1 \right)$? If not, how to derive $\mathbb{P} \left(X_{ij} = 1 \right)$ considering the fact that if the chose pivot is not in $Z_{ij}$ we are given another chance?

Update

Yuval Filmus' answer is very good and complete in itself. But let me just add a little more step just for completeness. In particular steps leading to $\frac{2}{n} + \frac{2}{n} \cdot \frac{i-1}{j-i+1} + \frac{2}{n} \cdot \frac{n-j}{j-i+1}$ were not trivial to me. So hopefully this may help others.

As Yuval Filmus said we can prove that $p(n,i,j) = 2/(j-i+1)$ using (strong) induction (over $n$). First check the base case which is $n = 2$ because we need at least two elements in order to even think about comparing $z_i$ and $z_j$. With $n = 2$, $j = 2$, $i = 1$ and $p(2,1,2) = \frac{2}{2 - 1 + 1} = 1$. If we have 2 elements, then pivot has to be one of them, and $\mathbb{P} \left(X_{ij} =1; 2\right) = 1$. This proves the base case.

Now consider the inductive step. Assume that $p(m,i,j) = \frac{2}{j-i+1}$ for all $m < n$. In particular, note that all the values of the first argument of $p(\cdot, \cdot, \cdot)$ inside both summations are less than $n$. Hence, we can plug in $p(m,i,j) = \frac{2}{j-i+1}$.

\begin{equation}
  \begin{aligned}
    p(n,i,j)
  &= \frac{2}{j - i + 1} \frac{j - i + 1}{n} + \frac{1}{n} \sum_{k=1}^{i-1} \frac{2}{(j-k)-(i-k)+1} + \frac{1}{n} \sum_{k=j+1}^{n} \frac{2}{j-i+1} \\
  &= \frac{2}{j - i + 1} \frac{j - i + 1}{n} + \frac{2}{n} \frac{i-1}{j-i+1} + \frac{2}{n} \frac{n-j}{j-i+1},
  \end{aligned}
\end{equation}

which is the expression given by Yuval Filmus. The rest of the step is in his answer.


texts: Knapsack problem with specified amount of objects

texts:
Suppose I need exactly $X$ flowerpots.

I have $Y$ flowerpots to choose from, and $Y > X$.

Each of the $Y$ flowerpots has a cost and a capacity. I have a fixed budget to buy flowerpots. The budget, and costs and capacity of each flowerpot are all strictly positive integers. Assume that the total cost of the cheapest $X$ flowerpots do not exceed my budget.

My goal is to maximize total capacity subject to not exceeding my budget (I can spend less, but not more).

If I didn't need exactly $X$ flowerpots, this is the standard 0/1 knapsack problem. However, I need exactly $X$ flowerpots.

What does this problem become, and what algorithm can I use to solve this?


texts: Optimal prefix code: full binary tree existence

texts:
I'm ok following the passages generally used to prove this theorem, like in this question concerning the same subject. Anyway i've the unpleasant feeling that the proof lacks something to be completely understood, perhaps because considered obvious by many people.

We know that a binary tree corresponding to the optimal prefix code is full.
To produce a proof you start considering a binary tree $T$ corresponding to optimal prefix code, and suppose it's not full. If it's not full, then it must contains at least a node $u$ with just one child $v$. If you replace $u$ with $v$ you end up with a new tree $T'$ whose leafs in the subtree rooted in $u$ require less bits to be encoded: so the average bits per letter of the prefix code corresponding to $T'$ is smaller and this contradicts the optimality of $T$.

As far i can see, with this proof, we know that if we had the possibility to erase useless nodes we would obtain trees with best encoding, and therefore they must be full. But how do we prove that these trees actually exist?

I think that you can always replace nodes that aren't leafs, as stated by the proof, because they are just "auxiliary": you don't loose any information replacing them as long as the structure of the new tree you obtain is still valid to produce a prefix code. So, starting from a tree $T$ that is not full, $T'$ always exists.

Is this interpretation correct?


texts:
Consider a uniprocessor system with four processes having the
following arrival and burst times:

(i) Calculate the average waiting time and also the average
turnaround time if shortest (remaining) job first (SJF) scheduling policy is used with pre-emption. Assume that the context
switching time is zero. Note that in SJF, if at any point there
is a tie, then the job that arrived earlier will get priority.

my CALCULATION:-

ready queue:

Am I going correct??
reference :_- JRF-CS-CSB[ISI,2018 question]


texts:
Consider the following problem: let $(U \cup V, E)$ be a bipartite graph. Is it possible to label the vertices of $U$ with either $``+"$ or $``-"$ such that every vertex of $V$ is adjacent to a vertex labeled $+$ and a vertex labeled $-$?

This seems like a pretty natural problem, and I would be surprised if it hasn't been considered before. I'm not asking for someone to come up with an algorithm for this (although that would be great). Does this problem have a name?

Obvious it can be reduced to an integer linear program, which might be efficient in practice.


texts: Why does using unary in subset sum problem result polynomial time complexity?

texts:
From my understanding, the complexity of the algorithm is O(number of inputs * number of bits for input).
The number of bits in binary notation is obviously less than the number of bits in unary notation. Then why is it that for binary, complexity is exponential but for unary, it is polynomial?

EDIT: I think the binary time is still faster. It just appears to be faster in case of unary due to notations.
If x bits are used, then n has to be less than equal to x. So it becomes polynomial.
while in case of binary, it's obviously O(n*2^number of bits).
There might be something wrong in my explanation. Feel free add an answer to correct it.


texts: Proof that the language $ww^R$ is not regular without using the pumping lemma

texts:
I am breaking my head over this. Let the alphabet $A$ be given by
$A = \{a,b,c\}$ and let

$$L = \{ww^R \mid w \in A^* \}.$$

Prove that the language $L$ is not regular without using the pumping lemma, but using:

The fact that $\{a^nb^n \in A^* \mid n \geq 0 \}$ is not regular.
The fact that $\{w \in A^* \mid w \text{ is a palindrome} \}$ is not regular.
Closure properties of the class of regular languages (such as if $L_1$ and $L_2$ are regular, then $L_1 \cup L_2$ is also regular, etc.).


texts: Are there any algorithms to find top N possible knapsacks?

texts:
The classic knapsack problem is maximize $P^T X$ subject to $W^T X\le M$ for $P, W\in \mathbb{R}^d$ and $M\in \mathbb{R}$ and $X\in \{0, 1\}^d$. Is there any research into algorithms that find the top $X_1, X_2, \cdots X_N$ such that $P_T X_1$, $P^T X_2, \cdots, P^T X_N$ are the top $N$ possible knapsack values subject to $W^T X_i\le M$ over all possible $X_i\in \{0, 1\}^d$? $X_1, X_2, \cdots , X_N$ need not necessarily be disjoint.

So when $W\in\mathbb{N}^d$, we have an efficient dynamic programming solution to the classic knapsack problem. Is there a similar dynamic programming solution when trying to determine the top $N$ knapsacks?


texts: Can one reduce a problem of unknown complexity to a hard problem to show hardness?

texts:
In this paper (page 3 Theorem 1) the authors want to prove that their problem is NP-complete. Their method is as follows. Let their problem be known as $P$. They show that their problem can be written as a $0\text{-}1$ integer program. Then they claim that $0\text{-}1$ integer programs are NP-complete and therefore their problem $P$ is NP-complete.

I find this proof hard to believe. For the problem $P$ to be NP-hard I think one has to reduce the $0\text{-}1$ integer program into an instance of problem $P$ and not the other way around.

Please can someone explain if this proof in the paper is acceptable?


texts:
I want to compute the amortize time of a type of dynamic array (inserting such that if i have no place to insert i am multipling the array by (1+a) (a is between 0 to 1).
I need to compute the time with the accounting method.
The answer is that i need for each insertion a 2 + $1/a$ coins.
I can see why the answer is right, problem is that i don't understand how i was supposed to get to the answer myself so what i am asking for is the way to the solution and the way to approach the question.


texts: Modulo hash function and multiples of three

texts:
This is a textbook based question. In The Art of Computer Programming Volume 3, Knuth says that for a hash function $h(k) = k \bmod M$, $M$ should not be a multiple of $3$.

The explanation given is:

  If keys are alphabetic, two keys that differ only by permutation of letters would differ in numeric value by a multiple of 3. This occurs because $2^{2n} \bmod 3 = 1$ and $10^{n} \bmod 3 = 1$)."

I'd be grateful, if someone can clarify why this is so, and how that equation is connected to alphabetical keys and $M$ being a power of $3$.


texts: Travelling Salesman which can repeat cities

texts:
In the TSP problem, we usually assume a complete graph. If we can only visit each city once, we need a complete graph to ensure that there will be a path from every city to every other city. This is easy to accomplish as if there is no straight path between A and B, we can simply assign a new edge whose length is the shortest path between A and B.

However, if we have a sparse graph, maybe we can benefit from not having a complete graph. In this case, we might be forced to repeat vertices. If our graph is only 3 cities, and only two edges, connecting (1, 2) and (2, 3), then the solution must repeat city 2: 1 - 2 - 3 - 2 - 1.

I am struggling to find examples of TSP in the scientific literature which assume a non complete directed graph. Any known references? Any keywords I may be missing? In this case, cycles are allowed.

I am especially interested in how we could separate subtour inequalities when cycles are present.  I am hoping for a solution based on integer linear programming and branch-and-bound, and am wondering how to add subtour elimination inequalities.  Any ideas?


texts: Efficient algorithm to find number of sequences in string

texts:
Suppose I have a string that goes like "abcabcdeaabcdef", where each character is either one more than the previous one or a.

If the character at position i is "c", I know that it is preceded by "ab".

I want to find the number and length of all sequences (substrings that contain sequential characters). For example, the above string would give "abc", "abcde", "a", "abcdef".

Is there a more efficient algorithm to do this than simply doing a O(n) search over the string?


texts:
I'm trying to solve this puzzle but I get stuck. I thought about trying to use the law of total probability to solve intermediate problems with subset of size $k$ but it didn't helped me that much. Is anyone kind enough to give me the right approach to solve this ?

Problem: You are given $N$ boxes indexed from 1 to $N$. The number of boxes with 0, 1, or 2 coins is $n_0$, $n_1$, and $n_2$, respectively. You take a random subset of the boxes where each subset has the same same probability to be selected. The empty set and the set itself are considered a subset.

What is the probability that the total number of coins in a random subset is divisible by 3?


texts:
So in reading I have come across the terms "InLeft" and "InRight" and I am unable to find a concrete definition for it.

I have found it used in the specification for COQ, and in some notes on compilers (there it was refered to as INL and INR).

As far as I am able to ascertain it is to do with making a difference between two options. However the seems like a weird nomenclature for something so simple.


texts: How to check whether a graph is connected in polynomial time?

texts:
I have to solve the following problem:

  Consider the problem Connected:

  Input: An unweighted, undirected graph $G$.

  Output: True if and only if $G$ is connected.

  Show that Connected can be decided in polynomial time.

I have been at this for hours, and I can't seem to find a way to prove this.
Any hints?


texts: Prove that for any finite set $X$, $|P(X)| = 2^{|X|}$. The solution should use induction.


texts: Example of tree with > 6 vertices, tree would have depth = n after splay() deepest vertex

texts:
How to build tree with more than 6 vertices, that after operation splay() would have depth = number of vertices? Is it possible?

UPD:
Example for n = 4:

insert 60
insert 10
insert 20
insert 50
splay(10)

You can use splay tree visualization


texts: If you want to archive (and compress) a number of files into one archive is it more efficient to archive first and then compress?

texts:
When compressing multiple files, is it more efficient to (1) first compress each individual file separately and then concatenate/merge the results, or (2) first concatenate/merge the files into a single archive and then compress that archive?  Which one will be faster, in terms of running time?

From what I understand back in the days (.tar.gz, .tar.Z) when a number of files were archived the files were usually "merged together", and then the resulting file was compressed. But now on newer systems with newer software and algorithms like WinRAR or win ZIP, the files are individually compressed and then the resulting compressed files were merged together to form an archive.  Is one of those approaches faster than the other?

It seems like (2) might be faster. Let's take for example huffman compression. If we compress different files separately than we need to remember a dictionary or some sort of table where we know how many times or with what percentage a certain word appears in the file. This table takes additional space for every file stored. If we compress a huge file than we store less tables.  Is this right?


texts:
Can someone explain the working of the GHS algorithm using the graph given below. GHS is a distributed algorithm for finding the Minimum Spanning tree of a graph. The description of which can be found here https://en.wikipedia.org/wiki/Distributed_minimum_spanning_tree

What I think is that the fragments(the nodes in a fragment are shown within curly braces) will be formed as follows:

Step 1: {1, 2}
        {5, 6} {3}  {4}

Step 2: {1, 2, 3, 4}
        {5, 6}

Step 3: {1, 2, 3, 4, 5, 6} //as 1 and 5 get connected.

But what my professor said is that 4 will become a part of the MST at the end. These are the steps that he told us.

Step 1: {1, 2}
{5,6}// this step is the same
{3}{4}

Step 2: {1, 2, 3}{5,6}{4}

Step 3: {1, 2, 3, 5, 6}{4}

Step 4: {1, 2, 3, 4, 5, 6}

Can you please tell me which version is correct?
The graph ->


texts: Grammar types constraint after adding a couple of types (and a statement involving them) to a "typeless" language

texts:
Foreword : by "typeless programming language", I naively mean "language in which you don't write statements like type x (=) ... to declare(define) x". Maybe there is an internal typing deduced from what is in ... but I suppose that this is not the case, as it is not the case in the example interesting me. (If "typeless programming language" already means something, forbid me, but this is not the point.)

Consider the grammar of a "typeless" programming language, python (3.6.3) for instance :

https://docs.python.org/3/reference/grammar.html

I rather used its description here :

https://github.com/erezsh/plyplus/blob/master/plyplus/grammars/python.g

Then I lightened the grammar a lot and modified the resulting subgrammar by adding new features, but for the sake of simplicity, one can assume that I add features to the complete python grammar, not to a subgrammar of it.

Here are my modifications :

1) I added a date "type" (I put type in "" because there's no type in python)

date: US_DATE;

where :

US_DATE: '!(?:(?:(?:(?:(?:[13579][26]|[2468][048])00)|(?:[0-9]{2}(?:(?:[13579][26])|(?:[2468][048]|0[48]))))(?:(?:(?:09|04|06|11)(?:0[1-9]|1[0-9]|2[0-9]|30))|(?:(?:01|03|05|07|08|10|12)(?:0[1-9]|1[0-9]|2[0-9]|3[01]))|(?:02(?:0[1-9]|1[0-9]|2[0-9]))))|(?:[0-9]{4}(?:(?:(?:09|04|06|11)(?:0[1-9]|1[0-9]|2[0-9]|30))|(?:(?:01|03|05|07|08|10|12)(?:0[1-9]|1[0-9]|2[0-9]|3[01]))|(?:02(?:[01][0-9]|2[0-8])))))';

(thx to https://stackoverflow.com/a/16088645/1581875)

and I propagated date to atom.

Then d = !20171116 produce the following syntax tree :

2) I also added what I call an underlying, and this time it's a real type. Namely, I added a

UNDERLYING: 'underlying';

in the %unless part of NAME definition, and I introduced an underlying statement :

underlying_stmt : UNDERLYING name (COMMA name)*;

that I of course propagated to small_stmt.

Now one can write :

underlying z

which produces the following syntax tree :

3) Here comes the tricky (at least for me) part : after what preceeds, I introduced a new use of the @ symbol, namely a "stamp statement", stamp_stmt, as follows :

stamp_stmt: name AT (name | date);

(that I propagated of course to small_stmt)

Namely, I can write

z @ d #or
z @ !20171116

and this will produce the following syntax tree :

In fact, as I defined the stamp_stmt, I can write name @ date for any name (and date).

I cannot write 2 @ !20171116 for instance : this is already a constraint. I would like to be able, within the grammar, to also add the following constraint : name @ date could be written only for a name of an underlying.

How could I achieve this ? I mean, I could still introduce a kind of light "typing" in name by refining it by saying that date (resp. underlying) has datename (resp. underlyingname) and try to use it to achieve the wanted constraint, but I could also say that d = !20170823 is not an assignement statement (assign_stmt) and introduce a "date assignement statement", same for underlying.

Is it anyway a good idea to want to put such a type constraint already in the grammar or not ? (I am really not an expert in languages designing etc ... I am doing all of this because I need a small programming language with the aforementionned features and because around me, no one can help.)

Remark : I am doing all of this under windows with plyplus in python and producing syntax trees figures using graphwiz.


texts: Find small superset of at least k of n given sets

texts:
Say we're given $n$ sets and the size of their union is $m$. We would like to construct a small set which contains at least $k$ of the $n$ given sets.

Lets assume that $m$ is less than some polynomial in $n$, i.e.: $m < P(n)$. In this case is there an efficient (polynomial) algorithm for the optimization problem:

Find the smallest set which contains at least $k$ of the $n$ given sets.


texts: What is the class of automata with stack and unlimited amount of memory, addressable only by immediates?

texts:
Let's assume we've got an automata with infinite stack ($s_n \epsilon \mathbb{Z}$) and infinite amount of "registers", but no arbitrary memory access whatsoever and it's data is separated from code.

I'm sure that this is at least pushdown automata, but I'm not entirely sure can we pull this machine up to the linear bounded automation in the current state of art. The upper bound is obviously the Turing machine (because pushdown automata with one additional stack has the same capabilities as the Turing machine).

The only way to store data using this automata would be either pushing it onto the stack (push #3 - push contents of register 3 to the stack, or push 3 - push 3 to the stack), or using mov instruction with at least one register specification (mov #1, 1 register 1 = 1, mov #2, #1, register 2 = register 1). We can also assume that loop operations are there, along with addition or subtraction.

Let's assume only allowed operations are while-like loops, addition and subtraction.

The question(s) are:

What is the class of this automata?
If this automata isn't a linear bounded automation or a Turing machine, what needs to be done for it to become one except the following:

Adding another stack(s)
Allowing arbitrary memory access

Edit: Let's define register (in this context) as memory cell, $r_n$ where $n \epsilon \mathbb{N} \wedge r_n \epsilon \mathbb{Z}$, that is addressable only using constant stated explicitly, eg. $r_7$ (invalid: $r_{r_3 + 2}$).


texts: What are disadvantages of a Operating System that recognise file extensions ?

texts:
When Operating system recognise the file types It has several advantages like
1. avoid mistakes like trying to print a object file that produce garbage output

but I can't think about disadvantages of an OS that recognise file systems
Anybody has an idea ?


texts: Context formal language recognizing even number of 0's and odd number of 1's

texts:
I have an assignment, it's asked to write a context free grammar recognising the language $L=\{ w \mid w\text{ has an even number of }0\text{s and an odd number of }1\text{s}\}$, over the alphabet $\{0,1\}$.

My first guess was:

$$
\begin{align}
S &\rightarrow A1A\\
A &\rightarrow A0A0A \mid A1A1A \mid \varepsilon
\end{align}
$$

But I realized it's wrong, since, for example, it doesn't accept the string $01011$ (I think my CFG forces pairs of $0$s).

Any suggestion?


texts: Find pair of complex numbers with maximal sum

texts: Given two lists of complex numbers, is there an efficient algorithm to choose one element from each list such that the magnitude of their sum is maximal?


texts: Why are hash map look-ups assumed to be $O(1)$ on average

texts:
To look up a key in a hash map you have to

calculate its hash
find the entry in the resulting hash bucket

Hash calculation takes at least $O(l)$ operations when the hashes are $l$-bit-numbers.

When using an index (like a binary tree) for each bucket, finding an entry within a bucket that contains $k$ entries can be done in $O(\log k)$. With $n$ being the total number of entries in the hash map and $m$ being the number of buckets, $k$ averages to $n/m$. Due to $m=2^l$ we thus get
$O(\log k) = O(\log n/m) = O(\log n - \log m) = O(\log n - l)$.

Combining these two runtimes one gets a total look-up time of $O(l + \log n - l) = O(\log n)$, which conforms to the intuition that a lookup in a collection with $n$ entries is not possible below $O(\log n)$ operations.

In short, it is generally assumed that $l$ and $k$ are both constant with regard to $n$. But if you fix $l$ then $k$ grows with $n$.

Am I missing something here?


texts: State of the art time complexity for getting (tree) descendants by type/attribute

texts:
Let's say I have a tree comprised of nodes where each node is of some type (T), where there is a known/fixed number of types (i.e. similar to attributes in an xml document), and where a node can only have one type. Let's also assume that our tree is somewhat balanced, and that there are far more nodes in the tree than there are unique types. Assuming I have already created some sort of index on the tree, I need to know the state of the art time complexity for the following types of queries (using whatever type of index / data structure you like):

Where A is some arbitrary node in the tree and T is some arbitrary type:

find all descendants of node A that are of type T
find the number of descendants of node A that are of type T

If the tree is static and no updates to the index are required, I have a data structure that will do 1 and 2 in $O(1)$. If the tree can have nodes added/removed, I also have a data structure that will do 1 and 2 in $O(\log m)$ where m is the total number of nodes of type T in the tree ($m << n$), and that can update the index when changes are made to the tree in $O(k\log m)$ where k is the number of nodes affected.

Are my data structures state of the art for these types of queries, or on par with state of the art? What existing work is out there that can match or beat this performance, if any?

(assume that any indexing structure we use must take less than $O(n^2)$ time and memory to construct)

(assume that any indexing structure we use for the case where the tree/index can be modified, that modifications can be handled in better than $O(n)$)

My understanding is that XML indexing generally has the state-of-the-art indexing schemes for dealing with trees where there are typed nodes, so I assume something with XML indexing will crop up here. I've tried looking through a number of papers myself but it's very difficult to get actual time complexities out of people in that field for some reason.


texts: Strassen's matrix multiplication algorithm when $n$ is not a power of 2

texts:
The above image, describing Strassen's matrix multiplication algorithm, is from the book Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein.
The algorithm multiplies two square matrices of order $n$, where $n$ is a power of $2$, i.e., $n=2,4,8,16,32,\dots$ and so on.

  Can this algorithm be modified so that we can multiply two square matrices of order $n$, for all $n$?


texts: Asymptotic analysis of $T(n) = T(n/5) + T(4n/5) + \Theta(n)$

texts:
If I have a recurrence relationship like this:
$$T(n) = T(n/5) + T(4n/5) + \Theta(n),$$
how would I analyze its rate of growth?
I believe I can't use the master theorem. I tried to draw a tree but some of the branches terminate earlier. There's a way to calculate the big-O notation by assuming $T(n) \le 2 T(4n/5)$, but does this result in a tight estimate?


texts: Trying to verify the solution to a lambda calculus equation

texts:
I am going through the following introduction to lambda calculus :

http://www.cse.chalmers.se/research/group/logic/TypesSS05/Extra/geuvers.pdf

At page 12 , the following has been asked to prove

$ \exists $ $ G $ $ \forall X $ such that

$GX$ = $GG$

This means to find a function which takes a function as an argument and returns the same expression irrespective of the function .

The book posits the solution to be $ G $ = $Y$ $(  \lambda gx. gg) $

On trying to verify this I first evaluated the L.H.S to be

$ GX $ = $ Y ( \lambda gx.gg ) $ $X$.

Now $X$ being the argument will be picked up by the first bound variable  so .

$L.H.S $ = $ Y ( \lambda x . XX) $ =  $( \lambda x . XX)$  $ Y ( \lambda x . XX)
$ = $ Y ( \lambda x .$ $ Y ( \lambda x . XX)$ $ Y ( \lambda x . XX)$)

Here  due to the presence of the form $ YF $ , I can carry on the reduction continuously  by replacinf $YF$ with $FYF$

$R.H.S$ =  $Y$ $(  \lambda gx. gg) $ $Y$ $(  \lambda gx. gg) $
           = $Y$$ \lambda  x.$ $( Y(  \lambda gx. gg) $ $Y(  \lambda gx. gg)) $

Now similarly  the reduction can be carried on further by again consuming the first $g$ that comes in the expression with  $Y(  \lambda gx. gg)) $ and this can on perpetually and it will look like   $ Y ( \lambda x .$ $ Y ( \lambda x . XX)$ $ Y ( \lambda x . XX)$).....
So I couldn't completely ascertain that they ( L.H.S and R.H.S) will turn out to be equal but I can  see that L.H.S and R.H.S are going to be infinitely long  and will resemble each other more and more as the number of reductions go on since  the $ g$ 's in the R.H.S will continually get replaced .

Is this logic correct ? If not , where did I err ?

P.S. : On a general and on a lighter note , how are this lambda calculus equations solved ? (They look analogous to differential equations ).


texts: What exactly is the semantic difference between category and set?

texts:
In this question, I asked what the difference is between set and type. These answers have been really clarifying (e.g. @AndrejBauer), so in my thirst for knowledge, I submit to the temptation of asking the same about categories:

Every time I read about category theory (which admittedly is rather informal), I can't really understand how it differs from set theory, concretely.

So in the most concrete way possible, what exactly does it imply about $x$ to say that it is in the category $C$, compared to saying that $x\in S$? (e.g. what is the difference between saying $x$ is a group, versus saying that $x$ is in the Category $\mathrm {Grp} $?).

(You may pick any category and set that makes the comparison most clarifying).