texts: A physical algorithm that finds all integer partitions of a number

texts:
If this is not the right forum for this question let me know.

I am looking for a physical algorithm that can be easily followed by anyone not knowing much mathematics to get integer partitions of a number.

I have come up with the following way - but there is an issue (described later).

Suppose I want to divide number 11 into all its integer partitions (order is not important).

For finding partitions of size 2 we do following.

Take 11 coins of identical widths. Take a paper. Write 1 and 2 on it

1    2

Below the first number, keep all 11 coins one upon another to make a tower of height 11. This is represented as -

1      2

11c   0c

Now, shift 1 coin from first column to second column.

1      2

10c   1c

Here, height of tower 1 = 10, height of tower2 = 1

Keep on doing this, only if Height of tower 1 >= Height of tower2

On each step of the algorithm, we get new integer partition.

This "physical algorithm" is easy to understand by anyone knowing
basic mathematics.
Preferrably, each step in the physical algorithm must show a new
partitioning way.
There should be an end condition to the algorithm.
When the algorithm reaches end condition, all possible partitioning
ways must have been shown.

If we now want to find all partitions of size 3, the problem gets a bit tricky.

We have 3 towers, with following restrictions
Height of tower 1 >= Height of tower2 >= Height of tower3

But thing is, there are certain positions, from which we cannot go to next stage without destroying earlier stage - what do I mean by this? See below

Step1

1      2     3

9c    1c     1c

Step2

1      2     3

8c    2c     1c

Step3

1      2     3

7c    3c     1c

Alternative Step3

1      2     3

7c    2c     2c

At step 3 the algorithm creates two branches - people could either put new coin in tower2 or tower1. How should the algorithm statements be written so that by the time the algorithm is finished, all partitions of size 3 are known?

If you could come up with a new algorithm, that's welcome too!


texts: Factorial algorithm more efficient than naive multiplication

texts:
I know how to code for factorials using both iterative and recursive (e.g. n * factorial(n-1) for e.g.). I read in a textbook (without been given any further explanations) that there is an even more efficient way of coding for factorials by dividing them in half recursively.

I understand why that may be the case. However I wanted to try coding it on my own, and I don't think I know where to start though. A friend suggested I write base cases first. and I was thinking of using arrays so that I can keep track of the numbers... but I really can't see any way out to designing such a code.

What kind of techniques should I be researching?


texts: Time complexity of dequeue function (queues)

texts:
Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter.

MultiDequeue(Q){
     m = k
     while ((Q is not empty) and (m > 0))
     { Dequeue(Q)
       m = m – 1
      }
}

What is the worst case time complexity of a sequence of n queue operations on an initially full
queue having n elements.?

(A) $\Theta(n) $

(B) $\Theta(n+k)$

(C) $\Theta(nk)$

(D) $\Theta(n^2)$

Here suppose we do one dequeue operation, then the loop will run for min(n,k) times. Now remaining 1 operation can be 1 enqueue operation which will take O(1) time so total complexity in this case will be O(min(n,k)).

Suppose we have k=1 and do (n-1) dequeue operations then it will take k*(n-1) time for multideqeue function and remaining one enqueue operation will take O(1) time . So in total we are getting O(kn) time in this case.

I am confused on how to handle 'k' parameter when we are calculating complexity.

NOTE :- n queue operations can be any combination of enqueue/dequeue/multi-dequeue(as defined) operation.

Any help would be appreciated.


texts: Existence of non-context free but decidable languages

texts:
I've been reading the decidablity and undecidability chapters in Sipser's "Intro to Theory of Computation" however I could not find an explanation on the existence of a language that is both non-context free and decidable.

The only reference to this was a simple language hierarchy diagram showing where the decidable/recognisable bounds were in relation to language types.

I'm unsure as to how I should approach this but I've thought about proving this by diagonlisation:

Let $M$ be the set of all decideable Turing Machines, and $L$ the set
of all languages that are context-free. (Assume finite alphabet)
By drawing up and filling the table where each language corresponds
to a Turing Machine, I was hoping that I could find a contradiction
in some $m \in M$ where there is no corresponding language $l \in L$.

I know that this will not work as both $M$ and $L$ are countable.

Any ideas on how I should approach this?


texts: LInear time algorithm to find the diameter of a tree

texts:
This is NOT HW, this is from Skienas book, and I just couldn't solve it at all.

Please give me a hand here, in understanding and solving it, thanks.

Let G = (V, E) be a binary tree. The distance between two vertices in G is the length of the path connecting these two vertices, and the diameter of G is the maximal distance over all pairs of vertices. Give a linear-time algorithm to find the diameter of a given tree. (*)

I figured I'd do a DFS, and increment on each node in terms of the depth of the tree


texts: Prove that any tree contains a matching of size |InternalNodes|/2

texts:
How can i prove that any tree contains a matching of size |InternalNodes|/2?
Thanks in advance


texts: How to explain a language with modulo conditions is regular?

texts:
I don't want to create a duplicate question of How to prove a language is regular?, I only want to know what is a good and simple way to explain why a language like

$\qquad \displaystyle L = \{w \in \{a,b,c\}^* \mid w = ua \text{ and } |u| \equiv 2 \pmod 3  \}$.

is regular.


texts: Efficient algorithm to replace list of integers with nearest bigger element

texts:
The original question was in the context of an array, but I just used a list without changing the length for easier debugging purposes of toString().

  Given an unsorted list of integers, design a O(n) algorithm to transform the list such that the integers are replaced by the next bigger integer on their right. If there is no bigger integer on its right, the integer remains the same.

  For example [2,1,4,5,3,6,7,9,4,8] becomes [4,4,5,6,6,7,9,9,8,8].

I have come out with an algorithm after a long time, but a recent test case reveals that my algorithm doesn't cover all cases. Here is my attempt written in Java. Can anyone suggest the algorithm for this problem?


texts: How is it that programs can be identified with partial functions for programming language semantics?

texts:
I was reading about denotational semantics

  Broadly speaking, denotational semantics is concerned with finding mathematical objects called domains that represent what programs do. For example, programs (or program phrases) might be represented by partial functions.

I was wondering, how does one map programs to partial functions? What is the mapping? What is the intuition and conceptual idea? I don't understand what the relationship (formally or conceptually) is between partial functions and program (or Turing Machines).


texts: Convergence of Simulated Annealing Based Algorithms

texts: I designed a simulated annealing-based optimization algorithm. My simulation shows that it converge fast. I am looking for some sort of proof to show that simulation annealing-based algorithm converge fast (based on satisfying some properties) to global/local optimal point and doesn't oscillate in the optimal points (or any related fast about its stability). Are there any useful literature about it?


texts: Quadratic programming problem involving permutation matrices

texts:
Does anyone know a good algorithm for quickly finding an approximate solution to the following problem?

Given two square matrices $A$ and $B$, minimize $\| P A P^\top - B \|$ over all permutation matrices $P$.

I have heard that there are several types of algorithms for these kinds of problems, like iterative improvement, simulated annealing, tabu search, genetic algorithms, evolution strategies, ant algorithms, and scatter search. I am looking for existing software.


texts: What is the time complexity of this "reverse words" algorithm?

texts:
I had to write an algorithm that, given the input ['h', 'a', 'r', 'd', ' ', 'i', 's', ' ', 'c', 's'] would return ['c', 's', ' ', 'i', 's', ' ', 'h', 'a', 'r', 'd']. I found an algorithm that I think I am happy with, but unfortunately, I do not know how to compute its running-time.

The algorithm essentially has two stages. First, I reverse the entire string. Then, I scan that string to find words, and when I find a word, I reverse only that word. In terms of message, the first time we reverse we will do (n/2) steps. Then, for each word we find, we'll do (m / 2) steps, where m is the length of the word (m is not constant). How do I express the Big O notation for this?

function reverseWords(message) {
  // reverse entire string
  reverseStrArr(message, 0, message.length - 1);

  let wordStart = 0;
  let wordEnd = null;

  for (let i = 0; i < message.length; i++) {
    const char = message[i];

    if (char === " ") {
      wordEnd = i - 1;

      reverseStrArr(message, wordStart, wordEnd);

      // reset
      wordStart = wordEnd + 2;
      wordEnd = null;
    }

    if (i === message.length - 1) {
      reverseStrArr(message, wordStart, i);
    }
  }
}

