texts:
i encountered the following problem:

Exact2IS ={G has exactly 2 independent sets}

Assuming that given a graph G i can find an independent set how can i check if G has exactly 2 independent sets.

(i can check if a graph contains independent set in O(1) and also find some independent set in O(1))

I was thinking on find some independent set(if there is any) of size k and then remove one vertex from the set and check if the graph still has independent set of size k
-after i check i return the vertex to the graph exactly as it was.

The problem my idea check only if a graph G contains at least 2 independent sets and not exactly.

Anyone have an idea how can i check if a graph has exactly 2 independent sets(in polynomial time and given the fact that find and check if there is independent set is O(1))?

Any clues or ideas will be appreciated :)
Thanks


texts:
In "regret" styled analysis over $T$ steps of an iterative algorithm $\{x_i \in F \}_{i=1}^T$ (where $F$ is some feasible set) being given the sequence of loss functions $\{ f_i\}_{i=1}^T$ one defines the regret $R_T = \sum_{i=1}^Tf_t(x_i) - \min_{x \in F} \sum_{i=1}^T f_t(x)$ Most typical analyses assume that the $f$s are convex.

Is this notion of "regret" lower bounded?
Or under what conditions is it lower bounded?

I guess "minimizing the regret" does not make sense because one can always have an "Oracle" access to the sequence of points $x^*_i$ such that $x^*_i = \min_{x \in F} f_i(x)$. Then for this sequence for $x^*$ points the regret is only at most $0$.


texts: simulation of Randomized distributed algorithms

texts: I want to implement various Randomized Distributed algorithms for MIS, Broadcast, Coloring in Radio Networks. I want use very high level language or any simulator for this. Please suggest on this.


texts: Why do mainstream speech models no longer require a personalized training step?

texts:
Back in the Windows XP era, when setting up Windows OS-built-in speech/dictation, I had to speak out a bunch of programmed-in text samples to the speech-to-text engine to personalize my voice profile.

Today, with networked speech-to-text engines like Siri or Cortana, I can just start dictating.

The quality of the text-to-speech conversion seems equivalent, though my memory may be faulty on that aspect.

