texts: Why ⊢ for affirmative predicates and ⊨ for ¬negations?

texts:
I read a book which says that in Predicate Calculus, syntactic theorem proving is identical (complete and sound) with semantic entailment and this is very useful because it is easier to prove positive witnesses in natural deduction whereas when you seem to fail you better switch to semantic account to demonstrate a counter-example.

Particularly Logic in computer science says

  to show that Γ  ⊢ψ is valid, we need to provide a proof of ψ from Γ.
  Yet, how can we show that ψ is not a consequence of Γ? Intuitively,
  this is harder; how can you possibly show that there is no proof of
  something? You would have to consider every ‘candidate’ proof and show
  it is not one. Thus, proof theory gives a ‘positive’ characterisation
  of the logic; it provides convincing evidence for assertions like ‘Γ
  ⊢ ψ is valid,’ but it is not very useful for establishing evidence
  for assertions of the form ‘Γ ⊢ φ is not valid.’

  Semantics, on the other hand, works in the opposite way. To show
  that ψ is not a consequence of Γ is the ‘easy’ bit: find a model in
  which all φ_i are true, but ψ isn’t. Showing that ψ is a consequence
  of Γ, on the other hand, is harder in principle. For propositional
  logic, you need to show that every valuation (an assignment of truth
  values to all atoms involved) that makes all φ_i true also makes ψ
  true. If there is a small number of valuations, this is not so bad.
  However, when we look at predicate logic, we will find that there are
  infinitely many valuations, called 'models' from hereon, to consider.
  Thus, in semantics we have a ‘negative’ characterisation of the logic.
  We find establishing assertions of the form ‘Γ ⊭ ψ’ (ψ is not a
  semantic entailment of all formulas in Γ) easier than establishing ‘Γ
  ⊨ ψ’(ψ is a semantic entailment of Γ), for in the former case we need
  only talk about one model, whereas in the latter we potentially have
  to talk about infinitely many. All this goes to show that it is
  important to study both proof theory and semantics. For example, if
  you are trying to show that ψ is not a consequence of Γ and you have a
  hard time doing that, you might want to change your strategy for a
  while by trying to prove the validity of Γ ⊢ ψ. If you find a proof,
  you know for sure that ψ is a consequence of Γ. If you can’t find a
  proof, then your attempts at proving it often provide insights which
  lead you to the construction of a counter example. The fact that proof
  theory and semantics for predicate logic are equivalent is amazing,
  but it does not stop them having separate roles in logic, each
  meriting close study.

I was sure that we can prove the opposite by proving ⊢ ¬ψ and wondered why do we need the entailment. Now I see that validity of the opposite has nothing to do with validity of affirmative statement. Thanks. What we need is the satisfaction of the ¬ψ, which says that there is a counterexample. We do not need the validity of ¬ψ. But why semantics instead of proof? Do you say that semantics is in patrimony of satisfaction whereas proof theory is dedicated to validity?

I have mistakenly thought that not being able to prove ψ means that ψ is absurd and, thus, you can prove ¬ψ. But, this seems not to be the case.


texts:
In Spanner, TrueTime & The CAP Theorem, Eric Brewer writes:

  One subtle thing about Spanner is that it gets serializability from
  locks, but it gets external consistency (similar to linearizability) from TrueTime [emphasis added].

What is the definition of external consistency, and how does it differ from linearizability?


texts: Prove simple theorems in Haskell in automated way

texts:
I would like to prove in Haskell, whether in vanilla Haskell or using some libraries / tools, some simple theorems such as:
and [n*(n+1)/2 == sum [0..n] | n <- [0..]]

Is there a simple enough (ie. fully automated) way to prove such theorems involving integers in Haskell? I am not really interested in the proof itself, or a counterexample, but merely a yes/no answer.
There's this publication which doesn't seem practically usable; other than that most of everything else seems to be rather complex, ie. involving a completely separate language and not concerning Haskell.


texts:
Be $L$ a formal language over the alphabet $\Sigma$. $L$ can be defined by induction:
$L^0 = \{\epsilon\}$ and for $i>0: L^i = \Sigma*L^{i-1}$.
Means that $|L^n|$ is the number of words in $L$ of length $n \in \mathbb{N}$ letters from $\Sigma$.
Find $|L^n|$.

For $\Sigma = \{a,b\}$, $|L^n| = 2^n$ scince $|\Sigma| = 2$ and $|K*\Sigma| = |K|*2$ (with $K$ being an arbitrary set). Right?
But what happens if $\Sigma = \{a,b,aa,ab,ba,bb\}$ ?
For some $n$ some elements can be created in multiple ways (e.g. $a$ and $ba$ result in $aba$ and $ab$ and $a$ result in $aba$). Therefore $|L^n| \neq 6^n$.
The problem clearly is, that some letters of $\Sigma$ (e.g. $aa$) consist of other letters of $\Sigma$ (e.g. $a$).
So far i looked at some results (no guaranty for correctness):

$|L^1| = 6$
$|L^2| = 28$
$|L^3| = 120$
$|L^4| = 496$
$|L^5| = 2016$
$|L^6| = 8128$

And found a formula for these values: $|L^n| = 2^n*(2^{n+1}-1)$
However, i can't explain or prove it. What is the correct way to approach this? Which words can be created in multiple ways?


texts: Reduce Subset Sum to a modified knapsack problem

texts:
The problem looks a bit like the knapsack problem, but here the objects placed in the sack are unique and it is allowed to overflow the sack. The main goal is to see if it is possible to fill all of the sacks.

PROBLEM: Say I have a set of unique buckets $Q = \{4,2,7,1\}$, where the value indicates the space of each bucket. Also, I have a set of unique objects $T = \{1,3,2,2,4,3\}$ where the value of each indicates the spaces it takes up.

Overflowing values are discarded, meaning that you can't split an object between buckets.

Is there a way for me to take those unique objects and place them in the buckets such that all of the buckets are filled - overflow is allowed.

My question: For a given number of buckets $Q$ and objects $T$ - I wish to show this is NP-Complete by reducing from the Subset Sum problem. How would I go about doing this?


texts: Can the zero-one principle be used to prove the stability of a sorting network

texts:
When dealing with sorting networks, we can check the validity of a sorting network with only $2^n$ sequences of $0$ and $1$ (where $n$ is the size of the collection to sort) thanks to the zero-one principle:

  The zero-one principle states that, if a sorting network can correctly sort all $2^n$ sequences of zeros and ones, then it is also valid for arbitrary ordered inputs.

I have used this principle to prove that my sorting networks worked. However, I also wanted to check whether some of them were stable or not: in order to do so, I tried to feed pairs of $(0, index)$ and $(1, index)$ to the networks instead of simple $0$ and $1$ and checked whether the indices of elements with the same values were still in the correct order after the sort (of course, the sequences were sorted based only on the first value of the pair). It was sufficient to prove that my sorting networks weren't stable since the algorithm was able to find at least one sequence that wasn't stably sorted per network.

However, even if every sequence was stably sorted, I still wouldn't be sure whether the sorting networks are stable or not without answering this question: can the zero-one principle be used to prove the stability of a sorting network?


texts: Would you ever use a skip list over a treap?

texts:
Skip lists are taught as a standard of the undergrad CS curriculum at many major universities.  However, from my reading* I can't find any practical situation where you would use a skip list over  a treap. Also they have the same asymptotic performance  for all the main operations.

As a result this left me wondering:

  Should you ever choose a skip list over a treap?

*A few web links that suggest that treaps are faster in practice or a just very fast in practice.

http://pinporelmundo.blogspot.co.uk/2011/06/skip-lists-compared-with-treaps-and-red.html
https://stackoverflow.com/a/16009599/2179021
https://stackoverflow.com/a/18303163/2179021

and here is a link suggesting that skip lists are almost never useful

https://www.quora.com/Why-arent-skip-lists-used-more-often-instead-of-balanced-trees


texts: Which would be better for programming using Homotopy type theory Agda or Idris

texts:
I'm looking to model data inputs for an artificially intelligent system, which is affected by its internal parts and has feedback loops. I'd like to model it mathematically, using category theory or homotopy type theory.
Is Agda or Idris the best choice for such modelling?


texts: How operating system is generic with different processors?

texts: I have one query, Operating system (In machine language) as I study is the combination of opcodes that executes, Now, the opcodes are dependent on the instruction set architecture like how and which opcodes are executes. There are number of architectures such as RISC, CISC, Intel x86 which by sure have different opcode structure so how come the operating system become generic. For example we can run same Windows on X86 Intel computer and same windows DVD can be run on the AMD processor architecture ? or Am I missing some thing.


texts: Grammar that contains letters a,b,c and number of letters $c$ is greater than number of letters $b$

texts:
I look for grammar which use letters $a,b,c$ that numbers of letters $c$ is greater than number of letters $b$.

Example: $acbccba$

I thought about:

$$S \rightarrow aS \mid bS \mid SCS$$
$$C \rightarrow cb \mid ca$$

but not sure if it work. Could you help me, please.


texts:
The general question, as the title suggests, is:

What is the difference between DS and OR/optimization.

On a conceptual level I understand that DS tries to extract knowledge from the available data and uses mostly Statistical, Machine Learning techniques. On the other hand, OR uses the data in order to make decisions based on the data, for example by optimizing some objective function (criterion) over the data (input).

I wonder, how these two paradigms compare.

Is one subset of the other?
Are they consider complementary fields?
Are there examples that one field complements the other or they are used in conjuction?

In particular, I am interested in the following:

  Is there any example where OR techniques are used to solve a Data Science question/problem?


texts: Meaning of , and ; in relation to defining context

texts:
I have seen use of , and somewhere use of ; when defining context :

$$\dfrac{\phi \ ,  \ \Gamma \  \vdash }
        {}
       $$

somewhere else i have seen :

$$\dfrac{\phi \ ;  \ \Gamma \  \vdash }
        {}
       $$

What is the difference between both. I have read something like extension of context. Then what second one means.


texts:
I'm taking the MIT Open Courseware for Introduction to Algorithms and I'm having trouble understanding the first homework problem/solution.

We are supposed to compare the asymptotic complexity (big-O) for different functions:

$f_1(n) = n^{0.999999}\log(n)$
$f_2(n) = 10000000n$

$f_2(n)$ is obviously O(n), but the big-O given for $f_1(n)$ confuses me and I don't follow the given solution.

The solution says $f_1(n)$ has less Big-O complexity than $f_2(n)$:

"recall that for any $c > 0$, $log(n)$ is $O(n^c)$.

Therefore we have: $f(n) = n^{0.999999}log(n) = O(n^{0.999999}n^{0.000001}) = O(n) = O(f_2(n))$"

I do not understand the logic underlying the solution. I may be forgetting something simple? Can someone break it down for me? Thanks!


texts: reducing $CLIQUE$ from decision to search problem

texts:
consider the language:$$CLIQUE = \left\{\langle G,k\rangle \ |\ \text{ $G$ is a graph containing a clique of size at least $k$ } \right\}$$

  Suppose there's a polynomial time algorithm for $CLIQUE$. I need to show a polynomial time algorithm for finding a clique of size $k$.