function reverseStrArr(stArr, minIdx, maxIdx) {
  const midIdx = Math.floor((minIdx + maxIdx) / 2);

  for (let i = minIdx; i <= midIdx; i++) {
    const tailIdx = maxIdx - (i - minIdx);

    const temp = stArr[tailIdx];
    stArr[tailIdx] = stArr[i];
    stArr[i] = temp;
  }
}
```


texts: Minimizing the distance from a set of nodes in a tree

texts:
We have a binary tree with n nodes and a number k which signifies the number of nodes that we put on a set. What is the optimal algorithm to select a set consisting of k nodes, that minimizes the maximum distance of a node (of our tree) from an ancestor of his that belongs in the set we have chosen. By distance we mean the steps we have to take to get to the ancestor, if every edge has a cost of 1. For this problem we always have to take the root of the binary tree to belong in the subtree.

I have figured out, that I have to use Dynamic Programming to solve this problem, but I can't find the recursive function. I also think, to optimize the complexity, the recursive function should start from the bottom of the tree, to work its way on the top.

Edit: The nodes that belong on the set, are not necessarily connected with eachother


texts: Difference between heuristic and approximation algorithm?

texts:
i have a problem regarding the following situation.

I have two arrays of numbers like this:

index/pos     0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
Array 1(i):   1   2   3   4   7   5   4   3   7   6   5   1   2   3   4   2
Array 2(j):   4   4   8  10  10   7   7  10  10  11   7   4   7   7   4

now suppose the second array is very hard to compute but I have noticed that if I add

A[i] + A[i+1]

in the array 1 I get the number very close to the number A[j] in the array 2.

Is my solution a heuristic or approximation?
If I had a reason to believe that I will never overshoot the value of A[j] by +-x with this algorithm and can prove it, would then  my solution be a heuristic or approximation?

Is there any literature that deals with heuristic vs. approximation questions for P class problems where the solution can be achieved in polynomial time but the input is just too big for a poly time algorithm to be practical.

thank you


texts: Tightest upper bound on length of distinguishing string in Hopcroft's algorithm

texts:
Hopcroft's algorithm is an algorithm for DFA minimization that produces a table identifying which pairs of states are distinguishable.

What is the tightest possible upper bound (with proof) on the minimum length of a string that distinguishes two distinguishable states?

This question is taken directly from Hopcroft, Mowtani, & Ullman, Exercise 4.4.3.  I believe that the tightest upper bound is $\frac{(n-1)(n-2)}{2}-1$, but other sources I have found indicate that the tightest bound is $n-2$.


texts: Can we use reductions to design approximation algorithms for NP-hard problems?

texts:
Let us say that I have a problem $P(n)$ that I need to solve (where $n$ is the size of the input of problem $P$). I used a polynomial-time reduction from a known NP-hard problem $Q(m)$ (where $m$ is the size of the input of problem $Q$) to $P(n)$ and showed that $P(n)$ is NP-hard. The time complexity of the reduction is $O(n^k)$ for some fixed $k$.

Can I use a known approximation algorithm for problem $Q(m)$ that is $O(f(m))$-approximation for problem $Q(m)$ to design an approximation algorithm for problem $P(n)$ that is $O(g(n))$-approximation for problem $P(n)$?


texts:
I've been playing around with converting regular languages to regular expressions and was wondering if my thinking is correct for this one.

Question:

The set of all strings that begin or end with a doubled digit, either 11 or 00.  (In all cases assume the alphabet is {0,1}).

So far, I have: $((11+00) + (1 + 0)^*) + ((1+0)^*(11 + 00))$.

My thinking is that we want to take the union of:  the set of strings that start with 11 or 00 followed by any sequence of 1's and 0's AND the set of strings that end with 11 or 00 preceded by any sequence of 1's and 0's.

Sorry for the somewhat clunky writing.....still trying to get the hang of styling my questions.


texts: Optimally sized bloom filter for two different sets

texts:
Given a set with n inserted elements and a desired false positive probability p, we can find the minimum number of bits in the bloom filter m by computing -n*ln(p)/(ln2)2

Suppose we have two sets of different sizes and we want to compute their intersection using the bitwise-AND operator on their bloom filters - this means that we have to construct a bloom filter for each set that is of equal size. What is the smallest such bloom filter we could construct (we can assume that both bloom filters need to have a false positive rate below some threshold)?


texts: Find longest subsequence in array with given condition

texts:
I am given an array $A$ having $n$ elements and an integer $k$.

I need to find the longest subsequence which always includes the first element and the subsequence follows the given condition:

for all $i < j$: $|A[i] - A[j]| \leq k$.

Example: $n= 4$, $k = 5$, $A = [1, 2, 50, 6]$

Answer: the longest valid subsequence, $[1, 2, 6]$, has length $3$.
Note that the first element is always to be included in the sequence.

I think this can be solved with Dynamic Programming. But I can't form a recursive equation for Dynamic Programming.


texts: Communication between hardware components

texts: We know that each component has different frequencies, but what happens when a fast component directly comunicates with a slow one?


texts: It seems pretty obvious that $PSPACE$ is not equal to $DSPACE(2^n) $. Can this be shown using the space hierarchy theorem? Is that the most simple and straight-forward way?


texts: How can I use the NP complexity Venn diagram to quickly see which class of NP problem can be poly reducible to another class?

texts:
I'm so bad at solving the problem of the type:

  "If $A$ is an NP-complete problem, $B$ is reducible to $A$, then $B$ is..."

That I have to come here and ask these silly questions each and every time I encounter them.

Is there a good way of using the Venn Diagram shown below to tackle these kind of problem?

For example, how can I prove that If $A$ is an NP-complete problem, $B$ is reducible to $A$, then $B$ can be NP-hard using the above diagram?

If not possible, what would be another way to drill this into my head?


texts: Why is it that Btrees most of the times have a degree that is odd? What happens if they are even?

texts: I was watching a lecture video and the Professor states that it would be very rare to see the order of a Btree to be even. I was hoping for an explanation but he cut it off there and moved on with the lecture.


texts: Proving that $ L = \{ 0^{{2n}\choose{n}} : n\in\mathbb{N} \}$ is not regular

texts:
I was asked to prove that $ L = \{ 0^{{2n}\choose{n}} : n\in\mathbb{N} \}$ is not regular. I can't solve this, could anyone help me?
This was an exam question from previous year. I looked your answers, but I can't really understand Yuval's solution and Matt's solution would be too long for an exam question.
From lecture we were given 3 methods to prove non-regularity. I thought that 3 methods are all classical methods to prove non-regularity, but it seems like the third one isn't so 'classical'.
The third one is as follows:

Let $\ L \subseteq (\Sigma_{bool})^* $ be a regular language.
Let $\ L_x=\{ y \in (\Sigma_{bool})^* | xy\in L \} $ for every$\ x \in (\Sigma_{bool})^*$. Then there exists a constant $\ c$, such that for all $\ x,y \in (\Sigma_{bool})^* $
$\ K(y) \leq \lceil log_2(n+1)\rceil+c $
if $\ y $ is the n-th word in the language $\ L_x $.

I'd like to show my proof using this method.

Suppose that $ L = \{ 0^{{2n}\choose{n}} : n\in\mathbb{N} \}$ is regular.
We have ${2(n+1)}\choose{n+1}$ = ${2n \choose n+1}{2 \choose {0}} $ + ${2n \choose n}{2 \choose {1}}$ + ${2n \choose n-1}{2 \choose {2}}$.
i.e. ${2(n+1)}\choose{n+1}$ = $2*{2n \choose n}$ + ${2n \choose n+1}$ + ${2n \choose n-1}$  .        $(\ast)$
Then we define $\ L_n = L_{0^{{{2n}\choose{n}}+{{2n}\choose{n+1}}}}:=\{ y \in (\Sigma_{bool})^* | 0^{{{2n}\choose{n}}+{{2n}\choose{n+1}}}y\in L \} $ for every $n\in \mathbb{N} $.
Let $y_1$ be the first word in $L_n$. Obviously $y_1= $  $0^{{{2n}\choose{n}}+{{2n}\choose{n-1}}} $ by $(\ast)$. By the theorem,  there exists a constant $c$ ,such that for any $n \in \mathbb {N}$,
$\ K(y_1) \leq \lceil log_2(1+1)\rceil+c $.
Thus we can bound the Kolmogorov complexity of all elements in $S=\left\{0^{{{2n}\choose{n}}+{{2n}\choose{n-1}}} | n\in \mathbb {N}\right\}$ by constant $c$. However, this is an infinite set , we have only limited number of programs of length $\le c$. So we can't bound the Kolmogorov complexity of the elements in $S$, this means $L$ can't be regular.

If you don't know this theorem, you can find it here Proof of non-regularity, based on the Kolmogorov complexity. I don't know if my solution is right or not, if you find any problems please let me know.


texts: Finding an interval in a binary search tree that contains a point

texts:
I have a binary search tree where nodes are non-overlapping intervals. I'm given a point, and I need to determine which interval the point belongs to (if any). This is easy to do because I can compare against the low and high of each interval and descend either left, right, or exit.

Is it possible to only compare against the low, or the high, or some kind of median to reduce the number of comparisons in the average case? I know the optimal lower bound would be O(lg n) but in many cases the max of a predecessor is very close to the min of a node, which seems redundant.

I'm wondering if there is a way to branch more aggressively at first and make small adjustments along the way. Potentially determining the next step based on which direction we branched previously.

I could not find any literature on this. Interval trees don't quite match this setup and almost all other resources relate to overlapping intervals.

What would be an optimal algorithm to find an interval?


texts: Minimal Separator / Vertex disjoint Paths

texts:
I'm in need of implementing the algorithm to actually locate the minimal vertex separators set of the whole graph (not just s-t).

It is my understanding that this can be done by doing the s-t procedure for all possible vertex pairs and then looking at the minimal sets of vertex independent paths that arise from that.

Now, I get that all possible paths can be found easily by solving "max flow" s-t, and I do it with matlab, but I'm curious about getting the maximally vertex independent sets of paths.

I understand, from this that this can be acheived by doubling the vertices in some way, but I'm not able to figure it out on my own.

Question covering a similar issue: I'm specifically interested in case (a) that the first comment termed "network flow". Practical algorithms for the disjoint paths problem

Any advice ?

PS: this is not homework. I'm actually trying to solve this problem on my data and I'm not a computer science expert.


texts: Soft binary ECC? How to maximize the minimum distance over a channel?

texts:
Given that

The channel is tiny, it has message size of 72 bits
Each bit is probabilistic, meaning that I have a value between 0 and 100 of how likely that bit is on/off1
Only 24 bits of acutal data are needed

Currently, BCH[63,24,7] is the closest thing I've found, but it doesn't capitalize on all aspects of the channel.  It isn't probabilistic and 9 of the 72 bits are unused.

Can anyone suggest an algorithm that can perform better on this type of channel?

1 The bits are derived from pixels on a greyscale image (values 0 to 255) read from a camera by the recipient of the code. Any pixel P ≤ 128 translates to 0, otherwise 1.  Due to the lighting conditions when the image is taken, some bits are more likely to be erroneous. For example, half of the image is in a shadow, white pixels begin to look more grey, so instead of reading 255 (full white) they read 110 (which is ≤ 128, therefore the bit is 0).  So, pixels that are far away from 0 and 255 are more likely to be erroneous, so to speak. The value of each bit is independent. In the end, the algorithm should be able to verify that the bits converted from pixels match a valid codeword and correct them otherwise.


texts:
As I understand it encrypted emails have a high profile (detectable through pgp header / attachment).

Would it be possible to match the encrypted data with a wordlist to hide the fact that the email contains a encrypted message?

I know that the other person would need the same list of words for decrypting and the message would be only a bunch of random words, but the fact that its encrypted world be not as obvious for automated scanning.

EDIT: As pointed out I am referring to steganography to hide from traffic analysis.


texts: OS: Why is it necessary to have hardware support for implementing Preemptive Scheduling Strategies?

texts:
I think, Preemption can easily be done in kernel mode, where it just have to call the Context-Switch procedure. Also, based on algorithm we can select the new process from the ready queue as well...
I'm unable to think and find Why and where the role of timers come and what exactly are significance of Hardware in preemptive scheduling.
Can we not do preemptive scheduling without hardware support?
Why I didn't ask on Stack-overflow?
=> I need the theoretical point, although I'll appreciate if someone mentions the actual implementations of Unix.


texts:
I was recently faced with a hackerrank interview test where I couldn't solve the following problem correctly. I would not want to name the exact problem for privacy purposes, but I can tell that it was nowhere in Google with this name.

Problem

We want to organize an event with as much performers as possible. We are given a list of possible performer arrival times and performance durations. Our function should return the maximum number of performers that can be selected without conflicts.

Example

N = 5
arrivals = [1, 3, 3, 5, 7] (performers arrive in these times)
durations = [2, 2, 1, 2, 1] (the time needed to finish their performances)
solution = 4

So at time 1 we can accept the performer and will finish at time 3. At time 3 we have two conflicting choices, and doesn't matter which we chose. Time 5 and 7 are not conflicted either.

My solution

Made tuples of the arrivals and durations by zipping. Sorted the tuples first on arrival, then on duration.
Outer for cycle for i from start to finish. Initialize new set in each iter.
Inner for cycle for j from i to finish. Check if j can be added to the set without conflict. If set is longer than max I save.

Python source

Questions

Are there better ways, standard algorithms to solve this problem?
I know that there are some edge cases, for which my algorithm doesn't work. Hackerrank evaluated my algo, and it only passed 7/13 test cases. What could be some edge cases I am missing?
Is this a search problem or an optimization problem?


texts: Why ASCII letter A has a Hamming Distance of 3?

texts:
My question is what does [this construction gives a Hamming Distance a distance of 3] means? Why the Hamming Distance of ASCII letter A is 3? How do you determine the Hamming Distance is 3?

This is an excerpt from Computer Network by Andrew S. Tanenbaum page 206.


texts: Why is removing the second largest element from a max-heap not in O(log n)?

texts:
I have a max PriorityQueue designed using a heap.
A function removemax() that removes and returns the element with the largest priority in $\Theta(\log n)$ and a function insert in $\Theta(\log n)$ for the worst cases (both of them work with the heap by reorganizing it whenever necessary in order to retain the heap properties).

I am designing a function to remove the second largest element in the queue.

This is my algorithm assuing queue is a priority queue with the functions insert and removemax:

removesecondlargest(queue)
    largest = queue.removemax()
    secondlargest = queue.removemax()
    queue.insert(largest)
    return secondlargest

However, I am not sure why this approach isn't in $O(\log n)$ for the worst case?

Can someone explain me why?


texts: Qualification or Disqualification of Machine Intelligence test as "Turing test"?

texts:
Let's us the following definition:

Tu·ring test noun

  A test for intelligence in a computer, requiring that a human being should be unable to distinguish the machine from another human being by using the replies to questions put to both.

Also observe from Wikipedia:

  The Turing test is a test, developed by Alan Turing in 1950, of a machine's ability to exhibit intelligent behaviour equivalent to, or indistinguishable from, that of a human.

Notice in each case a human (singular) is pitted against the demonstrated intelligence of another human (singular);  WHETHER against an actual human or a machine exhibiting behaviour equivalent to or indistinguishable from the intellect of a human's int (again, singular).

In this article the question was asked whether IBM's Watson pass the Turing test. Yet Watson did not demonstrate intelligence of a single human but that of an entire team of programmers and the community of chess expertise they relied upon.

By definition Turing did not propose a test of a human against a community of humans (plural) OR against a machine exhibiting intelligent behaviour equivalent to or indistinguishable from a community of humans (plural) since whether a machine is artificially intelligent or not, a single human can nearly always be flummoxed by a community of humans given a sufficiently large community (one or more intellects).  Definitions in Science are precise.

Turing's test contained the self-ordained constraint that apparent 'machine intelligence' approximated by the Turing test exhibit the approximate intelligence of a single human rather than an entire community of humans.  Because of these differences the Turing Test must be distinguishable from other non-Turning Tests.

QUESTION:

  If Computer Science by definition, deals with the theory and methods of processing information in digital computers including artificial intelligence, and as a matter of pragmatics, on what basis are tests between human and machine qualified or disqualified as Turing test as Turing proposed them, or some other type of test Turing didn't conceive of (say non-Turing test for artificial intelligence)?


texts:
The exercise is to prove or give a counterexample to the following proposition with $L \subseteq \Gamma^*$ regular and $h: \Gamma \to \Sigma^*$ a homomorphism.

Is there any regular language $L'$ such that $h^{-1}(L^*) = L'^*$
?

I know that it isn't that easy to see, since $h^{-1}(L^*) \not= h^{-1}(L)^*$ in general with $L = \{a\}$ and $h : \{a,b\} \to \{a\}^*$ with $h(a) = a, h(b) = aa$. It is $h^{-1}(L^*) = \{a,b\}^* \not= \{a\}^* = h^{-1}(L)^*$.

I still fail to deliver a proper argument to prove it.


texts: Find non-regular $L$ such that $L \cup L^R$ is regular?

texts:
I've been studying for an exam I have tomorrow, and I was looking through some previous sample exam questions, when I came across this problem:

  Give a non-regular language $L$ such that $L \cup L^R$ is regular.

I've been sitting here and thinking and thinking, and I can't seem to come up with a situation where this is valid. I've determined a few things based on my understanding of non-regular languages, as well as the problem itself:

$L$ must be infinite.
$L$ must involve some kind of counting.
$L$ must contain multiple letters (i.e. it cannot be composed of entirely $a$s).

Given this, I went through a few basic possibilities:

$a^ib^i$ : This would result in $L \cup L^R$ being irregular also.
$(ab)^i(ba)^i$ (or something else palindromic) : Again, this would result in $L \cup L^R$ being irregular also. (Any palindrome would, as $L = L^R$.)
$a^pb^q$ (where $p$ and $q$ are prime) : This, too, would result in $L \cup L^R$ being irregular also, though it would be a very much broader language, which I think is a step in the right direction.

After I got this far, I think the key is in creating some language that, when unioned with itself, forms something akin to $a^*b^*$ or $(ab)^*$. The broader the words within the language, the easier it seems to define. But I can't seem to quite wrap my head around doing this.

Does anyone have a hint/spoiler or possible solution to this?

(NB: My professor does not post solutions.)


texts: I'm not sure how to get from the left hand side to the right. It appears in Sipser's Introduction to the Theory of Computing, in a proof of showing that a $t(n)$ time nondeterministic single-tape Turing machine has an equivalent $2^{O(t(n))}$ time deterministic single-tape Turing machine.


texts: solving Recurrence relation f T(n)=T(n/2)+log log(n)

texts:
T(n)=T(n/2)+log log(n)--------1
T(n)=T(n/4)+log log(n/2)+log log(n)-------------2
T(n)=T(n/8)+log log(n/4)+log log(n/2)+log log(n)-----------3
T(n)=T(n/2k)+log log(n/k)+....+log log(n/2)+log log(n)
T(n)=1+log log(n/k)+....+log log(n/2)+log log(n)
 n/2k=1 => n=2k
 T(n)=1+log log(2K/k)+....+log log(n/2)+log log(n)
 T(n)=1+log log(2)+....+log log(n/2)+log log(n)
 T(n)=1+log (log(2)*....*log(n/2)*log(n))

I ARRIVED AT THIS POINT BUT I DIDN'T KNOW HOW TO CONTENU ANY HELP PLEASE


texts: How to identify labels in unsupervised learning?

texts:
Let's say I am working on handwritten digit recognition (0 to 9). I know for instance that if I use clustering then I need to look for 10 clusters. But once I have the 10 clusters,how do I identify automatically which cluster corresponds to which digit?
In general, say I have some other classification task where I don't have the labels for the training data, but I know that there are, lets say, two classes. I want to build a model which can then tell me, for the test instances, which classes they belong to. But again the problem that even if I can group the train cases together, how do I know the actual label of the test instance in this unsupervised setting?


texts: Would a 'smallish' oracle for an NP complete problem actually be useful?

texts:
A quick thought experiment here:

Suppose one could construct an oracle that could yield a solution to an NP-complete problem (3SAT, TSP, SUBSET, etc) for smallish (30-60) inputs in a single operation.

Would there be areas in computer science/graphics/processing/etc where this would be particularly useful?  Which NP complete problem would be the 'most useful' to have an oracle for?


texts: How big is the capacity of a standard memory cell that the pointer is linking to?

texts: Often programming language lectures and references have an illustration of computer memory as an array composed of individual cells. Each cell has an address, which is effectively the pointer and can be used to access it. I learned that 32 bit systems will have 4 byte pointers and then got curious what the (standard) capacity of those cells (they are pointing to) was. The most discrete unit of memory is a Memory Cell, but with 1 bit capacity, this does not really fit the bill.


texts: Non-context free languages with word degree

texts:
I have stumbled across these 2 problems

$L_1= \{\alpha \mid w \in \{a,b\}^* | \alpha $  has exactly 2 b's$\} $ ,prove that $L =\{ \alpha^n   |  \alpha ∈ L_1 ,n \ge 0 \}$ is not context free
Given : $P= \{\alpha \mid w \in \{a,b,c\}^* | \alpha $ is palindrom with even length $\} $
and $L_2= \{\beta b^n| b$  ∈ $P^n$ and $n ∈ \mathbb{N} $} prove that  $L_2$ is context free.

In both problems we have degree $n$ of a word with length >1,usually in such problems how do we cope with that ?Also any suggestions,tricks or hints how to proceed in these 2 problems or in general with degree $n$  will be very helpful


texts: Path in an edge-weighted undirected graph

texts:
Is it an $NP$-hard problem?

You're given an undirected graph $G(V,E)$ with edge weight $w: E \to \mathbb{N}$ and a function $\mathrm{max}$-$\mathrm{visit}: V \to \mathbb{N}$ and a number $W$ in unary.

Does there exist a path in $G$ with overall product of edge weights equal $W$ and that does not visit any vertex $v$ more than $\mathrm{max}$-$\mathrm{visit}(v)$ times?


texts:
I realized that if a language L is recognized by a DFA, then flipping its accept and reject states (aka switching all the accept to reject states and all the reject states to accept) works to recognize the complement of L (which wold be L^c).

I was curious if that worked also with NFAs (flipping the accept and reject states to go from L to L complement), but with their additional paths it doesn't seem like it would work..Definitely seems like it would have too many accept states that aren't correct.

Is this correct? Is there more to it?
Thank you!


texts:
A Question from CLRS book:

  (CLRS 11.1-4) We wish to implement a dictionary by using direct addressing on a
  huge array. At the start, the array entries may contain garbage, and initializing the
  entire array is impractical because of its size. Describe a scheme for implementing a
  direct-address dictionary on a huge array. Each stored object should use O(1) space;
  the operations SEARCH, INSERT and DELETE should take O(1) time each; and the
  initialization of the data structure should take O(1) time.
  (Hint: Use an additional stack, whose size is the number of keys actually stored in the
  dictionary, to help determine whether a given entry in the huge array is valid or not.)

In SEARCH(K) - We can go to directly that Kth index, But we not sure about that garbage, We may access that garbage location and have Some Random behaviour or any other exception. That's why we using Stack, that's fine.

We are using Stack for validation of a slot in huge array, In most of the solution we are only storing the index of each other as value (i.e. index of Stack in a slot of huge array and index of that slot in Stack). This is just for validation, But where is that object with satellite data will go I mean how we can point that out via pointer? Hope you got my point.

Many thanks in Advance!


texts: Calculate maximum ammount of Bus Bandwidth

texts:
Don't know if this is the right community for this and this should be pretty basic but here goes.
I'm studying System Engineering and one of the homework problems is the following question.

  A 32-bit computer with a 200-MHZ Bus requires four cycles to read a
  32-bit word. How much bus bandwidth does the CPU consume in the worst
  case ?

I just can't get my head around this for some reason.
I thought that because it's a worst case scenario the CPU would just consume 4x (cycle) the entire Bus (200MHZ) which would be 800MB/s. I even reasoned this with reversing BIT > BYTE. Byte per Clock cycle. clock Cycle * Clock rate = bandwidth.
But appereantly i'm wrong with the correct answer seemingly being 400MB/s. I can't find (in the study material atleast) how to determine this.

Anyone out there that can help me out or at least set me on the right track ?
I could drop this question but i'm afraid this will haunt me in my nightmares.

Thanks so much.


texts: Polymorphism restriction on lambda-bound variables in HM

texts:
I'm trying to implement the Hindley-Milner type system, following Milner 1978, "A Theory of Type Polymorphism in Programming" (link). In the Hindley-Milner system, a polymorphic let-bound expression may take on a different type each time it is referenced. For example, we can have let id = (λx · x) in (id 3, id true) where id has type α → α with two instantiations, α = int and α = bool. However, the variable of a lambda expression is not permitted to be polymorphic in this way: λf · (f 3, f true) is not a well-typed expression.

To prevent this restriction from being "cheated" by something like λx · let x2 = x in ..., we must recognize some restriction on the polymorphism of let-variables as well. Milner 1978 describes it as follows:

  We decree that in instantiating the type of a variable bound by let or
  by letrec. only those type variables which do not occur in the types
  of enclosing λ-bindings (or formal parameter bindings) may be
  instantiated. We call such instantiable variables (in a generic type)
  generic type variables.

However, using what seems to me the obvious interpretation of "enclosing λ-bindings" (namely, that the let-expression should occur in the e of some λx · e), Milner's prescription does not seem to cover all of the cases where it is necessary to prevent some type variables of a let-binding from being polymorphically instantiated. Consider the following expressions:

let id = (λx · x) in (id 3, id true)
let id = (λx · x) (λx · x) in (id 3, id true)

While the first one is of course acceptable, I believe the second one should not be, as if this type of code is allowed, it becomes impossible in general for a compiler to generate statically typed code. And indeed, OCaml rejects the statement let id = (fun x -> x) (fun x -> x) in (id 3, id true).

So my questions are:

Am I interpreting the paper incorrectly?
How should I determine whether a type variable in a let-bound expression is eligible to be instantiated with multiple types?


texts: Are multiple interrupts generated when I hold down a key on my keyboard?

texts: When I hold down a key on my keyboard, a continuous stream of characters is generated and is displayed on the text editor, Now since pressing a key is a hardware interrupt, so does holding down a key continuously generates interrupt signals and does CPU constantly keeps acknowledging those ? or something else happens ?


texts: How a NTM guessing depends on the input?

texts:
After looking at the definition of nondeterministic TMs, it seems that, while guessing, the machine could go to at most $|Q|\times | \Gamma |$ configurations, being in a particular one.

However, if we look at several concrete NTMs, the guessing part depends on the size of the input, i.e. it's not bounded. For instance, let's take this machine finding Hamiltonian Path here:
How does this non-deterministic algorithm to find if a Hamiltonian path exists work?

A part of the algorithm says "Each number in this list is non-deterministically selected to be from 1 to x.", where x is the number of nodes of the graph(and we may have arbitrarily big number of nodes).

I know the answer is perhaps trivial, but I couldn't find it.


texts: Are deterministic context-free languages closed under reversal of languages?

texts:
It is well known that context-free languages are closed under the reversal of $L$. My answer to the question "Is the time reversal symmetry of non-deterministic computations important?" notices that this fact can be derived from the time reversal symmetry of non-deterministic computations. Hence:

  This raises the question whether deterministic context-free languages are closed under the reversal of $L$, because this is the only one of the examples where the deterministic and the non-deterministic languages are not identical.


texts: Which algorithm for predicting the next word(s) based on previous words, given a sentence?

texts:
I want to input some words, and out comes the next word(s). Neural nets are really hot at the moment, and I'm afraid of throwing a neural net at something, when one is not really needed. Or... maybe it is needed?

My current options are:

Predict next word(s) using N-grams
Predict next word(s) using a neural net

There are quite a number of Github repositories that does this using neural nets, and a few that does it with N-grams. Are there any clear advantages to choosing the neural net approach?


texts:
Imagine there is an area on which you have to put radio towers. Each radio tower sends signal to a circular area of fixed size.
How do I determine the optimal number and placements of these towers so the overlapping areas are as small as possible, the whole area is in range of towers, and the number of towers is minimal?


texts: Designing CFG that accepts a^n b^m (n<m<2n)

texts:
Designing CFG for the following language $\{a^nb^m \hspace{0.2cm} | \hspace{0.2cm} n\ge0, m\ge0, n\le m \le 2n \}$ is easy.

  $S \to aSb \mid aSbb \mid \lambda$

Then how about this? Language $\{a^nb^m \hspace{0.2cm} | \hspace{0.2cm} n\ge0, m\ge0, n<m<2n \}$.

It is somewhat difficult for me. I have no idea how to exclude $n=m$ or $m=2n$.

Could you give me some hints?


texts: Multiplying bivariate polynomials using FFT

texts:
Consider two bivariate polynomials of degree at most $n-1$ in each variable:
  $$ F(x,y) = \sum_{i,j=0}^{n-1} f_{i,j} x^i y^j \quad \text{and} \quad G(x,y) = \sum_{i,j=0}^{n-1} g_{i,j} x^i y^j. $$
  Show how to compute the product polynomial in $O(n^3\log n)$ time.

I know the product of two bivariate polynomials of degree $n$ is $O(n^2 \log n)$ but not sure about how to obtain the product at a degree of $n-1$ in order to get the answer needed.


texts: Time-Complexity Verification: Code with two loops with an index halved at each iteration

texts:
I have the following code in python and was asked to find the tightest upper-bound in terms of Big-O , I've done two attempts below and I don't know which one is right, can you help me verify as to which one is the right answer/approach?
def f1(L):
   n = len(L)
     while n > 0:
        n = n // 2
        for i in range(n):
          if i in L:
             L.append(i)
   return L

My attempts:
Approach 1:
While loop runs $ log(n) $ times. And at the $ith$ iteration the for-loop runs $ \frac{n}{2^i} $ times; inside the for-loop the conditional runs at most $ O(n) $ times ( because "in" has complexity of $ O(n) $ according to https://wiki.python.org/moin/TimeComplexity ). Thus, the time-complexity of the for-loop is $O(n^2) $. So  the time-complexity of total code is: $ \sum_{i=1}^{log(n)} O(\frac{n^2}{2^i}) = O(\sum_{i=1}^{log(n)} \frac{n^2}{2^i} ) = O( n^2 \cdot \frac{1-(1/2)^{1+log(n)}}{ 1-(1/2)^{log(n)} } ) = O(n^2)  $
Approach 2:
In the for-loop we have the conditional “if i in L” , the “in” costs $ O(n) $, thus time-complexity of for-loop is  $ \sum_{i=1}^{n} O(n) = O( \sum_{i=1}^{n} n  ) = O(n^2). $ Looking at the while loop  we see that “n” is halved at each iteration because of the statement “n=n//2” . Denote $ n_k = \lfloor \frac{n}{2^k} \rfloor  $ as the value of $n$ at the k-th iteration; Disregarding the floor function ( we won't care about $ \pm 1 $ for the value of $ n_k $ since we care about time-complexity ), we'll seek the smallest $ k $ ( we denote $ k $ as the iteration of the while loop ) where $ n_k = 1 \leq \frac{n}{2^k} \iff k \leq log(n) $. Hence the total time complexity of code is $ \sum_{i=1}^{log(n)} O(n^2) = O(log(n)) \cdot O(n^2) = O(n^2 \cdot log(n) ) $


texts: Genetic algorithm - fit max circles inside box - what chromossomes?

texts:
I am using a genetic algorithm to fit the max number of circles into a box. Right now my cromossomes are both coordinates of the each circle. I am not sure how to crossover and mutate the x and y coordenates in order not for the to converge but to keep a distance.

Can someone please shed some light? Thank you

This is where I am getting at:

Now I am getting this:

But there is the last ball always overlaps. I think my problem is with the crossover.

So far and by gathering all the ideas here this is what I have reached:
Given a fixed number of circles (easier to explain) this is what I am doing.

Create a random set of circles for each individual in the population

Calculate the fitness of every individual base on the overlaping area are and area outside the box.
I then order the individuals by their fitness
Do a cross over. For that I am using a cumulative sum to choose randomly but with priorities which individuals are likely to go through to the next generation based on the fitness. The fittest have a higher probability of being chosen.
After choosing them indivudals I am aplying the crossover to I randomly choose the chromosse to which I do the single point cross over.
Then repeat for n generations

I am doing this but not getting to any convergion in terms of solution.


texts: Does the host operating system know the content of your messages in a messaging applications?

texts: Let's say you are using a messaging application (Microsoft Team, Skype, Telegram,..) on an operating system (Windows, MacOS, Linux). Does the OS know what you are sending or receiving? If yes, how? Assuming that the computer can be setup for monitoring (e.g. company's computer).


texts: Direct construction of NFA for the difference of regular languages

texts:
Let $A$ and $B$ be regular languages. Let $C$ be their difference, i.e $C = B \setminus A$.

Given NFAs for $A$ and $B$, is it possible to directly construct an NFA for $C$ without (implicitly or explicitly) converting them to DFAs first?


texts: Finding embedded DAG in another DAG based on colors

texts:
I am looking for some graph theory concepts and definitions around embedding a DAG into another DAG.  I could only find a few lines on Wikipedia around this so I wonder if someone can help me find good references for the important concepts and definitions.

For example, assume I have a DAG $G=(E,V)$ where there are two types of edges, red and black.  $E_{red} \subset E$, $E_{black} \subset E$, and $E_{red} \cap E_{black} =  \emptyset$ .

I assume that the red edges represents some "core" DAG and the black edges represents "details".

If I want to extract this "core" DAG, I might do something like this:

Put $E_{red}$ and all related vertices into a new graph $G' = (E',V')$.

For every pair $e_p,e_c \in E_{red}$, if $e_c$ is reachable from $e_p$ and there is no other $e \in E_{red}$ on the path, then add the edge $(end(e_p),beginning(e_c))$ to $G'$.

$G'$ might then be thought of as having removed the black edges (and thus the details) from $G$.

My question is, what am I doing, and where can I read about embedding DAGs and extracting embeddings based on edge colors?


texts: Can I remove left recursion on this grammar

texts:
$S \rightarrow Sa \mid S \mid \epsilon$

This is a weird case where I have only one non-terminal. I'm trying to apply the algorithm 4.19 in the dragon book. It don't think it should be applicable but I think it gives something like that :

$S \rightarrow S'$

$S' \rightarrow aS \mid S' \mid \epsilon $

but this is equivalent to say

$S' \rightarrow aS' \mid S' \mid \epsilon $

Is this the right way to think about this?


texts: Functional data structure fast to add and unorded deletion

texts:
I am looking for a functional data structure that would work in this role.

Adding items to the struct happens often. Removing items from the struct happens as often as adding them but I have no way of knowing what order the deletion happens in. Over the long term addions will equal removal Rarely I need all items currently in the struct

I thought of using a queue but out of order removal from a queue is expensive.


texts: How can we prove that $g = O(f) $ (Big-Oh notation)

texts:
Problem description
I am trying to understand the first example of Big-Oh notation in Computational Complexity:A Modern Approach page 9.
If $f(n) = 100nlogn$ and $g(n) = n^2$ then we have the relations $f = O(g)$, $g = Ω(f)$, $f = o(g)$, $g = ω(f)$.

I understood why $f = O(g)$ and $f = o(g)$ . As for the rest I didn't. For instance in order for $g$ to be equal to $Ω(f)$ we must have $g = O(f)$.

Question
How can we prove that $g = O(f)$ and $g=o(f)$?


texts: How to prove that a problem is undecidable by using the Halting problem?

texts:
I cannot understand how to reduce the halting problem to a property to show that is undecidable.

For example, I have this property of a Turing Machine and I have to prove if it's recursive or not:

"M eventually enters the fifth state in its rule list when executed on an empty tape"

How can I do it? Do I have to reduce it to a halting problem or vice-versa?

Thanks in advance.


texts: Let $X$ a maximal prefix code on an alphabet $A$, $m(X)$ its maximal length, $F = X \cap A^{m(X)}$ and $F’ \subseteq A^{m(X)}$. Let $X’ = X \setminus F \cup F’$ a maximal prefix code. Why is it true that $X’ = X$? In other words, why is it true that one cannot obtain a maximal prefix code from another maximal prefix code with same maximal length by changing only the words of maximal length? Any reference for this result?


texts: What if a formal grammar cannot be terminated?

texts:
I'm currently in a class on Computability and we just finished looking at formal grammars before moving onto finite automata. We were given an several examples of a formal grammar, and one stuck out in particular:

V: { S, A, B, C }
T: { a, b, c }
P: {
    S -> aA | λ | ASA
   AA -> aA | a
}

My professor described the result as "any number of as". This makes sense if you never use the first S or AA rule; you can simply replace S with ASA as many times as you like, then replace each S with λ (getting some even-length string of As); you can then replace all AAs with as.

But what if I picked the first rule? So, I start with S, then replace S with aA. I now have a string that contains neither S, nor AA, so the final terminal string should be aA. (This could also be done with S -> ASA -> AA -> aA.)

Is this allowed? If so, what is the result called? Since it still contains a variable, is this just a rejected/invalid result?

NB: I did ask my professor about this. He explicitly said to "ignore the first rules of each 'S' and 'AA'", and could not give me any further explanation on why to do this.


texts: Is the balanced parentheses language inherently ambiguous?

texts:
I have this grammar:

$S\rightarrow SS |S \rightarrow(S)|S\rightarrow\epsilon  $

Now this grammar generates the set of balanced parentheses. But this grammar is ambiguous. I am trying to find an unambiguous grammar for this language but all in vain. This has led me to believe that the language is inherently ambiguous. Am I true? If not please provide an unambiguous grammar for this language.


texts:
Wondering about any known relations between $\mathsf{RL}$ complexity class (one sided error with logarithmic space) and its complementary class, $\mathsf{coRL}$.

Are they the same class?

What are $\mathsf{coRL}$'s relation to $\mathsf{NL}$, $\mathsf{P}$?


texts: Update model parameter with new data, discarding old data

texts:
I have this dataset, and I am using y = (a * x^n) / (b + x^n) Hill function as the model, where a is the limit of the Hill curve, b is the point at which a/2 is reached (for n = 1) and n is the cooperativity or steepness of the curve.

Currently, I am storing all x,y values and computing the parameters a,b,n using black-box optimization to minimize the least-squares error. (I currently use scipy.optimize.curve_fit, a standard optimizer that can minimize an arbitrary objective function.  In my case, the objective function is the total least-squares error.).

When new data points come along, I re-calculate the parameters with the old+new data, i.e. I append the new data to the old tuple of x,y values and get the new parameters.

Is there a way to update the parameters of the model without storing all of the previous old data points, once the initial parameters are obtained from the previous data points? I am looking for some kind of on-line algorithm to tackle the problem, but have no clue how to go about it. I read a blog-post that shows how do this for polynomial regression, but as the power of x which is n is a parameter to the model, I have no idea how to extend the approach to my specific function.

I am looking for a solution like so: I fit the curve to the first 1000 data points and have my parameters. Next, I discard some or all of the old data. Then, when I see the 1001st point I simply update my parameters and plot the curve again and so on for every new data point.


texts: Theta bound for runtime analysis of nested while loops

texts:
I am trying to fully analyze the running time of $\texttt{nestedLoops}$ in terms of $n$ with a Theta bound.
The Java code I have is as follows:
public void nestedLoops(int n) {
     int i = 1;
     while (i < n) {
          int j = i;
          while (j > 1) {
               int k = 0;
               while (k < n) {
                    k += 2;
               }
               j = j // 2
          }
          i *= 2
     }
}

I know that the innermost while loop has an obvious runtime of $\lceil \frac{n}{2} \rceil$.
But I get stuck on the next while loops. I think the middle while loop has a runtime of $\lfloor
\log_2\texttt{i} \rfloor$, but that is very confusing for me.
Any help would be taken with much gratitude.


texts: How to describe the languages of these regular expressions in plain English?

texts:
This is actually a question my lecturer gave us, so I know that it's kind of homework, but I tried to answer this and still had no luck.

The question is

  Give English description of the languages of the following regular
  expressions.

  $(1+\epsilon)(00^*1)^*0^*$
  $(a^*b^*)^*aaa(a+b)^*$
  $(a+ba)^*b^*$

I could only guess that the second one as the set of strings that at least have three consecutive $a$s. But I'm really clueless about others. Can someone make this clarified for me? Any help is highly appreciated.


texts: Guessing the smallest unique positive integer

texts:
Let us consider the following game: there are some players and a computer. Each player inputs one positive integer and his name (player doesn't know another's numbers, just his own). When all the players made their moves, computer outputs a name of winner – who submitted the lowest unique number.

How do you think, what is the best strategy for this game?


texts: Log-Space Reduction $CO-2Col \le_L USTCON$

texts:
I want to show that $CO-2Col \le_L USTCON$ (Log-Space reduction)

$USTCON$

  The $s-t$ connectivity problem for undirected graphs is
  called $USTCON$.

  [Input]: An undirected graph $G=(V,E)$, $s,t \in V$.

  [Output]: 1 iff $s$ is connected to $t$ in $G$.

$CO-2Col$

  A graph is $2$-colorable if there is a way to color the vertices
  of $G$ with $2$ colors, such that for every edge the two vertices
  on the edge are colored differently. $CO-2Col$ is the following
  problem:

  [Input]: An undirected graph $G$.

  [Output]: 1 iff $G$ is NOT $2$-colorable.

My solution is for an input graph $G$ the reduction outputs $(G',s,t)$ where
 $s$ an arbitrary vertex of $G$, $t$ is one of its neighbours and
$G'=G^2$ namely an edge $(u,v)\in E(G')$,iff there is $w \in V (w \ne u,v)$
such that $(u,w)\in E(G)$ and $(w,v)\in E(G)$.

$G$ is bipartite
iff $G'$ is not connected (and $s$ and $t$ belongs to different
parts).

But this only works when the input graph $G$ is connected.

A counter example: (if we choose s,t to be A,B)

How can I improve my reduction that it will work at the unconnected case? or maybe a new reduction is needed?

Thanks!


texts: Where would someone find amortized analysis more useful than average analysis and the opposite?

texts:
I'm trying to understand the difference between these two. They both look at what happens on average, however amortized analysis is actually dealing with exactly the amount of operations you are doing in each step, while average analysis produces an expected cost based on probabilities.

For them to both exist as separate ways of doing analysis of algorithms, then one must be preferred over the other one in some cases, however I can't figure a case to actually show that.


texts: $k$-SAT completeness proof when $k$ is linear in number of variables

texts:
I'm looking at a special version of SAT in which each clause has exactly $n/2$ literals, where $n$ is the number of variables. Can we prove NP-completeness of SAT in this case?
I tried reducing 3-SAT to it by expanding, but this introduces $2^{k-3}$ extra clauses per original 3-SAT clause, hence the reduction is not polynomial when $k=n/2$.
Any ideas?


texts: Find binary number with max hamming distance wrt given set of binary numbers

texts:
Suppose we have a set $A$ of binary numbers with the same length $n$.
For example (with $n=8$):

$A = \{ 10010011, 01011011, 00010010, 11110001\}$

Now, I want to find the binary number $z$ (also with $n$ bits) such that the minimum hamming distance between $z$ and any of these numbers is maximized.

i.e. $z = \arg \max \{ d(x,A) \mid x \in X\}$

with

$d(x,A) := \min \{ d(x,a) \mid a \in A\}$

where $X$ is the set of all $n$-bit binary numbers, and $d(x,a)$ the hamming distance between $x$ and $a$.

Is there any efficient algorithm for this?

Obviously, if $n$ is small enough we can brute-force this, but I'm looking for something more efficient when $n$ is large. The size of $A$, on the other hand, can be assumed relatively small, so any algorithm polynomial in $|A|$ is fine. Also, it does not have to be an exact algorithm. Any algorithm that approximates the correct answer is welcome too.


texts:
I have a cake with $n$ layers in total. I know that $k$ are vanilla, and at least $n-k$ are not. I dislike all flavors other than vanilla, so I decide to only eat those layers.
I can't tell which layer is which flavor, but I can smell the vanilla. For any $m$ with $1\le m\le n$, I can test the top $m$ layers of the cake by removing them from the cake and taking them to another room. There, I can smell whether any of those layers are vanilla. Then I can replace those $m$ layers in their proper position on top of the cake.
Once I've performed enough tests to determine if a layer is vanilla, I eat it right out from the middle of the cake, leaving the $n-1$ layers intact. I need to be certain what I eat is vanilla. Then I can return to doing more tests to find the next vanilla layer.
How can I write an algorithm that takes in $n$
and $k$, and outputs the number of tests required to identify (and therefore eat) all of
the vanilla layers?

In my opinion, the only way we can do this is by checking every single layer individually... I don't see how taking multiple layers at a time would ever work.
Let vanilla = 1 and other flavors = 0.
Let's say we have a cake 011:
and we take 3 at a time, and find there is vanilla, then we anyways need to check every layer.
Let's say we have 0000001
and we take 3 layers, then yes, we can move on to the next 3. But why don't we take 4 or 5?
Or 7? if we take 7 though, we'd be back at the first issue.
I think we have to do this individually (it would take $n$ tests) because trying to shorten it simply does not give us enough information. Any clarification would be helpful as this does seem too simple to me!


texts: Does an abstract syntax tree have to be a tree?

texts:
Does the output of a parser have to be a tree or could it also be general graph?

Moreover, is there any existing language or a plausible one that uses general graphs representation instead of trees for their syntax?


texts: Halting problem reducing to the blank tape halting problem

texts:
I was going through my book of proof and I find very confusing its definition, so I would like someone to help me in understanding this.

The blank tape problem takes a machine and an empty tape and tells if this machine halts or not
We prove it is unsolvable by proving it reduces to the halting problem

Whenever I read online, I read that we we write the input on the tape and we run this on the halting problem.

How do we construct the reduction?
Why do we write the input on the tape?
Isn't this all about having an empty tape?

update:
I think my misunderstanding is in the definitio of input and tape


texts: Formulas for which any equivalent CNF formula has exponential length

texts:
I read a claim that

  there are formulas for which any equivalent CNF has exponential length.

Can you show me an example for such a boolean formula? I have been trying to build it myself and failed.


texts:
This is not homework. I have the solution but it's not what I'm getting. I know there are multiple solutions to the problem but I want to make sure that I'm not missing anything.

The question is as follows:

  Prove that 2$n^2$
   - 4n + 7 = Θ ($n^2$). give the values of the constants and show your work.

Here is how I approached the problem:

From the definition of Θ(g(n)):

0 ≤ C1$n^2$ ≤ 2$n^2$ - 4n + 7 ≤ C2$n^2$

Divide the inequality by the largest order n-term. (This is the only way I know how to solve these equations.)

  0 ≤ C1 ≤ 2 - (4/n - 7/$n^2$) ≤ C2

Split the problem into two parts: LHS and RHS.

We start with the RHS:

Find constant C2 that will satisfy

  0 ≤ 2 - (4/n - 7/$n^2$) ≤ C2

n=1, (2 - (4/1 - 7/$1^2$)) = 5

n=2, (2 - (4/2 - 7/$2^2$)) = 7/4

n=3, (2 - (4/3 - 7/9)) =  13/9

We choose C2 to be 2, n≥2 to satisfy the RHS.

LHS: we try to find a constant that will satisfy

  0 ≤ C1 ≤ 2 - (4/n - 7/$n^2$)

From above, we know that after n=2, the equation approaches 2 as n grows larger, so if we pick a constant that is less than 2 then it should satisfy the LHS.

We choose C1 to be 1.
For n, choosing 1 would satisfy the left hand side, but since the RHS needs n≥2, we stick with it.

So the constants that prove 2$n^2$ - 4n + 7 = Θ ($n^2$) are

  C1 = 1 , C2 = 2 , n≥2

The given solution to this problem chooses n≥4, but I'm not sure why. It seems that n≥2 would work fine. Am I wrong somewhere?

If I'm not wrong, if I would have picked C1 to also be 2, wouldn't that also satisfy the left hand side since the inequality allows it to be ≤?


texts: How to generate a pushdown automata for accepting a language?

texts:
I have an exercise in my book to come up with a pushdown automaton accepting a language.

The exercise is to come up with a state diagram for the PDA accepting the language of all odd-length strings over $\{a, b\}$ with middle symbol $a$.

Here's what I have so far...

I wasn't sure how many states I needed, but I was thinking 3. State $q_0$ for pushing symbols onto the stack until reaching the middle symbol, $q_1$ for after middle symbol is found, and state $q_2$ the accepting state. I think in $q_1$ I need to cancel out input symbols from the stack with the input. I don't know how to account for the string being odd length, also.

Is there a smart, systematic way to do this?


texts: Pseudo code of recursive method of printing all permutations of $n$ given integers

texts:
I really don't understand this pseudo code. The function prints all permutations of $n$ given integers, assuming that all numbers are different.

Is there a way to explain this code more easily as I really don't get the purpose of the swapping.

PERMUTATE(A, start, end)
   if start == end return A
   else
      PERMUTATE(A,start+1,end)
      for i = start+1 to end
         SWAP(A[i],A[start])
         PERMUTATE(A,start+1,end)
         SWAP(A[start],A[i])


texts: algorithm performance with insufficient input

texts: Generally speaking, an algorithm takes some inputs and provides some output. I would like to understand how the algorithm performs when the inputs are incomplete for various real-world reasons. Are there any papers on this issue?


texts:
Can anybody give me  an idea how to write this assertion in in first order logic?

  X has not passed one or more of the prerequisites for A.

Here, X is the name of a person and A is a constant representing a course name.


texts: weight balanced binary tree vs height balanced binary tree

texts: What are advantages and disadvantages of weight balanced binary tree over the height balanced binary tree?


texts: How does processing speed affect algorithm performance?

texts:
I'm currently taking a class on algorithms, and we are studying algorithmic efficiency. I understand classifying algorithms based on their time complexity, but I am confused about the following category of questions:

Suppose algorithm A has time complexity C (C being along the lines of n^2, n + 1, 3 * 2^n, etc.), and it takes t seconds to execute A on a given machine for a certain number of inputs n. If you execute A on a machine that is M times faster than the original machine, how many inputs (n) can be processed in t seconds (same number of seconds as on the previous machine)?

I know that the greater the time complexity of an algorithm, the less improvement is gained by speeding up the machine, however I can't seem to figure out a reliable equation to compute the new number of inputs. For algorithms with linear time complexity, I think I am correct with: multiply the time complexity (constant * n) times the increase in speed to get M * constant * n. I haven't found much information about this either in books or elsewhere on the web; if anyone can help me create a better equation it would be much appreciated!


texts: Which area of research is the logical successor to Minsky's society of mind idea?

texts: I'm curious if there is any body of research that could be considered as the logical successor to Marvin Minsky's "society of mind" idea? It seems as if the notion of agents plays a crucial role in his thinking. I'd be interested in reading more about recent efforts in this direction.


texts: If $f(n)=\omega(h(n))$ and $g(n)=o(h(n))$ then is $f(n)=\Theta(g(n))$?

texts: My question is exactly what the title says. If I have that $f(n)=\omega(h(n))$ and $g(n)=o(h(n))$ hold, then does $f(n)=\Theta(g(n))$ hold as well? My intuition says that the second part is false, but I couldn't put this idea on paper.


texts: In a DAG, what is the name for a vertex with only one predecessor and one successor?

texts: In a directed acyclic graph (DAG), what is the name for a vertex with only one predecessor and one successor?


texts: prove that the satisfiability problem with each clause containing at most 3 literals, denoted by ≤3SAT, is NP-complete

texts:
I've tried to prove it for several days but I can't make sure if it is equivalent to max-3-SAT problem? This problem seems similar to the proof of SAT ∝ 3-SAT except the case where there are more than 3 literals in each clause.
so, we could prove that a clause with more than 3 literals could be broken into several 3-SAT.

for example

  x1
& x2 ∨ x3
& x4 ∨ x5 ∨ x6
& x7 ∨ x8 ∨ x9 ∨ x10 ∨ x11

This is a typical SAT problem. If we could break the last clause into several clauses and prove they are equal to the original, then we prove SAT ∝ ≤3SAT.

Fortunately, the way to break last clause into 3-SAT is exactly the same with how it is done in SAT ∝ 3SAT.

That is, we add y1 and y2 and make the last clause become

x7  ∨  x8  ∨  y1
x9  ∨ -y1  ∨  y2
x10 ∨  x11 ∨ -y2

suppose they are denoted S' and the original clause is S.
and, if S is satisfiable, then S' is satisfiable and if S' is satisfiable, then S is satisfiable

Since SAT, which is NP-complete, is polynomially reduced to ≤3SAT,
≤3SAT is also NP-complete.

However, The above proof is quite trivial if we already understand
the proof of SAT ∝ 3-SAT.

is there any general proof that could solve 3-SAT, ≤3SAT, n-SAT, ≤nSAT simultaneously?

Thanks


texts: What graph theory algorithm(s) would help solve this problem?

texts:
I have a directed graph with the following properties:

Except for a few special progenitor nodes, every node has two parent nodes
Any node can have any whole number of child nodes
The graph is generated such that no node is a descendant of itself in the following way: I starting with a few progenitor nodes (which have no parents) then randomly select two nodes and create a "child" node with directed edges going from each parent to the child. I repeat that step an arbitrary number of times.

I'd like to find an algorithm to efficiently identify subgraphs with the following properties:

The subgraph consists of two "parent" nodes and some or all of their descendants
Except for the two "parent" nodes in the subgraph, each node has both parents also contained in the subgraph (that is, if the subgraph were separated from the rest of the graph, no node would be separated from its parents, except for the two "parent" nodes).

It's easy to find a 3-node example of this type of subgraph - just take any two nodes and one of their mutual children. However, I'd like to be able to efficiently identify larger examples of these subgraphs.

I'd really appreciate some help pointing me in the right direction. I thought that what I need might be related to finding "weakly connected components", but I haven't made much progress, and my inexperience with graph theory makes it hard to figure out what to search for. Thanks!

PS: I've provided an example depiction of one of these graphs


texts: Type inference in compiler is context sensitive?

texts: Have read in Compiler textbook that type inference is context sensitive. Can anyone explain why is it so? This means that we need context sensitive grammar in semantic analysis phase of a compiler with this feature? How is it done in popular programming languages like C?


texts: Why can't we say that NP is closed under complement given that we can say it is closed under intersection

texts:
I found online solutions which prove the closure of NP under intersection in the following way: given machines $M_1,M_2$ for accepts nondeterministically languages $L_1,L_2$, we construct the following machine $M$ which accepts nondeterministically $L_1 \cap L_2$:

$M$ = ”On input $w$:

Run $M_1$ on $w$. If $M_1$ rejected then reject.
Else run $M_2$ on $w$. If $M_2$ rejected then reject.
Else accept."

Is this proof correct? Can't we use similar ideas to show that NP is closed under complementation, which is supposedly an open problem?


texts: test points inside of polygons/piecewise-linear contours

texts:
I have a set of piecewise-linear curves (i.e. "points connected by line segments") as shown in the figure below:

additional points are added on the borders (drawn in red) "closing" the open regions of the figure. In fact, the figure can be any plot with some closed piecewise-linear shapes on it (i.e. there are no lines or curves with open ends).

I need to find some (one is enough, but more is OK too if it doesn't significantly slow down the algorithm) testing points inside of EVERY closed contour (see e.g. the figure above). By adding the border lines all "open" regions become closed ones, so the whole figure consists of simple "closed" regions. However, this condition is not necessary in general.

The test points should also lie on some minimal distance from the boundary (this condition assures the meaningful results).

I also have a possible solution to the problem:

1) By a curve intersection algorithm all intersection points of any curve (incl. the "borders") with any other curve were found. By this procedure every curve was divided into segments by the intersection points lying on the curve.

2) Next, two normals are drawn from some linear piece of a segment to "infinity" (i.e. the length of the normals is big enough to place their endpoints outside of the plotted/bounded region).

3) The two nearest intersections are found, and the two test points are chosen at the half of the distance between the normals' origins and their two nearest intersections. If the distance is too small - choose another piece of the segment and repeat (2) and (3).
This should work since every curve is a border of some closed contour.

4) repeat (2) and (3) for all segments found in (1)

The proposed solution doesn't require that the closed contours are "detected" (i.e. that they are available as ordered lists of points). However, it can be assumed that the closed contours are "known" (their detection was discussed e.g. in detect closed shapes formed by points)

The main concern about the proposed solution is that it might be not quite efficient, because we need first NN/2 intersection checks (since the curves are checked pair by pair) in order to find all intersections. N is the number of curves. And then we need at least MN/2 intersection checks in order to analyze every segment. M is the number of curve segments.

However, in this problem the speed IS an issue.


texts: Is it possible to eliminate the unit rules in this?

texts:
S -> aA | bC | CC | a | b | C
A -> B
B -> S
C -> A | S

It looks like its going to loop so it would be endless replacing the unit rule....


texts:
gcc is a collection of compilers, based on the file extension it compiles a source file. But compilers are only supposed to convert a preprocessed code into assembly code. And after that assembling and linking is done and an executable is generated.
But several definitions says that compilers are the ones who convert source code into executable code..
i am confused. what actually a compiler is? what is gcc?
Can anyone please give me a clear definition? And i have seen in man pages of gcc mentioning the term "compiler proper" what exactly is this?


texts: Need Help Reducing Subset Sum to Show a Problem is NP-Complete

texts:
I want to show that the following problem is NP-Complete:

For a set of vectors $v_1,\ldots,v_n \in \mathbb{N}^d$ and an integer $k$, does there exist a subset $S \subseteq \{v_1,\ldots,v_n\}$, such that $S$ has $k$ elements and all coordinates in the vector $\sum\limits_{x\in S} v_x$ are powers of two?

I'm quite certain that establishing a reduction from a known NP-Complete problem: the Knapsack Problem, Subset Sum or Vector Subset Sum (see section 4.3 here) to this problem is the correct way to approach this problem, but I'm having difficulty
figuring out how to exactly construct the reduction.

Concerning Subset Sum with a set $S$ and an integer $n$, I've tried taking one of the integer compositions of $n$, then splitting it up into its binary representation, and using that to dictate a desired vector. Then I would construct vectors $v_1,\ldots,v_n$ from the elements of $S$. But how do I create the input $k$?

One of the main issues here is that Subset Sum with a fixed subset size is not NP-complete. How do I work around that? Moreover, one of the trickier aspects of the problem is generalizing subset sum such that success is reported if some subset sums to any power of two. I don't see how not to appeal to multiple sub-instances of subset sum...

Is this the right approach? (If not, how should I do it?) What am I missing? How do I prove this?


texts: Do we have to overcome any barriers for a proof of $VP\neq VNP$ proof?

texts:
Does the same barriers of relativization, natural proofs and algebrization affect a possible $VP\neq VNP$ proof?

How do existing strategies try to overcome these?


texts:
I am new and I have to develop an algorithm with a 2d integer array as input to compute the best career path.
Lets consider a network with n nodes, which are numbered from $1$ to $n$.
All are connected one to the other.

To move from node $i$ to node $j$ can have different costs (classical example job changing):

positive value indicates a benefit
negative value indicates a loss
some steps have a cost of $0$

Each entry of $B[i, j]$  indicates the beneﬁt (or the cost, if negative), of a step from node $i$ to node $j$.

I need to find out the maximal gain of a path from i to j is

$$
G(i, j) = \max { \{ g(p) \mid \text{ p is a path from i to j} \}  }
$$

It is not possible to gain from walking in a cycle.
This means, the values in B must be such that for any path p from a node i to itself, we have $g(p) \leq 0$.

Ex of matrix B:

$$
\begin{array}{cc}
 0 & 1 & 0 & 1 \\\\
−2 & 0 & 0 & −2 \\\\
 0 & 2 & 0 & 1 \\\\
−3 & −1 & −3 & 0
\end{array}
$$

Hints:

1) Cycles bring no gain. Therefore, the greatest possible beneﬁt of moving
from $i$ to $j$ can be achieved by visiting any intermediate node at most once.

2) Consider the following variant of the problem. Let $G_{aux}(i, j, k)$ be the maximal gain that can be achieved by walking from $i$ to $j$ along a path that uses only the nodes $1, \ldots, k$ as intermediate points.

The tasks asked:

Explain how $G_{aux}(i, j, k)$ can be used to compute $G(i, j)$. Develop a recurrence for $G_{aux}(i, j, k)$.
Write pseudo-code for algorithms that compute arrays with all values of
$G_{aux}$ and $G$ and explain why your algorithms are correct.

Who can help me with this tasks?
Is the basis of all this task the Floyd-Warshall's algorithm ? right?


texts: Question on "Hitting the memory wall, implications of the obvious"

texts:
I'm reading through a short paper about hitting the memory wall and I'm struggling to understand how exactly said wall will be hit.

The equation for average access time is fairly simple Tavg = p x Tc + (1-p) x Tm. (Tc = time for cache, Tm = time for DRAM mem, P = probability of cache hit)

What I don't understand is how as Tc and Tm diverge, we hit a wall. I recognize that Tc grows exponentially faster than Tm eventually Tm will play little to no role in access time, but it seems like me that average access time would then just continually increase. I can't seem to understand how a wall is hit.

Would anyone with a sharper mind or keener eye than mine help me to understand this concept?


texts: Find the average number of steps to sort an array by randomly selecting two elements

texts:
I have sequence of an unique numbers from 1 to 10 in randomly order (for example: list = [7, 5, 3, 4, 2, 6, 10, 1, 9, 8]). I can choose two random number and if the list from left number larger then right number I swap them (for example 2 and 5  list[2] larger then list[5] so I'll swap them and etc).
Need to find average number of all choosings to order the sequence.
The algorithm should executed less then 1 second.
Can anybody help me?


texts: How does hash table search scales with number of keys?

texts:
Say, I have one of the standard implementations of a hash table: chaining or open addressing, and my hash key is a pair of strings. Instead of using the hash table with the pair as a key, I can use the first key to get to a "sub" - hash table, and then use the second key to find the element from it.

How do these strategies compare, e.g. if one assumes the key pairs are more or less uniform?


texts: Find all vertices that are included in a simple cycle through a fixed vertex in a directed graph

texts:
Given a directed graph $G = (V, E)$ and a vertex $v \in V$, how to find all vertices $v'$ such that exists a simple cycle $v \to ... \to v' \to ... \to v$? That is, to find the set of vertices $$V' = \{v' : \exists c, \text{c is a simple cycle in G}, v \in c, v' \in c \}$$
I found this question related: Find all cycles through a given vertex. I can first find all cycles and then union them to get $V'$. However, is there a more efficient way to do so?


texts:
This is exercise 2 of the lecture note by Jeff Erickson on decision tree lower bounds.

We say that an array $A[1 \ldots n]$ is $k$-sorted if it can be divided into $k$ blocks, each of size $n/k$ (we assume that $n/k$ is an integer), such that the elements in each block are larger than the elements in earlier blocks and smaller than elements in later blocks. The elements within each block need not be sorted.
(a) Describe an algorithm that $k$-sorts an arbitrary array in $O(n \log k)$ time.
(b) Prove that any comparison-based $k$-sorting algorithm requires $\Omega(n \log k)$ comparisons in the worst case.
(c) Describe an algorithm that completely sorts an already $k$-sorted array in $O(n \log(n/k))$ time.
(d) Prove that any comparison-based algorithm to completely sort a $k$-sorted array requires $\Omega(n \log(n/k))$ comparisons in the worst case.

The first problem can be solved by modifying the quicksort algorithm. However, I am stuck with the second problem which asks for a lower bound. My attempt is to use the decision tree technique. I think the number of leaves of the decision tree is at least $((\frac{n}{k})!)^{k}$. Therefore, the height of the decision tree must be
$$ H \ge \log ((\frac{n}{k})!)^{k} = k \log (\frac{n}{k})! = \Omega(k \frac{n}{k} \log \frac{n}{k}) = \Omega(n \log \frac{n}{k}),$$
which is not the desired result $\Omega(n \log k)$.
What is wrong with my argument? And how to establish the lower bound $\Omega(n \log k)$?


texts: Arithmetic network to compute floor of binary logarithm

texts:
I wonder how to build efficient arithmetic network (using logical gates only) to compute floor of binary logarithm of the given input number. I have read some articles on stackoverflow.com about this problem, respectively its implementation in C/C++ using bitwise operations only.

Stackoverflow: Computing the floor of log_2(x) using only bitwise operators in C
Stackoverflow: Computing the floor log of a binary number
Bit Twiddling Hacks
I am pretty sure there's a simpler way to get this done. Using De Bruijn sequences seems to be a magic for me.


texts:
My challenge is to derive three mapping scenarios separately for each memory module of the MPEG-4 to the 2-D mesh, so each task is mapped to a different core, and tasks are executed in parallel.

Here is the graph of tasks - blue circles, rectangles represent memory modules and numbers between memory modules and tasks are values of communication cost:

And this is given NoC with 15 routers:

Purple boxes represent routers, to every router a core is connected, every router can either be a memory module(SRAMS or DRAM) or a task(purple circles). The goal is to assign tasks to different cores or memory modules to different routers according to given constraints. Given constraints: idle cores are omitted; all memory modules are fixed to their positions, so there will be 3 cases because every case will include only one specific memory module in its topology. For now, I need to figure out how to map all of them and get 3 paths from the first task(no idea about the order of tasks) to destination(memory module).

It is unclear to me how can I assign a task to one of the routers, I mean how should I choose the router for each task. If in the first case, we mapping SRAM1, then there should be only two tasks RAST and MED CPU? If so, then which routers I should pick and how should I choose the path and order of tasks

I have already read a few articles describing similar problems, but authors were using different methods to solve it, so I am still a bit confused and do not really understand how to start. I would be really grateful if you could guide me through or advise me on literature sources to look up.

  Not sure if this question is appropriate for StackOverflow concept, if
  not - let me know where I can post this, or maybe there is a separate
  thread for similar topics, please.


texts:
I am trying to show that the following problem is NP-hard.
Input: A boolean function in CNF (conjunctive normal form) such that every clause has at most three literals and every variable appears in at most three clauses.
Output: An assignment that evaluates the given function TRUE.
=========
Now it is quite obvious this problem is almost similar to the 3-SAT problem but with the added rule each variable can only appear in at most three clauses. For example, given $(x_1 \vee x_2) \wedge (x_1 \vee x_3) \wedge (x_1 \vee x_4) \wedge (x_1 \vee x_5)$. There are four clauses, each clause having two literals or variables. It is not a valid input since the variable $x_1$ appears more than three times.
For now, I've arrived at reducing the problem to the above example, which I am trying to reduce further to fit the criteria. There are two cases I can imagine: $x_1$ being True or False. If $x_1$ is False, then all I have to do is remove all instances of $x_1$ to produce the same result. But I'm not sure what to do if $x_1$ is True.


texts: Restrictions that set binary variable to 1 when integer variable equals x, 0 otherwise

texts:
I have this problem: I'm building an integer linear program, which I'm going to give to an ILP solver.  I have a binary variable Y which can be either 1 or 0 and an integer variable MONTH which takes integer values 1-12.

I have to give restrictions such that Y = 1 if MONTH = 1, and Y = 0 otherwise.

I don't know how to do this. I can think of a way to make Y = 1 when MONTH = 1, like Y + MONTH > 2, but I can't think of a restriction to make Y = 0 otherwise.


texts: Knuth's proof of O(1) for linear probing

texts:
I'm currently reading Knuth's proof about O(1) number of probes in
linear probing. I have a small question on the page 536 (Volume 3, 2nd Edition). Knuth says

  Let $f(M, N)$ be the number of hash sequences such that position 0 of the table will be empty after the keys have been inserted using linear probing.
  The circular symmetry of linear probing implies that position 0 is empty just as often as any other position, so it is empty with probability $1 - \frac{N}{M}$; in other words $f(M, N) = (1 - \frac{N}{M})M^N$.

I explain to myself as follows.
Each hash sequence has $M-N$ empty positions, then the total number of
empty positions is $(M-N)M^N$ and -- due to the symmetry -- each position is empty for $(M-N)M^N / M = (1 - \frac{N}{M})M^N$ hash sequences.
Thus, the probability of zero position to be empty is $(1 - \frac{N}{M})$.

The problem is that Knuth first states that the probability that 0 position is empty is $(1 - \frac{N}{M})$ and after says that $f(M, N) = (1 - \frac{N}{M})M^N$. I'm able to prove this only in other way around.
Could please anybody explain how to prove the probability without showing
that the total amount of empty positions is $(M-N)M^N$.

Thank you.


texts: NP-completeness of Induced disjoint paths

texts:
In graph theory, it is well-known to be NP-complete the problem of given a set of $k$ pairs of source-sink, deciding whether there exists $k$ vertex-disjoint paths connecting these pairs.

Our problem is a variant in which the requirement of being vertex-disjoint is replaced by being induced.

A set of $k$ paths is said to be induced if:

They are vertex-disjoint.
Each one is itself an induced path.
No edge connects two vertices of two different paths.

  Input: A graph $G(V,E)$ and $k$ pairs of source-sink $\{(s_1,t_1),\dots,(s_k,t_k)\}$

  Output: YES if there exists (a set of) $k$ induced paths connecting $s_i$ to $t_i$ for every $1\leq i\leq k$, NO otherwise.

Is this problem NP-complete?


texts: Algorithm to find extrema of a function?

texts:
What are some simple algorithms that find the maximum of a function in a certain domain?

The function $f$ is guaranteed to have 1 maximum and no other turning points between $a$ and $b$, how can I find out what the value of this maximum is without knowing anything about the function? I can only query what $f(x)$ is for some $x$. How can I eventually approximate the $x$ for which the function has its maximum?


texts: How to check whether given $k$ vertices make a $k$-clique in an undirected graph $G$ efficiently

texts: Let $G=(V, E)$ be an undirected graph with vertex set $V$ and edge set $E$. Let $V'=\{v_1, v_2, ..., v_k\}$ be a subset of $V$ where degree of each $v_i$ is bigger than or equal to $k$. Is there a way to check whether $V'$ is a $k$-clique more efficient than the brute-force algorithm in $O(k^2)$? Thanks in advance.


texts:
I came across following excerpts while reading about regular expressions identities:

  The regex associative laws are:
  $$(L+M)+N=L+(M+N)$$
  $$(LM)N=L(MN)$$
  Some important implications out of associative laws are:
  $$r(sr)^*=(rs)^*r$$
  $$(rs+r)^*r=r(sr+r)^*$$
  $$s(rs+s)^*r=(sr+s)^*sr$$
  $$(LM)^*N*\neq L*(MN)*$$

The issue is that

I don't find the implications much intuitive as the identities themselves are. How can I understand the implications intuitively? I can always form a strings belonging to left hand side regex and check whether it can be accepted by other regex. The first implication is very simple to test this way. However how can I make them more intuitive??
Are these implications simply made up expressions which are tested rigorously to hold true and they don't have any specific expression as we can form many such expressions?
I am unable to get the point behind stating these implications. I dont think of any problem in which I can use these regexes straight / immediately. It may be because I am not able to get intuition behind these implications so that it may strike in my head immediately when to use these implications.


texts: How can we find a palindrome within a string?

texts:
The problem requires us to find the substring within a string which happens to be a palindrome. Multiple palindromes are also allowed.
For example, in "LODHIHDAK"  "DHIHD" is a palindrome.

Comparing the reversed string with the original string to identify the common substring is one way but it isn't fool-proof.

For example,In the case of "KLXABAXYC", it would work.But in the case of "ABACDGFDCABA", it would not.

I was wondering if brute force could be used but I don't understand how.I'm looking to find the longest palindrome.


texts: The complexity of the reachability-coreachability analysis of a finite state machine

texts:
Let $A = \{\Sigma,Q,\delta,q_{0}, Q_{m}\}$ be a finite state machine (FSM). A state $q \in Q$ is reachable if there exists a string $s \in \Sigma^{*}$ such that $\delta(q_{0},s) = q$. The state $q$ is coreachable if there exists a string $s$ such that $\delta(q,s) \in Q_{m}$.

I'm wondering what is the computational complexity of the reachability-coreachability analysis of a FSM, as a function of $|Q|=n$.  In particular, the input is a FSM $A$, and I'd like the algorithm to output a list of all states that are reachable, and a list of all states that are coreachable.  What is the worst-case asymptotic complexity of this function, as a function of $n$?


texts: How to analyze/test a binary search algorithm?

texts:
I was asked to "Compute the average runtime for a binary search, ordered array, and the key is in the array." I'm not quite sure how to approach this problem. Isn't the runtime of binary search O(log n)? And the average would be something like n + n/2 + n/4... etc?

I'm then asked to "Implement a program performing an empirical test of the binary search (using a fixed number of random arrays for each n), then do a ratio test justifying your analytical answer." How would I go about doing this? Could I perform a basic binary search algorithm on a number of random arrays, counting the basic operations, and compare that to my original analysis from the first question?

I appreciate any help/guidance here.


texts:
My professor uses the term "clean graph" to mean that the nodes have no idea of the topology. Each node is aware of its ID, but has no idea about parents or edges and so on and it has to discover.

Is this terminology a thing? Because I find no evidence in the internet. Is there another term for the same thing?


texts:
Given a directed graph $G$ and two nodes $s,t$, decide whether there is some node $s'$ such that $s'$ is reachable from $s$ while $t$ is not reachable from $s'$.

I am wondering whether this problem is in NL.


texts: One-sided, distance-optimal polyline reduction to a given number of vertices

texts:
So I have been battling this rather peculiar problem:

given the following input (on an euclidean plane):

point p
polyline l
integer n
p is not inside of the convex hull of l

find a new polyline l', such that:

it has n vertices
it "covers" l with respect to p, i.e., a line section connecting any point on l with p will intersect l'
it is not "behind" l with respect to  p, i.e., a line section connecting any point on l' with p will not intersect l
l' tries to approximate l as best as possible, even with the limited number of vertices n, it has, i.e., the maximum distance(l', any vertex on l) should be the smallest possible

In other words, if n = number of vertices of l, the result should be l' = l

I have drawn this sketch for better illustration with two different examples. The point p is drawn in green, the line l in black and l' in blue.

In layman's terms, I want to create a simplified version of the polyline by "pushing" a new polyline with a predefined number of vertices onto it, from the direction of the point. The new polyline cannot under any circumstances get to the other side of the old polyline.

The definition of "covers" is there in order to make sure that l' is not "smaller" from the point of view of p. As in, imagine you were standing at point p. You should not be able to see l, you should only be able to see l'. The difference is that "covers" is a line, but "is behind" is a line section. I guess they are basically the same, but I wanted to make it clear what I want to achieve.

I would like to find a fast optimization algorithm for this, provided this is polynomial-time solvable (it feels like it, right?). I was thinking linear programming, but I have no idea how to formulate the problem. I am of course open to any other ideas.

Any help would be greatly appreciated!

A few note about the two examples I posted in the comments:

Left vol, cell 4: As you can see, l has this large "valley". This is where l gets the farthest from p. The objective is for l' to close in on this distance as much as it can, with the limited number of vertices it has (n=4), without violating any of the constraints. The first and last points are where they are to satisfy the "cover" constraint and because it's the closest possible. The third point from left: it gets as close as possible, without violating the "behind" constraint (if it was any lower down, the lines would intersect on top right, below the second point of l, from right).

Right column illustration. This is a bit of a mistake on my part. The first point on the right is not exactly supposed to be where it is in this illustration. It is supposed to be there tho demonstrate the "covers" constraint, but it basically does not make sense with p being where it is in the illustration. Basically, Imagine that p is way farther to the top (i did not want to make a tall drawing). If its farther to the top, the right point of l' needs to extend over l like this, in order to satisfy the "covers" constraint.


texts:
In wikipedia NFA-ε transition function defined as follows $Δ : Q × (Σ ∪ \{ε\}) → P(Q)$, where $Σ$ is an alphabet and $ε$ - empty string. I don't understand the meaning of $ε$ in this context.

Assuming $ε$ means a sequence of symbols with length of zero, as per definition.

Alphabet $Σ$ is a set of symbols. But symbol $\neq$ sequence of symbols (string). Thus, $(Σ ∪ \{ε\})$ is no longer set of symbols, but a mixed set.
I don't know much of set theory, but is this mixed set allowed in this context?

Also. When does NFA ε-transition happen?

ε-transition happens when input symbol is an empty string? Meaning, that presence of empty string is necessary condition for ε-transition .
ε-transition happens when there are no input symbol at all? Meaning, that
presence of empty string is not necessary condition for ε-transition.

I think that the latter case, or I am wrong?

I would have avoided this confusion, if $ε$ would mean "NO_INPUT" symbol, rather an empty string as per definition.


texts: Does a PC age in terms of hardware and performance?

texts: Let's say you are using a personal computer for 10 years. Assuming all software things are the same, will the computer get the same scores on benchmarks as 10 years ago? If not, why?


texts:
A cache memory has a line size of eight 64-bit words and a capacity of 4K words.  The main memory size that is cacheable is 1024 Mbits.  Assuming that the addressing is done at the byte level, show the format of main memory addresses using 8-way set-associative mapping.

So here's what I have understood from this question so far:
Line size = 8 words = 2^3, which means that w = 3;
Cache size = 4K = (2^3 + 2^6)/(2^3) = 2^6 lines;
8-way set associative means that each cache contains (2^6)/(2^3) = 2^3
Main memory size = 1024 Mbits = 128 M

I am stuck as to how to proceed next. Any help would be greatly appreciated.


texts: Does the proof of undecidability of the Halting Problem cheat by reversing results?

texts:
I have trouble understanding Turing's halting problem.

His proof assumes that there exists a magical machine $H$ which could determine whether a computer would halt or loop forever for a given input. Then we attach another machine that reverses the output and we have a contradiction and therefore $H$ cannot exist.

My concern is that it seems as though we are saying an answer is wrong because we reversed it. As an analogy, if there is a machine called $A$ such that outputs a correct answer on certain inputs and an incorrect answer on others. Then we attach another machine that reverses the result of $A$ so the combination the two machines have a contradiction with how $A$ is defined. The two machines now generate incorrect answers for inputs that $A$ is defined to output correct answers and outputs correct answers for inputs that $A$ is defined to output incorrect answers. Would this be called a contradiction, and therefore there does not exist a machine that outputs correct answer on some inputs and incorrect answers on others?


texts: CFL Intersection with Regular Language prove

texts:
how can i prove the following statement :

1- $L_1\subseteq\Sigma^*$ is CFL and $L_2\subseteq\Sigma^*$ is regular Language, then $L_1$\ $L_2$ is CFL .

so i want to know what is the method to prove it ?

I'm not sure, but can i use a PDA and DFA or something else ?

so i tried the following :

$L_2$ is regular and thus is $\overline{\rm  L_2}$ also regular.

$L_1 \cap \overline{\rm  L_2}$ is CFL $\iff$ $L_1 \cap \overline{\rm  L_2}$ is recognized by a PDA.

$M1=(Z_1,\Sigma,\Gamma,\delta_1,z_{01},$#$,E_1)$ is a PDA for $L_1$

$M_2=(Z_1,\Sigma,\delta_2,z_{02},E_2)$ is a DFA for $\overline{\rm  L_2}$

$M^{'}$=($Z_1$x$Z_2$,$\Sigma,\Gamma,\delta^{''},(z_{01},z_{02}),$#$,E_1$x$E_2)$
, so that $M^{'}$=$M_1\cap M_2$

but how should i define $\delta{'' ?}$

Many Thanks