Have speech models advanced past the need for any personalization of the training data? Or, do they just do the personalization under the covers now, without an explicit training wizard? Or, do they not do training, even though it would still be beneficial (e.g. because it's inconvenient)?


texts: Propositional extentionality in the lean theorem prover?

texts:
Propositional extentionality in the lean theorem prover is stated as the following axiom:

  axiom proptext {a b : Prop} : (a $\iff$ b) \to a = b

My confusion about this is as follows: Previously I’ve read (in “introduction to type theory” by Herman Geuvers) that one key property of type theory is that we don’t say that two types are equal just because the set of its instances is equal (unlike in set theory).

He stated that this is on of the sources of type theory’s power because it allows one to syntactically check whether something is of a certain type, whereas with set theory, we can’t. He stated that this can be understood as, $:$ is a decidable operator, whereas $\in$ is not.

I’m confused about how the axiom of propositional extentionality fits into Geuvers’ characterization of what type theory is about.


texts:
Consider a linear list-based directory implementation in a file system. Each directory is a list of nodes, where each node contains the file name along with the file metadata, such as the list of pointers to the data blocks. Consider a given directory foo.
Which of the following operations will necessarily require a full scan of foo for successful completion?
A. Creation of a new file in foo
B. Deletion of an existing file from foo
C. Renaming of an existing file in foo
D. Opening of an existing file in foo

Here I know that the creation of a new file necessarily required a full scan. But I'm confused with how the renaming of the file necessarily requires a full scan. Please, explain how the renaming is done in the directory structure.


texts: We know that $10n^2 = O(n^2)$ but $10n^2 \neq o(n^2)$. What is the underlying principle?


texts: The line-covering step in the Hungarian algorithm

texts:
I am trying to understand the Hungarian algorithm for the assignment problem.

I found this presentation which gives an excellent explanation about the algorithm.  However, there is one step I do not understand.

Step 3 (pages 13, 16) says "Cover all the zeros of the matrix with the
minimum number of horizontal or vertical lines".  How can this step be done in polynomial time?

I.e, given an $n\times n$ matrix with some zeros, what is an efficient algorithm for finding the smallest set of rows and/or columns that contain all the zeros?


texts:
I have permutations:
4 1 2 5 3
4 3 2 5 1

numbers can be order magnitude of 1000 (fits in two bytes)
I want compute 32 bit (or better 64 bit) hashes, it should be non cryptographically secure but evenly distributed in 32 or 64 bits.
This second permutations is derived from first by swap 1-st and 4-th element (count form zero). I want incremental hash: if I know hash of first permutation, should be fast and easy obtain hash of second by knowing only 1-st and 4-th element.
Apart from evenly distribution, candidate can be modified XOR. XOR has disadvantage, that is insensitive to order - modified XOR computes xor with numbers and its positions. Smaller disadvantage , that would be 10-12 bits for this numbers instead of 32 or 64 bits, but 10-12 bits is enough to unique distinguish between permutations? when number bits would be order of magnitude of log2(permutation len)?
Unfortunately xor of permutation give 0 (or constant number?), xor of two permutations also.. Is possible add bit rotations but with incrementality?
What about checksum defined below:
simple sum is insensitive to order, but if we sum products:
tab[index]*(index+1)? This is order sensitive.


texts:
I came across an issue with the definition of a (directed) graph in Sipser's Introduction to the theory of computation, 2nd Ed.

On pp.10, An undirected graph, or simply a graph, is a set of points with lines connecting some of the points. The points are called nodes or vertices, and the lines are called edges, ...

On the same page,

  No more than one edge is allowed between any two nodes.

On pp.12,

  If it has arrows instead of lines, the graph is a directed graph,...

In Figure 0.16 on pp.12, there is an example of a directed graph, an arrow from node 1 to node 2 and an arrow from node 2 to node 1.

So, we have two arrows in opposite direction between two nodes.

I understand all of these basics.

My question is,

  Is directed graph a graph?


texts: Detecting approximate sum collisions in two lists.

texts:
Suppose two equal-length lists of double precision numbers $A=(A_1, \ldots, A_N)$ and $B=(B_1, \ldots, B_N)$. Given a constant, $\epsilon > 0$, I want an efficient algorithm for finding 4-tuples of the form $(A_a, A_b, B_c, B_d)$ for which $|A_a + A_b - (B_c + B_d)| < \epsilon$.

One thing you could do is form the sum sets $S_A:=\{A_j + A_k\}$ and similarly, $S_B$, sort them, and then iterative over these in parallel looking for elements that satisfy the requirement.

This algorithm should have complexity of the form $O(N^2)$ (with perhaps a constant multiplicative factor). Forming the sum sets has complexity $\sim O(N^2)$, the sorting has complexity $\sim N \log N$; the final step is a single pass through both sum sets; also complexity $O(N^2)$.

Is there an algorithm that does better than $O(N^2)$?


texts: Confusion about example in Raft consensus paper

texts:
In part (c) of Figure 8 in this paper http://ramcloud.stanford.edu/raft.pdf, I am confused how S1 knows that the current term is 4 when it restarts and is elected leader.

Here is the sequence as I currently understand it:

S1 is elected leader for term 2, partially replicates a request, and then dies.
S5 is then elected leader for term 3, receives but does not replicate a request and then dies.
S1 restarts, (still thinking it is term 2), is elected leader (for term 4?), and then replicates a term 2 request to a majority of nodes, but does not commit.

My confusion is in step 3. When S1 reawakens, it is elected leader for term 4, even though it hasn't been active since term 2. How does S1 know that it is now term 4?

Citation for linked paper:

O NGARO , D., AND O USTERHOUT, J. In search of an understandable consensus algorithm. In Proc ATC’14, USENIX Annual Technical Conference (2014), USENIX.


texts:
Are there efforts to automatically discover new logics? Logics are simple structures - they have formal language, deduction rules, semantics and certain properties that are proved or discarded for every new logic. In fact, each logic can be put into framework of institutions (by Diaconescu et al).

So - is it possible to automatically learn/discover new logics?

E.g. type logical grammars (development of (abstract) categorial grammars) map natural language sentences into lambda expressions (some logics into language in lambda expressions). It can appear, that resulting expressions can not be built due to low expressibility of the logic. So - new, more expressive, more adaptable logics should be discovered. Can the process be automated by using criterion of "optimally highest level of understanding" (i.e. whether the machine can understand and operate with the formalized text or not) - e.g. if machine can not understand the valid natural language text, then machine is obliged to discover new logic into which the text can be translated and understood.

There is formalization of the notion of "understanding" https://link.springer.com/chapter/10.1007/978-3-319-41649-6_11 and this understanding can be optimized for the discovery of new logics.

So - are there trends to do this?

I am aware of inductive logic programming which discover rules in some logic, but I am aiming for the discovery of the logic itself. So - there is also inductive metalogic programming but I have managed to find only two articles about this (one in Japanese) and they seem to be not about new logics.

I have also heard about framework of ludics of Girard, but it is very, very bounded work on linear logic, more general setting is required and ludics seem to be not generalizible enough.


texts: Is P the set of all algorithms whose run-time is $O\left( n^{ O \left( 1 \right) }\right)$?

texts:
I'm coming to Computer Science from Mathematics and am familiar with the idea of building classes of objects using Propositional Logic. Namely, start with some universe of objects, define some proposition $P \left( x \right)$, and then iterate over the universe of objects, applying $P \left( x \right)$ to each; keep the objects for which $P \left( x \right)$ is true; exclude each object for which $P \left( x \right)$ is false.

So, when we define a class of objects called $\mathbb{P}$ (as in P vs NP), I really need to see a formal definition of the proposition used to build that class--as well as a formal definition of the universe of objects we're starting with.

Defining the Universe of Discourse, $\mathbb{U}$

My understanding is that, for the question of $\mathbb{P}$ vs $\mathbb{NP}$, our universe of discourse is all decision problems that are satisfiable. Namely, problems that can be implemented in boolean logic, return a boolean result, and that someone somewhere at some point has found a finite sequence of inputs that cause the implementation to return $TRUE$.

In spite of Russell's Paradox, let us define our universe of discourse as the set $\mathbb{U}$.

Defining $\mathbb{P}$

$\mathbb{P}$ is a subset of $\mathbb{U}$. Namely, it is the set of all objects in $\mathbb{U}$ for which the following proposition returns $TRUE$:

  This object can be written as a decision problem that returns a boolean value--and that decision problem takes at most $O \left( n^{O \left( 1 \right)} \right)$ time.

That is, given some implementation of a decision problem in $\mathbb{U}$, if that implementation takes at most polynomial time, we can include that implementation in $\mathbb{P}$.

The Point I Need Clarified

Are we really using $O \left( n^{O \left( 1 \right)} \right)$ to define $\mathbb{P}$? Or are we using $\theta \left( n^{O \left( 1 \right)} \right)$? $O \left( n^{O \left( 1 \right)} \right)$ seems right to me, but--so often material I study from doesn't distinguish between Big-O and Big-Theta. So, I need to clarify.

For example, given the following simple, Java-like implementation of an algorithm:

function boolean isOne(int input) {
    return input == 1;
}

Should I include this algorithm in $\mathbb{P}$? It is clearly faster than polynomial time; it is constant time. So, it is $O \left( n^{O \left( 1 \right)} \right)$ but not $\theta \left( n^{O \left( 1 \right)} \right)$--as long as zero $\not\in O \left( 1 \right)$?

Should I include it in $\mathbb{P}$?

If zero $\in O \left( 1 \right)$, then is a constant time algorithm in $\theta \left( n^{O \left( 1 \right)} \right)$?


texts: Following but not intersecting time segments to detect multiple accounts

texts:
In some code I'm currently writing, I'm stuck on the following algorithm to implement. The goal is to find real world users using multiple different accounts.

I've a List of UserData. This list is pretty big (> 10M entries)

A UserData is defined as: { userId, List<TimeSegments> }. A TimeSegment is {connectionDate, disconnectionDate}. We can assume here that the average size of the list of timeSegments is 100.

I want do find groups of users such as:

for each group of users, all timeSegments are non overlapping (we assume here that a user cannot be connected with multiple accounts at the same time)
for each user U1 in a group of users, there is a user U2 in the same group such as at least one, U1 disconnected and then U2 connected in the following 15 minutes (or the opposite) (we assume here that at least once, a user will disconnect from an account and with another one immediately after)

Of course, the brute force O(n²) solution (find couples of users and then merge those couples) is not good enough due to the size of data

Any idea of how to start this ?

Thanks !


texts: Turing machine to output enumeration of a language

texts:
I am trying to write a Turing machine enumerator that enumerates the language where $w = 0^n1^n$ and $n ≥ 0$.

So for example it should output the following to the first tape:
e,#,0,1,#,0,0,1,1,#,0,0,0,1,1,1 etc.

Here e means empty, i.e., to leave that index blank.

I can't figure out how to display this as a Turing machine with states and transitions.


texts: Algorithm to find path with max sum of degrees in a tree structure

texts:
Is there an efficient way to find a path from root to a leaf such that it has the maximum sum of degrees of nodes from all the paths possible in the tree.

For example if a tree is defined as the one in which each node is an integer and it has as many child nodes as the perfect divisors of the integer. And the root node is 16 then the sum of degrees of the required path would be 4+4+3+2+1 = 14.
The path being : 16->8->4->2->1.


texts: Looking for a formal grammar for $\{ a^{2^n} \mid n \in N\}$

texts: The title says it all. The language $\{ a^{2^n} \mid n \in N\}$ looks quite simple. Yet I could not find a grammar that generates this language.


texts: Can the complement of an unrecognizable language be a recognizable language?

texts: I know that complement of a language that is recursively enumerable, but not recursive, is definitely not recursively enumerable (or unrecognizable). So my question is what can be said about the complement of an unrecognizable language?


texts: Proof that total computable functions are not enumerable

texts:
In an answer to this question, a sketch of the proof that total computable functions are not enumerable is made:

  Because of diagonalization. If $(f_e:e \in N)$ was a computable enumeration of all total computable functions from N to N, such that every $f_e$ was total, then $g(i)=f_i(i)+1$ would also be a total computable function, but it would not be in the enumeration. That would contradict the assumptions about the sequence. Thus no computable enumeration of functions can consist of exactly the total computable functions.

I really don't understand why

  then $g(i)=f_i(i)+1$ would also be a total computable function

Indeed if $g$ was a total computable function, then $\exists k, f_k=g$, so that $g(k) = f_k(k) + 1 = g(k) + 1$, which is impossible.

So it seems to me that building $g$ is impossible, so that we cannot reach a contradiction by saying that we have built another total computable function which is not in our enumeration.

I tried shifting the diagonal to avoid this effect, but other loops of the same kind can't be ruled out.


texts: Can a cycle be represented by L1 metric?

texts:
Let G be a graph that forms a cycle on $n$ vertices, with non-negative weights on the edges.
Can you give each vertex v a vector $\mathbb{R}^m$ (for some $m\in \mathbb N^+$) such that the L1 distance (taxicab distance) between two vectors is the same as the distance between them in $G$?

Prove for a general circular graph or give a counter example with proof.

(I was told it is true so I have a good reason to think it is but I can't prove it.)


texts: Dynamic programming - maximize sum of functions subject to constraints

texts:
Let $\{f_i\}_{i=1}^{k}:[0,k]\to\mathbb{Z}$.

The problem: Maximize the sum $\sum_{i=1}^{k}f_i(x_i)$ subject to the the constraint $\sum_{i=1}^{k}x_i\le k$

I think we suppose to come up with a polynomial time solution, but i got stuck on identifying the sub-problems and using them.

One direction that i had was creating a list for each function, where both the arguments and the function values are in decreasing order: in each iteration, find the argmax of the function, delete bigger arguments that yield smaller function values, and proceed with the smaller arguments that remain (($O(k^3)$ for all functions).

Then  use those lists to iterativly construct the optimal solution under the constraint for 1, 2, .. and finally for all $k$ functions, Got stuck about here. Not sure if it's a good direction at all...

Would appreciate any assistance.


texts:
I want to check if I understood it in the right way.
In some example where $L\in RE$ the explanation deal with 2 cases: 1st when $L$ finite and 2nd when $L$ infinite. In the second case $L\in R$, isn't? Is it possible somehow that $L\in RE\setminus R$ be finite?


texts: Describe a data structure to track visitors

texts:
Given $n$ cities, describe a data structure which supports the following functions:
Init$(n)$ - initializes the data structure in $O(1)$
Visit$(j,i)$ - adds "citizen from city $j$ would like to visit city $i$" in $O(1)$
Favorite($k$) - prints the $k$ most favorite cities in descending order in $O(k)$ (ignore ambiguity such as 2 cities with same amount)

I can't find how to do the last one in $O(k)$, hints would be appreciated.


texts: Sort an array of $n$ elements when only $\log n$ are not in place

texts:
I'm trying to understand how can I sort an array of $n$ elements when only $\log n$ are not in place.

I heard that sorting an array with at most $I$ inversions has complexity $O(n\log(I/n))$. Because there are $\log n$ elements that are unsorted, in my case there are at most $n\log n$ inversion.

The answer to the question is $O(n\log\log n)$ which is consistent with the formula, but I can't understand the"idea behind it, or which sorting algorithm achieves it.


texts: Given two DFA's accepting the same language, does one have to refine the other?

texts:
I have a logical question that I can't quite crack:

Given two automata accepting the same language $L$, does one have to refine the other?

In other words, if $A_1$ and $A_2$ both accept $L$, with associated equivalence relations $R_{A_1}$ and $R_{A_2}$, does $R_{A_1}$ have to refine $R_{A_2}$, or vice versa?
I am leaning toward the answer yes because if we have a regular language $L$ which is accepted by an automaton $A$, we can show that the relation $R_A$ refines the relation $R_L$, meaning $R_A \sqsubseteq R_L$,
which means that both $R_{A_1} \sqsubseteq R_L$ and $R_{A_2} \sqsubseteq R_L$.
We are currently studying the Myhill-Nerode Theorem, so I'm guessing it has something to do with it.
I've tried combining few theorems together, but came out empty.


texts:
How should I go about building a Turing machine for the following language:

$$L = \{  a^ib^j \in (a,b)^* \mid i \le j \le 2i \} $$

I know how to construct a Turing machine for $\{  a^nb^nc^n \mid n \in \mathbb N \}$ but don't really where to start for the one above.


texts: Number of hardware page tables and page directories kept in the MMU

texts:
How many hardware page tables (physical) and page directories are kept in the memory management unit?
If a cpu has a 32 bit virtual address, the upper 10 bits are used for the page directory, the middle 10 bits for the page table, and 12 bits for the 4K page frame. Does that mean 1 page directory containing 1042, 32 bit pointers, and 1042 page tables containing 1042, 32 bit pointers are needed?
What is the role of the page directory cr3 pointer control register in intel cpu?


texts: Prove that the language L = {a^(m+n) b^m a^n | m, n ≥ 0} ∪ {a^m b^n a^(m+n) | m, n ≥ 0} is not regular

texts: In general, how can we go about proving that union of two languages as non regular. In this case, the individual languages can be proved as non regular using pumping lemma. How can we apply pumping lemma to union of two languages ?


texts: Why do online compilers/interpreters use different limits for the maximum recursion depth error?

texts:
When using two different online Python compilers/interpreters for executing a program (this one, and this one), I found that both sites showed the maximum recursion depth error at $n = 998$, whereas the one which I had downloaded from python.org showed the error at $n = 1024$. Is there a reason why online compilers/interpreters have lower maximum recursion depth limits?
For example, this recursive function (which displays the first $n$ terms in the Fibonacci sequence) shows a recursion error at $n = 998$ in an online compiler/interpreter.
def fib_memo(n):
    if n in fib_cache:
        return fib_cache[n]
    if n == 1:
        value = 1
    elif n == 2:
        value = 1
    elif n > 2:
        value =  fib_memo(n-1) + fib_memo(n-2)
    fib_cache[n] = value
    return value
fib_cache = {}
print (fib_memo(998))

But it shows a recursion error at $n = 1024$ in the Windows Python application.


texts:
Working through some material on CPU architecture and am unsure on the following question:

Suppose that an instruction encoding format has 4 bits for argument registers. How many registers is the architecture most likely to have? Why?

What is the general principle is here - how the size of argument registers corresponds to the total of registers


texts: Proof that there is unambigous grammar for every regular language

texts: How can I prove, or where can I find proof that for every regular language there is unambigous grammar?


texts: How to disambiguate symbolic regular expressions

texts:
What I mean by a "symbolic regular expression" (if there already is a different name for this I'm not aware of it) is a regular expression that may include exponents that are symbolic arithmetic expressions.

Example 1: $a^k|b^*$ means "either $k$ copies of $a$ or zero or more copies of $b$".
Example 2: $a^{k+1}|a^k$ means "either $k$ or $k+1$ copies of $a$".

What I'd like to do is disambiguate such regular expressions.  I know that to disambiguate a normal regular expression, you can convert it to an NFA, then a DFA, then back to a regular expression.

The problem is not completely straightforward.  For example, $a^k|a^j$ is ambiguous if $j=k$ and unambiguous otherwise.  Thus, the appropriate output would be, for example,
$$a^k \text{ if } k=j, \qquad a^k|a^j \text{ otherwise.}$$

Does anyone know if there has been anything written about this problem?


texts: Diff list with unique elements - Algorithm review

texts:
in the past few days I've been working on a diff algorithm for a UI library I'm working on.

My use case only target lists with unique elements.

The main goal is to find the minimum amount of operations needed to transform list A into list B.

Here you can find the current version of the algo:
https://github.com/cruijs/crui/blob/diff/packages/reactive/rx/list/diff/generic/index.ts

It's in typescript. In case you are not familiar with it, here is a rough explanation:

Build an index Map for both A and B, where key is the list's item and value is the index position in the list
Initialise two sets:

one for elements we'll need to add later
one for elements we'll need to remove later

Compare elements from list A and B

both elements match: move both forward
element doesn't exist in list A or is in set shouldAdd

add it
move to next B

element doesn't exist in list B or is in set shouldRemove

remove it
move to next A

otherwise:

given a the current element in A
given b the current element in B
di = distance in B between b and a.
dj = distance in A between a and b.
if  di >= dj (element b is closer in A and could possibly require no change):

remove a
add it in shouldAdd
move to next A

else:

add b
add it in shouldRemove
move to next B

If we add all elements of B, then A and B have nothing in common

early return with a full Replace

If there are items unchecked at the end of A

remove all of them

If there are items unchecked at the end of B

add all of them

Squash all remove and add operations to be more efficient

All in all, this should be a O(n+m) complexity in both space and time, where n is the initial list size while m is the target list size.

I wonder, is there a more efficient or elegant solution?

Allowed operations are:

Insert one or more elements at index i:

given [1, 2, 3]
when insert [6, 7] at index 1
then [1, 6, 7, 2, 3]

Remove one or more elements at index i:

given [1, 6, 7, 2, 3]
when remove 2 elements at index 1
then [1, 2, 3]

Insert & Remove elements at index i:

given [1, 2, 3]
when insert [6, 7] and remove 1 elements at index 1
then [1, 6, 7, 3]

Replace list:

given [1, 2, 3]
replace with [4, 5, 6]
then [4, 5, 6]

Replace single element at index i:

given [1, 2, 3]
replace with 1 at index 2
then [1, 2, 1]

Current algorithm do not use the single item replace and initially produce just remove and insert, which then tries to collapse as much as possible.

Thanks to everybody who will take time to review it :)


texts: How to classify simple priority queue algorithm

texts:
I have a simple priority queue algorithm that I implemented, and I doubt it's new
but I haven't been able to classify it. Wondering if I could get some help with classifying it! Once I classify it I can read more about how to implement it properly, etc.

Assuming the implementation is sound, I am also trying to figure out how to prove certain aspects of the queue, namely to determine if the maximum amount of time (or steps) for an item to come off the queue is deterministic.
Ideally we could figure out how long that would be as a function of some variables and initial state, or what not.

Here is the basic algorithm:

Setup/background/assumptions:

We have a FIFO queue, and each item in the queue has a priority of 1, 2, or 3 (generically, we could make it 1 -X  where those are all integers). By FIFO we mean that, in general, items that are enqueued first get dequeued first, but with a priority queue that is not exactly the case (that should be pretty obvious).
3 is highest priority, 1 is lowest priority, the higher the number the higher the priority.
Let's assume a single server for simplicity, but the concept should be similar enough for multiple servers.
Assume we only take one item off the queue at a time, but this same algo should work if we pop off multiple items.

Algorithm:

(Note that the only question at hand is: What item do we pop off the queue next? That is what the algorithm is trying to solve).

Step 1: For all your priority levels, determine a number of cycles for each level. Higher priority levels should have more cycles - so let's say priority 3 has 10 cycles, priority 2 has 6 cycles and priority 1 has 2 cycles.

Step 2: Instead of looking at the whole queue, look at only the first Y items, for example the first 20 items. This makes things faster (O(20) instead of O(n)), and easier to prove that the implementation is working as expected. Most importantly, setting this cap should prevent starvation for the lower priority levels. Because eventually the 20 items will be filled with lower priority items, and then they will start seeing some attention.

Step 3: Every time you dequeue an item, increment an integer. Then mod this integer against the total number of cycles (10 + 6 + 2) = 18. This will determine which priority cycle you are in, for any given dequeue event.

Step 4:
Take the value from the mod operation, determine what cycle you are in by comparing the value to an accumulated cycle value, e.g.:

Priority     Cycles      Accumulated

3            10           10

2            6            16

1            2            18

In that way if the mod result of our incremented integer is in the range
0 - 10 we are in priority 3 mode, if the mod result is in the range 11-16 we are in priority 2 land and if the mod result is in the range 17-18 we are in priority 1 realm.

Step 5: Sort the first 20 items in the head of the queue, first by priority level, then by age, oldest to the front.
Given the priority level found from step 4, look through the sorted list find the first one that is at the priority level or below. So if we are at priority 3 we will look at all items. If we are at priority 2, we look at items with priority 2 and below, etc etc.

Step 6: If no items can be found with priorty Z and below, then cycle to the highest priority again, in this case 3, which will always yield something off the queue.

Done.

The basic idea is that our priority system is is based off of the number of cycles given to each priority, where more cycles are given to higher priority items. This should make things more deterministic.

But like I said, I am most interested in (a) proving this actually works somehow and (b) determining some value for maximum time (or steps) for an item to come off the queue.


texts: Mean and median distance in unweighted graph

texts:
I have a very large graph of ~7 million vertices and ~100 million edges. One dfs run in my current implementation runs in 30 seconds.   The graph is an unweighted directed strongly connected graph.

I need to find the mean and median distances of the graph (median and mean distances over all shortest-path distances of the graph). I need the exact mean/median, not an approximation. This problem must be related to all-pairs shortest paths. But the only algorithms I know of for this problem are: Floyd Warshall, Dijkstra starting from each vertex, and Breadth First Search starting from each vertex. However, their running time is $\Omega(V^2)$ for all three of these algorithms, so for such a large graph they are too slow.

Can this problem be solved in linear or linearithmic time?  If not, what is the fastest algorithm for this problem, in asymptotic complexity?


texts: What is the time complexity of binary sum (recursion)

texts:
Currently, I'm reading Data Structures and Algorithms in Java, 6 edition by Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser link, particularly a chapter about recursions.

There is an example of algorithm which uses a recursion to calculate sum of all elements of the array:

public static int binarySum(int[ ] data, int low, int high) {
  if (low > high)  // zero elements in subarray
    return 0;
  else if (low == high) // one element in subarray
    return data[low];
  else {
    int mid = (low + high) / 2;
    return binarySum(data, low, mid) + binarySum(data, mid+1, high);
  }
}

It further says:

  the running time of binarySum is O(n), as there are 2n−1 method calls, each requiring constant time.

I don't understand why it is that the time complexity is O(n) and not O(logn). What am I missing here?


texts: Determine whether a flow can satisfy node demands in a directed acyclic graph

texts:
I have the following problem that I'm unsuccessfully trying to solve:

I have a directed graph with node demands. Unlike circulation with demands, these node demands do not "subtract" from the flow - the nodes merely demand that there would be a flow of strength k flowing through them. The graph is acyclic, however, it is not a tree - multiple routes exist from the higher to the lower nodes.

The question is, whether a flow of strength R can satisfy all of the nodes' demands. Of course, a flow with strength more than k can flow through a node with demand k. Also, there are no capacity limits in the input graph.

I need to reduce this problem to the max-flow problem. I have been trying to reduce it to Circulation with lower bounds and Circulation with demands, but unsuccessfully, as I am unable to find out a good way on how to somehow limit the flow in the nodes to be minimal while satisfying the demands and measuring it at the same time.


texts: Show that the "first half" language is regular by describing how you build a DFA or NFA for it

texts:
$L \subseteq \Sigma^*$ is a regular language.

  Show that the following language

  $L/2 = \{x \in \Sigma^* \mid \exists y \in \Sigma^* : xy \in L, |x| = |y| \}$

  is a regular language as well by describing how you change an
  arbitrary given DFA for $L$ to another DFA or NFA which accepts $L/2$.

About $L/2$, it only accepts the first even half of the word which is from the language $L$. As example, $aaabbaba \in L$, then $aaab \in L/2$.

So a DFA for $L$ is already given and now we need to change it so it works for $L/2$. What seems important to me at first, is the length of the word. It needs to have an even length else it won't work taking the first half of the word which has an even length (this is required by $L/2$). For this reason, we also need to know the total length of the word accepted by $L$. We then divide it by 2 and set an end state when we reached the first half.

Hmm it doesn't really seem to work like that because this is specially designed for a specific word but we need to take care of any word with any even length..

Can you give me some hints / ideas?


texts: The language of Logical Theory as Metalanguage

texts:
I am reading the Handbook of Satisfiability, and in Chapter 1 (History of Satisfiability), I found the following statement:

  Moreover, necessary and possible are predicates of the metalanguage
  (the language of logical theory) because they are used to describe
  sentences in the “object” language (the language that refers to
  entities in the world that is the object of investigation in logical
  theory).

I have two questions:

Could you help me please, to know what is "The language of logical theory" I have writen "'Language of Logical Theory'" in google and only found this in the same book.
Can I use necessary and possible as predicates? Could you give some example, please?


texts:
From Sipser,

Language A is mapping reducible to language B, written $A \leq_m B$,
if there is a computable function $f : \Sigma^* \rightarrow \Sigma^*$, where for every $w$, $w ∈ A \Leftrightarrow f(w) \in B$. The function $f$ is called the reduction from A to B.

A function is injective if every element in the co-domain is mapped to by at most one element of the domain.

I'm confused on how $w \notin A$ are handled. It seems that for $w \in A$ every element must map to a unique $b \in B$. Because $w \in A \Leftarrow f(w) \in B $.

New question then, is there any use to having an injective reduction? I've noticed that many proofs of NP-hardness seem to have reductions that are injective (at least on $w \in A$). If reductions are not injective ~~ Why don't we simply define our reduction function $R$ as follows, check if $w \in A$, If $w \in A$ then map to a constant $b \in B$. Else, map to a constant $c \notin B$?


texts: Using a computer algebra system to optimize mathematical expressions

texts: This is something I've been wondering for years. Software like Mathematica is great at manipulating expressions into simplified, factorized, and other forms. I'm wondering if there's a way, theoretically and/or practically, to find the form that has the fewest operations. The next step would be to prefer operations that are faster (ie. multiply instead of divide). Lastly, to find a form that maximizes extraction of repetitive subexpressions, so that the subexpressions can be evaluated once and substituted for potentially significant performance gains. Has any research been done in this area? Thanks.


texts: Validity of □(P→ Q) → (◊P → ◊Q) in linear temporal logic

texts: How can I prove that $\Box(P\rightarrow Q)\rightarrow (\Diamond P\rightarrow\Diamond Q)$ is valid in linear temporal logic (LTL)?


texts: Why add a +1 to the constant proving an O(n) bound?

texts:
I have calculated a running-time function $T(n) = 4 + 4n$, which is $O(n)$.

To determine the constant $C$ given by the relation $|T(n)| < C \cdot g(n)$,
we take

$\qquad\displaystyle \lim_{n \to \infty} T(n)/g(n)$

which gives us

$\qquad\displaystyle \lim_{n \to \infty} (4+4n)/n = 4$.

However, in the answer sheet it say to take

$\qquad\displaystyle \lim_{n \to \infty}(4+4n)/n + 1 = 5$.

What is the purpose/reasoning for this $+ 1$ term, I haven't seen anything about before?


texts: Why do low fitness individuals have a chance to survive to the next generation?

texts:
I am currently reading and watching about genetic algorithm and I find it very interesting (I haven't had the chance to study it while I was at the university).

I understand that mutations are based on probability (randomness is the root of evolution) but I don't get why survival is.

From what I understand, an individual $I$ having a fitness $F(i)$ such as for another individual $J$ having a fitness $F(j)$ we have $F(i) > F(j)$, then $I$ has a better probability than $J$ to survive to the next generation.

Probability implies that $J$ may survive and $I$ may not (with "bad luck"). I don't understand why this is good at all? If $I$ would always survive the selection, what would go wrong in the algorithm? My guess is that the algorithm would be similar to a greedy algorithm but I am not sure.


texts: Formulate the Marriage Problem into a Maximum-flow problem (Graph theory)

texts:
Suppose I have $M=\{1,\ldots, n\}$ men and $W = \{1, \ldots, n\}$ women and $B =\{1, \ldots, m\}$ brokers, such that each broker knows a subset of $M \times W$ and for each pair in this subset a marriage can be set up among the corresponding man and women.

Each broker $i$ can set up a maximum of $b_i$ marriages and a person can only be married once. Also we assume all marriages are heterosexual.

I want to determine the maximum number of marriages possible and I want to show that the answer can be found be solving a maximum-flow problem.

What I've tried:

Make source and sink nodes with opposite demand. And then for each ordered pair $(i,j)$ where $i$ is a woman and $j$ is a man making a node. For each broker $j$ make a corresponding node and introduce an arc with capcity $b_j$. For each node $(i,j)$ make an arc from broker $k$ with capacity $1$ if broker $k$ can arrange a marriage otherwise $0$.

However, after this I stop. I need to keep track of state, that is no person gets married twice !


texts: Is the outer loop in typical bubble sort algorithm precise?

texts:
I analized  the bubble sort algorithm and I cannot see why they "implemented this way". I wrote down the results as the two loops performed their works and, with my small testing arrays, the outer loop condition to stop was always too much (the array was sorted when "i" was like 2, when the loop conditon to stop was 5.

this.bubbleSort = function(){
     var length = array.length;

      for (var i=0; i<length; i++){ //this loop seems too much

         for (var j=0; j<length-1; j++ ){

            if (array[j] > array[j+1]){

               swap(array, j, j+1);
               }
             }
           }
        };

Is there a possibility that the outer loop will have to reach its limit?  I mean the "i - 1 < length" will be necessary to sort. Is the array length on the outer loop really a precise choice or just a good choice, because it gives a clue of how many inner loop iterations will be needed with some leftover if necessary?

For me it means that the algorithm could be written, somehow, like this

var length = array.length;

  for (var i=0; i< 10; i++){ //I used 10 instead of the array length

     for (var j=0; j<length-1; j++ ){

        if (array[j] > array[j+1]){

           swap(array, j, j+1);
           }
         }
       }
    };


texts: Chomsky Normal Form for context free grammars ambiguous/unambiguous properties?

texts:
My textbook states:

  Finally, it must be stressed that the Chomsky normal form says nothing about ambiguity in general—a CFG in Chomsky normal form may or may not be ambiguous, just like we have for arbitrary CFGs. On the other hand, if you start with an unambiguous CFG and perform the conversion described above, the resulting CFG in Chomsky normal form will still be unambiguous.

I don't really get this. Why does an unambiguous CFG when converted to Chomsky normal form always yield unambiguous CFG? Is it possible for an ambiguous expression to become unambiguous when converting it to Chomsky normal form?

If someone could explain I would appreciate it.


texts: Proof of Simple Properties About Terms, Position of Subterms and Replacement of Subterms

texts:
I am studying term rewriting by reading Baader/Nipkow's book: "Term Rewriting and All That".
I want to prove a lemma about terms, position of subterms and replacement of subterms. The notation is as follows:

$s|_{p}$ denotes the subterm of $s$ at position $p$.
$s[t]_{p}$ denotes the term obtained from $s$ by replacing the subterm at position $p$ by $t$.

The lemma I want to prove is:

Lemma 3.1.4 Let $s, t, r$ be terms and $p, q$ be strings over the positive integers.

If $pq \in Pos(s)$, then $s|_{pq} = (s|_{p})|_{q}$.

If $p \in Pos(s)$ and $q \in Pos(t)$, then
2.1 $(s[t]_{p})|_{pq} = t|_{q}$
2.2 $(s[t]_{p})[r]_{pq} = s[t[r]_{q}]_{p}$

If $pq \in Pos(s)$, then
3.1 $(s[t]_{pq})|_{p} = (s|_{p})[t]_{q}$
3.2 $(s[t]_{pq})[r]_{p} = s[r]_{p}$.

If $p$ and $q$ are parallel positions in $s$ (i.e. $p || q$), then
4.1 $(s[t]_{p})|_{q} = s|_{q}$
4.2 $(s[t]_{p})[r]_{q} = (s[r]_{q})[t]_{p}$

The book provides proof for the first item:

As an example, we show, by induction on the length of $p$ that $s|_{pq} = (s|_{p})|_{q}$ holds for all $pq \in Pos(s)$.
For $p = \epsilon$, we have $pq = q$, and thus $s|_{pq} = s|_{q}$. In addition, $p = \epsilon$ implies $s|_{p} = s$, which shows $s|_{q} = (s|_{p})|_{q}$.
Now assume that $p = ip'$. Because $ip'q \in Pos(S)$, we know that $s$ is of the form $s = f(s_1, \ldots, s_n)$ with $i \leq n$. By definition, $s|_{pq} = s|_{ip'q} = s_{i}|_{p'q}$, and by induction $s_{i}|_{p'q} = (s_{i}|_{p'})|_{q}$. Again, by definition, we obtain $s_{i}|_{p'} = s|_{ip'} = s|_{p}$, which finishes the proof of the induction step.

I want to prove that the other items are also true. I wrote my attempt as an answer, but of course, I welcome other solutions or feedback. Thanks in advance.


texts: Problem with forming a context-free grammar describing a language

texts:
I've been trying for hours to figure out, how to form a CFG describing this language $L$:
$$L=\{ w\in\{a,b\}^* \mid w\text{ is of the form }a^nxb^{n+2}\text{, where }x\text{ is a string of length }3\text{ in }\{a,b\}^* \}.$$

The problem I'm having is related to the first $n$ of $a$'s. I can't wrap my head around how can this be described properly, since the $x$ can also contain 3 $a$'s.

This is my current solution. It does not work because it doesn't take the $n$ $a$'s to the front.

A -> aB | bB
B -> aC | bC
C -> aD | bD
D -> bE
E -> bF
F -> bF | _


texts: Algorithm to find individual, closed groups of lines in a large set of connected lines

texts:
I'm currently trying to write an algorithm that can find individual groups of connected lines within a larger set of lines. The images below should explain this a bit more clearly.

In the first image you can see a set of lines. What I'm trying to do is split those lines into 3 groups, as seen in the second image. The red and green groups share a line.

I can assume that each line has a start and an end coordinate, and each line can belong to one or more groups.

I'm currently trying to write a recursive function that follows each line until it reaches an end point with one or more lines it can follow. At this point the function recalls itself until it's followed the lines back round to the split point. However this is proving unsuccessful.

The output of this example, as shown in the second image, should be 3 separate groups of lines, stored in a list. I'm currently using c#, however I should be able to use a suitable algorithm in any language, including pseudocode. I know there must be an algorithm that can achieve this, however I cannot seem to work it out or find it online.


texts: Simplex Algorithm: Why must the optimal value of the LP lie on the face or vertex of a polyhedron?

texts:
The feasible region of a Linear Program (LP) is $\{x \in {\bf R}^n: Ax \le b, x\ge 0 \}$. This is an intersection of halfspaces, a polyhedron. If the LP is bounded and feasible, its optimal value will be attained on some face of the polyhedron, typically a vertex. A vertex is a point determined by the intersection of n hyperplanes bounding the halfspaces with linearly independent normal vectors. There might be more than n hyerplanes through a vertex. A basis is any subset of bounding hyperplanes that determines a vertex. Some inequalities will be the nonnegativity inequalities, the corresponding variables are called nonbasic and the rest basic. Only the basic variables can take nonzero values.

These are some lecture notes that I'm struggling to understand. Why does the optimal value not lie in say, the center of the polyhedron? Why must the optimal value be on the face or on a vertex? It seems arbitrary to me because there are so many points that lie on the faces. The center makes more sense to me.

Could anyone give me an intuition?


texts: Is physical pages zeroed out before it's mapped to a virtual page?

texts: I don't how this works. According to me if the physical memory is not cleared then there is some security risk as there may be some sensitive information in it from the other processes. How does the kernel take care of this?


texts: What is the time complexity of this recurrence relation?

texts:
T(n) = 12 T(n/(logn)^2) + nlogn
How to find the value of b using masters theorem. I think with the help of masters theorem we can't solve this. Is there any other method ?


texts: When it times to decide the decidability or undecidability, sometimes I see that we can simulate a Turing-Machine on another Turing-Machine. I heard it is related to Universal Turing-Machine. Can you explain what it means that we can simulates a TM on another Turing-Machine? For me, if I have a deterministic automata $M$, then I do understand that $M$ simulate on a input $w$, but the case for the question is so confusing to me.


texts: Why $\theta/2$ in common qubit representation?

texts: If we take angle names as shown on the Bloch sphere below and a typical qubit representation written as $\cos(\theta/2)|0\rangle + \mathrm{e}^{-\mathrm{i}\phi}\sin(\theta/2)|1\rangle$, why do we divide $\theta$ by $2$ in the cosine and sine parameters?


texts: Contraint with three variables into three binary constraints

texts:
I'm having a hard time tackling the following problem (perhaps some key data is missing). We have a constraint:

$A+B= C$

One is supposed to represent this one constraint using three binary constraints. Is this even possible? No domain is given, but even if it was, I really don't see how this could be achieved...


texts: Can I make last part of counting sort become to be starting from lowest index?

texts:
Counting sort is originally like below code.

for (int i = 0; i <= 5; i++) c[i] = 0;
for (int i = 1; i <= 8; i++) c[a[i]]++;
for (int i = 1; i <= 5; i++) c[i] = c[i] + c[i - 1];
for (int i = 8; i >= 1; i--) {
    b[c[a[i]]] = a[i];
    c[a[i]]--;
}

In the above, last for loop iterates from last index because of stability of counting sort.

But, I want to iterate from first index 1 as well as maintaining the stability of sorting.

I'm trying and thinking lots of time, I cannot do. How can I do?


texts: Problem about getting a value of the hashed password

texts:
Given a database with usernames and the first six bytes of their hashed passwords. A standard hashing function has been used for hashing.

admin 827ccb0eea8a

user c3981fa8d26e

operator 5f4dcc3b5aa7

guest 084e0343a048

The password of admin is 12345.
What value of the hashed password will be added to the database after the creation of the username operator with the password qwerty123?

How can I solve this problem? Any tips?


texts:
Many years ago I read a GC survey paper that was updated every few years with advances; I tried to find such a paper today to point a questioner on Stackoverflow at.

However all I can find is very old survey papers that don’t include current thinking on items like hardware assistance.


texts: Transport Triggered CPU Architecture MOV and Turing Completeness

texts:
Reading up on TTA CPU designs and the wikipedia article states that

  Some TTA implementations support conditional execution.

The trick to make an TTA ISA Turing-complete with an unconditional MOV instruction escapes me. Can anyone explain how that would work?
(or share some resources where it is explained)


texts: Algorithm(s) for creating balanced 5-a-side teams?

texts:
I play 5-a-side soccer twice a week. 10 people play each game out of a pool of about 30 people who are giving the opportunity to play as it's first come first serve. Some people play more often than others.

The best matches are the ones where the score stays even throughout the game because they are the most competitive. Our rules are as following: first team to score 5 goals gets 1 point then the goals count resets.

The problem is figuring out how to pick balanced teams. I am going to program a script to log teams and scores over time and I am wondering what algorithm(s) can I use to generate the teams based on this history keeping in mind that we wont always have the same 10 players but we might have the same 8 players, etc?


texts: How is the Longest Common Sub-sequence of two sequences is a special case of the Sequence Alignment problem?

texts: Could anyone briefly show me how the Longest Common Sub-sequence of two sequences is a special case of the Sequence Alignment problem? I cannot wrap my head around this. Thank you.


texts: What does the language {a, b, c}* exactly mean? How will the automaton for this look like?


texts: What is the largest possible minimal 3CNF formula as function of the number of variables?

texts:
I have already defined here what is minimal 3CNF formula.

In the answer to the question, D.W. answered:

What you are thinking is wrong. A minimal, unsatisfiable formula can have more than 8 clauses.

In response to:

In a minimal k-cnf formula, there should be 2k different k literals clauses exactly, so in a minimal 3CNF formula, there should be 23=8 different 3 literals clauses exactly.

So my question is now, what is the largest possible minimal 3CNF formula or how many clauses there are in the largest possible minimal 3CNF formula, i.e. what is the maximum number of clauses in the largest minimal 3CNF formula as function of n, where n is the number of variables in the 3CNF formula.

Is it $O(n)$? Is it $O(log(n))$? Is it $O(1)$, but just larger than 8?


texts: Dynamic Programming: Sum from two subset sums subtracted from each other

texts:
There are n values given. Is there a possibility to have two Arrays A and B each containing elements from the given values such that the sum of all elements of A minus the sum of all elements of B gives the searched value? Each value can be used twice, but not twice in the same subset, so once in A and once in B at most (not necessary to use all the values in either A or B)

I was thinking of calculating every subsum and then, if one of the subsums is greater than the sum we want to reach, we search another subsum such that if we subtract it from the first sum we reach the searched value.

I don't think my idea is very efficient, nor dynamic. Any ideas how this problem could be solved dynamically?


texts: Why do relational databases use 2PC for distributed transactions over the likes of Paxos?

texts:
Paxos is more powerful and in the famous writing "Consensus on Transaction Commit" : http://research.microsoft.com/pubs/64636/tr-2003-96.pdf, Jim Gray and Leslie Lamport describe 2PC as a special case of Paxos.

Why do relational database use 2PC in real world? Also 2PC is not fault tolerant because it uses a single coordinator whose failure can cause the protocol to block.


texts:
In a process like
$$
R \stackrel{def}=((a.\bar{b}.0)\setminus\{b\})[a\to b]\mid(\bar{b}.b.0)+\bar{b}.c.0
$$

$b$ is restricted to perform on the inner process of RHS $(a.\bar{b}.0)\setminus\{b\}$, thereafter the $a$ is relabeled to $b$.
What I am confused is in drawing the LTS of it, the $a$ action occur at first process (we can have a transition with label $a$ in the LTS) and it is the next process that renaming takes place?
can the following LTS be valid as first actions transitions? (the bar is replaced by underline)


texts:
Are there any known "hard" instances for NP-Complete Problems,

or are there no general hard instances. So for different algorithms different instances are hard?


texts: Is the language of words having same number of a's and b's context-free?

texts:
I'm trying to use the pumping lemma, to show that the language $$L = \{w \in \{a, b\}^+: na(w) = nb(w)\}$$ is not context free, where $na(w)$ is the number of $a$'s in $w$ and $nb(w)$ is the number of $b$'s in $w$.
I have this: By contradiction, if $L$ is context free, we use the pumping lemma, then let $N$, and $w = a^{floor(N/2)}*b^{floor(N / 2)}$, with $|w| = N$. Then if we divide $w = uvxyz$, with $v \not = \epsilon$ and $x = \epsilon$, we see that when repeating v there appear more a's than b's, then $uv ^ kxy ^ kz$ $\notin$ L. Contradiction.
Is this right or am I missing something?


texts: Why do most books say that a 1 bit branch predictor mispredicts on the first loop iteration?

texts:
I am reading two books, Computer organization and design by David A Patterson, and Digital Design and Computer Architecture by Harris and Harris. These books claim that a 1 bit branch predictor mispredicts on the first and last iterations of every loop.
I don't understand why it mispredicts on the first iteration. I think that the first prediction result depends on the history of the CPU, so we don't know whether the predictor would predict correctly or not.
My question is whether I have to assume that the initial state of the 1 bit predictor is for the branch to be taken.


texts:
Supposing we have two grammars which define the same languge: regular one and LALR(1) one.

Both regular and LALR(1) algorithms are O(n) where n is input length.

Regexps are usually preferred for parsing regular languages. Why? Is there a formal proof (or maybe that's obvious) that they are faster?


texts: Can an alphabet be $\{ε\}$ or $\mathbb{N}$?

texts:
Hopcroft says it is a finite nonempty set of symbols.

$\varepsilon$ (empty string) is not an ordinary symbol.
$\mathbb{N}$ is not finite.
So, no to both?

On the other hand, I do not see why $\{\varepsilon\}$ cannot be an alphabet. Its Kleene closure is $\{\varepsilon\}$, so a language over this alphabet can be either $\{\varepsilon\}$ or $\emptyset$, both of which are valid languages.

For the alphabet $\mathbb{N}$, I have seen on Wikipedia that an alphabet can contain an infinite number of symbols, so which claim is true? Hopcroft or Wikipedia? Personally, I do not see why that would not work.


texts: How to get 2-LOOKAHEAD results in this grammar?

texts:
G:
S -> bRS | RcSa | @(epsilon)
R -> acR | b

....

2-LOOKAHEAD(S->@) = {$,a,aa}
2-LOOKAHEAD(R->b) = {b,ba,bb,bc}

I don't understand a result of these rules..

----+

when I tried to solve 2-LOOKAHEAD(S->bRS), it solve easily.( {ba,bb} ).

but I don't understand why 2-LOOKAHEAD(S->@) results are {$,a,aa} and

2-LOOKAHEAD(R->b) are {b,ba,bb,bc}. Please explain how to get these results.


texts:
Sell (Bar, Beer)
I want a table in which the first column has the name of the beer and the second has the total number of bars which sell that beer, but I have no idea how to use count () in the right way to obtain this.
Could it be Beer G count(Bar) as count_bar (Sell) ?
And later that, how could I set a table with the best-selling beer (or the best-selling beers)?


texts: Amortized analysis of virtual, dynamic array using potential function

texts:
You often want to implement an array $A$ where the length fluctuates over time. If at some point $A$ has length $n$, then you would like to use space $O(n)$. Consider the following: At all moments, a virtual array $A[0...n-1]$ is simulated by an actual array $B[0...m-1]$ where $m\ge n\ge 1$. Initially, $m=n=1$.

Extend: If $n<m$: increment $n$ and set $B[n-1] = NULL$. Else: set $m=2m$, allocated a new array $B'$ with length $m$, copy $B[0...n-1]$ to $B'[0...n-1]$, deallocate $B$, rename $B' $to $B$, increment $n$, and set $B[n-1] = NULL$.

Show, using a potential function, that the amortized cost of $N$ extend operations is $O(N)$.

The potential function I was thinking of using was $r(s)$ defined as the number of elements in the virtual array $A$ at time $s$. So $r(0) = 0 \le r(s)$ for $s > 0$.

However, when I calculate the potential of the extend operation, I get $r(s+1)-r(s) = n+1-n = 1$ (i.e. the number of elements in the array after the operation minus the number of elements in the array before the operation). Yet, the actual amount of work seems to be much higher in the "else" case $\Rightarrow 2m$ (to allocate new array $B'$) $+n$ (to copy from $B$ to $B'$) $+m$ (to deallocate $B$) $+3$ (to rename, increment, and set to $NULL$).

So the amortized cost (equal to actual cost + potential cost) is clearly not $O(1)$, and so the cost of $N$ extend operations will not be $O(N)$. What am I doing wrong here?


texts: What is the difference between Big-O and worst-case run time?

texts:
Big-O describes an upper bound on run time. Is that not the definition of "worst-case"?

For example, how can we say that a hash table insertion require O(1) time on average? Constant time is the best case, n time is the worst case. How can an upper bound describe an average run time? In what sense is that bound "upper"?


texts: Use closure properties to transform languages to $L := \{ a^nb^n : n\in \mathbb N \}$

texts:
For the purpose of proving that they are not regular, what closure properties can I use to transform the languages

$L_a = \{ a^*cw \mid  w \in \{a,b \}^* \land  |w|_a = |w|_b \}$ and
$L_b = \{ab^{i_1}ab^{i_2}\ldots ab^{i_n} \mid  i_j∈\mathbb N \land \exists j∈[1,n]  \ i_j \not= j \}$

to  $L := \{ a^nb^n \mid n\in \mathbb N \}$, respectively?

I tried:

$L_a = \{ a^*cw \mid w \in \{a,b \}^* \land  |w|_a = |w|_b \}$

$L_a' = \{ \{a,d\}^*cw \mid w \in \{a,b,d \}^* \land  |w|_a + |w|_d = |w|_b \}$ (union?)

$L_a'' = \{ d^*cw \mid w \in \{a,b \}^* \land |w|_a = |w|_b \}$
(concatenation?)

$L_a''' = \{ w \mid w \in \{a,b \}^* \land |w|_a = |w|_b \}$
(homomorphism?)
$L_b = \{ab^{i_1}ab^{i_2}\ldots ab^{i_n} \mid i_j∈\mathbb N \land\exists j∈[1,n] \ i_j \not= j \}$

$L_b' = \{ab^{i_1}ab^{i_2}\ldots ab^{i_n} \mid i_j∈\mathbb N \land\forall j∈[1,n] \ i_j = j \}$  (complement?)

$L_b'' = \{ac^{i_1}ac^{i_2}\ldots ac^{i_n} \mid i_j∈\mathbb N \land\forall j∈[1,n] \ i_j = j \}$ (homomorphism?)


texts: Is automaton not practical in real coding?

texts:
This question relates with this question and answer.
May I know why "Writing a structured program for any tangle of an automaton is possible in principle, but probably not worth the hassle (translating arbitrary transfers of control into a nice structure -- for some non-trivial value of "nice" -- is a lot of work, and making sure both check out even more so)" and why "it's rarely done in practice"?
Does that mean automaton is not useful in practice (real coding)? In terms of translating the automaton into a code. If not useful, then what is used in practice? Is automaton still useful in problem solving though?


texts: Prove $L = \{M \mid L(M)\text{ is infinite}\}$ is not Turing-recognizable

texts:
I'm supposed to prove this through mapping reducibility. I think I'm supposed to show that $A_{\mathrm{TM}} \le_\mathrm{m}\overline{L}$, which means that $\overline{A_{\mathrm{TM}}}\le_\mathrm{m} L$ and, since $\overline{A_{\mathrm{TM}}}$ is not Turing-recognizable, then $L$ is not Turing-recognizable.

I think that $\overline{L} = \{M\mid L(M) \text{ is finite} \}$ and that it means that $L(M)$ contains a finite number of strings.

I don't know how to construct a Turing machine that can prove $A_{\mathrm{TM}}\le_\mathrm{m} \overline{L}$.


texts:
Imagine a Fibonacci heap with 1 tree: a root node, 4 child nodes (to that root node), with 2 of them being leaves and the other 2 having 1 child each (7 nodes total). Is this a legal Fibonacci heap? In other words, does there exist a series of actions that lead to this sort of heap structure.

My intuition tells me no, because it just seems too "unstructured". On the other hand, it doesn't seem to violate the max degree property or any other basic properties of a Fibonacci heap.

I thought about extracting the minimum and seeing if that'll lead to an illegal heap, but it doesn't seem to be the case.


texts: What is the average-case complexity of trial division?

texts:
The trial division algorithm for checking if a number $N$ is prime works by trying to divide $N$ by all integers in the range 2, 3, ..., $\lfloor \sqrt{n} \rfloor$. If any of them cleanly divide $N$, then we say that $N$ is composite; otherwise we say that $N$ is prime.

In the worst case, this requires $O(\sqrt{N})$ divisions to be made. However, this only happens in the case where $N$ is prime. If $N$ is a composite number, then we might stop much earlier than this.

I'm curious about the average-case complexity of this algorithm, assuming that the input is a natural number chosen uniformly at random. Since there's no way to choose an natural number uniformly at random, I'm curious about the asymptotic growth rate of

$$\mathbb{E}[T(X_n)]$$

where $X_n$ is a random variable that takes on a value from $\{2, 3, 4, 5, ..., n\}$ uniformly at random and $T(N)$ denotes the number of divisions made by the trial division algorithm when run on the number $N$. Since the number of divisions made is equal to the smallest prime factor of the number in question, and since the number is chosen uniformly at random, this expression is equivalent to

$$\frac{\sum_{i=2}^n \xi(i)}{n-1}$$

where $\xi(i)$ denotes the smallest prime factor of $i$.

I have some thoughts about what this might look like, but I'm not sure how to formalize them. First, there's the observation that about half the integers in $\{2, 3, 4, 5, ..., n\}$ are divisible by two, about a third are divisible by three, etc., so for many numbers very few divisions are required. Second, there's the prime number theorem that gives a good asymptotic estimate for the density of the prime numbers. However, I'm having trouble seeing how to combine all this information together.

Does anyone know how to determine the asymptotic growth rate of this expression?


texts:
$S \rightarrow AB$

$A \rightarrow aA \mid bA \mid \epsilon$

$B \rightarrow aBb \mid \epsilon$

Does this grammar generate regular language?

According to me this grammar generates language of the form
$$
L = \{ (a+b)^* a^nb^n \mid n\ge 1\}
$$

I think it's a DCFL. If the condition would have been $n\ge0$ then it's regular according to me. But my book says it's regular language.

Am I correct ?


texts:
I came across a problem about a cashier scanning goods that I'm stuck on. I paraphrase the question below.

A cashier only has x time to scan a person's goods. The goods come 1
item per time step in a conveyor belt. In one time step, the cashier
can either scan an item or bag the item (so when bagging, the cashier
misses the item on the conveyor belt for that time step). The place to
hold scanned, unbagged goods has a max capacity of c, where each
good takes 1 unit space. However, once the cashier starts to bag
scanned items, the cashier must bag all unbagged scanned items. The
cashier also wants to ensure he makes the most money possible. How
would the cashier go about choosing the goods such that he maximizes
the amount of money the buyer spends. What is the maximum amount of
money the cashier can make?

This seems to be a modification of the 0-1 knapsack problem, where the max capacity c is the max capacity of the knapsack, the price of the item is its value in the knapsack, and all items have a 1 unit space. I am, however, confused about how I would incorporate the "conveyor belt" of missing items and the moving of items out of c into the algorithm. I imagine this could still be run in $O(nc)$ time with $O(c)$ space complexity (in fact the original problem statement says it should be possible in these bounds). How would I go about modifying the 0-1 knapsack problem for this?


texts: Finding a tight bound for a recurrence relation

texts:
Problem:
Give tight asymptotic bounds $( \Theta )$ for the following function:
$$ T(n) = T(n-2) + n $$
Answer:
We are not given the base case. I am going to assume that $T(0) = 0$ and $T(1) = 1$. Here are some
values for the function.
$$T(2) = T(0) + 2 = 2$$
$$T(3) = T(1) + 3 = 4 $$
$$T(4) = T(2) + 4  = 6 $$
$$T(5) = T(3) + 5 = 9 $$
$$T(6) = T(4) + 6  = 12 $$
$$T(7) = T(5) + 7 = 16 $$
$$T(8) = T(6) + 8 = 20 $$
$$T(9) = T(7) + 9 = 25 $$
$$T(10) = T(8) + 10 = 30 $$
It is growing faster than $O(n)$ time. I am fairly sure that $T(n) \in O(n^2)$. That is, $O(n^2)$ is an
upper bound. If $T(n)$ is $\theta(n^2)$ then going from $n = 5$ to $n = 10$ we would expect, about, a
factor of $4$ increase. We got an increased by a factor of $\frac{ 10}{3}$. I am thinking that the correct answer is:
$$T(n) = \Theta(n^2)$$.
However, I do not know how to prove that it is correct? or disprove it?


texts: Computational Complexity of a Matrix Multiplication

texts: I am computing a matrix multiplication with inverse operation $AB^{-1}C$ $A \in \mathbb{R}^{m \times n}, B \in \mathbb{R}^{n \times n}, C \in \mathbb{R}^{n \times o}$. So the inverse operation takes $O(n^3)$. Multiplying $B^{-1}C$ takes $O(n^2o)$ and multiplying $A(B^{-1}C)$ takes $O(mno)$. So the overall time complexity is $O(n^3 + n^2o + mno)$. Kindly correct me if I am wrong ?


texts: Probabilistic analysis of finding 2nd largest value in vector

texts:
Given the following algorithm for finding the second largest element in a vector:

2ndMAX(v):
  n = length of v
  largest = 0
  second_largest = 0
  for i in 1 to n:
    if v[i] > largest:
      second_largest = largest
      largest = v[i]:
    else if v[i] > second_largest:
      second_largest = v[i]
  return second_largest

How many assignments is the algorithm expected to make to second_largest?

I can see the asymptotic lower and upper bounds on the problem, but how can I approach this probabilistically and give the expected number of assignments?

For the maximum I suppose it is N/2 assignments; but for the 2nd largest I am getting confused. I am trying to divide the cases in: largest comes before second largest, so there are no more assignments past the second largest, but there may be before the largest and between the largest and second largest. But it gets complicated really quickly. I also tried some inductive analysis but couldn't get too far.


texts: Matrix whose eigenvectors are Hermite polynomials

texts:
I first constructed a symmetric matrix as the Laplacian operator, and its eigenvectors are a series of harmonics functions as expected. I programmed it and convinced myself. The matrix looks like:
$$
\left(\begin{array}{ccc}
1& -1 & 0 & 0 & 0 \\
-1& 2 & -1 & 0 & 0 \\
0& -1 & 2 & -1 & 0 \\
0& 0 & -1 & 2 & -1 \\
0& 0 & 0 & -1 & 1\end{array}\right)
$$
multiplying this matrix with $\{x_0, x_1, x_2, x_3, x_4\}$ leads to $\{x_0-x_1, -x_0+2x_1-x_2,-x_1+2x_2-x_3,..\}$; The term $-x_{i-1}+2x_i-x_{i+1}$ is equivalent to the second order derivative (in the Laplacian) on a discrete 1-dimensional domain: $(x_i-x_{i-1})-(x_{i+1}-x_i)$.

Everything works fine until I try to construct the matrix for Hermite polynomials. Wiki says the operator is
$$
L[u]=u''-xu'=-\lambda u.\tag1
$$
I think the matrix for the first derivative should be
$$
\left(
\begin{array}{ccc}
1& -1 & 0 & 0 & 0 \\
0& 1 & -1 & 0 & 0 \\
0& 0 & 1 & -1 & 0 \\
0& 0 & 0 & 1 & -1 \\
0& 0 & 0 & 0 & 0\end{array}\right)
$$
however, combining this new matrix with the Laplacian matrix (according to $(1)$) does not produce the expected eigenvectors.

Another source derives polynomial from the operator
$$
H=-\frac12\frac{d^2}{dx^2}+\frac12x^2,
$$
but what are the matrix entries for $x^2$?

Any help? Thanks!


texts: Concept of Weights in Principal Component Analysis"

texts:
I have got a confusion in PCA:

Is the concept of weight same as Eigenvalues  as discussed in the research paper Eigenfaces for Recognition by Matthew Turk and Alex Pentland:

  efficient way to learn and recognize faces would be to build up the characteristic features by experience over time and recognize particular faces by comparing the feature weights needed to (approximately) reconstruct them with the weights associated with known individuals. Each individual, therefore, would be characterized by the small set of feature or eigenpicture weights needed to describe and reconstruct them—an extremely compact representation when compared with the images themselves.


texts: Proof that n-dependent Set in Graph theory is NP Complete

texts:
Consider an undirected graph $G$. A subset $S \subseteq V(G)$ is n-dependent if for every $x \in S, d_{<S>}(x) \leq n-1$. The n-dependence number of $G$, denoted $\beta_n(G)$, is maximum cardinality of an n-dependent set of $G$. That is, the n-dependence number of $G$ is the maximum cardinality of a subset of vertices $S$ such that $\Delta(<S>) < n$.
Consider the following question:
Instance: Given a graph $G$ and positive integers $n$ and $k$
Question: Does there exist $S \subseteq V(G)$ such that $S$ is an n-dependent set and $|S| \geq k$?
Prove that the n-dependent set problem in undirected graphs is NP-complete
This was a midterm question and my answer was this:

For the sake of argument let's assume that there exists an algorithm $\mathcal{A}(G, n, k)$ that can solve the given problem in polynomial-time. Now let's say we are given an undirected graph $G$ with a number $k$ and are asked to check if the graph contains an independent set of size $k$. To solve this problem in polynomial-time, we are going to call $\mathcal{A}(G, 1, k)$. But since the independent set decision is NP-complete, we can't solve it in polynomial-time, hence $\mathcal{A}$ does not exist.

I can't understand why this answer is wrong (I got 0). Please explain.


texts: Why is the time complexity of the word break O(2^N)

texts:
I am trying to understand the time complexity of the word break problem which uses the backtracking recursive approach. It is O(2^N).

Well lets take an example abcd as input with the recursive approach naive, the recursion tree will be something like this

                      abcd
                     /.... \
                    /\     /\
                   a bcd..abc d
                     /  \
                    /\
                   b  cd

So eventually at the end of the tree, I mean the leaves the count will be (2^N). is that right?


texts: How does a minimal DFA ensure minimal computational cost?

texts:
I just went to read wikipedia to check a point on FA minimization, and
I read there the following sentence:

  The minimal DFA ensures minimal computational cost for tasks such as
  pattern matching.

I have tried to imagine how, but my feeling is that DFA minimization
reduces the size of the program, which is especially important when it
is hardware, but will hardly do anything to speed up the computation
(well, indexing states might be easier when there are less states, depending
on computation model, but this seems far fetched).

Of course, from an abstract logical point of view, a minimal DFA does ensure
minimal computational cost, when that same cost is ensured by any DFA
for the language.

Am I missing a point? Which?


texts:
I'm relatively new and am still learning the basics. I've used NVIDIA DIGITS in the past, and am now looking at Tensorflow. While I've been able to fumble my way around creating some models for a few projects I'm working on, I really want to start diving deeper into what I'm doing, how I'm doing it, and ultimately a better understanding of why.

One area that I would like to start with is the Images that I'm using for training and testing. Can anyone point me to a blog, an article, a paper, or give me some insight in what I need to consider when selecting images to train a new model on. Up until recently, I've been using datasets that have already been selected and that are available for download. Lets say I'm going to start working on a project that involves object detection of ships from a variety of distances and angles.

So my thoughts would be

1) I need a large quantity of images. 2) The images need to contain ships of the different types I would like to detect. (lets just say one class, ships, don't care what type of ships) 3) I also need to have images that have a great variety of distance perspective for the different types of ships.

Ultimately, my thoughts are that the images need to reflect the distance, perspective, and types of ships I would ideally want to identify from the video. Seems simple enough.

However, there are a number of questions

Does the images need to be the same/similar resolution as the camera I'll be using, for best results? Does the images all need to be the same resolution? Can I use a single image and just digitally zoom out on the image to give the illusion of different distances?

I'm sure there are a number of other questions that I'm not asking, or should be asking. Are there any guide lines available for creating a solid collection of images to use when creating the collection of images for training and validation?


texts:
I am trying to understand the runtime complexity of the below code in terms of n.

I know that it is $Θ(n^{4/3})$, but I don't get why.

I thought the outer loop runs $log(n)$ times, the second one runs $n^{1/3}$ times and the innermost runs $O(log(n))$ times as it runs $i$ times and $i$ is at most $log(n)$. This would add up to $log^2(n)*n^{1/3}$, right?

for (int i = 1; i ≤ n; i = 2 ∗ i) {
    for (int j = 1; j∗j∗j ≤ n; j = j + 1) {
        for (int k = 1; k ≤ i∗i; k = k + i) {
            f();
        }
    }
}

( f() runs in constant time)

Thanks for any help!


texts: CSP heuristics to help avoid redundancy while checking values for constraint inconsistency?

texts: I'm a complete beginner. Please forgive my ignorance.Trying to learn about CSP online, I noticed a lot of the focus on search methods and heuristics which tell you which variable to expand next (e.g. most constrained variable) and those that tell you which value to try first (e.g. least constraining value) but I've yet to see heuristics that relate to constraint checks. Since I'm doing everything by hand, I notice a lot of redundancy when eliminating values from variable domains. How do you go about checking for violated constraints in a way that is efficient? Say constraint A will have me eliminate odd numbers 1 to 1000 and constraint B will have me wipe out everything above 250. Intuitively, it feels like order matters as I would waste my time cherry picking even numbers above 250 to only later find out that anything above 250 was not consistent in the first place. I apologize for lacking the proper terminology, my understanding is mostly intuitive. I hope it makes sense. Thanks in advance! I'm mostly looking to acquire a conceptual understanding of selected topics in computer science so if you have book recommendations or any resource that would be appropriate for me as an interested layman, please don't hesitate!


texts: The exact relation between complexity classes and algorithm complexities

texts:
Are all algorithms which have polynomial time complexity belong to P class ? And P class do not have any algorithm which does have not polynomial complexity ?

Are all algorithms which have non polynomial complexity belong to NP or NP-Hard or both ?

I am just trying to understand the basic relationship.


texts:
Say that for a particular problem, e.g., the independent set problem, it has been shown that no polynomial-time algorithm exists to solve it.

Could we get around this by finding an algorithm which approximates the solution to a certain accuracy?

That is, would the result above bar the existence of an algorithm which finds a maximum independent set to an accuracy of 0.5? I.e., it is guaranteed to be less than 0.5 away from the size of a maximum set? (And hence implying that it actually is a maximum independent set.)

It seems to me that the latter wouldn't violate our proofs of non-tractability, which are discrete in nature, while still giving an answer that satisfies the problem from a practical perspective.


texts: What Exactly Does the Term "Key" Mean with Regards to a Hash Table?

texts:
I know it is supposed to be some arbitrary term that is a stand-in for a large class of possible objects.

But I still don't understand what part of the array the term "key" is meant to represent or denote.

Does it mean an element of the array? The index of the element of the array? Some arbitrary function from the elements of the array to some subset of the natural numbers?

EDIT: Since many people seem not to understand the question, here is a quote from Introduction to Algorithms by Cormen et al.

  "With direct addressing, an element with key $k$ is stored in slot
  $k$. With hashing, this element is stored in slot $h(k)$; that is, we
  use a hash function to compute the slot from key $k$. Here $h$ maps
  the universe $U$ of keys into the slots of a hash table $T$... We also
  say that $h(k)$ is the hash value of key $k$."

It seems to me that the key, element index, and hash value are all different based on this.

Here is where the term is introduced in the chapter for the first time in a formal manner:

  "Suppose that an application needs a dynamic set in which each element has a key drawn from the universe $U=\{0,1,\dots,m-1\}$, where $m$ is not too large. We shall assume that no two elements have the same key."

From this I would draw the conclusion that a universe of keys cannot exist for a multiset of integers which allows duplicate values, since the former is a finite set which is in bijection with all possible elements of the array (implying that the set of all possible elements of the array is finite), whereas the latter has no bound on its cardinality (since it can increase in size with every operation, hence the "dynamic", and there is no bound to the number of elements which can be added because (1) duplicate elements are allowed and (2) the number of possible integers is infinite).

Context:

For instance, when discussing the "pth-smallest key" algorithm, you want to find the "key" with the pth-smallest "rank" -- so the "rank" is different from the "key", and you want to sort the "ranks" of the "keys", but usually the "keys" are numbers too, so why not sort them? And why would there be a "rank", a "key", a "hash value", an array element, and an array element index?

As another example of where seemingly imprecise terminology is confusing me, consider a dynamic multiset $S$ of integers which allows duplicate values. Would this object allow a hash function? If it would, what would be the "keys", and what would be the "hash values"? Both the universe of keys and the target space for the hash function are supposed to be finite, whereas $|S|$, the cardinality of $S$, is clearly potentially unbounded, and in fact any integer can appear arbitrarily many times -- so how could anything associated with this problem be a "key"?

It is seemingly similar to other problems that admit hash functions.


texts: Why isn't the Swift programming language type inference more aggressive?

texts:
Couldn't the type inference in Apple's new programming language Swift had been done more aggressive? For instance why can't the return type of a function be deduced?

func sayHello(personName: String) -> String {
   let greeting = "Hello, " + personName + "!"
   return greeting
}


texts: What are the rudimentary types of information connectivity i.e. model types?

texts:
I am looking at a modelling tool and are trying to determine all the types of ways that you can model (at a rudimentary level)
I remember seeing a list of ways in which you can connect or categorise information elements. basically the types were as follows:

Lists - constitute a list of information elements

Hierarchies- visualise information in a parent-child relationship (ie organisational chart)

Flows - connect elements in a logical (lateral) flow (ie process model)
Have you seen any reference to these types, or can you elaborate on the full list of "model types"


texts: What is the depth of recursion if we split an array into $\log_2(n)$ with each recursive call?

texts:
We have a function which takes an array as input. It breaks an array into $\log_2(n)$ parts with equal sizes where $n$ is the size of the subarray. It keeps breaking each of the subarrays until there are only two elements left in it.  What is the depth of this recursion?

Example of the process:

First we have $n$ elements and break them up into $\log_2(n)$ parts with equal sizes. Each of these parts has $\frac {n} {log_2(n)}$ elements in it. In the next level of recursion we will break each of the subarrays into $log_2(\frac {n} {log_2(n)})$ parts again with equal sizes. These will now have $\frac {\frac {n} {log_2(n)}} {log_2(\frac {n} {log_2(n)})}$ elements in each one of them. And we keep on breaking the array in this manner until we reach a subarray with only two elements in it.


texts: Finding all paths with lengths in a fixed interval in sparse graphs

texts:
What is the most efficient way to find all paths of length M to N in a large sparse graph?

Some general information:

Graph has 30,000 to 50,000 nodes
Average number of edges per node ~ 10
M=4, N=7
Graph has cycles


texts: Dijkstras Algorithm with Bounded Integer Edge Weights

texts:
I don't really understand how we can use the fact that the edge weights are integers in the range [1, 2, ... , C] in order to speed up the computation of Dijkstra's algorithm. I read this lecture but I still don't really get it. I understand why we make an array of size |V|C + 1 holding buckets where we put nodes with length i in bucket i. But from that point on I can't really wrap my head around how it'd help us solve it any faster.

I suppose we start off with putting the startnode s in the 0:th bucket and then putting its neighbors in their respective buckets, but that's just the normal algorithm. How does it change from there?


texts:
I have a numpy array of shape N_Samples x 360, as an example, consider the following:

 [ 89 94 56 - - - 55] <-360 length vector
 [ 56 98 55 - - - 98]
 |                  |
 |                  |
 [ 67 55 99 - - - 77] Total N such vectors

There is one label 0 or 1 corresponding to each of the 360- length vector I am asked to train this using CNN but everywhere I am observing that CNN is used for image classification. I am confused about the following:

Is CNN appropriate for such data?
If yes, then how concepts like max pooling and strides are
applicable?
Should we use Conv1D instead of Conv2D?

I will also appreciate if some helpful papers or blogs are provided with respect to this context on how to adjust shapes of input and weight.

Edit:
The 360-length vector is showing ECG signal values of one heartbeat. Keeping R-peak in the middle, I have 180 signal values after and 180 before the R-Peak to have 360 long chunks represent heartbeats (Sampling Rate: 360). I am using it to classify each heartbeat as arrhythmic or non-arrhythmic.


texts: Assuming the Exponential Time Hypothesis is true, what's the fastest possible algorithm that can be produced for NP-complete problems?

texts:
Assuming the Exponential time hypothesis is true, what's the fast possible algorithm that can be produced for NP-complete problems?

If 3-Sat takes exponential time, then could it be possible that some NP-complete problems can be solved in $n^{log^k(n)}$ time? $2^{n^{1/log(log(n))}}$ time? $2^{n^{0.5}}$ time?


texts:
The problem says to find the shortest way (the smallest amount of intermediary points), with given source and destination points, such that between two consecutive intermediary points there are two alternative routes. Also, all the
connections between the points on the map are given.

I understood that the problem is about a graph with given edges and that i have to find the shortest path between two given nodes, but i didn't understand how to search the right path with the given condition (2 alternative paths between every two intermediary nodes).
Is the BFS algorithm applicable in this case? And wich other algorithm could I also use?

Thanks in advance for help!


texts: Linked allocation in operating systems: why not use a doubly linked list?

texts:
I'm reading here that linked allocation uses a linked list, where each block has a pointer to the next block. For sequential access, this would take moving through the blocks one by one. Would it not better to use a doubly linked list so that this time could be cut in half?
Algorithmic analysis
I understand that sequential access remains ( O(n) ) worst case time for both singly linked list and doubly linked list. But non-asymptotically the time spent does become half.


texts:
I don't understand why GCD is not Strongly Polynomial Time?

Can you explain in an example, why the storage size cannot be Polynomial Bounded?

So is GCD in the Complexity Class P?


texts: Best Algorithm for searching for an index in an array such that A[i] = i

texts:
Recently i got a question in one of my exams about asking for an algorithm which searches an element in a sorted array such that $A[i] = i$. My algorithm was based on binary search and did a $O (\log n)$ order of comparisons.
The other part of question demanded to prove there exists no other algorithm which does better than this. I tried to design an adversarial argument but it didn't seem to go in the correct direction. How can one go about proving this with an adversary argument , if one exists. Other approaches to proving this are also welcome.
My algorithm works as follows :

Search(A , start , end)
  Find mid
  if A[mid] > mid // the element with A[i] = i cannot exist in A [mid ... end]
    Search (A,start, mid-1)
  else if A[mid] < mid // the element with A[i] = i cannot exist in A [start... mid]
    Search(A,mid+1,end)
  else if(A[mid] = mid)
    return A[mid];
  else
    return false;
end

Edit: edit contains my algorithm. Kindly forgive any typesetting errors


texts: Create an Finite Deterministic Automata for a regular expression

texts:
I want to create a finite state machine that accepts the following language:
$$
L=\{w\in\{a,b\}^* | w \text{ contains abb but not on the first position}\}
$$
So I began by writing a regular expression from this and this is what I came up with:
$(a+b)(a+b)^*abb(a+b)^*$
And for the finite state machine I tried to do this:

But it doesn't work since I can go from qo->(a)q1->(b)->(b)q1 and have $abb$ at the begining. How should I approach this? How should I approach to create a finite state machine when for example I have the regular expression? How should I develop an intuition without using algorithms such as FollowPos?


texts: Converting a greedy algorithm to a dynamic programming algorithm

texts:
Suppose I have a greedy approach to solve a certain problem. Say, I wish to solve the problem of coloring a particular graph. Now, my naive approach would be:

First, find a maximum indpendent set of vertices in the graph, and give it one color.

Next remove the set of vertices found in the previous case from the graph, and repeat the same process till I reach the empty set.

Now, I agree that it is hard to find the maximum independent set of an arbitrary graph. But, is there a way where this greedy sort of simple algorithm could be converted to a dynamic programming type algorithm? Say, may be we could decompose the graph into two simpler graphs and find maximal independent sets in each of the subgraphs, and then try to club the two individual independent sets to form a larger independent set by checking for adjacency. Is such a kind of 'conversion' from greedy to dynamic programming or vice-versa always possible? Can this change the complexity of the problem radically? Thanks beforehand.


texts: Contradiction proof for inequality of P and NP?

texts:
I'm trying to argue that N is not equal NP using hierarchy theorems. This is my argument, but when I showed it to our teacher and after deduction, he said that this is problematic where I can't find a compelling reason to accept.

  We start off by assuming that $P=NP$. Then it yields that $\mathit{SAT} \in P$ which itself then follows that $\mathit{SAT} \in TIME(n^k)$. As stands, we are able to do reduce every language in $NP$ to $\mathit{SAT}$. Therefore, $NP \subseteq TIME(n^k)$. On the contrary, the time hierarchy theorem states that there should be a language $A \in TIME(n^{k+1})$,  that's not in $TIME(n^k)$. This would lead us to conclude that $A$ is in $P$, while not in $NP$, which is a contradiction to our first assumption. So, we came to the conclusion that $P \neq NP$.

Is there something wrong with my proof?


texts: How to design a Turing Enumerator which either ends with 011 or is of odd length?

texts: This question was asked by my professor in optional brain teaser section, I have tried to solve it for last 48 hours, I am not able to construct a deterministic Turing Machine, Can someone provide hint or something because this seems like impossible to me :( ..


texts:
A function is $(\varepsilon, t)$-collision resistant if there is no boolean circuit (using "not", "and", "or") of size at most $t$ which outputs a collision with probability at least $\varepsilon$.

Let $h_0:\{0,1\}^{2m}\rightarrow\{0,1\}^m$ be a $(\varepsilon, t)$-collision resistant hash function and $i\in\mathbb{N}_{\geq 1}$.
Define a hash function $h_i: \{0,1\}^{2^{i+1}\cdot m}\rightarrow \{0,1\}^m$ recursively using $h_{i-1}$ in the following way:
Interpret the bit string $x\in \{0,1\}^{2^{i+1}\cdot m}$ as $x=x_1 x_2$, where both $x_1,x_2\in \{0,1\}^{2^i\cdot m}$.

Then the hash value $h_i(x)$ is defined as

$$h_i(x)=h_0(h_{i-1}(x_1)h_{i-1}(x_2)).$$

For which $(\varepsilon_i, t_i)$ is $h_i$ $(\varepsilon_i, t_i)$-collision resistant?
And can we successfully use the birthday attack on this hash function to find collisions?


texts: Is there a specific search paradigm for finding pairs in a set?

texts:
I'm dealing with a very common problem in computer programming that involves, for example 4 people to be divided into 2 pairs. Mathematically, this is just a permutations problem, and the number of possibilities would be 4!/(2! * 2^2) = 3.

In computer programming, when searching for these specific solutions, a programmer would just recurse through the possible solutions. For example --

int solve(void) {
   int i, count = 0;
   for (i = 0; i < n; i++) {
     if (partners[i] == -1) {
       break;
   }
 }

 // if all the pairs are matched with each other
 if (i == n) {
   return check() ? 1 : 0;
 }

 for (int j = i + 1; j < n; j++) {
   if (partners[j] == -1) {
       partners[i] = j;
       partners[j] = i;

       // recurse back through to find all possible sets of pairs with this configuration
       count += solve();
       partners[i] = partners[j] = -1;
    }
 }
  return count;
}

Now, what I found interesting was that when you draw a permutation tree diagram, you see that the unique solutions for this problem arise naturally in this pattern:
Permutation Tree. This pattern goes on as the number of people increases. Taking all that into account, my question is, is this simple recursive function a unique search paradigm (like BFS or DFS) that models the behavior/pattern seen in the tree? If not, could an algorithm be designed that models that pattern?

I'm a high school student, and I'm comfortable with basic and intermediate algorithm design concepts, but I'm still learning, so if you could, please explain your answer in more depth than usual.


texts: Turing machines moving left at least once

texts:
Is the following language decidable?
  $$ L = \{ \langle M,w \rangle \mid \text{$M$ moves its head left at least once when run on $w$}\}. $$

I feel like this is a decidable language. But I don't know the algorithm to prove that it is decidable. Any help would be appreciated.


texts: How can I understand if reduction is Karp reduction?

texts:
I have a reduction and can't understand if it is Karp reduction. I want understand if my reduction is Karp reduction as well as understand how to determine which one is so.

Let I have formula $\Phi = (l_{1,1}\lor l_{1,2}\lor...\lor l_{1,k_1})\land(l_{2,1}\lor...\lor l_{2,k_2})\land...\land(l_{n,1}\lor...\lor l_{n,k_n})$

And I want to check if it is minimal CNF (decision variant of CNF minimization, one that requires to minimize amount of literal occurences). Determine if formula has an equivalent with $m$ or lower amount of literal occurences. This problem is $\Sigma^P_2$-complete. However, I have reduction:

$$Min(\Phi)=m\ge(length(\Phi)-(\overline{S(\Phi\land\overline {l_{1,1}}\land l_{1,2}\land...\land l_{1,k_1})}+\overline{S(\Phi\land l_{1,1}\land \overline{l_{1,2}}\land...\land l_{1,k_1})}+...+\overline{S(\Phi\land l_{1,1}\land l_{1,2}\land...\land\overline{l_{1,k_1}})}+\overline{S(\Phi\land\overline {l_{2,1}}\land...\land l_{2,k_2})}+...+\overline{S(\Phi\land l_{2,1}\land...\land\overline{l_{2,k_2}})}+...+\overline{S(\Phi\land\overline {l_{n,1}}\land...\land l_{n,k_n})}+...+\overline{S(\Phi\land l_{n,1}\land...\land\overline{l_{n,k_n}})}))$$

Here I use $S$ to denote $SAT$-problem.

$length(\Phi)$ counts amount of literal occurences in formula $\Phi$.

If this reduction is Karp reduction, then $\Delta^P_2 = \Sigma^P_2$ and $PH$ collapses.

But is this reduction Karp reduction, how can I determine it (general method is preferred)?

Okay, it seems, using $P^{NP}$ machine I can use $+,-,<,>,=$ operations (do not know about $\cdot,/$) for any data machine has at some step (after getting answer from oracle). If so, then I'm surprised that no one found such simple algorithm for CNF minimization.


texts: Is the language of words containing equal number of 001 and 100 regular?

texts:
I was wondering when languages which contained the same number of instances of two substrings would be regular. I know that the language containing equal number of 1s and 0s is not regular, but is a language such as $L$, where $L$ = $\{ w \mid$ number of instances of the substring "001" equals the number of instances of the substring "100" $\}$ regular? Note that the string "00100" would be accepted.

My intuition tells me it isn't, but I am unable to prove that; I can't transform it into a form which could be pumped via the pumping lemma, so how can I prove that? On the other hand, I have tried building a DFA or an NFA or a regular expression and failed on those fronts also, so how should I proceed? I would like to understand this in general, not just for the proposed language.


texts: Does instruction which control unit fetch contain both what to do and where to do (in which unit of processor)?

texts: What instruction really means? I am facing problem in understanding it. If the instruction is to copy this and create a new file and place there so it seems it d doesn't need processing so what will control unit do?


texts: Pseudocode for constructing control flow graph

texts:
I'm trying to build a complexity analysis tool and I need an algorithm for constructing the control flow graph (to get cyclomatic and eventually essential complexity). I couldn't find any pseudocode online so I just got down to writing it. Using recursion seems to have been a bad way to go; my code handles most simple cases but with deeper nesting of control structures errors arise.

Is there somewhere I can find pseudocode for constructing the CFG?

(For the curious I'm doing this for VHDL.)


texts: Expressions that cannot be evaluated in normal-order?

texts:
It seems to me that when the outermost|toplevel function is itself an expression to be evaluated (i.e.: a higher-order function returning the function to be applied at top-level), then normal-order evaluation "gets stuck".

For example $(\lambda x . (\lambda y . (y^x)) 2) (5+1)$ is such that I have to evaluate $\lambda x . (\lambda y . (y^x)) 2$ to $\lambda y . (y^2)$ in order to be able to substitute $(5+1)$ into its body. But then I reduced an expression that is not the outermost, hence it was not normal-order.

Are this and similar expressions not evaluatable in normal-order?

Or can I reduce it to $(\lambda x . ((5+1)^x)) 2$ by substituting into the inner lambda?

Or is the top-level expression simply not considered a redex, because it is not of the form $(\lambda y. e) a$, but of the form $(\lambda x.(\lambda y.e)b) a$, hence the leftmost outermost redex is its left part $\lambda x.(\lambda y.e)b$?