Now, the idea is pretty easy if there's only one clique in the graph - You remove each vertex $v_i$ and query for $CLIQUE(G_i, k)$.

If there are two cliques in the graph this algorithm could not be applied since no matter which vertex will be removed there will always be a clique of size $k$.

An alternative would be removing each one of the ${m}\choose{k}$ but if $k = n/2$ for example, that wouldn't be a polynomial time algorithm anymore.

So my question is, can we solve this problem for the general case where there might be multiple cliques?


texts: Is a system of equations derived from mutually recursive ADTs always uniquely solvable?

texts:
After looking at Can a computer determine whether a mathematical statement is true or not? for a while, I worry we may be into incompleteness/halting problem territory with this question, so an answer on that front, while disappointing, would also be acceptable
I've been interested by ADT equations since I read the linked post, and I've started thinking about them in the context of Coq's inductive types (which essentially permit the usual sum, product, and unitary type constructors).
In particular, I've been considering the correspondence between type definitions and the number of elements inhabiting the type. In particular, solving the type's equation yields the number of elements inhabiting the type, and it seems reasonable to me that, for any so-definded type, this number is at most $\aleph_0$. That is, for any ADT or inductively defined type, the number of inhabitants is at most countably infinite. I'm thinking about how to formulate or prove such a statement in Coq, and in the meantime had some questions. (It seems further natural that such types and numbers are in one-to-one correspondence up to isomorphism between types of the same cardinality, but that might be a step too far).
It seems easy enough to show a type definition containing exactly $n$ elements for any natural $n$, so that gives one direction of a theorem connecting the two. Going the other way, though, seems more difficult, and in either case it woudl be natural to me to rely on a function $C$ from types $\tau$ to numbers (what class of numbers?) $n$ where $C(\tau) = n$ means there are $n$ elements inhabiting the type.
The trouble is, this function doesn't seem computable. If we take the naturals as
Inductive nat: Type :=
  | O
  | S: nat -> nat.

such a function would be required to produce an infinity (namely $\aleph_0$), and thus I don't think Coq could accept such a definition. (Worse, how would the definition know when to return 0?)
So I've come back around to equations. I wondered if I could formulate this idea by constructing for each type $\tau$ (possibly parameterized on other types $\alpha, \beta, \dots$) a polynomial (is this the right term, since it may really be a recurrence?) in the same class of numbers $\tau(\alpha, \beta, \dots) = P(\tau, \alpha, \beta, \dots)$ and proving that all such equations have a unique solution (and herein lies my concern above: would this even be provable?).
This brings me to my main question: I believe that the above statement is true in the absence of mutually recursive types. But mutually recursive types suggest systems of equations, rather than a single equation, and it is well-known that systems do not always have a solution.
But these systems would have some (possibly unique) properties:

they would be polynomial in this class of numbers
each would have the form $\tau_i = P(\tau_1, \dots, \tau_n)$
there would be exactly $n$ equations for $n$ mutually recursive types

Is it possible to prove (or already proven) that such systems are always uniquely solvable in the naturals? I suspect it might be easier to formulate in Linear algebra, but I'm a bit rusty on what it takes to do that here.


texts: Prove that every two vertices in graph are connected by a path of some length

texts:
I'm working on simulating a network architecture. I'm representing every node and their connections as a connected graph with no directional edges. I need some help with my reasoning.

Every node in network is connected to exactly 3 others. Is it possible for me to prove that every two nodes have a path of length O(n/3) between them? I can show people that the way I setup the network guarantees some existence of relatively fast routes. The n is much more than 3

Thank you


texts: Algorithm Suggestion for periodic alerts

texts:
I am making a webapp that alerts when product prices fall or rise above a number. Let's say a product costs 100 and the user wants to be alerted when it reaches 80, the prices change every hour or so and I need to trigger all the alerts. What is the best way for this to make this work.

What I have tried so far?

Approach 1
At the time of setting the alert, if the price was 100 and user wanted 80, I am classifying this as a "less" alert or if the price was 100 and user wanted 120, I classify this as a "great" alert
If the price reaches 75 at a later point in time, I have a "less" alert whose value is greater than 75 and therefore I trigger it

(type=less and current_price > alert_price) or (type=great and current_price < alert_price)

Is there a better algorithm to achieve the same task with perhaps lesser comparisons as this takes a lot of time to scan on the database with 1 million+ products (sequential scan)


texts:
One of the paper titled "Rules of Thumb in Data Engineering" (Jim Gray et. el.) mentions some calculations based on Amdahl's balanced system law.

Link to paper: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/ms_tr_99_100_rules_of_thumb_in_data_engineering.pdf

Initially, the paper provides some rules of thumb.

"10. Amdahl’s revised balanced system law: A system needs 8 MIPS/MBpsIO, but the instruction rate and IO rate must be measured on the relevant workload. (Sequential workloads tend to have low CPI (clocks per instruction), while random workloads tend to have higher CPI.)

Alpha (the MB/MIPS ratio) is rising from 1 to 4. This trend will likely continue.
Random IO’s happen about once each 50,000 instructions. Based on rule 10, sequential IOs are much larger and so the instructions per IO are much higher for sequential workloads."

Later, the paper provides following example.

"Amdahl’s balanced system law becomes more complex to interpret in the new world of quad-issue pipelined processors. Table 2 summarizes the following analysis. In theory, the current 550 MHz Intel processors are able to execute 2 billion instructions per second, so Amdahl’s IO law suggests that each 550 MHz processor needs 160 MBps of disk bandwidth (all numbers rounded). However, on real benchmarks, these processors demonstrate 1.2 clocks per instruction (CPI) on sequential workloads (TPC-D,H,R) and 2.2 clocks per instruction on random IO workloads (TPC-C, W) [7,8]. These larger CPIs translate to 450 MIPS on sequential and 260 MIPS on random workloads. In turn, Amdahl’s law says these processors need 60 MBps sequential IO bandwidth (~450/ 8) and 30 MBps random of IO bandwidth (~260/8) per cpu respectively (for tpcH and tpcC). A recent tpcH benchmark by HP [5] used eight 550 MHz processors with 176 disks. This translates to 22 disks per cpu, or about 70 MBps of raw disk bandwidth per cpu and 120 MBps of controller bandwidth per cpu (consistent with Amdahl’s prediction of 60MBps). Amdahl’s law predicts that system needs 30MBps of IO bandwidth. Using 8KB pages and 100 IO/s per disk implies 38 disks per processor – a number comparable to the 50 disks Dell actually used [4]."

I could not understand two parts of it (marked in bold). Need help to understand it.

1). How Amdahl's IO law suggests 160 MBps here (or is it 60MBps as indicated later (in bold))?

a. According to Amdahl's IO law, 50,000 instructions will need 1 IO (but of what size??)

b. Hence, 2 billion instructions (= 2 * 10^9 instrs = (50,000) * (40,000)) will need 40,000 IOs (but of what size?)

c. Should we multiply this 40,000 by 4 (because of quad-issue pipelined processor)? This will give 160,000 IOs.

d. Should we assume 1000 Bytes for each IO? If this is the case, it will give 160MBps!!

e. After this I am lost. Are my assumptions in (c) and (d) correct?Please help

2) How tpcH benchmark by HP translates to 70MBps of raw disk bandwidth per cpu and 120 MBps of controller bandwidth per cpu?

a. I could understand that if 176 disks are used with 8 processors, it is about 22 disks per cpu.

b. But, how this translates to 70MBps of raw disk bandwidth per cpu and 120MBps of controller bandwidth per cpu?


texts: Merge sort worst case running time for lexicographical sorting?

texts:
A list of n strings each of length n is being sorted in lexicographical order using the merge sort algorithm. Since we have to take care of comparison of each character in the strings so the merge step would be $O(n^2)$. So the recurrence should be of the form

  $$T(n) = 2T(\frac n2) + O(n^2)$$

By master's theorem it solves to $O(n^2)$.

Somehow some people on the internet claim the following explanation:
Merge sort makes $O(nlogn)$ comparisons and since it is lexicographical sort each comparison take $O(n)$ time, so worst case time is $O(n^2logn)$.

Which of the above is correct and if at some point i am incorrect please correct me.


texts: Encoding System that Assign Same Number of Bits for Each Character

texts:
I am trying to get a binary string that has been converted from text of a text file, I am able to get that but the problem is, I need each character to be represented by same number of bits, but that is not what I get (please see the below python code and corresponding output).
For example, character i is represented by 1101001, which is 7 bits long, but character  ! is represented by 100001, which is 6 bits long.

Is there any encoding/decoding system where each character takes same amount of bits?

content = open('a.txt', 'r').read()
test_str = content
# using join() + ord() + format()  ... Converting String to binary

Binary = ' '.join(format(ord(i), 'b') for i in test_str)

#Decimal=int(Binary, 2)

# printing original string
print("The original string is : " + str(test_str))
# printing result
print("The string after Binary conversion : \n" + str(Binary))

Output:

The original string is : Hi! Is there a solution?
The string after Binary conversion :
1001000 1101001 100001 100000 1001001 1110011 100000 1110100 1101000 1100101 1110010 1100101 100000 1100001 100000 1110011 1101111 1101100 1110101 1110100 1101001 1101111 1101110 111111


texts:
I have a graph related problem.
Let $G$ be an undirected weighted graph of $N$ nodes. I want to find $p$ independent (they have no edge linking them) sub-graphs of $m$ nodes in a way that the total weight is maximized.

For example, let $G$ be a graph of $16$ nodes, I want to find $4$ sub-graphs of $4$ nodes with $w_1, w_2, w_3, w_4$ as their weights (sum of the weights on the subgraph's edges) I want to determine the $4$ subgraphs that will maximize $w_1+w_2+w_3+w_4$.

Is this a classic graph problem? Is there already an algorithm for this? I am not very experienced with graphs and my research on the net was only confusing. Any ideas on how to approach this?

Thank you for your help


texts: Using the decision problem, PATH in order to solve the optimization problem, SHORTEST-PATH in polynomial time

texts:
So, if I were using a black-box decision algorithm, PATH in which I could say, "does a path of weight k exist in this graph from S to V", problably the typical way one would solve the optimization problem of shortest path is to start at k at zero and increment until PATH returns true. But since paths start at -inf shouldn't we be starting there? (Thus making this optimization problem not solvable in polynomial time)

I know this isn't right, I'm just having a hard time seeing which part I am missing here.


texts:
I am attempting to find the maximum value in a matrix (or 2d array) and want to find it in less than O(n) time. The easiest way, which results in O(n) run time, is an element wise search. If a better run time is possible, I would also like to find any values over a specific threshold in less than O(n) time. Is any of this possible?

I cannot re-sort and do a binary search or something along those lines as the ordering is important.


texts: 3Sum Why this O(nlogn) solution doesn't work?

texts:
I have been doing LeetCode and tackled the problem of the 3Sum and first I tried to do a O(nlogn) solution and after seeing the proposed solution I see that the solution is $O(n^2)$ or $O(n^2 \times \log n)$ and not only that but the problem is a highly researched topic so I don't think I found a better solution but can't see why my approach wouldn't work, can use help to figure it out.
The problem is the following
Find three numbers in an array such that $a + b + c = t$,
the LeetCode problem is slightly different in which you need to find the closest sum.
My code is the following:

Sort the array.
  Start with two pointers i=0 and j= last element of array
    Use binary search between i and j to find m such that arr[m] == target - arr[i] - arr[j], if such m doesn't exist return m such that arr[m] is the closest.
    If arr[i] + arr[m] + arr[j] == target then your finished.
    Otherwise if arr[i] + arr[m] + arr[j] < target then add 1 to i else subtract 1 form j.
Repeat 3 → 5 until j - i == 2
Return the best found i,m,j

The logic in step 5 is that if the solution found is less than the target then we should increase i such that our next guess is bigger.
Code:
def binSearch(arr, s, e, t):
    m = (s + e) // 2
    r = m
    d = 9999
    while s <= e:
        m = (s + e) // 2
        if arr[m] == t:
            return m
        elif arr[m] > t:
            e = m - 1
        else:
            s = m + 1

        if d > abs(t - arr[m]):
            d = abs(t - arr[m])
            r = m
    return r

class Solution:
    def threeSumClosest(self, nums, target: int) -> int:
        nums.sort()

        s = 0
        e = len(nums) - 1
        minn = 999999
        t = ()
        while e - s >= 2:
            left = nums[s]
            right = nums[e]
            remaining = target - (left + right)
            m = binSearch(nums, s + 1, e - 1, remaining)
            middle = nums[m]
            r = left + middle + right

            # print("i's: ", (s,m,e))
            # print("values: ", (nums[s], nums[m], nums[e]))
            # print("r", r)
            # print("**************")

            if r == target:
                return r
            elif r < target:
                s += 1
            else:
                e -= 1

            if abs(target - r) < minn:
                minn = abs(target - r)
                t = r
        return t


texts: What is the complexity of finding the two prime numbers a composite number (used in RSA Protocol) is made of?

texts:
I am aware that as the number increases in Digits the process of locating the two prime numbers that when multiplied produce the given number is increased as well.

I also know that is it somewhat exponential or even more and with current machines it is rendered impossible to do in less than a year to find it for numbers used in an RSA protocol (they are too big).

What I am asking is what is the actual complexity of such a task? I am looking for average and maximum complexity.


texts: Is there a model of ZF¬C where some program always terminates but has no loop variant?

texts:
Wikipedia has a proof that every loop that terminates has a loop variant—a well-founded relation on the state space such that each iteration of the loop results in a state that is less than the previous iteration's state under the relation. Here, well-founded refers to the usual classical definition of a well-founded relation: every nonempty subset has a minimal element.

The proof given in the linked article is as follows:

Let the loop variant be the "iteration" relation, i.e. the reflexive transitive closure of the transition relation.
Since the loop always terminates, the loop variant has no infinite descending chains.
Apply the axiom of choice to conclude that the loop variant is well-founded.

My question is about step 3. Using the full, uncountable axiom of choice here feels like swatting a fly with an atom bomb. Elsewhere on Wikipedia, we have the following:

  Equivalently, assuming the axiom of dependent choice, a relation is well-founded if it contains no countable infinite descending chains: that is, there is no infinite sequence $x_0, x_1, x_2, \dots$ of elements of $X$ such that $x_{n+1}\ R\ x_n$ for every natural number $n$.

So the much weaker axiom of dependent choice is sufficient.

It seems like it might be possible to weaken this assumption further. The state space of a computer program is not an arbitrary set from the entire Von Neumann universe of ZF. Maybe countable choice suffices, since the state space of any program is countable?

On the other hand, if dependent choice is required and countable choice will not suffice, then (assuming ZF is consistent) there must exist a model of ZF + countable choice where there is some program that (a) always terminates, (b) has an iteration relation with no infinite descending chains, yet (c) has no well-founded loop variant. This seems deeply weird.

My question is:

Is there a model of ZF where a program always terminates but has no loop variant?
If the answer to 1 is yes, then what is the weakest choice principle that, when added to ZF, changes the answer to no?
If the answer to 1 is yes, is it possible to write down an explicit example of such a program (a la Harvey Friedman's explicit formulas equivalent to the strengths of ordinals), or does such a program necessarily correspond to a non-standard natural number?


texts: Pi Calculus: Restriction necessary for molecular (atomic) action?

texts:
In "A Calculus of Mobile Processes, Part 1" [1], Milner et al. give an example for transmitting a pair of values $(u,v)$ from the process $P$ to either $R$ or $Q$ (see page 13). All three processes are assumed to run in parallel.

They present following solution:

$$
\begin{align}
P &= (w) (\bar{x}(w).P' | \bar{w}u.\bar{w}v.0) \\
Q &= x(w).w(y).w(z).Q' \\
R &= x(w).w(y).w(z).R'
\end{align}
$$

They claim that "it is vital to this idea that w (...) is indeed a private name". Why is this a necessity?

Wouldn't following solution without restriction work?

$$
\begin{align*}
P &= \bar{x}(w).P' | \bar{w}u.\bar{w}v.0 \\
Q &= x(\alpha).\alpha(y).\alpha(z).Q' \\
R &= x(\beta).\beta(y).\beta(z).R'
\end{align*}
$$

[1] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.159.363&rep=rep1&type=pdf


texts: Implementing a Boolean function with NOR gates

texts:
Implement f(a, b, c, d) = Σ m(3, 4, 5, 6, 7, 11, 15) as a 2-level gate circuit
  (a) Using OR gates and NOR gates.
  (b) Using NOR gates only.

I have found that F=ab+d using Karnaugh map.
I have also been able to construct the logic expression using OR gates and NOR gates as in part a of the question.

Can you please provide me some idea on how to construct the logic expression ab+d using NOR gates only?

Please do not say this is a homework help question and close this thread.
I'm not asking to do the entire homework, I have only asked for some idea on how to do part b.


texts: Are there complete problems for P and NP under other kinds of reductions?

texts:
I know that the complexity class $\mathsf{P}$ has complete problems w.r.t. $\mathsf{NC}$ and $\mathsf{L}$ reductions.

Are these two classes the only possible classes of reductions under which $\mathsf{P}$ has complete problems?

Also, what classes of reduction can be used for $\mathsf{NP}$ beside polynomial-time reductions?


texts: match an array with a given set of arrays

texts:
We have a set of 24 distinct arrays, each array has 36 elements and each element can have one of 13 possible values.

Then we're given an array X (this array is certainly part of our set) and we have to find to which array of our set it corresponds to.

Of course, we can check all 36 elements of X against each of 36 elements of our 24 arrays and find out with which it corresponds to.

I'm trying to reduce this number of 36 comparisons.

My naive approach is something like this:

Take all possible subsets of 0..35, except the empty subset.
Each of this subsets denotes which elements we should compare.
Use each of this subsets with input all the 24 arrays of our given set and check which of these subsets produce as output the given set of our 24 arrays, these are valid subsets.
From these valid subsets, the one with the fewer elements is our solution.

Unfortunately, all possible subsets of 0..35 excluding the empty subset is $2^{36}-1$

I was wondering if there could be another approach to the problem.

Many different arrays X will be matched against the given set of 24 arrays so any preprocessing of the 24 arrays is really worth the effort.

User JarkkoL suggested to precompute CRC32 of the set of the given arrays and then compare with the CRC32 of the array X.

Still, I'm wondering if there's a smart way not to calculate CRC32 for the whole array. I'm looking for the smallest possible number of elements for which I should compute it.


texts: Psedu-polynomial Time : Conflict with the definition of input size

texts:
From wikipedia

  In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is a polynomial in the length of the input (the number of bits required to represent it) and the numeric value of the input (the largest integer present in the input). In general, the numeric value of the input is exponential in the input length, which is why a pseudo-polynomial time algorithm does not necessarily run in polynomial time with respect to the input length.

From this SO post that was very helpful.

  An algorithm runs in pseudo-polynomial time if the runtime is some polynomial in the numeric value of the input, rather than in the number of bits required to represent it.

And this MIT OCW lecture on the knapsack DP running time and definition of pseudo-polynomial time.

They are all talking about the same thing in that a running time is pseudo-polynomial when it is a multivariate polynomial of $(x, k)$ where $x$ denotes the size of the input and $k$ is some integer(numeric value) involved. Since $k$ is often exponential in $x$, pseudo-polynomial time is not necessarily polynomial time in $x$, the number of bits needed to represent the input. Mathematically, $k = \Theta(2^{x})$, 2 is replaceable by a constant.

This works absolutely fine when we have a numeric value $k$ as the input with running time $\Theta(k)$. Then $x = \Theta(\log k)$ and we have running time $\Theta(2^{x})$. Everything is clean.

And then I start to see more complicated issues in other algorithms. For example, in the knapsack case, let $N$ denote the number of things or objects in the input. As described in the MIT video, the input is $x = \Theta(NlogS)$ and the running time is $\Theta(NS)$. The instructor describes that since $S$ is exponential in the input size $\log S$ (the number of bits needed to represent the numeric value), we can see how knapsack running time is not polynomial time. $\log S$ is only a part of $x$, so I don't see how $\Theta(N\cdot 2^{\log S})$ is exponential in $\Theta(N\log S)$. How is running time expressed in the form $O(c^{x})$ where $c$ is a constant?

Something similar happens for counting sort running time. The SO post gives running time $O(N + k)$. It gives the same logic as above to say that the running time is exponential in the input size $\log k$. But to me it seems like $x = \Theta(N\log K)$ since the input is a list of $N$ things with the maximum value $k$. I don't really see how $O(N + k)$ can be exponential in $x$ just because $k$ is exponential in the number of bits needed to represent it, since $\log k$ is definitely not $x$, only a part of it. Same thing: running time doesn't seem exponential in $x$, rather only in $\log S$.

So either I am still not getting what it means to have exponential "length of the input" is or there is some conflict with how people define length of the input. MIT video defines input size similar to how I think of $x$ while many other sources have a different opinion it seems. I see it as the total number of bits needed to represent the whole input, but some analysis just sees it as the number of bits needed to represent a numeric value that is only a part of the whole input. Is running time exponential in the input size if it is exponential in the size of a part of the input or the whole thing?? Please clarify!!


texts: number lesser than a given number composed of only binary numbers

texts:
Give a decimal number, such as 123. Need to figure out all smaller numbers lesser than 123 made up by 1 and 0 composed of decimal numbers such as 111, 110, 101, 100, 11, 10, 1, 0.

I am thinking of below recursive solution:

a. If the first number is 1 then we can append 0 or 1 to it. Vice versa is true for 0 if it is the first number.

b. In every step check the formed number if it is lesser than the given number. If it is greater than given number then abandon that path.

This way we can find all combinations. However, would this solution be optimal or there is some hidden mathematical logic to this problem?


texts: Which Graph Algorithm should I use to find all possible groups in a graph?

texts:
I have the following situation:

(Alex, Bob)

(Alex, Charlie)

(Debra, Erika)

Imagine that each row in the list represents a friendship. Alex is friends with Bob. Alex is friends with Charlie. And Debra is friends with Erika.

I would like to figure out how many independent friends groups there are. So if someone is a friend of a friend (or a friend of a friend to the nth degree), they would belog to the same group. In other words how many groups are there, that do not overlap eachother.

From the list above I would expect 2 groups:

(Alex, Bob, Charlie)

(Debra, Erika)

Which algorithm should I use to calculate these groups, from the list provided above?

Note: In the actual case the number of friendships is in the tens of millions, so I am looking for the most efficient solution.


texts: Are context free grammars the only ones that have parsing trees?

texts:
As I understand, the generation process of a string in a context free language according to its context free grammar can be represented as a tree.

For a formal language which can have a formal grammar, can the generation process of a string  also be represented as a tree?

What kind of trees can identify context-free grammars then? I.e. a formal grammar is context free, if and only if the generation of each string according to the grammar can be represented as what kind of trees?


texts: I know that device drivers are attached to device controllers, which have their own registers and some local buffer storage. I'm wondering if I can think of device drivers as little state machines -- i.e. do they read and write to memory, or not?


texts: Show that $L:=\{(a^{k}b)^{i}|i,k \epsilon \mathbb{N}_{+} \}$ is context-sensitve. (With context-sensitive/noncontracting grammar)

texts:
I am studying for an upcoming exam and this is an old exam question from two years ago (all exams were made available through our lecturer):

Show that $L:=\{(a^{k}b)^{i}|i,k \epsilon \mathbb{N}_{+} \}$ is context-sensitve.

I could easily construct a LBA for this language.
But since the notation/construction of LBAs weren't really explained, I would have to define it in the exam.

So I assume this task was expected to be done by constructing a context-sensitive grammar.

NOTE: In our lecture the definition of a context-sensitive grammar was in fact the definition of a noncontracting grammar.
So any rule like this x -> y is allowed if |x| <= |y|

So this is allowed:

aAb -> bXaa

My best idea goes like this:

S  -> AB
B  -> bB | b
A  -> CA | C
Cb -> abC
Ca -> aC

so to generate aaabaaabaaab I do this:

S
AB
AbB
AbbB
Abbb
CAbbb
CCAbbb
CCCbbb
(let all C-Variables run through the word and leave an 'a' before every 'b')
CCabCbb
CCababCb
CCabababC
...
aaabaaabaaabCCC

But I can't make all the 'C'-Variables disappear.


texts:
There are some arbitrary-chosen points in 1D space. What needs to be found is the approximate number of them without counting all of them. It is possible to choose some coordinates (numbers) and for each one there are two numbers returned - the distances to the closest points to the left and to the right.

I'm looking for some sources on how to solve such problem efficiently so any papers, generalizations or similar problems are needed.


texts: Complexity Analysis of Nested Loops with Sigma Notation

texts:
There are two nested for loops. I'm not sure but I think that it's geometric series, but I cannot get well solution for it. It seems n + n/2 + n/4 + .. + n/n^2, but how? What I tried is below up to now,

$$ \sum _{i=0}^{log\left(n-1\right)}\:\sum _{j=0}^{i-1}\:1 $$
$$ \sum _{i=0}^n\:\sum _{j=0}^n\:\left(\frac{1}{2}\right)^j $$

At first, I thought it's $O(nlogn)$ but instead as far as I research the right result is  $O(n)$.

int try(int n) {
    int sum = 0;
    for (int i = n; i > 0; i /= 2) {
        for (int j = 0; j < i; j++) {
          sum += 1;
          }
    }
    return sum;
}

Could you show its sigma notation with its complexity? I want to comprehend it with steps.


texts: Proving (relativized) upper bounds against SZK

texts:
Does anyone know of any instances where we've been able to show that some complexity class is strictly harder than SZK relative to some oracle?

In general, it seems that SZK is really hard (for example, this paper https://arxiv.org/pdf/1609.02888.pdf shows that SZK is harder than PP relative to some oracle) and so I've been wondering if any results have been obtained in the opposite direction.


texts: How is knowledge of lambda calculus applicable in Computer Science and Machine Learning?

texts: If I want to do research in computer science and machine learning, is it important to have a well-rounded understanding of lambda calculus?


texts: Bitwidth requirements for the division algorithm using redundant radix

texts:
I'm studying the chapter "Division by Digit Recurrence" in "Digital Arithmetic" of Ercegovac. I like this book is overall well written. Although sometimes I struggle understanding some aspect like the one I'm about to expose.

First of all let me give some introduction to the method, almost everything is taken from the book I mentioned, so please refer there mainly if you're interested. Let $r > 2$ be the considered radix.

Let's consider two fractional number $x,y$ such that

$$
\begin{array}{l}
x = 0.x_{-1} \ldots x_{-2k} \\
y = 0.y_{-1} \ldots y_{-k} \\
\frac{1}{2} \leq y < 1 \\
x < y,
\end{array}
$$

the goal is to find two numbers $q$ and $s$ such that

$$
\begin{array}{l}
q = 0.q_{-1}\ldots q_{-k} \\
s = 0.s_{-1} \ldots s_{-k} \\
r^{-k} s < y \\
x = qy + r^{-k}s
\end{array} .
$$

To derive the recurrence let's define

$$
q[j] = \left\{
\begin{array}{ll}
0 & j = 0 \\
0.q_{-1} \ldots q_{-j} & 1 \leq j \leq k
\end{array}
\right.,
$$

and

$$
s[j] = r^k (x-yq[j]) \;,\; 0 \leq j \leq k,
$$

observe that $s[0] = r^{k}x$.
Observing that $q[j+1] - q[j] = q_{-j-1}r^{-j-1}$ we can write the following recursion for $s[j]$:

$$
\left\{
\begin{array}{ll}
s[j+1] = s[j] - q_{-j-1}r^{k-j-1}y & 0 \leq j \leq k - 1 \\
s[0] = r^kx
\end{array}
\right.
$$

Multiplying both sides of the recursion by $r^{j+1-k}$, and defining $w[j] = r^{j-k}s[j]$ we end up with the following

$$
\left\{
\begin{array}{ll}
w[j+1] = rw[j] - q_{-j-1}y & 0 \leq j \leq k - 1 \\
w[0] = x
\end{array}
\right.
$$

which is the actual recursion implemented in hardware/software when the division is performed. Now let's move on... let $a$ be an integer such that

$$
\left\lceil \frac{r}{2} \right\rceil \leq a \leq r - 1
$$

we define the redundancy factor $\rho$ as

$$
\rho = \frac{a}{r-1}
$$

easy to show that

$$
\frac{1}{2} < \rho \leq 1.
$$

We finally define the set $D_a = \left\{-a,-a+1,\ldots,-1,0,1,\ldots a-1,a \right\}$.

It can be proven that if

$$
| w[j] | < \rho y
$$

then the division algorithm will converge with $1$ ulp error. Please keep in mind such bound because it is where my problem arise, also observe that $\rho$ is actually a real number (specifically is rational, but I don't think it matters for this discussion, we can therefore assume it is real in general).

What I'm trying to work out is how many digits do I actually need to represent these shifted partial reminders $w[j]$, I'm struggling because of that $\rho$ factor in the bound.

Is there any hint you could give me in order to find out the bitwidth?

Thank you

More details:

Extrapolated from the book

By looking at first point specifically, if $\rho = 1$ then $w[0]$ has to be initialized to $x/2$ therefore to represent $w[0]$ I would need $2k+1$ bits, otherwise $w[0] = x/4$, therefore $2k+2$ bits. Given at each I have to compute $rw[j]$ this means I need $n_1 = \left\lceil \log_2(r) \right\rceil + 2k + 1$ when $rho=1$ otherwise $n_2 = \left\lceil \log_2(r) \right\rceil + 2k + 2$, is this correct (It's not a formal proof... just a guess).


texts: Need help understanding which values can be inserted into a specific node in a binary tree

texts:
I am studying binary trees and I am failing to see what numbers can be inserted into this specific node position. The values to pick from are : 16, 24, 36, 45, 49, 51, 58.

I have tried values 24, 36, 45, and 16, 24, 36. I have tried these values because going from left to right, they go in increasing order. Though this is not working and I'm not quite sure why. I'm not sure why what I am selecting is wrong. Any help trying to solve my confusion is appreciated.


texts:
In several papers I have read that Bit-parallel pattern matching is an NFA-simulation.

My questions are:

1- Is it true in general? Or, is there any restrictions?

2- As any regular expression can be converted to NFA, how Bit-parallelism is able to handle some regex like: a?5

Update: Bit-parallel pattern matching is a family of well-known pattern matching algorithms in the literature of hardware-based pattern matching. It was introduced by Baeza-Yates and Gonnet (A New Approach to Text Searching, Communications of the ACM, 35(10):74–82, 1992; PDF) and has gained more attention recently, for example in Faro and Lecroq, Twenty Years of Bit-Parallelism in String Matching (Festschrift for Bořivoj Melichar, pp. 72–101; PDF).

In these papers there are several statements like:
"Bit-parallelism is indeed particularly suitable for the eefficient simulation
of non-deterministic automata.", second reference, page 2.


texts: Generate Hamiltonian path with obstacles

texts:
I want to make some Hamiltonian paths with obstacles in a grid that are hard to find
It's for a game that I want to create, which consists of passing from all the cases of the grid without passing from the same one twice, and there is a start and an ending case, and the map "Grid" may have some obstacles.

The cases would be the vertices,
The player may move UP/DOWN/LEFT/RIGHT "Existing Edges"
Obstacles "Absent vertex and edge leading to this case"

My problem is, how can I generate the levels from easy paths to the hardest

PS : I've been searching the net about my problem and I didn't seem to find any solution


texts: Sub-matrix with minimum size of $k$ and minimum sum

texts:
We have an $n \times m$ matrix whose entries are non-negative integers and we want to find a sub-matrix whose area (number of entries) is at least $k$ such that the sum of the entries in minimal. The answer to this problem is the sum of these entries.
My solution:
Using dynamic programming, I have defined the sum of entries from the (0,0) entry to (i,j) as $sum[i][j]$. If the $(i,j)$ entry is $entry[i][j]$ then we have $sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + entry[i][j]$. Except, when either dimension of $sum$ is 0, the values are only the entries.
I do not know how to continue from here.
If you have a better idea for this problem, that would be appreciated too!


texts:
I came across the following question. Given a 2-approximation for minimum bin packing problem, find a 2d-approximation for d-dimensional bin backing.

To clarify, inputs to the bin packing problem are real numbers $x_1,...,x_n\in [0,1]$, which should be divided into $k$ bins $S_1,...,S_k$ such that for all $i$: $\sum\limits_{x\in S_i}x\le 1$.

Inputs to the vector bin packing problem are vectors $x_1,...,x_n\in [0,1]^d$, which should be divided into $k$ bins $S_1,...,S_k$ such that for all $1\le i \le k$ and $1\le j\le d$: $\sum\limits_{x\in S_i} x^j\le 1$, where $x^j$ is the $j'th$ coordinate of $x$.

It seems intuitive to use the 2-approximation on each coordinate of the given vectors $x_1,...,x_n\in [0,1]^d$ and obtain $d$ partitions into at most $2k$ bins (where $k$ is the minimal number of bins for the vectors partition). However, i cant seem to combine those bins into a partition of size at most $2d\cdot k$. For any vector $x_i\in [0,1]^d$, let $b_i\in \left\{1,...,2k\right\}^d$ be the vector whose $j'th$ entry is the bin in which $x_i^j$ was placed (after running the approximation on all the $j'th$ components). Since i cant allow two vectors $x_i,x_j$, whose corresponding vectors $b_i,b_j$ differ in at least one component, go into the same bin, it seems i need at least $(2k)^d$ bins. What am i missing?


texts: In a bloom filter, why does the optimal number of hashes *increase* with the number of bits in the filter?

texts:
Multiple resources, such as Wikipedia, state that if you have an $m$-bit Bloom filter with $n$ elements inserted, then the optimal number $k$ of hash functions to use is

$k = \frac{m}{n} \ln 2$

This is very counterintuitive. If $m$ is the number of bits in the filter, then as you increase $m$, why would the optimal number of hashes have to increase to reduce the rate of false positives?

Intuitively, as you increase $m$, the number of collisions goes down. So, as $m \to \infty$, using only one hash function would yield a 0% false positive rate. But this equation would say that as $m \to \infty$, you would need $k \to \infty$ as well. Why?

Is there some way to understand this?


texts: For Djikstra's algorithm, why are we surely done if we update all edges $|V|-1$ times?

texts:
Apparently, if we use Djikstra's algorithm to find the shortest path between the root node and all other nodes in a weighted graph with no negative cycles, we are done after updating the distance of each node $|V| - 1$ times.

This puzzles me because I think that a single round of breadth first search is enough. Why must we do $|V| - 1$ of these searches?


texts: What is the best way to index lookups on a 2D array of integers that is boundless in x and y?

texts:
Lets say you have a data model that consists of a 2D grid of integer points. This grid is sparsely populated and boundless in x and y (up to the max of a 32-bit integer).

What is the best way to index these points in order to have an optimised lookup on an arbitrary (x,y) coordinate? Is an O(1) lookup solution possible?


texts: Reduce the following decision problem to CNF-SAT

texts:
Input:

$X$ = {$x_1$,$x_2$,$x_3$,...,$x_n$}
$Y$ = {$y_1$,$y_2$,$y_3$,...,$y_m$}
$k$, where, $k$ $\leq$ $m$

Output (Yes/No):
Satisfying the following condition, can all the elements in set $X$ be assigned to elements in set $Y$, such that, no elements in $X$ is left unassigned?

Condition: At least $k$ elements in $Y$ is needed to access all the elements in $X$. All the elements assigned to $y_i \in Y$ are said to be accessible using $y_i$.

Reduce this decision problem to CNF-SAT.

Thoughts:

I have considered $n \times m$ no. of variables. Each variables for a pair of element of set $X$ and set $Y$. i.e., $a_{ij}$ : for all $x_i$ and $y_j$.

For ensuring that no elements in $X$ is left unassigned the CNF expression will be.
$(a_{11} \vee a_{12} \vee ... \vee a_{1m}) \wedge (a_{21} \vee a_{22} \vee ... \vee a_{2m})... (a_{n1} \vee a_{n2} \vee ... \vee a_{nm})$

I am not able to form the CNF expression for ensuring that at least $k$ elements from $Y$ are required to access all the elements in $X$. It seems that there will be an exponential number of clauses in the expression.

Thanks for helping.


texts: What is the meaning of this pseudo-code function?

texts:
While reading the paper Holistic twig joins: optimal XML pattern matching I came across the pseudo code for liststack algorithm. (available through google scholar)

A function in the algorithm confused me, since I can understand what it is supposed to do, but can't deconstruct the notation:

$\qquad \mathtt{Function}\ \mathtt{end}(q\mathtt) \\
 \qquad\qquad \mathtt{return}\ \forall q_i \in \mathtt{subtreeNodes}(q) : \mathtt{isLeaf}(q_i) \implies \mathtt{eof}(T_{q_i})$

This function is supposed to return a single boolean result. It is supposed to be true when all lists associated to leaf nodes of a query pattern node are at their end. So true means there are no more nodes in the query pattern to process.

But what is the meaning of the set builder(ish?) notation here? Is it

$\qquad$ "for all subtree nodes of $q$ for which $\mathtt{isLeaf}(q_i)$ is true $\mathtt{eof}(T_{q_i})$ is also true"

(which means that the list is at the end position)?

Or is it

$\qquad$ "for all subtree nodes of $q$, $\mathtt{isLeaf}(q_i)$ implies $\mathtt{eof}(T_{q_i})$ is true"?

Is double arrow representing implies with its truth table?

As you can see, I'm having a bit difficulty in associating the colon and its precedence.


texts: NEAT algorithm and dynamic topology neural networks

texts: I have recently been investigating dynamic topology neural networks and there is only one problem I have with understanding them. Because a neuron could be inserted at any point, the neurons are no longer organised into layers, so how is it possible to ensure that all of the inputs for Neuron A at position X have been computed, prior to the computation of Neuron A's output, especially when each neurons output is calculated linearly? I am by no means experienced in the topic, just curious so any information would be helpful, Thank you.


texts: Prove a^4n b^m is irregular using puming lemma

texts:
My assignment is to prove that the language

$L = \{ a^{4n} b^m \mid n > m >= 0\}$ is not a regular language.

My first attempt was to prove that if if you set $a^l$ and $b^{l-1}$ you'd have an equal #a and #b if you "pump down" your $v$ so that it is $v^0$, so that the condition $n > m$ is no longer fulfilled. Then I realized I completely disregarded that it's $4n$ and not just $n$, so I wasted a lot of time on that.

Now I'm absolutely out of ideas, because as I see it you can always find an number $p$, so that you can pump a number of as however often you want as long as p is divisible by 4 because if you divide your word $z = uvw$, both $u$ and $v$ need to have a number of as divisible by 4 as to not break the $4n$ condition.

However, that would mean that you absolutely can not prove that $L$ is not regular using the pumping Lemma, which contradicts the assignment. Where is the flaw in my logic?

I would really appreciate some pointers.


texts: Assembly writer vs compiler in VLIW architecture

texts:
I read this sentence in a book:

  In VLIW architecture, the compiler/and or assembly writer chooses instructions that can be executed in parallel.

What is the difference between assembly writer and compiler? Would an assembly writer also mean the same as assembler?


texts: Why Aren't Programs Written In Any Language Just As Fast?

texts:
From my basic understanding of computer architecture, a computer understands instructions and a computer program written in a high level language is converted to a set of such instructions for the computer to understand.

Also, that given a set of rules are satisfied, any programming language can do what any other can do.

So why is it that a C program is faster than say a program in another language? Why is it not that regardless of the syntax, and features of the language, when converted to a set of instructions in binary, each programming language tries to get a similar result. Thus making each of them more or less as fast as the others, at the expense of say compilation time?

Obviously I'm missing something important here, so what is it?


texts: What makes lambda calculus relevant to study?

texts:
I'm starting an undergraduate computer science course next fall, but I can't really understand λ-calculus in the context of functional programming. I may be misinterpreting this completely, but based on this definition from the Stanford Encyclopedia of Philosophy, it's just another notation for functions.

If it is just that, why is it advantageous to use λ-calculus over regular function notations to calculate algorithm run time?


texts: Where I can find example how prove red black tree?

texts:
I need prove that any red-black tree with at least two elements obtained through the insertion algorithm has at least one red node.
For this, I need use Induction.

I don't understand how apply induction. (((


texts:
Today I had a weird dream about a kind of automata. Each automaton has a finite 2D grid wrapped around like a torus, formatted as a table. Execution starts in one cell. Each step it executes whatever is in the current cell, and in each cell there's a symbol and a numeric operator. In one variant the numeric part is said to be optional. The symbol can be "n" or "a", or some other letters that I don't remember. They are not arbitrary but have meanings.

If the symbol is "n", the numeric operator will rotate the current row or column by a number of cells like in a Rubik's cube(without changing the "execution pointer"). It's written like this: +1 for rotating a row to the right, -1 to the left (presumably other numbers are allowed too but I didn't see examples in my dream), $+\frac{1}{-}$ for rotating a column upwards, $-\frac{1}{-}$ for rotating downwards. There's no separate state apart from what's on the grid. I'm not sure what "a" means, but it may have meant rotating the whole grid in the given direction while keeping the execution cell position fixed. I saw an example in my dream with just one cell with "n" in it, described the the smallest automaton that doesn't do anything.

I didn't see any examples of explicit machine input or output. Maybe the input is encoded in the grid, or maybe it's designed to be interactive and the animation created by the moving cells is the intended output. I'm not sure if there's any way to halt/accept/reject in it.

Does this kind of automata happen to have a name? Is there any related research?


texts: What impact does the modulo operator have in a for-loop?

texts:
Here's an example of what I mean:

def complexity(n):
    count = 0
    for x in range(1, n+1):
        for y in range(1, (n*n)+1):
            if y % n == 0:
                for z in range(1, n+1):
                    count += 1
    return count

The first for loop is of course θ(n), the second one θ(n^2).
But what impact does the modulo operator have? And what would then be the complexity of the whole thing?


texts: Given computable function, what are conditions for computability of inverse function?

texts:
If $f:\mathbb{N}\rightarrow\mathbb{N}$ is computable and has an inverse, under what conditions is $f^{-1}$ also computable? I couldn't find that in a textbook, and googling gets some vague suggestions about bijective, but I couldn't find a clearly stated theorem to that effect. Offhand, bijective seems sufficient but not necessary, e.g., $f(n)=2n$ isn't surjective but is computably invertible (for a total function inverse, use lifted domain $\mathbb{N}_\perp$ and map odd numbers back to $\perp$). In addition to an answer, a reference to a theorem/proof would be great, or just the name of a relevant theorem so I can successfully google it.

This question came to mind regarding the following thought (which I also wasn't able to find in a textbook or google anything about). The distinction between $f$ computable and $f^{-1}$ not, versus both computable, seems kind of analogous to an r.e. versus recursive distinction. Can that be expressed rigorously?

For example, consider $f:E\rightarrow E$, with $f\in D=[E\rightarrow E]$ the (Scott- or Lawson-continuous) function space domain of some domain $E$. Let $K_D$ be $D$'s compact elements, $\downarrow f=\lbrace g\in K_D\mid g\sqsubseteq f\rbrace$, whereby $f=\sqcup\downarrow f$, all in the usual way. Then $f$ is computable if an enumeration of $\downarrow f$ is r.e. Similarly, $f^{-1}$ is computable if an enumeration of $\downarrow f^{-1}$ is r.e. So if both are computable, meaning both enumerations r.e., then that seems (to me at least) kind of analogous to recursive.

Of course, it's not quite the same thing as recursive, since if $\mathbb{N}_f\subseteq\mathbb{N}$ is an enumeration of $\downarrow f$, and similarly for $\mathbb{N}_{f^{-1}}$, then $\mathbb{N}_{f^{-1}}\neq\mathbb{N}\setminus\mathbb{N}_f$ (at least I don't suppose so). But there seems to be some kind of analogous idea trying to express itself. So how could you formulate that kind of thing rigorously? Among the first steps, I'd think you'd want to express $\mathbb{N}_{f^{-1}}$ in terms of $\mathbb{N}_f$, but I'm not seeing how to go about setting that up (any suggestion how to do that?).

So, is this idea also well-known and discussed? A textbook or google reference (or google-able search term) would be great. Thanks.


texts: What is the time complexity of computing $AA^T$? The context is building a co-citation weighted adjacency matrix.


texts: Understanding a proof in the sweep line algorithm when finding all line segment intersections

texts:
You have a set of line segments and you want to find all intersections.

First  sweep line approach:

Use a priority queue Q for the events as they come, where each event is just an end point of a line segment.

Use an unordered list L for the status of the sweep line, that is, all the segments that are currently intersecting the sweep line.

If you reach a beginning of a new segment, add it to the status and test it for intersections against all other segment in the status.

If you reach an end of a segment, remove it from the status.

This algorithm is O(n^2) if for example all segments are intersecting the x coordinate and assuming that you are sweeping from top to bottom.

Second sweep line approach:

It can be proved that we only have to test for intersections horizontally adjacent segments that are currently in the status of the sweep line. If you understand this proof then you can just use an ordered set for the status and come up with an easy O(nlogn) algorithm.

Here's part of the proof that I don't understand:

I don't think this is a clean proof of the lemma. Events are only either end points or intersections. So in practice the sweep line will never have no event points on it and from the image it seems like the sweep line is moving continuously, which is wrong because the sweep line moves from either an end point to another end point or end point to an intersection or an intersection to another end point.

How would you prove this lemma correctly?


texts: Proving that $T(n) = T(\lfloor n/2 \rfloor) + T(\lfloor n/4 \rfloor) + T(\lfloor n/8 \rfloor) + n$ is $\in O(n)$

texts:
Show $T(n) = T(\lfloor n/2 \rfloor) + T(\lfloor n/4 \rfloor) + T(\lfloor
n/8 \rfloor) + n$ is $\in O(n)$.

I will make the bound to be $\in O(cn)$ instead.

Proof by strong induction.

Base case n =1

$T(1) = c$ and $cn=c*1=c$ $\checkmark$

Inductive Hypothesis : $T(k) \in O(ck)$ for $1\le k<n, n>1$.
Inductive Step: Prove for n.  So prove that $T(n) \le O(ck)$.

Right away we can write
$T(n) = T(\lfloor n/2 \rfloor) + T(\lfloor n/4 \rfloor) + T(\lfloor n/8 \rfloor) + n \\
\leq T(n/2)+T(n/4)+T(n/8) + n\\ = c(n/2)+c(n/4)+c(n/8)+n \ \ \  \ By \ Inductive \ Hypothesis$

$$= c(7n/8)+n \le cn+n ... $$ I am stuck here

*Goal: $\le cn - (some \ stuff)$ and some stuff needs to be $\ge 0$.


texts: Why does induction with big-O lead to paradoxes?

texts:
For example, say I want to analyze $T(n)=3T(\lfloor n/3 \rfloor )+2n$ for $n>2$, and $T(n)=1$ otherwise. This is clearly $O(n\log n)$; however it seems that with induction you can prove it is $O(n)$:

Base case: $T(1)$ is $O(1)$, $T(2)$ is $O(2)$

Inductive step: $T(n) = 3\times O(n/3) + 2n \in O(n)$

Where does this go wrong? Why can I do this? Induction clearly is a valid technique, but what subtlety of $O$ causes me to be able to prove a wrong bound?


texts: W[1]-hardness of Steiner tree w.r.t. number of non-terminal vertices

texts:
This is an exercice is Rolf Niedermeier's book "Invitation to fixed-parameter algorithms", Chapter 13.

Show that the following problem is W[1]-hard:
Steiner Tree in Graphs with respect to the parameter "number of non-terminal vertices".

The way I understand it, if there are most $k$ non-terminal vertices, then this doesn't help in solving the Steiner problem in time $f(k)n^c$.

The objective is to find the minimum number of edges connecting terminal vertices (while some vertices are non-terminal).
I can't find a reduction however.  I am convinced that the parameter $k$ being number of included non-terminal vertices in a solution makes it W[2]-hard. But if $k$ is the number of existing non-terminal vertices, I don't know.  Proof ideas or references will be appreciated.


texts:
Is there a faster algorithm to merge two sorted linked lists where one is guaranteed to be much larger than the other?

By merging two sorted lists I mean taking two sorted lists $A$ and $B$ and producing a new list that contains all the elements of $A$ and $B$ and is sorted itself.

The typical solution, which Wikipedia lists and I have written in Haskell below, is $O(n+m)$

merge :: (Ord a) => [a] -> [a] -> [a]
merge [] [] =[]
merge a@(_:_) [] = a
merge [] b@(_:_) = b
merge (a : ax) (b : bx)
 | a <  b = a : merge ax (b : bx)
 | a >= b = b : merge (a : ax) bx

However simply inserting each element of the shorter list into the longer one using binary search is $O(n\log m)$1, which when $n \ll m$ is considerably better than $O(n + m)$.  This doesn't even use the fact that the smaller list is already sorted which may be leveragable for better speeds.

Are there a faster algorithms to merge two sorted lists where one is much larger than the other?

It has now been pointed out that I was incorrect about this, it cannot be done that fast because we to walk through the list for binary search.


texts: Is this a known problem in graph theory?

texts:
My basic problem includes a graph where each node $i$ is associated with a weight $c_i$, and the problem is to find a minimum (or maximum) weighted independent set with a fixed cardinality $p$. This is I believe a well-known problem in graph theory that is well-studied for different types of graphs.
Now, suppose I am dealing with a generalized form of the problem as following. The weight of each node can take $p$ different values, that is each node is associated with $p$ different weights. The aim is again to find a minimum (or maximum) weighted independent set with a fixed cardinality $p$, however, each type of weight can be selected only once. Precisely, if the weight type $j$ is selected for the node $i$, i.e., we select the weight $c_{ij}$, then the other selected nodes cannot take a weight of type $j$.
My question is that, is this still a graph theory problem? Is it a known generalization in the graph theory problems?
Any help and/or reference is appreciated.


texts: What's the input to the decoder in a sequence to sequence autoencoder?

texts:
What's the input to the decoder part of a sequence to sequence autoencoder? I've seen certain examples of such an autoencoder (using LSTM's more often than not) but am still unclear.

For example, here in this often-cited paper by Dai & Le ('Semi
Supervised Sequence Learning'), we have the following diagram:

What's the input to the decoder portion of the autoencoder here? In this example it's 'W-X-Y-Z.' But in general, is
it the same as the input to the encoder? Or is it using the output
from the previous timestep/LSTM cell as input?
Similarly, in another popular paper by Srivastava et. al
('Unsupervised Learning of Video Representations using LSTMs'), they
have the following diagram:

It seems they're using the reversed input from the encoder as input
here. However, there's a section as follows:

  The decoder can be of two kinds – conditional or unconditioned. A conditional decoder receives the last generated output frame as
  input, i.e., the dotted input in Fig. 2 is present. An unconditioned
  decoder does not receive that input.

In the unconditioned decoder, what input does the decoder receive?


texts: What does increasing the input size by a factor of 100 do to a linearthimic algorithm with the complexity of 2nlog(n)

texts:
So far what I've tried to do is break this into parts and work from there
So for the $2n$, increasing by a factor of 100 means the runtime goes up by 100 times
But I get stuck with the log(n) part. Initially, I had thought this gets reduced down to $2n$ as $log(100) = 2$ but that didn't seem to work.


texts: How do I test if a polygon is monotone with respect to a line?

texts:
It's well known that monotone polygons play a crucial role in polygon triangulation.

  Definition: A polygon $P$ in the plane is called monotone with respect to a straight line $L$, if every line orthogonal to $L$ intersects $P$ at most twice.

Given a line $L$ and a polygon $P$, is there an efficient algorithm to determine if a polygon $P$ is monotone with respect to $L$?


texts: Common models for inferring semantics (truth/factuality of statements)?

texts:
What are common models for creating rules for inferring meanings (e.g. truth values) of natural language statements such as if one wanted to infer the truth value of the input statement

  John Lennon is in Beatles.

which would depend on, whether the model "knew" John Lennon is in Beatles.


texts: Decidability of Turing Machine accepting exactly 14 words

texts:
Would you say that the following problem is undecidable?
$$L_1 = \{\langle T \rangle \mid T \text { accepts 14 words}\}$$
My intuition says that this must be undecidable, and I want to try to reduce it from the emptiness problem for Turing Machines. If we can tell whether or not a TM accepts 14 words, then we should be able to tell if it accepts 0. Since we know EMPT is undecidable, I have been trying to do reduce EMPT to this problem, but I am not sure exactly how to do it.

Can anyone confirm if this is actually a valid starting point, and if it is, any hints on how to formulate a formal reduction?


texts: Find the median of a list of sorted arrays

texts:
Input:
A set of $\ell$ arrays $A_i$ (of numbers).

The elements within each array are in sorted order, but the set of arrays is not necessarily sorted. The arrays are not necessarily the same size. The total number of elements is $n$.

Output:
The $k$th smallest element out of all elements in the input.

What's the most efficient algorithm for this problem?

Is it possible, for example to achieve a running time of $O(\ell + \log n)$?


texts: I am studying approximation Set Covering problem, from "Introduction to Algorithms by Thomas H. Cormen" book. What I cannot understand is why they use harmonic numbers to the proof? What harmonic numbers have to do with this?? I am totally confused..


texts: Winning strategy using Dynamic Programing

texts:
Let $G=(V,E)$ be a DAG and let $v_0\in V$.
Alice and Bob are playing a game in which every player has his own turn and Bob is starting. In every turn $i$, the player is picking an edge $e=(v_i,x)$, then $x$ become $v_{i+1}$ and then it becomes the other player's turn. The player which doesn't have an edge to choose (the vertex $v_i$ has no out edges) is losing.

Propose an algorithm which determines if Bob has a winning strategy.


texts:
I was asked the next question in my homework assignment:
I just want to make sure that I fully understand what it is that's required of me.
Am I asked to find an algorithm which decides if the language that's accepted by the PDA is finite? And if not, then what is it? Any initial intuition?

**I don't need help with answering it, just understanding the question.
I'm asked to show an algorithm that given a PDA $A$ decides whether there exists a word $w$ that's accepted by the PDA for which there exists a decomposition
$w=uvxyz$ that satisfies that the length of $vy$ is atleast 1 and $u(v^i)x(y^i)z$ is accepted by the PDA for every $i\ge0$.


texts: Light approximation for shortest path tree

texts:
I am looking for the paper : "B. Awerbuch, A. Baratz, and D. Peleg, Eﬃcient broadcast and light-weight spanners, Manuscript, (1991)."
It claims that we can build $(\alpha ,1+\frac{4}{\alpha -1})-LAST$ where LAST hold for "Light Approximation Shortest path Tree"
if not available could any one explain the algorithms used there ?


texts: Are there some real-world optimization problems with very cheap objective functions?

texts:
Many real world optimization tasks (especially black box optimization) have objective functions, which are quite expensive to evaluate. For example to find the optimal shape of an airplane wing, a computer model of the wing needs to be constructed and then a large physical simulation needs to be executed, usually taking many hours.

Are there some real-world optimization tasks that have optimization functions which are extremely cheap (on the order of milliseconds) to evaluate? The only thing that comes to my mind are some classical functions, such as the travelling salesman problem with up to a few hundred nodes. The evaluation of a solution consists just of adding a few hundred numbers, which is easily accomplished on the desired time scale. Unfortunately, I am not convinced that the TSP is a real-world problem, since it is so simple.


texts: Why theta(n^2) if m=floor(n/2) for Naive String-matching

texts: I’m reading CLRS(Introduction to Algorithm, 3rd edition). In the chapter 32.1 about the naive string-matching algorithm, the book says the worst case running time is $\Theta(n^2)$ if $m = \lfloor \frac n2\rfloor$. I get that when $m$ equals $\frac n2$, but I don’t see it when $m$ is less than $\frac n2$. Any hint or suggestion is very appreciated!  m is the length of the pattern string, n is the length of the text to be searched for the pattern. The book uses (n-m+1)m to calculate the running time.


texts: Can a regular expression based "grammatic" be programatically minimized?

texts:
I have a list of pairs like (regex, substitute) that take quite long to apply to some input text so I was thinking about optimizing them a bit.

From my knowledge for each regular expression there is a deterministic finite automaton that accepts the same language, and as its possible to merge DFAs merging two regex should be possible...

My question is now how does this interact with the fact that I want to replace something and not just match it.

Basically: given two pairs of a regex and its replacement in a specific order:

1. /\./    -> "Found #DOT#"
2. /#DOT#/ -> "something"

Is it programmatically possible to create a new pair:

   /\./    -> "Found something"

that applied to some input creates the same result?

Note: are e.g. Python regex even regular in the sense of theoretical informatic? (I mean would I get problems with e.g. look-arounds?)

My reason for asking: there are some regex-chains in my collection that just replace things with other things so that other regex can replace these things but that's only to keep it simple enough for a human to understand, a computer doesn't need to comprehend the regex.


texts: neural net architecture fails to approximate hybrid functions

texts:
I adopted a feedforward net to approximate the following hybrid function:
$$
output=
\begin{cases}
f(x,y) & \text{if}~~~ z=1\\
g(x,y) & \text{if}~~~ z=2
\end{cases}
$$
where $x \in R,y \in R,z \in \{1,2\}$ are inputs. With a simple example where $f(x,y)=c$ and
$$
g(x,y)=
\begin{cases}
c' & \text{if}~~~ x<x_0,y<y_0\\
c & \text{otherwise}
\end{cases}
$$
I fed a set of data points generated from this example to the feedforward net. However, the feedforward net failed to approximate output correctly. Any insight why?

The feedforward net has one hidden layer of 50 neurons. The process is done in MATLAB and I used built-in MATLAB tools to update the weights of the neural net.

I also noticed if I use separate neural nets for each $z$ then each neural net is able to approximate $f$ and $g$.


texts: Counting an integer's divisors without just enumerating them (or estimating if not possible)?

texts:
I'm trying to count the number of divisors an integer $n$ has.  The simple way to do this is to just enumerate all integers from 1 to $\sqrt{n}$, and count how many integers evenly divide $n$.

For example, 28 has six divisors (1, 2, 4, 7, 14, 28). 15 has four (1, 3, 5, 15). I want to, say, figure out how many divisors 242134575355654335549798955848371716626563756785 has.

I'm not trying to factor the integer; I don't care about what two numbers or what three numbers and so on I can multiply to get $n$.

How can I count (or estimate, if need be) the number of divisors an integer has other than by enumerating them?  I don't need the actual values for each divisor; I just want to count them faster than by just enumerating them.  If that's not possible, I'd be OK with estimating the number of divisors (and, even better, using that estimate to help me find the actual number of divisors).


texts: Problem to understand a Bellman Ford algorithm exercise

texts:
I am trying to understand the following exercise from Introduction to algorithm (3rd edtion).

Exercise 24.1-3 (page 654)
Given a weighted, directed graph $G=(V, E)$ with no negative-weight cycles, let $m$ be the maximum over all vertices $v \in V$ of the minimum number of edges in a shortest path from source $s$ to $v$. (Here, the shortest path is by weight, not the number of
edges.) Suggest a simple change to the Bellman-Ford algorithm that
allows it to terminate in $m + 1$ passes, even if $m$ is not known in
advances.

So what is $m$ exactly? I am really have the trouble to understand the first sentence.


texts: largest samples of set of random variables

texts:
Suppose we have two discrete random variables and we want perform maximum operation to obtain the max PDF.

We know that max of two independent random variables is: if $Z = max(X,Y)$

$pr(Z = k) = pr(X = k) pr(Y < k) + pr(X < k) pr(Y = k) + pr(X = k) pr(Y=k)$

Where in the above figure pr(Z=3) for instance is pr(X=3)*pr(Y=3)+ pr(X<3)pr(Y=3)+ pr(X=3)pr(Y<3) so (1)(1) + (1+1)(1) + (1)(1+1+1) =7.

My question how this operation has O(nm) timing complexity where n and m are the sample size of X and Y receptively or O(n^2) when both has n samples?

According to my calculations there is only 2 multiplications and n sums involve to generate each sample, so it should be o(n), right?


texts: Looking for an algorithm to find a shortest path in a special graph

texts:
I have the following problem: given a directed unweighted graph and a set of source vertices, it's needed to find the shortest path to the specified vertex. The mentioned graph has two special extensions:

A graph's edge can be active or inactive depending on edges placed in the path before. In other words, the edge $E$ can be placed in the path at position $i$ only when $ f( E, path[1..i-1] )$ is true. The $f$ function in not specified explicitly; each path has a corresponding set of named properties and each graph edge has a function which modifies property values if the edge is involved (placed in the path). The edge $T$ is active (i.e. can be inserted in the path) if $g(T, set\ of\ properties)$ is true. A property may have a boolean or enum value, but it is desirable for me to allow properties to have integer and string values too.
Two adjacent edges in a path are not required to be linked. I.e. $path[j].end$ is not necessary equal to $path[j+1].start$. For example, we want to add the edge $B$ to the path and it has a property requirement which can only be satisfied if the edge $A$ is placed in the path before the $B$. In this case a $path[j]$ edge equals to the $A$ and $path[j+1]$ edge corresponds to the $B$. Still, $path[j+1].start$ should be equal to at least one of $path[1..j+1].end$ vertices.

The graph examples I've seen are sparse and pretty small (several dozen vertices). However some paths may contain up to several thousands of edges to satisfy the complex transition rules.

My current solution to this problem is based on the BFS algorithm. First, I construct a new graph where each vertex represents a vertex in the source graph plus the current path and it's property values. This is similar to how a game like Chess can be represented as a graph: a set of vertices each describing a current state of the game and a set of edges which describe the possible actions. Then, I simply use the BFS to find the shortest path. This approach has several drawbacks:

For each combination of property values a new vertex should be created. If property has an integer value, the number of vertices is going to be really large.
Because of the extension number two, the vertex can have a large number of edges connected. We need to represent an each edge which can be visited from this state, and when path is long the number of edges becomes big too.
If I need to find a path to several vertices, it's necessary to start a search several times and combine received paths. In some cases it is possible to make a shorter path if the algorithm will be aware that I actually need to reach several vertices, not the single one only.

My questions are:

Are there an existing name for such graphs? I've learned about dynamic graphs and they don't fully correspond to my description because they don't usually have a state (a state is the main feature of my graph).
Are there any better (faster, with less computational complexity, more functional) algorithms to find the shortest path in such graphs? To be more specific, are there an algorithm which solves at least some of the issues mentioned before?
If such algorithms exist, are there any libraries that implement it?

P.S. $f$, $g$ functions are simple logical predicates or integer arithmetic expressions. For example, to require some edge to repeat 100 times in the path I may set transition function for this edge as $i_{new} = i_{old} + 1$ and place another edge after it with $g$ equal to $i > 100$. SMT solver may be a helpful tool for this task, but I don't know how to encode the problem itself in a solver format. Also I'm not sure that applying SMT is the best approach.


texts: Viewing images that compressed using lossless algorithms

texts:
I am just trying to understand a few minor details regarding images that are compressed with lossless algorithms such as RLE.

If a bmp image is compressed using RLE, when does the decompression occur when viewing the image? does the image viewer have a built-in library to decompress the image and then view it? or is it using a system library? Is the decompressed image file stored in the RAM temporarily?

Do you any references for this process?


texts: Decomposition of graph to subgraphs according to parallel edges

texts:
I am supposed to calculate all-pair shortest path lengths of a graph. However, I first need the graph to be decomposed/expanded to a simple one based on the presence of parallel edges.

If N parallel edges exist between any two vertices A and B, I need to create N replicas of both vertices. Each replica of A will be connected to one and only one replica of B, and vice versa. In addition, all replicas of a vertex must be fully connected to each other.

As an example:-

A === B

will become

A1 ----- B1
|        |
A2 ----- B2

Does this formulation match any well-defined graph theory problem? I am trying to come up with an algorithm that can make use of a GPU's speed, since the graphs I am dealing with can become huge, and I am trying to do it by manipulating the adjacency matrix.


texts:
Apologies if this isn't the correct forum but I thought it would be too academic for the DBA forum. In my work I'm looking to research some of the benefits of using an RDBMS product over traditional files (text, XMLs JSON what have you).

I'm not planning to cover the advantages over Big Data / NoSQL but that would be a bonus.

Is there an academic paper(s) that I can start my research from?

To narrow it down I would say the advantages around indexing, validating relationships and database views are what I would like to concentrate on but anything will be highly appreciate.


texts: How do O and Ω relate to worst and best case?

texts:
Today we discussed in a lecture a very simple algorithm for finding an element in a sorted array using binary search. We were asked to determine its asymptotic complexity for an array of $n$ elements.

My idea was, that it is obvisously $O(\log n)$, or $O(\log_2 n)$ to be more specific because $\log_2 n$ is the number of operations in the worst case. But I can do better, for example if I hit the searched element the first time - then the lower bound is $\Omega(1)$.

The lecturer presented the solution as $\Theta(\log n)$ since we usually consider only worst case inputs for algorithms.

But when considering only worst cases, whats the point of having $O$ and $\Omega$-notation when all worst cases of the given problem have the same complexity ($\Theta$ would be all we need, right?).

What am I missing here?


texts:
I'm unclear about the use of the phrases "infinite" language or "finite" language in computer theory.

I think the root of the trouble is that a language like $L=\{ab\}^*$ is infinite in the sense that it can generate an infinite (but countable) number of strings. Yet, it can still be recognized by a finite state automaton.

It also doesn't help that the Sipser book doesn't really make this distinction (at least as far as I can tell). A question about infinite/finite languages and their relationship to regular languages came up in a sample exam.


texts: In a Operating System, who decides which parts of a program (or task) has to be stored in the virtual memory and which in the RAM ?


texts: Hardness of the Minimum Steiner Tree problem on grid

texts: Is the Minimum Steiner Tree problem $NP$-hard even on (2D, unweighted) grid graph ? A proof (for either case) will be very appreciated.


texts:
In P2P(peer-to-peer) networking, it is possible for the server program(software) and the client program(software) to be running on the same computer.

So the two must have the same IP address.

I am confused about this. Is there nothing going wrong if both of them uses the same IP address?

Please clarify.


texts: Hardness of approximation statement clarification?

texts:
In the paper I'm reading, there is a hardness of approximation result for an algorithm proved using a reduction to set cover. Roughly, the claim states that if there existed an algorithm that solved this problem considered in the paper with an approximation ratio less than or equal to $(1 - \alpha)( 1 + \log x)$ for any $\alpha > 0$, the result for set cover would be contradicted. $x$ is a quantity that is shown to satisfy $x \leq n$. The set cover result is that set cover is NP-hard to approximate within $(1 - \alpha) \log n$.

My confusion stems from the fact that $(1 - \alpha)( 1 + \log x) \leq (1 - \alpha)( 1 + \log n)$ is not less than $(1 - \alpha) \log n$.

Can we just disregard this constant additive factor of $(1 - \alpha)$? What if the approximation ratio had a constant multiplicative factor? Like it would something like $(1 - \alpha)( 1 + \log x) (1 + \beta)$, where $\beta > 0$?


texts:
A common issue in app development is avoiding over-fetching of data, such as in this naive (pseudocode) example:

get_user(id) {
  return sql_query("SELECT * FROM users WHERE id=$1", id);
}

render_some_webpage() {
  // ...
  print get_user(session.user_id).username;
  // ...
}

While this would work, it requires the database to send back a bunch of user fields when only the username is used (it's not a big deal in this trivial example, but gets much worse when associations/joins are involved). This problem is normally solved via adding an additional argument to get_user with a list of required fields, but that's far from a perfect solution. It seems the language could infer which fields of the user were actually used and allow get_user to act on this information (by only fetching the username).

Is this a known concept? Are there languages that implement this idea?


texts: What should I call algorithms with non-linear non-constant time?

texts:
I am writing a paper in which I want to refer to a group of algorithms. Some of these algorithms are of complexity O(NlogN), and some of the are more complex (e.g polynomial-time) and I want to refer to them all in one term. Is there any common term to use in such a situation?

linearithmic refers to O(NLOGN) algorithms and it's narrower than what I'm looking for. I don't think of non-linear as a good term to use here. If it is, then correct me please.

my sentence:

  In such a setting, state-of-the-art community-detection algorithms does not scale well. To reduce the running time of these XYZ algorithms, each sub-graph is partitioned into chunks.

I want to change `XYZ' in the above, to what I am asking for.


texts: What is the best algorithm to find the optimal path in reducing company's real-estate footprint?

texts:
I was hoping someone could point me in the right direction in terms of what type of problem I am describing and what type of algorithm I should use to answer it.
Here is the problem: A company is in the process of reducing its office space and wishes to find the path that will minimize double-rent costs during the transition period.
Constraints:

There are 200 teams in the company (team = indivisible unit). Teams are of different sizes ranging from 10 to 500 individuals.
The start and end locations for each team are given.
There are 250 office locations initially (1 per team), 150 will ultimately be removed and 100 will be added. The 100 remaining locations may see a change in occupant, and there will/can be empty locations at any time period.
The transition period is of 24 time-periods (months), however, teams do not need to move every month, and should move only when new buildings are added.
Teams may move 0, 1, 2 or 3 times during the 24 month time-span
Locations are added at different time periods. Once a building is added, monthly rent starts to be charged.
Locations which are removed have leases ending at different time periods, but leases can be terminated early for a set fee.

Cost function to minimize:
$$C = \sum_{t=0}^{24}\left (M(F_{t},F_{t-1}) + DR\left (F_{t} \right ) +T(F_{t})\right)$$
with:

$M(F_{t},F_{t-1})$ the cost of moving teams from one location to another between 2 subsequent time periods, here moving cost per team is an arbitrary constant.
$DR\left (F_{t} \right )$ the cost of double-rents for the footprint at time t.  If at time t, a team's start and end locations are available, only the rent of the team's start location is counted for computation of double rent.
$T(F_{t})$ the total of early lease termination fees at a time period.  Early lease termination fees depend on each location.

Options explored:
I have started exploring different tracks to answer this problem, namely :

Create a graph with every possible permutation at every time step and then find the shortest path using a tree search algorithm.  However, the large number of teams, locations and time periods define an immense number of permutations hence I am pretty sure I cannot list all possible trajectories.
I am thinking of using a classical Solver-type tool in Python to find optimal path, however, I fear the number of variables may be too large.

My research also led me to potential methods in the fields of Dynamic Programming, Integer Programming, Branch & Bound.
Is there a clear algorithm or manner to address this that comes to mind ?
Edit : I forgot to mention that teams may move 0, 1, 2 or 3 times during the 24 month time-span.


texts: Computing square vs computing square-root? Time complexity

texts:
I am working on something that requires checking a very large natural number $x$ to determine if it is the square root of an even larger natural number $y$. So I am wondering what are the fastest algorithms for computing square and square root, and how should I be approaching this i.e.

Computing $\sqrt{y}$ and comparing it with $x$
OR
Computing $x^2$ and comparing it with $y$

So as to write a code that has minimum time complexity.


texts: Go from source to destination in 2d matrix with min steps collecting all candies. How to do it?

texts:
If we have a 2d matrix of max dimension, 95x95 and we have at max 12 candies placed in some cells. We always start from top left corner(0,0) and we need to reach some given destination (x,y) after having collected ALL the candies. There are some cells which are blocked and hence cannot be visited.
Let 10 represent empty cell, 11 represent blocked cell and 12 represent candy. So, for the given 3x3 matrix:

10 10 11
11 12 10
11 12 11

with destination: (1, 2) (0-indexed), the min. no. of moves required to go from (0,0) to (1,2) is 5. i.e (0,0)->(0,1)->(1,1)->(2,1)->(1,1)->(1,2).

How to solve this question? Since BFS, DFS, etc all avoid re-visiting visited nodes, I am unable to use them. Same goes with backtracking.


texts: How to convert the left recursive grammar into right recursive grammar

texts:
I have a grammar: $A\rightarrow Aa|bB|c$

The above is the left recursive grammar.
I understand that I have to remove the string "Aa" from the above grammar or to convert it into the form "aA" to avoid left recursive.

Some body please guide me how to do that.


texts: Why does the Turing Machine allow for multiple final states?

texts:
Why does the Turing Machine allow for multiple final states when it would be simpler yet equivalent to work with just one? Why allow additional unnecessary states?

Is there some historical reason for this? Is the concept of multiple final states useful in any way? (Perhaps something akin to the ease of use of multi-track Turing machines, even though they're equivalent to standard ones?)


texts: Turing machines and languages -- recursive (enumerable) or not

texts:
For an assignment in my university, we have to answer multiple choice questions about theoretical computer science. This particular one I find very hard to understand. I wonder if some of you could explain it to me.

In this question, L1, L2, L3, L4 refer to languages and M, M1, M2 refer to Turing machines.

Let

L1 = {(M1,M2) | L(M1) is a subset of L(M2)},
L2 = {M | There exists an input on which TM M halts within 100 steps},
L3 = {M | There exists an input w of size less than 100, such that M accepts w},
L4 = {M | L(M) contains at least 2 strings}.

Decide whether each of L1, L2, L3 and L4 are recursive, RE or neither. Then identify the true statement below.

     a)      The complement of L3 is recursively enumerable.
     b)      The complement of L2 is recursive.
     c)      The complement of L2 is not recursively enumerable.
     d)      L1 is recursively enumerable.

What I do not understand is, how the definitions of L1, L2, L3, L4 can tell me whether or not they are recursive (enumerable).

My guesses (probably wrong) are:

L1: ?

L2: recursive enumerable (I thought this since obviously there are inputs on which the TM halts but we can not say if it halts every time – therefore only recursive enumerable and not recursive)

L3: recursive enumerable (Same explanation as for L2)

L4: not recursive (This is only a guess, I don't get how the number of minimum strings of the language can imply any type of recursiveness.)


texts: Count arrays with size n, sum k and largest element m

texts:
I'm trying to solve pretty complex problem with combinatorics.

Namely, we have given three numbers N, K, M. Now we want to count how many different arrays of integers are there with length N, sum K and all the elements in the range [1, M]

Constraints:

1 <= N <= 100
1 <= K <= 100
1 <= M <= 100

Example

Let's say N = 2, K = 5, M = 3. This means that we want to count arrays of integers of size 2 with sum of all elements equal to 5 and elements in range [1, 3]. There are total of 2 arrays: {2, 3} and {3, 2}. Please note that the order of the elements also matters, {2, 3} is not equal to {3, 2}

Second example: N = 4, K = 7, M = 3. We want to count arrays of length 4, sum of 7 and elements in range [1, 3].

There are total of 16 possible way of arrays: (1,1,2,3), (1,1,3,2), (2,1,1,3), (3,1,1,2), (2,3,1,1), (3,2,1,1), (1,2,3,1), (1,3,2,1), (1,2,1,3), (1,3,1,2), (1,2,2,2), (2,1,2,2), (2,2,1,2), (2,2,2,1)

What I have tried

I know that one solution is to generate all possible arrays, but such algorithm in best case will work in complexity O(N!) which is far too big for N = 100. I started thinking about solving this with three-dimensional dynamical programming, but I cannot find the relations between the states.

I'm thinking about this way: Let f(i, j, l) be the number of arrays of length i, sum j, and largest element l. We can see that for i = 0 f(i,j,l) = 0, so this is I think the base case. Also f(1, 1, 1) = 1 is another base case.

Now I cannot find the relations between the states. Can you give me some hints how to find the relations between the states. Thanks in advance.


texts: Inequality over the entropy of an integer-valued random variable

texts:
I stumbled upon this inequality over a course on Information Theory :

  If $Z\in\mathbb{N}$ with finite mean, then $H(Z) \leq E(Z)\times h(\frac 1 {E(Z)})$ where $h$ is the binary entropy function

I have been trying to prove it using the log-sum inequality :

  $ \sum_i a_i \log \frac {a_i}{b_i} \geq (\sum_i a_i) \log \frac {\sum_i a_i}{\sum_i b_i} $ for $a_i, b_i$ non-negative numbers

Using, for example, $a_i = P(Z=i)$ and $b_i = iP(Z=i)$.
But I couldn't really get throught it.

Part of my problem with this inequality is that I don't understand it : where does this use of the binary entropy function come from ? Even the relation between entropy and the mean seems unnatural to me.


texts: Determining whether one convex polygon lies within another through tangency

texts: Figuring out whether one convex polygon lies in another seems fairly straightforward... however the problem lies in computing counterclockwise points of tangency.