texts: Optimal data structure for a time-windowed streaming graph in order to compute fast statistics

texts:
I apologize if this is the wrong place or too trivial a question for this community. What is the best data structure to store a time-windowed streaming graph in order to compute fast statistics over all nodes in the graph, for e.g., running computation of average degree?

I believe the best way to describe this is as follows: Let $G=(V,E)$ be a sparse time-evolving network modeled as an undirected graph with $n$ nodes and $m \geq n$ edges over time (in hours) $t = t_0, t_1, \dots $. Suppose further, that at any time point $t_i$, any edges that are more than $k$ hours are removed. In addition, nodes that have no edges connecting to it are removed.

My idea (for e.g. the average degree) is as follows: keep track of an array of edge arrival times as well as a degree array of size $n$ where each element represents the total degree. At any new time point $t_i$, we would add 1 to the degree array corresponding to the two nodes with the new edge. We would then remove all edges that are older than $k$ hours (i.e. added before $t_i-k$). Any nodes that are edge-less are removed. At all time points, a running average of the degree is computed by taking the average of the degree array.

If I'm not mistaken, this algorithm would be $O(n)$ in run-time and $O(n)$ in space. Is there any better way of doing this?

The best data structure I could find from previous posts such as this one, recommend adjancency lists. Additionally, is there any advantage in using disjoint set data structures such as in the post here?


texts: Find a continuous path filling whole 3xN grid going through certain points in given order

texts:
I've got a grid consisting of squares that is 3 squares high and N squares long.
Some of the squares are filled with numbers that are not greater than 3*N. You can move only to squares that are below, above, on right, or left from you. When you move on a square, you fill that square with a number of the amount of moves you have already taken + 1. If square is already filled with a number, you can move onto it, only if the sum steps you've have taken + 1 is equal to the number on the square.

I need to find a continous path that leads through all the squares of the grid only once and output the same grid filled with numbers corresponding to the steps of your path. In other words, a path was previously laid out on the grid and then some numbers have been erased from squares. Now I have to retrace that path.

I should be done in O(N^2), but I will be thankful for any solutions.


texts: How to find $L_q = \emptyset$, a state that is not reachable for any given string?

texts:
In the book Introduction to Languages and the Theory of Computation, I'm reading section 2.6 on how to minimize the number of states in an FA.
I'm having trouble understanding a notation defined as $L_q$. Here's what the book says:

Suppose we have a finite automaton $M = (Q, \Sigma, q_0, A, \delta)$ accepting $L \subseteq \Sigma^*$. For a state $q$ of $M$, we have introduced the notation $L_q$ to denote the set of strings that cause $M$ to be in state $q$:
$$L_q = \{ x \in \Sigma^* | \delta^*(q_0, x) = q\}$$.
The first step in reducing the number of states of M as much as possible is to eliminate every state $q$ for which $L_q$ = $\emptyset$, along with transitions from these states. None of these states is reachable from the initial state, and eliminating them does not change the language accepted by $M$.

I tried looking at this automaton to try to understand this definition:

How can any of the states $1$ through $5$ be $L_q = \emptyset$ if I can find a string that can reach every state for this FA?
That is I can reach state $2$ with string $a$, and state $5$ with string $ab$, etc. Is this a correct way to approach this?


texts: Hoare triple for assignment P{x/E} x:=E {P}

texts:
I am trying to understand Hoare logic presented at Wikipedia,
Hoare logic at Wikipedia
Apparently, if I  understand correctly, a Hoare triple $$\{P\}~ C ~\{Q\}$$ means

  if P just before C, then Q holds immediately after C, as long as C terminates. (A)

However, the assignment axiom schema seems to be interpreted in a different way:

$$\frac{}{\{P[x/E]\} ~~x:=E~~   \{P\}}$$

The wikipedia says:

The assignment axiom means that the truth of $\{P[x/E]\}$ is equivalent to the after-assignment truth of $\{P\}$. Thus were $\{P[x/E]\}$ true prior to the assignment, by the assignment axiom, then $\{P\}$ would be true subsequent to which. Conversely, were $\{P[x/E]\}$ false prior to the assignment statement, $\{P\}$ must then be false consequently.

I think the Hoare triple only affirms that if P[x/E] before x:=E, then P(x) holds after x:=E. It DOES NOT affirm, by its definition, that if P(x) holds after x:=E, then P[x/E] holds before x:=E.

My naive question is, how can $\{P[x/E]\}$ before the assignment can be equivalent to $\{P\}$ after the assignment? Does this contradict with point (A) at the beginning of my post?


texts: Prove that $L^r$ is context free without alphabet

texts:
I'm stuck with this problem:

Given $L$ a CFL on the alphabet $\Sigma$. Prove that $L^r=\{x^r|x\in L\}$, where for each $a\in\Sigma$ and $y\in\Sigma^*$, $$\epsilon^r=\epsilon,$$ $$(ay)^r=y^ra,$$  is context free or not.

Since I don't have the alphabet I cannot think of a grammar that generates this language, so I decided to prove that it's not context free by applying the pumping lemma for CFL. So I started with the hypothesis that $L^r$ is context free, thus if $x\in L^r$ that $x^r\in L$.

Then I tried to find different possible strings that once pumped didn't belong anymore to $L^r$, but I'm not able to find such string.

Is this a bad aproach? Where am I wrong?


texts: How much bits need to add to 100bit of data in order to correct up to 10bits?

texts:
I'm trying to calculate how much minimum bits need to be added to data of 100bits, in order to correct 10 bits that are messed up by:

bits that deleted (Erasure Correcting)
bits that corrupted (Error Correcting)

I tried Hamming code and Reed-Solomon codes but didn't figured out the answer of 1 or 2.

There are some other more-efficient algorithm for that problem ?
Thanks in advance !


texts: Is the moment generating function for a sequence $\{a_n\}$ unique?

texts:
Suppose $\{a_n\}$ is a sequence with moment generating function $A(z)=\sum_{k \ge 0} a_kz^k$.

Can a sequence $\{b_n\}$ with $b_n \neq a_n$ for at least one $n\in \mathbb N$ have the same moment generating function as $\{a_n\}$, that is $B(z)=A(z) \ \forall z$.

This is equivalent to: Is the moment generating function for a sequence $\{a_n\}$ unique ?


texts: Is there a correspondence of steps between DPLL and sequent-calculus?

texts:
Is there a correspondence between the steps in using DPLL to find out that a formula in propositional logic is unsatisfiable and using sequent calculus to prove that its negation is valid?

And given that the latter problem asks for less information (e.g. no need for a "counterexample" in case the formula is invalid), is it possible to solve it more efficiently than standard SAT solving?


texts: How to distribute items of varying sizes into bins of varying sizes, such that percent utilization across all bins is minimized?

texts:
I have a bunch of databases, each having different access patterns, such that each puts a different amount of load on its database cluster. I would like to distribute them around my set of database clusters such that the workload for the clusters is evenly distributed.

I looked at the k-partition problem, which sounds close to what I want, except each of my database clusters has a different load capacity. That means I need an algorithm that minimizes what percent of load capacity is used on all clusters, whereas the k-partition problem minimizes the integer load on each cluster.

Does such an algorithm exist? And can anyone point me to a sample implementation of it?


texts: How to find the compression method used on an unknown sequence of bytes?

texts:
I have a sequence of bytes:
https://drive.google.com/file/d/17sfchPgsySi2ilIxLuBb1q-UUqq5lO87
What the data is, is unknown (see NOTE below).
I'm pretty sure this data is compressed in some way, due to the ent analysis results:
$ ent first-chunk

Entropy = 7.997831 bits per byte.

Optimum compression would reduce the size
of this 949674 byte file by 0 percent.

Chi square distribution for 949674 samples is 2962.74, and randomly
would exceed this value less than 0.01 percent of the times.

Arithmetic mean value of data bytes is 127.3922 (127.5 = random).
Monte Carlo value for Pi is 3.157487727 (error 0.51 percent).
Serial correlation coefficient is 0.001738 (totally uncorrelated = 0.0).

According to the Chi square distribution the data is definitely not random.
And compression is at an optimum. This leads me to believe the data is compressed and not encrypted. Is this a correct inference?
I've tried to decompress this data assuming the compression method to be zip, gz, xz, lz4, deflate, lzma, bzip, using tools like unlzma, gunzip, unzip, unlz4, zlib-flate etc. and none of them have worked. I always end up with a "file format not recognized" or a "invalid header check" error.
How do I find what compression method was used on the data? Could it be that the compression headers are missing?

NOTE:
This data is part of a slightly larger data file that is (possibly) the firmware and additional memory of a bluetooth speaker Flash memory.
The whole file is:
https://drive.google.com/file/d/1e9yG8xMkZ331C2TOTOzo9Y93L4abxX9F


texts: Is it valid to make an admission of a topological space by a "partial quotient map"?

texts:
It is well-known that the Sierpiński space, $\{F,T\}$ endowed with topology $\{\emptyset, \{F\},\{F,T\}\}$, is admissible. I tried to implement it in Haskell.
First I implement $\mathbb{N}$ (including zero; some topologists might prefer denoting it by $S_\omega$) by Peano definition:
data Peano = Zero | Succ Peano deriving (Eq, Ord)

This encodes $\mathbb{N}$, but there is one additional value lurking behind: fix Succ. I denote it by $\omega$, and I denote $\mathbb{N} \cup \{\omega\}$ by $\overline{S_\omega}$. We observe that $\overline{S_\omega}$ is in order topology.
I abuse this fact and implement the Sierpiński space by taking a quotient space. The quotient map $q$ is:
$$
q(o) =
\begin{cases}
F & \text{if } o < \omega \\
T & \text{o.w.}
\end{cases}
$$
In Haskell, This can be realized by:
newtype Sierpinski = Sierpinski Peano

instance Eq Sierpinski where
    Sierpinski m == Sierpinski n = let
        q m = case m of
            Zero   -> False
            Succ n -> q n
        in q m == q n

But to think about it, q doesn't halt on $\omega$. In other words, q is partial, and doesn't match $q$. Is this really a valid implementation of the Sierpiński space?


texts: Rearranging function in 'Theorems for free'

texts:
I'm reading Wadler's 'Theorems for free'. In section 3.5 he states that $m_{AA}(I_A)$ is a rearranging (i. e. injective) function. $I_A$ is the identity function on the type A.
$$m : \forall X.\forall Y. (X \rightarrow Y) \rightarrow (X^* \rightarrow Y^*)$$
How does he use section 3.4 to prove this without any $\forall^{(=)}X$-types? Why can't $m_{AA}(I_A)$ e. g. drop a few elements in the list?


texts: Which time series prediction techniques are useful given harmonic properties?

texts:
I have a time series dataset where events have harmonic properties, and seemingly the nature of the event's early segments can determine the remainder of the event (see example 1's oscillations). Additionally, these early segments might determine the properties/likelihood of some following/associated event (example 2).

Which time series prediction techniques may be suitable for making predictions based on this kind of behaviour? Specifically:

For determining how an event, from appearance, might oscillate and dissipate (forecast/extrapolation).
For predicting what event may follow (probabilistic model).

I am not very knowledgeable in this, but seemingly dynamic ARIMA may be appropriate for the extrapolation at a given point. Also, the early segment might be suitable as a feature for prediction in some other model (e.g. SVC)?

Example Event 1

Example Event 2

EDIT: I want to avoid fitting a highly specialised/targeted model based on observation - but would be happy for some process to learn this representation. I am interested in learning about existing models/methodologies that could be applied to this problem, references would be great.


texts:
I am a pure math person doing some ML self-study and I am pretty lost.
I am trying to solve the following exercises on decision trees:

Exercise 1. Consider the following training set where
$X_1,X_2,X_3,X_4$ are the attributes and $Y$ is the class variable.
$$ \begin{matrix} Y & X_1 & X_2 & X_3 & X_4 \\ 1 & 0   & 1   &  0  & 1
 \\ 1 & 1   & 0   &  1  & 0   \\ 1 & 1   & 1   &  1  & 0   \\ 1 & 0   &
 0   &  0  & 1   \\ 1 & 1   & 1   &  1  & 0   \\ -1& 0   & 0   &  1  & 1   \\
 -1& 0   & 0   &  0  & 0   \\
 -1& 0   & 0   &  1  & 0   \\
 -1& 1   & 0   &  0  & 0   \\
 -1& 0   & 0   &  1  & 1   \\ \end{matrix} $$

Learn a decision tree using the ID3 algorithm.
Draw a decision tree having only 4 leaf nodes, 3 internal nodes and depth bounded by 2, that has 100% accuracy on the given dataset.

Exercise 2. Let $x$ be a vector of $n$ Boolean variables
${X_1,...,X_n}$ and let $k$ be an integer less than $n$. Let $f_k$ be
a target concept which is a disjunction consisting of $k$ literals.
State  the  size  of  the  smallest  possible  consistent  decision
tree  (namely  a  decision  tree  that correctly classifies all
possible examples) for $f_k$ in terms of $n$ and $k$ and describe its shape.

Now, I've done the first part of Exersice 1 as follows: first I noticed that $X_2$ is pure and so I chose it as root; then I used Information Gain to find the nodes. The second question confuses me: my understanding was that ID3 already gives the smallest tree, so how am I supposed to make it smaller? Or if am I wrong can anybody help me clarify?
For the second problem, I really don't know where to start from, so any hint would be appreciated.


texts: Why is a Context Free Grammar that is simultaneously in Chomsky Normal Form and Greibach Normal Form regular?

texts:
In my course materials, there is one sentence about how if CFG is in Chomsky Normal Form, it is not regular, and if it is in Greibach Normal form, it also is not. But when a grammar is simultaneously both GNF and CNF, it somehow implies that the grammar is regular - why is it so?

I struggle to understand what would the productions of the grammar that is both in CNF and GNF look like. As in GNF, the production rule is in form: $A \rightarrow aA_1A_2...A_n$ such that the nonterminal sequence can be empty, I think that the only way a grammar can be in both normal forms, is when the production rules are in form: $A \rightarrow a$.

Even if this is the case, why does it imply that the grammar is regular? What is the relationship between regular and context-free grammar?


texts: Computability: Proving a predicate is not recursively enumerable

texts:
Let P(p) <=>  for each x, comp(p,x) is defined.

Can anyone explain to me how to prove that P is not RE (recursively enumerable) ?


texts:
Suppose I have an $N$ length integer array of pairs of the type $[value, key]$. Now, I need to query for range sum. Query is of the type : $l, N, x$ meaning I have to sum up all the $value$ in the index range $l$ to $N$ having key as $x$. Also, there can be updates that add a new pair to the end of the array increasing $N$. Succeeding queries consider the updated $N$. There can be multiple queries so I need to answer the query in $O(logN)$ but precomputation is allowed.

I think it might be done with a Segment Tree but I cannot see what to keep in the nodes. Is it even possible to do it with required complexity, because I feel you actually need to go to every element in the array to check it's key. Any help is appreciated.


texts: the height of a tree given n nodes and a condition

texts:
I came across a question on which I got totally stuck :( a sort of homework question)

A weight-balanced tree is a binary tree in which for each node. The number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the farthest leaf) of such a tree on n nodes is best described by which of the following?

a) log_2 n
b) log_{4/3} n
c) log_3 {n}
d) log_{3/2} n

I cant imagine to solve this one. Intuitive based answer is most welcome.


texts:
I've been trying to find lists of graduate level CS classes that have had their lectures videotaped. There's a similar question on MathOverflow, which has compiled a fairly extensive list of stuff:

Free online video lectures of mathematics courses.

What I'm mostly interested in is finding links to materials like the following (which you can only really stumble on by accident through YouTube's recommended videos):

CMU Advanced Optimization and Randomized Methods.

I know this question doesn't really satisfy the QA format of the site, but this is by far the most widely read website that I know of for the target audience. Since the question was OK on MO I assume it's also OK here...


texts: What is the relation between pure mathematics, applied mathematics and Cellular Automata?

texts:
I was reading about pure mathematics and I am wondering if there is a relation between it and Cellular Automata.

  Broadly speaking, pure mathematics is mathematics that studies entirely abstract concepts.

For example, elementary cellular automata transforms an input of {3 cells} based on a rule set to a fractal like rule 90, how this will be described in pure mathematics perspective?

Another fractal like Pascal's Triangle can determine the coefficients that arise in binomial expansions, how it can be related to applied mathematics?

  Applied mathematics is a branch of mathematics that deals with mathematical methods that find use in science, engineering, business, computer science, and industry.

The use here of Pascal's triangle is determining the coefficients of binomial expansion, so how it can be related to applied mathematics?


texts: Single Source Shortest Path: What does the weights on the vertex and edges tell you?

texts:
In MIT's open courseware (http://courses.csail.mit.edu/6.006/spring11/lectures/lec15.pdf), I do not see how computing a set of numbers on the edge and the vertex will produce the shortest path.

Can someone please explain what information I can get by looking at the above example? How can I tell what is the shortest path to where?


texts: DNA Computing Algorithm to solve the Hamiltonian problem

texts:
Is it possible to represent the algorithm proposed by Adleman to solve the Hamiltonian problem in a probabilistic Turing Machine?

See also Computing with DNA


texts:
The input space is a unit circle, $\mathcal{X} = \mathbb{S}^1 \subset \mathbb{R}^2$. There is class $\mathcal{F}$ of arcs on $\mathbb{S}^1$, where a point is labeled 1 if it is on the arc, and 0 otherwise. We want to find the VC dimension of $\mathcal{F}$

I think the answer is 2. Any two points can be shattered $(++, -+, +-, --)$. But if we have three points $\{(x_1,y_1),\dots,(x_3,y_3)\}$ that all have the label 1, with radius $r_1 = r_2 = 1$, and $r_3 = 0$, it is impossible to shatter them. Is my intuition correct?


texts: What algorithm paradigm is a recursive solver of Sudoku?

texts: I am interested in knowing what algorithmic paradigm are the usual recursive sudoku solvers. Can I consider it a local search? or are they Dynamic programming, greedy, divide and conquer, backtracking?


texts:
I have a basic question about Hamming distances, something confuse me in the book I'm reading about it.

Let's assume we have a codeword $y$ that received an error $e$. Thus we had the following event:

$$ y_0 \rightarrow y'=y_0+e $$

In Nielsen & Chuang, page 449, he says:

  Provided the probability of a bit flip is less than 1/2, the most
  likely codeword to have been encoded is the codeword y which minimizes
  the number of bit flips needed to get from y to y',that is,which
  minimizes wt(e)= d(y, y').

Where $d(a,b)$ is the Hamming distance between $a$ and $b$, and $wt(e)$ is the Hamming weight of $e$, which is $d(e,0)$.

My question is the following:

I agree that if there is more probability of no bit flip than the probability to have one, then the most likely codeword is the closest one from $y'$, thus a codeword $y$ minimising $d(y,y')$.

However, as he writes $d(y,y')=wt(e)$, he seems to assume that the closest vector from $y'$ is necesseraly the one we encoded. Which for me is not true in general, the error could have put us closer to another encoded word than the one we encoded right ?

Where is my misunderstanding here ?


texts: Kleene star closure of a context free grammar

texts:
I have this question about closure of a context free grammar, and if someone can check my answer and see if it makes sense, and if not, what is missing, I would be very grateful.

  Give an counter-example to show that the following contruction fails in to proof that class of languages free of context is closed under the operation star. By A a language free of context that it is generated by the GLC G = {V,,R,S}. Add the new rule S -> SS e call the resulting grammar G'. That grammar is expected to generate a*"

I have only a superficial comprehension, I believe it is necessary that Rg', the set of production rules of G' must be equal to Rg united with {Sg'->SgSg'|e} or in another words Rg': Rg U {Sg'->SgSg'|e}. Even if that it is correct I don't understand why {Sg'->SgSg'|e} is necessary


texts:
I have a graph data structure that represents a rail network. The nodes of the network are the train stations and the edges are the connections between stations.

Running PageRank on this graph gives me a way to rank the stations by importance. But I want to rank the connections between stations, the edges of the graph, by importance.

Is there an appropriate algorithm to do this? Is there a way to reformat the graph so that I can run PageRank for edges?


texts: Are self-stabilizing algorithms guaranteed to work in parallel?

texts:
Self-stabilizing algorithms are extremely useful in distributed systems,
  but can the algorithm be applied concurrently to each computational node?

My instinct is to say yes, but I can't help but imagine a 'Game Of Life' scenario
  where the state of the graph toggles between two states.
What keeps the question alive in my mind is the possibility that both such states would be considered 'correct', but then if the state were correct, wouldn't the graph stabilize?

If they are not guaranteed to work in parallel,
  can you provide an example where absolute convergence doesn't exist?

A self-stabilizing algorithm is an algorithm (in all my experience, applied to arbitrary graphs and graph structures exclusively) that, upon repeated applications, guarantees convergence onto a correct state—one that meets a set of requirements.  Consider a simple example:

  You maintain a network of hospitals and data centers.
  Each hospital must be connected to exactly one data center, and each data center must be connected to exactly two other data centers.  (You can imagine also attempting to minimize latency.)
  When you set up the network, it is in a correct state—all requirements are met.

  Weeks pass, and a giant storm takes out one of your data centers.
  Being the forth-dimensional thinker you are, you planned for situations like this by putting into place a self-stabilizing algorithm that will automatically reconfigure the network to get back to a correct state.
  You set up a daemon to oversee the operation.  It picks arbitrary nodes in your network and asks them if they are in a correct state.  If not, the daemon corrects that part of the network.

  All is well and you can stay asleep in bed (because everything catastrophic happens at 3am).

The trick is, the daemon isn't a necessary part of this system—it's just easier to think about it like this.
In reality, each node is its own computational unit—constantly evaluating its own state and taking steps to correct itself if necessary.

The introductory paragraphs of the Wikipedia article on the subject give a very good technical overview:

  Self-stabilization is a concept of fault-tolerance in distributed computing. A distributed system that is self-stabilizing will end up in a correct state no matter what state it is initialized with. That correct state is reached after a finite number of execution steps.

Just as a piece of requested information that doesn't fit in well above:

  When the graph is stable, no node has any faults with it.  Since no predicates apply to it, no actions are taken, and the graph remains stable.


texts: A linear time algorithm to find the array of indices of bigger numbers

texts:
Suppose you have an array nums of integers, unsorted, containing the values from 1 to n.  You have a second array, call it firstBigger, initially empty, which you want to populate with integers such that firstBigger[i] contains j if j is the least index such that i < j and nums[j] > nums[i]. A brute force search of nums runs in $O(n^2)$ time. I need to find a linear time search.

For example, if
nums        = [4,6,3,2,1,7,   5] and we use 1-indexing, then
firstBigger = [2,6,6,6,6,None,None].

I have considered first computing the array of differences in linear time. Certainly anywhere in the array of differences with a positive value, this indicates a place in firstBigger where it should store $i+1$. But I'm not seeing how to fill any other coordinates efficiently.

I might have gotten close when I started thinking of analyzing the array end-to-start.  The last $n$th coordinate of firstBigger is going to be None, the $n-1$th has to be directly compared to the $n$th. As we proceed backward, if the number at $i$ is smaller than at $i+$1 we make this assignment. Otherwise we look up the first number bigger than the one at $i+1$. If that's still too small, again look up the first number bigger than that.

On average this does better than the naive algorithm, but in the worst case it's still $n^2$.  I can't see any room to optimize this.


texts: Elements of Programming Interviews - 16.4 Generate Power Set - solution 1 time complexity question

texts:
hope you all are doing well.

I have a question about the time complexity of solution 1 for question 16.4 - Generate Power Set from the book Elements of Programming Interviews by Adnan and Tsung-Hsien.

The question instructs the reader to "Write a function that takes as input a set and returns its power set". The input is the set S = {0,1,2}.

I understand that there are at most 2^n recursive calls of the method directedSoFar. However, I don’t understand why we spend O(n) time within a call of directedSoFar. There are no loops inside the method, only 2 lines at the recursive case to add and remove elements into the current selectedSoFar solution, and another 2 lines at the base case. Doesn't this mean that we only spend constant time within a call, and not O(n) time?

I’ve struggled with this for a while, and have posted on the official forum as well as Reddit, but got no responses. I would appreciate it if anyone would be generous enough to help me.

Thank you


texts: Clustering algorithm with specific cluster grouping areas

texts:
I'm looking for a way to cluster points in a given space, where clusters form around specific closed, allowed zones of that initial space. Each allowed zone should be surrounded by points of its cluster.

However, it is not only necessary to match the points to the closest allowed zone, but also to take into consideration the distance to other points of the same cluster.

In the example image given, in the clustered picture, the green points at the top right belong to the green cluster despite being closest to the blue area, because their neighbours are all green.

Ultimately, a network would be created from each cluster (lets say the points are a series of sinks), and linked to each respective zone via a single optimally placed point within the zone (which represents the source). A cost function would evaluate the cost of the network (i.e. minimizing the cost of a weighted graph). The difficulty is that the optimal placement of the source point is not known until the cluster is defined. The overall goal is to minimize the cost of all the networks combined.

Is there any algorithm available that can do this type of clustering? Otherwise how would you proceed?


texts:
I have a text and a narration of the exact same text. What is the best way to synchronize them together? By synchronizing I mean, finding out for example the location of each word in the audio. For example if the sentence is "I took a cab" I want for markers on the accompanying audio which indicate start of each word.

Obviously any speech-to-text algorithm can be applied here, but given the fact that we've already know the text, I wonder if there's an algorithm for this simplified problem which works either much faster, or gives much better performance. Or if there is a general algorithm that can be tuned for this specific problem.


texts: Dynamic Programming on bracketed sequences

texts:
I am currently working on the following problem that involves developing a dynamic programming algorithm for finding the length of the shortest fully bracketed expression (FBE), $y$ that contains a given string $x = x_1x_2...x_n$. An FBE is defined as a string over the characters (,),[, and ] that is either

the empty string
the string $[T]$ or $(T)$, where $T$ is a fully bracketed expression, or
the string $TU$, where $T$ and $U$ are fully bracketed expressions.

So far I have worked through the potential recursive function $T(i,j)$ which I've defined as the length of the shortest possible FBE that contains $x_i...x_j$ as a subsequence (not necessarily a string). And I know that in the shortest FBE containing $x_i...x_j$ that $x_i$ is either "mathced" to an appropriate character $x_k$ such that $i + 1 \leq k \leq j$, or it isn't. So I think that I need two cases; either the former is true, or the latter is true.

I'm having trouble formalizing this and creating a recursion. I'm not sure how to deal with the addition of characters. Any help would be appreciated! Thanks!


texts: The Inverse of a function with logic operators

texts:
How would one be able to tell whether or not a function has an Inverse? I've got  a question in my discrete mathematics/ combinatorics class that asks whether or not the following function has an Inverse and if so give the Inverse.

{(p, q) | q =¬p}

where p and q are elements of the set {T,  F}  where T is tautology and F is contradiction.

I know for regular xy functions, it has an Inverse if it is one to one and also how to find the Inverse.  But how would I apply that knowledge to this question?


texts: Machine learning algorithm to play Connect Four

texts:
I'm currently reading about machine learning and wondered how to apply it to playing Connect Four.

My current attempt is a simple multiclass classificator using a sigmoid function model and the one-vs-all method.

In my opinion, the input features have to be the state (disc of player 1, disc of player 2, empty) of the 7x6=42 grid fields.

The output would be the number of the row to put the disc into. Because that is a discrete number between 1 and 7, I guess this can be treated as a multiclass classification problem.

But how do I generate training examples usable in supervised learning?

The main goal is to win the game but the outcome obviously isn't known when doing every but the last turn.
If I just let two players who decide randomly what to do play against each other thousands of times, will it be sufficient to simply take all turns made by the winner of each game round as training examples? Or do I have to do this in a completly different way?

Edit: As suggested in the comments I read a little about reinforcement learning.
From what I know understand, Q-Learning should do the trick, i.e. I have to approximate a function Q of the current state and the action to take to be the maximum cumulative reward beginning in that state. Then each step would be to choose the action which results in the maximum value of Q. However, this game has way too many states in order to do this e.g. as a lookup table. So, what is an effective way to model this Q-Function?


texts: Is "expert system" now an obsolete/unpopular term?

texts:
While doing research on expert systems, I notice that it is rare to see this term used in the last 20 years. For example, a recent paper was:

Wang, Hao, Naiyan Wang, and Dit-Yan Yeung. "Collaborative deep learning for recommender systems." Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2015.

Not only is the term expert system used nowhere in the paper, but a survey paper that referred to this paper does not mention expert systems anywhere either, even though that is exactly what the paper describes.

Apparently, the term "expert system" is now gauche and we now should not use it anymore.

Nevertheless, there seems to be no term to replace it. So, for example in the above cited paper the word used is a "recommender system" which is a joke. I am not going to use such an ungrammatical term to replace expert system. Is there a better term to replace "expert systems"?


texts: Principles of Distributed Computing - "processors" and "states"

texts:
So I'm learning about distributed computing, and I do understand a lot of the prerequisite material on algorithms and automata and whatnot... but I'm curious about the definitions I'm seeing as I read my textbook.

  A system consists of $n$ processors $p_{0},\dots,p_{n-1}$, where $i$ is the index of the processor $p_i$. Each processor is modeled with a (possibly infinite) state machine with state set $Q_i$. The processor is identified with a particular node in the topology graph. The edges incident on $p_i$ are labeled arbitrarily with the numbers $1$ thru $r$, where $r$ is the degree of the $p_i$. Each state of the processor $p_i$ contains $2r$ special components: $inbuf_i[\mathcal{l}]$ and $outbuf_i[\mathcal{l}]$.

Does this mean that each state of an n-state state machine has a separate inbuffer and outbuffer? Based on the wording of this, it seems to imply that there are n of each buffer, which would say to me that an outbuffer is mapped directly to the inbuffer of another state in another processor.


texts:
Let $A$ be a pushdown automata with input alphabet $\Sigma$ and stack alphabet $\Gamma$ and let $R \subseteq \Gamma^∗$ be a regular language. Let $L_R(A) \subseteq \Sigma^∗$ be a language of such words over alphabet $\Sigma$, for which there exists some run of automata $A$, such as in every step symbols on the stack belongs to the regular language $R$.

Show that language $L_R(A)$ is context-free.


texts: How do I prove all constants to some exponential power belong to little-o of some function

texts: I'm trying to prove that c2n = o((loglog n)n) (That's little-o) for any constant c. I understand that we can prove one function grows at a smaller rate than the other by taking the limit as n approaches infinity, and I can very easily pick some arbitrary integer value for c and show that indeed ((loglog n)n) grows at a faster rate. But how do I prove this to be true for any constant c?


texts: Policies for handling symbols leaking out of a lexical scope

texts:
Suppose it's possible for a symbol to escape the scope in which it is defined. What are considered the possible policies for handling that? I mean possible in the sense of what choices of language design that could be implemented -- different choices yield languages which differ in this respect.

For example, it's conceivable that two lexical scopes might each contain a symbol named "x". If these symbols escape from their respective scopes, what can we say about that? I can see three possibilities: all symbols named "x" are the same, so the symbol leaked out of the first scope is the same as that leaked out of the second; or each symbol named "x" is actually a distinct symbol, so the leaked symbols are not the same; or when a symbol escapes from its scope, something about that lexical context is carried along with the symbol, so that the result of the leakage is not a symbol but a more complex object representing the lexical context or environment and the symbol together. No doubt there are other possibilities.

I know Common Lisp implements the first policy -- (eq (let (x) 'x) (let (x) 'x)) yields T. I think Scheme does too. I don't know enough about other languages to say what might happen. I'm not aware of languages which implement the second or third ideas, but, as I was saying, my awareness is limited, and I would be interested to hear about any such languages.

I'm sure this is a topic which is well-known in the programming languages field, but through some reading and searching I haven't found it yet.


texts: What is the problem with this Busy Wait solution for two threads?

texts:
We have two processes. One process produces F and the other process consumes F

Initialization:

Consuming = false
Produced = false
F = EMPTY

The first thread (we can think of it as some kind of producer):

P1:
loop_for_ever:
    Produce(F)
    Consuming = true
    Produced = true
    while(Consuming) {Busy Wait)

And here is P2:

P2:
loop_for_ever:
    while(NOT Produced) {Busy Wait}
    Consume(F)
    Produced = false
    Consuming = false

One problem with this solution is after P1 has produced F, there is no way for P2 to consume F until P1 unlocks the Produced variable. Any other problems with this solution with regards to mutual exclusion? Is there a scenario in which P1 and P2 try to produce and consume F at the same time?

EDIT:

After reading fade2black's answer, I think I first need to address another more basic question. So let's add these extra conditions.

Extra conditions:

1- No mutex or semaphore based solution (only busy wait).

2- The threads have no remainder section (in that case this approach would obviously not work). Basically, what I am trying to do is to take a sequential algorithm (such as the one @fade2black has given) and distribute it among two threads. I could have blindly used an algorithm such as Dekker's (with turn given to P1 at the beginning). So I think first I need to find an answer for this question : "Is there any point to try and use a concurrent algorithm for this problem"? (when there is only one consumer and one producer and there is only one shared space between the two).


texts: Consequence of NP=coNP to some hierarchy problems

texts:
If $NP=coNP$ does it hold that $P/Poly=PH/Poly$ and/or $NP\subseteq P/Poly$ and/or $VNP=VP$?

What can we legitimately say if $NP=coNP$?


texts:
Prove that the following language $Σ = \{1\}$ is not regular.
$L$ = $\{w | |w| = k$, where $k$ is a prime number}.

How should one go about proving this? Should I use pumping lemma for this?


texts: Starvation algorithm in operating system

texts: Is there an algorithm for mutual exclusion with shared flag variables, as the Peterson's one, that doesn't prevent the starvation ?


texts: Discrete assignment problem with penalties

texts:
I came across a problem were you have to plan an optimal assignment pattern. Let's say you have $j=1,\ldots,n$ tasks during $i=1,\ldots,m$ time periods.

It's an single agent problem where we have to assign agent to perform exactly one task $j$ during each period $i$, i.e., $\sum_{j=1}^n x_{ij} = 1$ for $i=1,\ldots,m$ where $x_{ij}=1$ if agent is assigned to task $j$ in period $i$ and $0$ otherwise.

We receive a reward of $c_{ij}$ for performing task $j$ on period $i$. Additionally, there is a penalty $p$ each time the task changes between two consecutive periods. If during period $i$ we assign the agent to perform task $j$ and on $i+1$ the task $j^\prime$, we subtract the penalty $p$ from the total reward of all assignments.

We want to assign the agent in such way that the total profit $$\sum_{i=1}^m \sum_{j=1}^n x_{ij} c_{ij} - \text{penalties  introduced by changing task between periods}$$

is maximized. I have been able to model this as an integer program with binary decision variables, but I was thinking maybe there is some other type of recursive algorithm (via dynamic programming) that could handle this problem also. Is this a known problem with solution methods present in literature? It seems like it could have already been studied, but I haven't been able to find a name for this kind of problem.


texts: Integer solution that approximates a desired stock split

texts:
I am building software for an investment manager. The investment manager invests money on behalf of his clients.

The investment manager has a model portfolio, of say 20 stocks, each with certain weightage.

Eg: His model portfolio can look like this:

{GOOG: .03, AAPL: 0.4, MSFT: 0.25, TESLA: 0.5, IBM: 0.1, .....}
Now lets say the investment manager has one client, who holds all of the stocks, the total of which is worth, say USD50,000, but with slightly different weightage:

{GOOG: .0295, AAPL: 0.415, MSFT: 0.232, TESLA: 0.1, IBM: 0.2, .....}
Now the client wants to invest a lumpsum, lets say USD10,000.

Now, the investment manager wants to split this USD10,000 across 20 stocks, so that he gets closest to the model portfolio. i.e. I want the resultant USD60,000 to be split in a way that is closest to the ratios maintained in the model portfolio.

A limitation here is that, I can buy or sell a minimum of 1 stock; I cannot deal in fractions of stocks.

Is there a name for this kind of problem? I am pretty sure this has been solved by someone, so do not want to reinvent the wheel.

I do not know what I should google for, or where to start from.

I want the chosen allocation to have the least deviation from the model portfolio, measured by $L_2$ distance (sum of squared differences). Also, the investor keeps investing periodically, so there is a chance his portfolio might deviate further and further, so the idea is to keep these "tracking errors" to a minimum, so that it the investor's portfolio is as close to the model portfolio as possible.


texts:
I am going through problem 13-1 in CLRS 3rd edition. I came up with the following algorithm as a solution:
PERSISTENT-TREE-INSERT(T,z)
y= T.nil
x=T.root
while x != T.nil
   y=x
   if z.key < x.key
       x = x.left
   else x = x.right
if y == T.nil
    T'.root = z
    return T'
else if z.key = y.key
    y'=copy(y)
    y'.left = z
    z.p = y'
else y'= copy(y)
     y'.right=z
     z.p = y'
x = y'
while x.p != T.nil
  if x.key < x.p.key
     x' = copy(x.p)
     x'.left = x
     x.p = x'
 else x' = copy(x.p)
    x'.right = x
    x.p = x'
T'.root = x
return T'

Now the copy procedure is :
copy(x)
 w.p = x.p
 w.right= x.right
 w.left = x.left
 w.key = x.key
 return w

Now this means that I only need to copy the node that is going to be the father of the key that I'm adding and its ancestors. The book however says that additional copying is needed just because we have a reference to the parent, but I don't see it. If someone could point me in the right direction I would be much grateful.
For reference this is the exercise:
During the course of an algorithm, we sometimes find that we need to maintain past
versions of a dynamic set as it is updated. We call such a set persistent. One way to
implement a persistent set is to copy the entire set whenever it is modified, but this
approach can slow down a program and also consume much space. Sometimes, we
can do much better.
Consider a persistent set S with the operations INSERT, DELETE, and SEARCH,
which we implement using binary search trees as shown in Figure 13.8(a). We
maintain a separate root for every version of the set. In order to insert the key 5
into the set, we create a new node with key 5. This node becomes the left child
of a new node with key 7, since we cannot modify the existing node with key 7.
Similarly, the new node with key 7 becomes the left child of a new node with
key 8 whose right child is the existing node with key 10. The new node with key 8
becomes, in turn, the right child of a new root r0 with key 4 whose left child is the
existing node with key 3. We thus copy only part of the tree and share some of the
nodes with the original tree, as shown in Figure 13.8(b).
d) Suppose that we had included the parent attribute in each node. In this case,
PERSISTENT-TREE-INSERT would need to perform additional copying. Prove
that PERSISTENT-TREE-INSERT would then require .n/ time and space,
where n is the number of nodes in the tree.


texts: IA network that is path-consistent, but not consistent

texts:
I'm studying continuous CSP from the slides of my professor and i got that with the PATH-CONSISTENCY algorithm you can check consistency for PA (Point Algebra), SIA and ORD-Horn; however it cannot be used to determine consistency for IA (Interval Algebra), since it is just a necessary but not sufficient condition. From this i would say that it must exist a IA Network which is path consistent, but not consistent. However i cannot construct such a network.
Is my assumption wrong? If not what would be an example of a IA network which is path consistent but not consistent?


texts: Why is the scan line filling algorithm for computer graphics so complicated?

texts:
It seems to me that the algorithm is over complicated.

It makes use of tables, buckets, and sorting, which all seem unnecessary.

I don't understand why I can't just fill between pairs of scan line intersections, ignoring vertices and edges with gradient 0.

My lecturer didn't provide the best notes on this algorithm, and all I can find online are even more complicated versions of it.

An ideal answer would be an explanation of the algorithm, and a reason why simply filling between pairs of intersections won't work.

Thank you


texts: Differences between Fuzzy C-Means and EM

texts:
When clustering a set of data points, what exactly are the differences between Fuzzy C-Means (aka Soft K-Means) and Expectation Maximization?

In slide 30 and 32 of this lecture I found, it says that Soft K-Means is a special case of EM in Soft K-Means only the means are re-estimated and not the covariance matrix, why's that and what are the advantages / disadvantages? How does covariance matrix affect the outcomes of EM?

Another question about these two algorithms: When they converge, all the data points will be hard-assigned to a particular cluster if the probability of it being in the said cluster is highest, right?


texts: Is 'the bombe' technically a computer?what is technically meant to be a computer?

texts:
Some say that 'the bombe' created by Alan Turing is technically not a computer despite decrypting the codes.

Why is it so? Is 'the bombe' technically a computer?

First of all what is technically meant to be a computer?, When even olden mechanical machines like step reconer or hollerith tabulating machine is often regarded as computer but not 'the bombe'(correct me if I am wrong)


texts:
I have a simple problem of making a DFA which accepts all inputs starting with double letters (aa, bb) or ending with double letters (aa, bb), given $\Sigma =\{a, b\}$ is the alphabet set of the given language.
I tried to solve it in a roundabout way by:

Generating a regular expression
Making its corresponding NFA
Using powerset construction to deduce a DFA
Minimizing the number of states in DFA

Step 1: Regular expression for given problem is (among countless others):
((aa|bb)(a|b)*)|((a|b)(a|b)*(aa|bb))

Step 2: NFA for given expression is:

(source: livefilestore.com)
In Tabular form, NFA is:
State    Input:a     Input:b
->1        2,5         3,5
  2        4           -
  3        -           4
 (4)       4           4
  5        5,7         5,6
  6        -           8
  7        8           -
 (8)       -           -

Step 3: Convert into a DFA using powerset construction:
Symbol, State       +   Symbol, State (Input:a) +   Symbol, State (Input:b)
   ->A, {1}         |        B, {2,5}           |        C, {3,5}
     B, {2,5}       |        D, {4,5,7}         |        E, {5,6}
     C, {3,5}       |        F, {5,7}           |        G, {4,5,6}
   (D), {4,5,7}     |        H, {4,5,7,8}       |        G, {4,5,6}
     E, {5,6}       |        F, {5,7}           |        I, {5,6,8}
     F, {5,7}       |        J, {5,7,8}         |        E, {5,6}
   (G), {4,5,6}     |        D, {4,5,7}         |        K, {4,5,6,8}
   (H), {4,5,7,8}   |        H, {4,5,7,8}       |        G, {4,5,6}
   (I), {5,6,8}     |        F, {5,7}           |        I, {5,6,8}
   (J), {5,7,8}     |        J, {5,7,8}         |        E, {5,6}
   (K), {4,5,6,8}   +        D, {4,5,7}         +        K, {4,5,6,8}

Step 4: Minimize the DFA:
I have changed K->G, J->F, I->E first. In the next iteration, H->D and E->F. Thus, the final table is:
  State    +   Input:a     +   Input:b
   ->A     |      B        |      C
     B     |      D        |      E
     C     |      E        |      D
    (D)    |      D        |      D
    (E)    |      E        |      E

And diagramatically it looks like:

(source: livefilestore.com)
...which is not the required DFA! I have triple checked my result. So, where did I go wrong?
Note:

-> = initial state
() = final state


texts: What is the relation between the formal definition of strictness and its intuitive notion

texts:
I am currently reading Functional Programming in Scala and have encountered a statement in the book I cannot quite make sense of.

On page 67, we are told the formal definition of strictness:

"If the evaluation of an expression runs forever or throws an error instead of returning a definite value, we say that the expression doesn't terminate, or that it evaluates to bottom. A function f is strict if the expression f(x) evaluates to bottom for all x that evaluate to bottom."

This definition is somewhat puzzling because the discussion of strictness that comes before this definition has discussed strictness in relation to lazy evaluation. To say that an expression is strict is to say that it is completely evaluated, and not lazy. What is not clear is how this notion of strictness and laziness is at all related to the formal definition given.


texts:
Would the intersection of a recursive language and a recursively enumarable language be recursive or recurisvely enumbarable or neither?

Assume $L_{3}$ is the intersection of some language $L_{1}$ $\epsilon$ RE and some other language $L_{2}$ $\epsilon$ REC .

Since $L_{2}$ $\epsilon$ REC, there must be a Turing-Machine $M_{2}$ that holds on every input, whethere or not the input x $\epsilon$ $L_{2}$.
If we now have a k-NTM $M_{3}$ that on one band simulates
$M_{2}$ and upon acceptance of the input switches to another band where it then simulates $M_{1}$ (for $L_{1}$).

Since $M_{1}$ is only ever simulated if $M_{2}$ accepts the input, $M_{1}$ only gets the chance to hold for every word x $\epsilon$ $L_{1}$ $\bigcap $ $L_{2}$.

That means we can already assume that we wont get stuck in a loop for words x $\notin $ $L_{2}$.

However that is not the case for words that are in the intersection or only in $L_{2}$ and not in $L_{1}$, as the simulation of $M_{1}$ wil also be recursively enumarable and may run forever, without us ever knowing whether the input is accepted or not.

If my thoughts so far were correct, that means that  $L_{3}$ $\epsilon$ RE.

What I am uncertain about is if there is any sort of algorithm or technique with which we could make the simulation of $M_{1}$ decidable, or if maybe it is possible to make an entirely new TM, independent from $M_{1}$ and $M_{2}$ and make sure it is decidable?


texts: Is polynomial time reducibility reversible?

texts:
If a language $A$ is reducible to some language $B$, does it follow that $B$ is reducible to $A$?

My guess is no, it having something to do with the function $f$ in the definition of $A$ reducing to $B$ needing to be invertible.


texts: Questions about an answer to a pumping lemma question for CFLs

texts:
In the answer to this question, I'm not understanding how the string is derived for a given $l$.

For example,

  Case 1: $vx = a^i$ where $i > 0$. Choose $l = 2$ to get $a^{n+i} b^{n+1} c^{n+1} d^n \notin L$.

Why is $l = 2$ chosen and how is $a^{n+i}b^{n+1}c^{n+1}d^n$ derived from $l = 2$?

Also, how can $vx$ be chosen instead of $vwx$ as the OP chose? What do we do about $w$? Is it the empty string?


texts: Simulate the concatenation of two log-space programs in log-space

texts:
I've got two log-space programs $F$ and $G$.

Program $F$ will get input in array $A[1..n]$ and will create the output array $B[1..n]$.
Program $G$ will get as input $B$ as created by $F$ and create from it the output array $C[1..n]$.

I have to write a proof that there exist a log-space program $H$, which will get input Array $A$ and create from it corresponding array $C$. But I can't find the correct way to write it. How is this done?

A log-space program is a program which uses $O(\log n)$ bits of memory. Here are some conditions you have to keep:

You have to use only variables which have simple integer type (for example int in C++, longint in Pascal).
Allowed range of integer is defined: if $n$ is the size of the input we can save into variables only values which are polymonial sized based on $n$.

For example: we can have variables which can takes on values in $[-n...n]$, $[-3n^5...3n^5]$ or also values $[-4...7]$, but we can't have variables which will take on values in $[ 0...2^n]$.
No other types of variables are allowed, neither are arrays and iterators.
Exceptions from the rules about are input and output. Input will be available in special variables (mostly arrays) which your program can only read from, and the output can only be written to other special variables. So you can't read from output, and you can't increase values of input variables etc.
Your programs can't use recursion.

Example of log-space program written in Pascal (so everyone can understand it) which will find the largest number in the array of integer

    var n: integer;  //input variable the number of elements in A
    A: array [1..n] of integer; //input variable - the array of integers
    m: integer;      // output variable, the position of maximum
    i, j: integer;   //working variables
    begin
      j := 1;
      for i := 2 to n do
        if A[i] > A[j] then j := i;
      m := j;
    end;

The only two variables here are j and i and they evidently take values in $[1...n]$. Therefore all conditions are fulfilled and it really is a log-space program.


texts:
I am trying to make a non-deterministic NFA that does not contain a string "101".

How do I make my NFA so that it does not have this string?

My attempt:


texts:
Assume i have 2 numbers in binary form (or, more precisely, assume to know the number of their digits, DF1, DF2):

101010101001010101010101010111111111111111111111010101
10101111111111111111010101

Is there a formula for the exact number of binary digits (DP) of the product?

  DP = F (DF1, DF2)

[I need this, in a practical case, to size a target array]


texts: Maximizing the boolean combination of given real numbers

texts:
Let $x_1, x_2, \dots, x_n \in \mathbb R$ and $b_1, b_2, \dots, b_n \in \{0,1\}$. I want to know which of all the possible boolean combinations is maximal. For example, if $x_1 = 2$ and $x_2 = -2$,

$$\max \sum_i b_i x_i = 2 \implies b_1 = 1, b_2 = 0$$

I can see that a brute force algorithm will have a running time complexity of $O(2^n)$. My question is whether there is an efficient algorithm for this or, at least, an approximation algorithm.


texts: What is the difference between Data Hazard and Dependencies in Pipelining

texts:
In my GATE Exam I have given with the following question  statements and

R5 ← R0 + R1
R6 ← R2 * R5
R5 ← R3 - R6
R6 ← R5/R4
X  ← R6

the question was to calculate number of Output, True and Anti Dependencies in the instructions.
I calculated and it turns out to be
RAW (True Dependency)

I1 - I2 (R5)
I2 - I3 (R6)
I3 - I4 (R5)
I4 - I5 (R6)

WAR  (Anti-Dependency)

I2 - I3 (R5)
I3 - I4 (R6)

WAW (Output Dependency)

I1 - I3 (R5)
I2 - I4 (R6)

Now my friend argued

Had the question been to calculate the number of possible data hazards the answer would have been different because Dependencies and hazards are not same

When we calculate possible hazards we should reorder the instructions and find the dependencies. Dependencies and hazards are closely related but not same. He has also gave me a pdf which implies that a dependency may not be a hazard. A dependency is a "possible hazard" considering all cases which involve reordering of instructions etc. But the solution of GATE question is involving those dependencies only which are causing hazards only not potential or possible hazard.
I go through them but was not able to finalize proper relationship between hazard and dependencies.
Can someone please explain how Dependencies, Possible Hazards and Potential Hazards  relate to each other in a way more easily understood? (Explanation using the above instruction set  is preferred)


texts:
What does it mean when in a machine learning paper there is
$(arg)^{T}$, what does the T does to an arg  in this 3b1b video on neural networks he puts the: $(w^{l-1})^{T}$


texts:
I am coding a procedure that takes an integer $d$, and generates $d$ finite lists $X_1 \ldots, X_d$ of elements. I would then like for it to output a list of the elements in the product set $X_1 \times \cdots \times X_d$.

I can't use nested for-loops because $d$ can vary so I wouldn't know how many to nest. I'm sure there's a totally standard solution to this problem, but I don't know enough to search for it successfully either here on online.

For what it's worth, here's one dumb solution I came up with. Let $b$ be the maximum cardinality of the sets $X_i$. Then run a single loop for $n$ running from $0$ to $b^d$; for each $n$, write it in base $b$ and use the $i^{\rm th}$ digit to read off the element of $X_i$ corresponding to that digit (and ignore if any of those digits are too big for the cardinality of the corresponding set). This will work, but feels like a pretty stupid solution.

What's the standard way of doing this?


texts: simplyfing common data values (parts of a string) in an array - by merging same attributes (data values)

texts:
I have arrays comprised of string elements like the following 2 examples. Each of the following lines is a string element of the array.
example1:
aaa bbb cc1 dd1
aaa bbb cc1 dd2
aaa bbb cc2 dd1
aaa bbb cc2 dd2
aaa bbb cc3 dd1
aaa bbb cc3 dd2

example2:
bbb rrr nnn ttt ooo eee ddd fff contr
bbb sss nnn ttt ppp eee contr
bbb sss nnn aaa ooo eee ddd fff contr
bbb rrr nnn ttt yyy eee ddd fff contr

I want to simplify and remove "redundant" lines by merging in a single line duplicate attributes. The goal is to have the fewest lines possible, without the data values being confusing. So the results should be:
example1:
aaa bbb cc1/c2/c3 dd1
aaa bbb cc1/c2/c3 dd2

example2:
bbb rrr nnn ttt ooo/yyy eee ddd fff contr
bbb sss nnn ttt ppp eee contr
bbb sss nnn aaa ooo eee ddd fff contr

(the results are an array as well).
My current approach goes like this: remove the first column then compare all elements. if equal lines are found, merge them. remove second column, compare. It becomes though somewhat complicated, as not all lines have the same number of data values (separated by spaces).
I'm stuck here. Any help would be welcome.


texts: What does this context-free grammar generate?

texts:
The grammar is

$$ S\to aSb\ |\ bSa\ |\ SS\ |\ \epsilon. $$

I think this generates the set of strings with equal numbers of $a$'s and $b$'s based on examples I've done. Is this correct?


texts: Zero-based array implementation with logarithmic insertion time

texts:
Normal zero-based arrays (ie not those with a sort order) have constant lookup time, but linear insertion time.

For a specific problem I was musing about a balanced tree that would allow for an zero-based array implementation with logarithmic time for all of the following operations: insertion, removal and finding the next and previous element.

I'm reasonably sure it should be straight-forward to implement: The non-leaf nodes would have to store the count of elements in their left branch respectively.

Such a data structure should be useful in text editors, as the user obviously can insert text anywhere in the document and yet the editor is supposed to render a screenfull of text around a given location quickly as well.

My question: What's this data structure called? Is there a buzzword I can google? (Such as "B-tree", "red-black tree", etc. for key-ordered search trees?)


texts: How to calculate combination from given n,r and rank?

texts:
Suppose that $S=\{1,2,...,n\}$ and we are given an integer $r\leq n$.

An $r$-combination of $S$ is obtained by selecting $r$ distinct integers out of the $n$. We order all $r$-combinations for a given $r$ lexicographically. Call the rank of an $r$-combination its rank in this ordering.

I am interested in finding a $r$-combination given $n$, $r$ and the rank.

For example, if $n=10$, $r=5$, rank $=72$, then the answer should be $1, 3, 5, 6, 7$.

How can we compute this efficiently? In particular, can we do this faster than generating the entire enumeration?


texts:
I'm reading through the HoTT book and I have a hard time with path induction.

When I look at the type in the section 1.12.1:
$$\text{ind}_{=_A}:\prod_{C:\prod\limits_{x,y:A}(x=_Ay)\to \mathcal{U}}
\left(
\left(\prod_{x:A}C(x,x,\text{refl}_x)\right) \to
\prod_{x,y:A}\prod_{p:x=_Ay} C(x,y,p)
\right),$$
I have no issue understanding what that means (I just have written the type from memory, to check that).

What I have issue with is the next very statement:
$$\text{with the equality}\quad \text{ind}_{=_A}(C,c,x,x,\text{refl}_x):\equiv c(x)$$
my first impression was that this last expression does not define the resulting function $$f:\prod_{x,y:A}\prod_{p:x=_Ay} C(x,y,p),$$
but just states its property.

That is in contrast to previous examples of the induction principles $\text{ind}_{A\times B}$,$\text{ind}_{A+B}$ or $\text{ind}_\mathbb{N}$ -- there are defining equations for those elements -- we actually know how to construct the resulting function, given the premises. Which is in agreement with the "constructiveness" of type theory adverted throughout the chapter.

Going back to $\text{ind}_{=_A}$, I was suspicious about the fact that (looks like) it is not defined. Stating that the element $f$ just exists seemed out of tune with the rest of the chapter. And indeed, the   section 1.12.1 seems to stress that my impression is wrong and we in fact have defined

  ... the function  $f:\prod_{x,y:A}\prod_{p:x=_Ay} C(x,y,p),$ defined by
  path induction from $c:\prod_{x:A}C(x,x,\text{refl}_x)$, which moreover
  satisfies $f(x,x,\text{refl}_x):\equiv c(x)$ ...

That leaves me utterly confused, but I have a feeling that this point is very important for all the further developments. So which of the two readings for $\text{ind}_{=_A}$ should I go with? Or, probably, I'm missing some important subtlety and the answer is "neither"?


texts: Linear optimization or Constraint Satisfaction Problem with food

texts:
I was hoping someone could point me in the right direction in terms of what type of problem I am describing here so I can research it.  My initial thought is that it is some form of Constraint Satisfaction Problem.

Say as an example I am working with food, and I would like to determine from a massive database of recipes which foods might sum up to equal a certain macro-nutrient profile.

For example, maybe I want to target a 410 calorie meal consisting of 30 grams of protein (4 cals per gram), 10 grams of fat (9 cals per gram) , and 50 grams of carbohydrates (4 cals per gram).

Would this be in the domain of CSP, or should I look elsewhere?


texts: How many different max-heaps exist for a list of n integers?

texts:
How many different max-heaps exist for a list of $n$ integers?

Example: list [1, 2, 3, 4]

The max-heap can be either 4 3 2 1:

    4
   / \
  3   2
 /
1

or 4 2 3 1:

    4
   / \
  2   3
 /
1


texts: Measuring and maintaining the diversity of individuals in Genetic Algorithm

texts:
While I was using the Genetic Algorithm to generate full correct Sudoku grids starting from a population of random grids, I occasionally face the problem of the process being stuck on a local maxima until the population loses its diversity.

So, I decided to find a mechanism for maintaining the diversity of the population to avoid the problem. What I thought about was:

Measuring the diversity of each individual by computing how different it is from the rest of the population:

For each individual $i$ : $$diversity_i = \sum_j distance(i, j)$$ and I used the hamming distance as the $distance$ function.
Ranking the individuals (for selection) based on both their diversity and their fitness.

I faced two problem with this approach:

Computing the diversity this way is expensive as it requires $n^2$ call to the $distance$ function (which is itself not a constant time function), raising the following question: what is a relatively optimal way for measuring the diversity of a population?
How to rank the individuals of a population based on both diversity and fitness?


texts: Binary-ish search through partially ordered set

texts:
I have an interesting function.  It takes subsets of {1,...,N} to positive integers, i.e. $f:P([N]) \rightarrow Z^+$.
I know that if S is a subset of S', $f(S) < f(S')$.  Also, if S and S' have the same cardinality, the ordering induced by f is lexicographic, so for example $f(\{1,2,4\}) < f(\{1,3,4\})$.
Given a value z, I'd like to find S such that $f(S) <= z$ and $f(S) <= f(T) <= z$ implies $f(S)=f(T)$ -- that is, I want to do a search on the lattice of subsets of [N].
If I knew the ordering were perfectly lexicographic, I'd use a simple binary search.  I don't know that, and I believe it is not (e.g., $f(\{1,2,3,4,5,6\})$ is possibly greater than $f(\{7\})$). Is there a good O(N) algorithm to do this search on the poset?  Obviously for N of any appreciable size I have to compute f on-the-fly and can't rely on in-memory storage.
Clarification after a discussion in the comments:
The particular $f$ I am dealing with is additive -- specifically, $f(S) = \sum_{k\in S} g(k) + f(\emptyset)$, with $g$ a monotonically increasing function. This may be easier than the general case (which is also interesting, but not my particular problem).


texts: How to prove language $L=\{a^{i}b^{j} : i \leq j^{2}\}$ is not CFL using Pumping lemma?

texts:
I'm trying to found a way how to prove this language is not context free. Using pumping lemma I'm halfway done. Consider word $a^{n^2}b^n$. If you divide it into $uvwxy$ and have only $a$'s in $v$ and $x$, you clearly get out of language when you pump up. If you do the same with $b$'s and pump down, you get out of language as well. But how dow do you show situation where there are only $a$'s in $v$ and just $b$'s in $x$?

Thank you


texts: Why do black-box deep learning algorithms produce better word similarities than cognitively plausible ones?

texts: Why do black-box deep learning algorithms (e.g. Mikolov et al 2013) produce better word similarities than cognitively plausible ones (e.g. Baayen et al 2011)? Could we combine the best of both worlds, biologically motivated learning mechanisms and state-of-the-art performance?


texts: Original values of base and linkage pointer

texts:
When you first call a function, the first two commands in assembly are PUSH(LP), PUSH(BP) (BP = base pointer, LP = linkage pointer). What are the initial values of BP and LP?
For example, take pages 2-3 of https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-004-computation-structures-spring-2017/c12/c12s3/procedures_answers.pdf.


texts:
I am designing a algoritm for a game using a Monte Carlo tree search AI that I implemented. I play against another player and want to get the best move. Every time I do a move I completely build a new search tree and do as much iterations possible given a certain deadline. Is there a way to use the previous tree that I build or do I always have to build a tree every time I make a move.
our turn: calculate tree beginning from scratch using uct
otherplayer turn: his turn
our turn: calculate tree beginning from scratch using uct
Is there a way I can optimize this So i could do even more iterations/ be faster ?
like for exemple:
our turn first: calculate tree beginning from scratch using uct
otherplayer turn: his turn
our turn: use tree we already calculated in our first turn and do more iterations given the values
Or are there other optimalisations I could do?
EDIT: https://stackoverflow.com/questions/47389700/why-does-monte-carlo-tree-search-reset-tree


texts: Existence of walk in undirected connected graph where nodes must end with assigned value

texts:
We have a graph with $N$ nodes and $N-1$ undirected edges, where it's possible to reach one node from any other node. Each node will get assigned a value randomly from [1,...,10]. We want the value of every node to end up at 10. The way we update is as follows, whenever we visit a node, we increment the value of that node by 1 with wraparound (e.g. 7 -> 8 and 10 -> 1). We can revisit nodes and edges as we please. We don't initially advance the counter in our node we start from. Return the number of possible nodes we can start from, such that every node ends with value 10.

I tried just doing simple backtracking search on the states, but the complexity is way too high, and I don't know when I can say "not possible", since we can cycle from 10 to 1.


texts: Can every regular expression be written as sum of products?

texts:
I was trying to prove that Parikh Image of every regular language is semi-linear. Even though it is true for CFL, but this question was about regular languages.
To prove this, I decided to proceed as follows:

Lemma 1: Every regular expression can be written as sum of products with star, i.e., $R = R_1 + R_2+ ... +R_n $ where each $R_i$ is a regular expression not involving any $+$.

Lemma 2: The Parikh image of a language corresponding to a regular expression that doesn't involve any $+$ is linear.

I proved the lemma 2 by induction on the structure of this specific type of regular expression. (which was easy and correct, by the way).

After proving (allegedly) these, it was easy to state that the Parikh image of the language defined by $R$ is just the union of linear sets, hence it is semi-linear.

I proved the lemma 1, again, using induction on the structure of the regular expression, but I am not sure if it is correct. Moreover, I am not sure if the Lemma 1 is even valid or not!

My proof was as follows:

$R = a $ where $ a \in \Sigma$ or $a=\epsilon$. This is already in the same form we required.
$R = R_1.R_2$ . This is also in required form.
$R = (R_1 + R_2).R_3$. Replace by $R_1.R_3 + R_2.R_3$.
$R = (R_1 + R_2)^* $ Replace by $(R_1^*.R_2^*)^*$

Do you think this proof is wrong, or even worse, the statement if wrong!


texts: Find a recurrence relation for merging of sublists of an array

texts:
There are $\log n$ sublists each of size $\frac{n}{\log n}$. Write a recurrence relation for merging these lists into an $n$ element list.

My Approach
Let $m = \log n$. Then,
$T(m) = 2T(m/2) + O(n)$, where $O(n)$ is for merge algorithm.

We get $T(m) = 2T(m/2) + O(2^{m})$.

Now solving we get $T(m) = O(n)$.

But intuitively there are $O(\log\log n)$ levels each doing $O(n)$ work so complexity to merge should be $O(n\log\log n)$. Where am I wrong? Please help. Tried hard but unable to get loophole.


texts:
Assume we have a tree and we want to serialize it.

Example:

Tree:
      1
     / \
    3   2
   / \ / \
  5  N N  N
 / \
N   N

can result as:

"1,3,5,N,N,2,N,N, N", // Pre Order serialization;
"N,5,N,3,N,1,N,2,N", // In Order serialization;
"N,N,5,N,3,N,N,2,1", // Post Order serialization

I would like to know, which one of these three serializations is unique for all trees and why ?


texts: Why do we need Kleene Star when there is concatenation?

texts:
For an alphabet $A = \{ a_1, a_2..., a_n \}$, the set of regular langages $L_r$ on $A$ are recursively defined by closed union, concatenation, and Kleene star's operator. I understood that languages ($A^*$) and regular languages (a subset of $A^*$) are different. Why do we need Kleene star, isn't concatenation enough for this definition?
Very simple "proof" that should be obviously wrong:
If $X \in L_r$ a regular language on $A$, and $E \in X^*$ (if i'm right also $X^* \in L_r$) a word then we could write $E$ as $e_1e_2\dots e_n = e_1 . e_2 \ldots e_{n-1} . e_n$, with each $e_i \in X$. Then $E$ is explicitly constructible by concatenation.
I forgot $\epsilon$ but so just add a simple rule that allow $\epsilon$.
My intuition says that it has something to do with infinity, that Kleene Star allows infinite-lengh chains whereas concatenation doesn't. Is it that?


texts: Proof of Subject-Expansion Theorem in Type Theory

texts:
I am beginning to study type theory, using Hindley's book "Basic Simple Type Theory", and I would like your help in the proof of a theorem. I would like to know whether my idea for how to prove the theorem is correct or not and if there are better/other ways to do it.

While learning about subject reduction and expansion I came across the following theorem:

  2C2. Subject Expansion Theorem If $\Gamma \vdash_{\lambda} Q: \tau$ and $P \vartriangleright_{\beta} Q$ by non-duplicating and non-cancelling contractions, then
  $\Gamma \vdash_{\lambda} P: \tau$.

The author leaves the proof as an exercise and I am trying to do it. Here's my idea:

First, I wrote that it's sufficient to prove the theorem for a $\beta$-contraction (represented by $\vartriangleright_{1\beta}$) since a $\beta$-reduction (represented by $\vartriangleright_{\beta}$) is simply zero or more steps of $\beta$-contraction.

Next, I noticed that if $P \vartriangleright_{1\beta} Q$ then $P \equiv (\lambda x.M)N$ and $Q \equiv [N/x] M$. I also noticed that there must be exactly one occurrence of $x$ free in $M$, as the $\beta$ contraction is non-duplicating and non-canceling. Then, I tried a proof by induction on $|P|$.
There are 3 cases:

Case 1: $M$ is a variable. In this case, since the contraction is non-duplicating and non-canceling, we must have $M \equiv x$. Then, $P \equiv (\lambda x.x)N$ and $Q \equiv N$. After standard calculations, I was able to derive the type of $P$ as being $\tau$.

Case 2: $M$ is an abstraction. In this case $P \equiv (\lambda x. \lambda y. M_1)N$. Then, $Q \equiv [N/x] (\lambda y. M_1)$. My idea here is to use the induction hypothesis to say that $(\lambda x. M_1)N$ and $[N/x]M_1$ must have the same type $\tau_1$ and from there perform calculations to conclude that $P$ and $Q$ must have the same type $\tau$.

Case 3: $M$ is an application. In this case $P \equiv (\lambda x. M_1 M_2)N$. There will only be one free occurrence of $x$ in $(M_1 \ M_2)$ and we consider only the case of this free occurrence happening in $M_1$.  (because the other case is analogous). Then, $Q \equiv [N/x] (M_1 \ M_2) = (([N/x]  M_1) \ ([N/x] M_2)) = (([N/x] M_1) \ M_2)$. My idea is to use the induction hypothesis to say that $(\lambda x. M_1) N$ and $[N/x] M_1$ must have the same type $\tau_1$ and then performe calculations to prove that $P$ and $Q$ must have the same type $\tau$.

Is my approach to the problem correct? Are there better/other ways to proceed?

Thanks in advance.


texts: Multiplication algorithm I wrote - slower than I expected

texts:
Recently I thought of an algorithm for multiplication and decided to stop dreaming and start writing on paper my ideas, and even implement this to code (in this case - Python 3.9.1).
I do not know if it resembles Karatsuba's algorithm, but I glanced at it and it seems to work very differently.

The idea behind this multiplication (calculating $x \cdot y$) algorithm is to represent them as a power of two, plus some remainder, then use the distributive rule of multiplication to get:
$$x = 2^a + K  \\ y = 2^b + T$$
$$ x \cdot y = (2^a + K) \cdot (2^b + T) = 2^{a+b} + T \cdot2^a + K \cdot 2^b  + K \cdot T$$
I chose the power to be $2$ as it would help us with bit-manipulation later on.
Calculating $2^{a+b}$ is easy using bitwise operations as so: $$ 2^{a+b} = 1 << (a+b)$$
But how would we find $a$ and $b$?
We want $2^a$ or $2^b$ to be the largest power of $2$ below our $x$ (or $y$ correspondingly), to take as much 'volume' from the original number, and thus making the calculations easier with bit manipulations. So, I just used the $\lg$ function, which from what I've read it can run in $O(1)$ running-time complexity (Or at worst, $\lg \lg n$). We have:
$$ a = \lfloor \lg(x) \rfloor, ~~~ b = \lfloor \lg(y) \rfloor$$
We then need to find $K$ which is just the remainder when we subtract $2^a$ from $x$: $$K= x - 2^a = x - (1 << a)$$
However, maybe subtraction isn't the best idea, maybe it takes too much time, and though about another bit manipulation. All I had to do is to flip the most significant bit (left most bit) which represents the greatest power of $2$ this number consists of, and so I had to pad exactly $a$ $1$'s and use the $\&$ bitwise operation to clear the MSB. We now have a code to find $K$ and $T$ respectively:
$$ K = x~~ \&~~ \text{int('1' * a, 2)} \\ T = y~~ \&~~ \text{int('1' * b, 2)}$$
Finally, we can add all the factors together, calling the function recursively to compute $K \cdot T$ to get:
$$ (1 << (a + b)) + (T << a) + (K << b) + \overbrace{\text{mult(K,T)}}^{\text{recursive call}}$$

def mult(x, y):
    if x == 1:
        return y
    elif y == 1:
        return x
    elif x == 0 or y == 0:
        return 0

    base_x = int(log2(x))
    base_y = int(log2(y))

    K = x & int('1' * base_x, 2)
    T = y & int('1' * base_y, 2)

    return (1 << (base_x + base_y)) + (T << base_x) + (K << base_y) + mult(K, T)

But oh! from what I've tested, this algorithm does not seem to get near the time it takes to multiply two numbers by just using the plain-old $\text{*}$ operation, Sob!
times = []
for _ in range(10000):
    x = random.randint(10 ** 900, 10 ** 1000)
    y = random.randint(10 ** 900, 10 ** 1000)
    start = time.time()
    mult(x, y)
    end = time.time()
    times.append(end - start)
print(sum(times)/len(times))

This tests $1,000$ multiplications of $900$ to $1000$ digits long random integers, then printing the average time. On my machine the average is: 0.01391555905342102 seconds. Python's regular multiplication won't even show a number, just 0.0 because it is so fast.
From what I know, Python's algorithm uses Karatsuba's algorithm, and it is roughly $O(n^{\approx 1.58})$ - I did not analyze mine strictly, but in one sense it runs at approximately: $$O(\max (\text{#Number_of_on_bits_x, #Number_of_on_bits_y}))$$
Because every recursive call, we turn off the $\text{MSB}$ - thus the number of recursive calls we make is the maximum number of bits that are on ($=1$) in $x$ and $y$, which is strictly smaller than the numbers themselves.. thus we can surely say it is $O(\max (x,y)) \sim O(n)$ as all the other operations in the functions are $O(1)$. So it boils down to the question of 'why?' - why is it slower? What have I done wrong in my algorithm so it is slower even that from first glance it seems faster?
Thank you!


texts: I'm having some trouble converting a FA to a RegEx

texts: I was reviewing some of the material that I found about FA to RegEx and while I was practicing with one or another conversion, I came across this FA that I could not pass to RegEx. Would someone be so kind as to give me the correct approach? This is my initial approach for this FA:  aa * b(aa * b)b * + bb * a(bb * a)a *.


texts: Convert (x + y = z) to propositional logic formula for 8-bit numbers

texts:
(Note: this was asked in the cstheory stackexchange, but I was told this is a more appropriate place for it.)

I have three 8-bit 2's-complement numbers (X, Y, and Z). I want to find a propositional logic formula using only the variables (x1, x2... x8, y1... y8, z1... z8), where xi is the ith bit of x which expresses the concept that X + Y = Z. How would I go about doing this?


texts: loop invariant of selection sort algorithm

texts:
I am asked to write an C code Selection Sort algorithm and use loop invariant to show its correctness.
We are given array A[1...n] of n integers. (Indexation 1 for clearance. In my code it starts at 0)

int i, j, min_index, temp;
for(i=0; i<n-1; i++) {
    min_index = i;
    for(j=i+1; j<n; j++)
       if(A[j] < A[min_index])
           min_index = j;
 temp = A[i];
 A[i] = A[min_index];
 A[min_index] = temp;
}

I see we need to 2 loop invariants to prove correctness of the algorithm.
Loop Invariant for the second inner loop:
     At the start of each iteration of for loop, A[min_index] is the smallest element in A[i, j).

     Initialization: before the first iteration i = min_index and j = i + 1. A[min_index] is the only
       element in A[i, i+1) which is trivially the smallest element.

     Maintenance: Next, we tackle the second part: showing that each iteration maintains the loop
      invariant. suppose for j loop invariant holds, that is, A[min_index] is the smallest in
      A[i, j). for the next iteration of loop where j = j + 1, if A[j + 1] < A[min_index] we update
      min_index to j + 1. Now A[min_index] is the new min in A[i, j+1).  Else we do nothing. in this
      case A[min_index] remains the smallest in A[i, j+1). in both cases loop invariant hold true.

     Termination: condition which cause to terminate loop is j = n. now by termination condition and
      loop invariant we can conclude A[min_index] is the smalles in A[i, j = n) which means we found
      minimum element A[min_index] in the subarray A[i, n-1].

Now we've proved correctness of second for loop, which find the smallest element in subarray A[i, n-1]. Let's write loop invariant for the outer loop:
     At the start of each iteration of loop, A[0, i) contains i smallest elements of A[0...n-1] but in
      sorted order.

     Initialization: prior to the first iteration of loop i=0. A[0,i) is empty subarray and predicate
      is vacuously true.

     Maintenance: We need to show that each iteration maintains the invariant property. Assume for i
      invariant holds. A[0, i) contains i smallest elements of original array in sorted order. at the
      next iteration i = i + 1. we can definitely conclude by first loop invariant that A[min_index]
      will be the smallest element in A[i, n). Since we know predicate is true for i, we can say that
      A[0, i) is sorted, and we swap A[i] with A[min_index]. we're done. A[0, i+1) contains i+1
      smallest elements of original array in sorted order.

     Termination: Termination condition which is i=n-1 along with invariant implies that A[0, n-1)
      contains n-1 smallest elements of array in sorted order. Since A[0, n-1) contains the n-1 smallest
      elements of the array, automatically the last element which is A[n-1] is greater than or equal to
      all elements in A[0, n-1) and therefore is in the correct place in sorted array.

I think it's clear from the proof why do we need to operate on n-1 elements of the array. So I've described what I've done myself, but I have doubts about proof. Is there any bogus in proof or can you suggest something better to improve parts of it? I appreciate your answers.


texts: What's really meant by context-free in the term context-free grammar?

texts:
I have been studying compilers for a while, and I have been searching what's meant by "context" in grammar and what it means for grammar to be "context-free", but with no result.

So can anyone help with this ?


texts:
If the time complexity $T(n)$ of two functions $x(n)$ and $y(n)$ are mutually recursive, as in Time complexity of mutually recursive functions, this gives $T(n)=O(2^n)$.  But how do you measure an algorithm with two or more (4 in the example below) recursive functions that are not necessarily mutually recursive?

Example: Recursive Step Function

$$
\begin{align*}
w(n)&=
\begin{cases}
w(n-1)+1 & \text{if } x(n-1)=y(n-1), \\
w(n-1) & \text{otherwise.}
\end{cases} \\
x(n)&=8w(n). \\
y(n)&=
\begin{cases}
1 & \text{if } w(n) > w(n-1), \\
y(n-1)+1 & \text{otherwise.}
\end{cases} \\
z(n) &=
\begin{cases}
z(n-1)+1 & \text{if } z(n-1) < y(n-1) \text{ and } z(n-1)=1, \\
z(n-1)-1 & \text{if } z(n-1) < y(n-1) \text{ and } z(n-1)\neq 1, \\
z(n-1) & \text{otherwise.}
\end{cases}
\end{align*}
$$

These functions loop until $w(n)=I$ and then output the value of $z(n)$, where $I$ is the user input value.  This input value could be rather large.  I get the worse case scenario is dependent on $w(n)$, as it increases slowly.

I have calculated that the function specifically $$w(n)=O\left(\frac{\sqrt{16n+16}}{8}+\frac12\right),$$ but I am new to time complexity.  Could anyone help me to understand?

Here is the example in pseudocode:

SET w to 0
SET x to 1
SET y to 1
SET z to 0
GET i
REPEAT
    IF z<y and z=1 THEN
        z=z+1
    ELSEIF z<y and z != 1 THEN
        z=z-1
    ELSE do nothing
    IF x=y THEN
        w=w+1 and x=8*w and y=1
    ELSE
        x=8*w and y=y+1
UNTIL w=i
PRINT z


texts:
So I'm trying to learn how to simplify Big O notations, these are the ones i'm working on (also sorry if i mess up the format, i'm new)

So the first one i have is:
f(n) = n    g(n) = n/loglog 12

I have to determine whether f is O(g), Omega(g), or Theta(g).

I also want to account for Big O vs Little O (which is also something i'm having trouble understanding but i think the idea is simply strictly greater than or strictly less than).

How i simplified:
f(n) = n, g(n) = n/loglog12 -> g(n) = n
f is Theta(g) ?? since simplified it is, f(n) = n and g(n) = n?

Am i doing this right?


texts: on coq: Why is the proof complete after proving only for one induction when we have more than one variable?

texts:
So I'm learning coq. And I came across the proof for associativity in addition forall (a b c : nat)

Appearntly when we do induction a. after intros a b c., it creates 2 subgoals

and afterwards we simply need to show that the two sides in both subgoals are equivalent, and the proof is completed.

So I'm just wondering why we don't need to do induction b. and induction c. to complete the proof? Why only performing induction on a is able to complete the proof?

Or in other words, how come in the function that returns the proof, we just get b and c for "free"? Constructively don't we need something like a double induction applied twice?


texts: How to express the data structure in the pesudocode of your algorithm

texts:
If I stored the output for my algorithm as a data structure as a cell array. How can I express that when I am writing the pseudocode for my algorithm.

For example, I have a set of $n$ values like {2,4,6} and for each value, I run the algorithm and output a matrix.

I want to express in the pseudocode of my algorithm how I stored the matrix for each value and output these values and the matrices corresponding to it.


texts: Extending the implementation of a Queue using a circular array

texts:
I'm doing some exam (Java-based algorithmics) revision and have been given the question:

  Describe how you might extend your implementation [of a queue using a circular array] to support the expansion of the Queue to allow it to store more data items.

The Queue started off implemented as an array with a fixed maximum size. I've got two current answers to this, but I'm not sure either are correct:

Implement the Queue using the Java Vector class as the underlying array structure. The Vector class is similar to arrays, but a Vector can be resized at any time whereas an array's size is fixed when the array is created.
Copy all entries into a larger array.

Is there anything obvious I'm missing?


texts: PSPACE-completeness of DFA intersection problem

texts:
Let some deterministic finite automata be given. There is a problem of determining whether the intersection of these DFA is empty, and I want to show its PSPACE-completeness.

It seems to me that I understand, why this problem lies in PSPACE: if $ n_1,\dots, n_k $ are the numbers of states, then one can take the product of these DFA and get that if there is a recognisable string, then there is a recognisable string of length $ \le n_1\dots n_k$. Then we can non-deterministically guess this string and use Savitch theorem.

So, the question is, how to prove PSPACE-hardness? Should I reduce any given TM to this problem, or maybe some known problem like QBF?


texts: How can the class of tail recursive functions be compared to the classes of PR and R?

texts:
How can the class of tail recursive functions (TR) be compared to the classes of primitive recursive functions (PR) and recursive functions (R)?

The computation of a PR function always halts. This does not apply to TR functions.
Given a tail recursive function $f$:
   $$f(x) = f(x)$$
The function $f$ obviously will result in an endless recursion and therefore $TR \not\subseteq PR $.
Also a PR function has a finite time and space complexity, where a TR function can have a finite space and infinite time complexity.
For this reason I assume:
 $$PR \subset TR \subset R $$

 Is this assumption correct?
 Is the Ackermann function $\in TR$?
 Is there a well known function which is in $R$, but not in $TR$?


texts: Why is the following language undecidable?

texts:
I'm currently learning for my exams this semester and tried to solve some old exams from the last years.
The question is to show, that L ist undecidable.
$L=\{w|T(M_w)\neq\emptyset \land \forall x \in T(M_w): xx\in T(M_w)\land xxx\notin T(M_w)\}$
I showed that the language $L'=\{w | T(M_w)\neq \emptyset\}$ is undecidable due to the Rice Theorem. I created to Turing Machines $M_1$ with $T(M_1)=\emptyset$ and $M_2$ with $T(M_2)=\Sigma^*$ to show that the language L' is not trivial. (since $1\in L$ and $2\notin A$. With out loss of generality i assume those machines have the Gödelindexes 1 and 2)
My problem now is, that I know no way to show, that this result transfers to the language L. I know that the language L must only contain such Gödel Indexes, that for those indexes the following TM must accept infinite words (because in case of $x\in T(M_w)$ there must be $xx\in T(M_w)$... and therefore must be $xxxx\in T(M_w)$ etc.)
I would love to hear suggestions / answers!
Thanks in advance


texts: For which values of $m$ is $m$-partition hard?

texts:
Consider the following reduction: $m$-colouring to $m$-partition.

Define an $m$-partition as: Given an undirected graph $G = (V, E)$ and an integer $j$. Does there exist a partition of the vertices into $m$ parts $\{V_1, V_2, \ldots , V_m\}$ such that at least $j$ of the edges have their endpoints in different parts of the partition?

I was able to come up with the reduction, but now I'm stuck at this question:

What I need to find is the values of $m$ where the reduction implies that $m$-Partition is NP-complete?


texts:
I want to solve job assignment problem using Hungarian algorithm of Kuhn and Munkres in case when matrix is not square. Namely we have more jobs than workers.
In this case adding additional row is recommended to make matrix square.
For example in the following
link.

And here task IV is assumed to be done.
But in real we do not have man D. Who will actually do task IV?
Can someone explain this phenomena?

In general I want to complete all tasks by loading workers uniformly and get maximum cost.
So how to implement this task by using job assignment algorithm above?


texts:
In AI we can classify a problem in 3 classes,  ignorable, recoverable or irrecoverable problems. Now while reading Water jug Problem

I am wondering in which of these 3 class it should fall? It should reside under recoverable right? As we can go back to the previous state in Water Jug Problem by altering the water level, I think it is recoverable. Is my thinking right?


texts: Linked list: advantages of preventing movement of nodes and invalidating iterators on add/remove

texts:
C++ and Java include native classes for linked lists, C++ std::list and Java LinkedList

For C++ std::list, nodes can be "moved" within a list, or from list to list (if the lists are compatible), via std::list::splice(), which in turn is used by std::list::merge() and std::list::sort().

With Java's native LinkedList, there is no method like splice() to move nodes. Attempting to emulate splice() by using listiterator add(element) and listiterator remove() methods doesn't work because add or remove will invalidate all iterators for a list other than the iterator used to do the add or remove. The indexed based get(index), add(index, element) and remove(index) functions could be used, but have time complexity O(n).

As for C++ std::list versions of add and remove, note that std::list::insert() doesn't invalidate any iterators, and std::list::erase only invalidates iterators that point to deleted nodes, and depending on the compiler, iterator invalidation may only occur with a debug build, while a release build (meant for speed) will not invalidate any iterators.

I ran into this issue with an SE question about implementing a merge sort with Java's native LinkedList. With C++, merge sort can be implemented using iterators using either top down (uses stack to store iterators) or bottom up (uses small (26 to 32) array of iterators), both of which sort a list by moving nodes within the original list via splice(), using the iterators as pointers to sorted run boundaries.

Why does Java's native LinkedList not include a splice method?

Some background on C++ and Java linked lists:

C++ std::list is usually implemented as a doubly linked list. I'm not aware of any exceptions to this, but it's possible since the standard doesn't require specific implementations. std::list is a standalone class. Visual Studio implements std::list as a circular doubly linked list with a dummy node. std::list::end is an iterator to the dummy node.

Java LinkedList is always implemented as a doubly linked list, and part of the ArrayList family of classes.


texts: A state machine that is either DFA or NFA: is it possible?

texts:
I am studying Crafting Interpreters, and although I understand the responsibility of the Scanner (or Lexer), I still cannot understand if it is a deterministic finite automaton or non-deterministic finite automaton. The code responsible for scanning the input text in the book is:
    private void scanToken() {
        char c = advance();
        switch (c) {
            case '(': addToken(LEFT_PAREN); break;
            case ')': addToken(RIGHT_PAREN); break;
            case '{': addToken(LEFT_BRACE); break;
            case '}': addToken(RIGHT_BRACE); break;
            case ',': addToken(COMMA); break;
            case '.': addToken(DOT); break;
            case '-': addToken(MINUS); break;
            case '+': addToken(PLUS); break;
            case ';': addToken(SEMICOLON); break;
            case '*': addToken(STAR); break;
            case '!':
                addToken(match('=') ? BANG_EQUAL : BANG);
                break;
            case '=':
                addToken(match('=') ? EQUAL_EQUAL : EQUAL);
                break;
            case '<':
                addToken(match('=') ? LESS_EQUAL : LESS);
                break;
            case '>':
                addToken(match('=') ? GREATER_EQUAL : GREATER);
                break;
            case '/':
                if (match('/')) {
                    while (!isAtEnd() && peek() != '\n') {
                        advance();
                    }
                } else if (match('*')) {
                    do {
                        if (peek() == '*' && peekNext() == '/') {
                            advance();
                            advance();
                        } else {
                            advance();
                        }
                    } while (!isAtEnd());
                } else {
                    addToken(SLASH);
                }
                break;
            case ' ':
            case '\r':
            case '\t':
                // Ignore whitespace.
                break;
            case '\n':
                line++;
                break;
            case '"': string(); break;
            default:
                if (isDigit(c)) {
                    number();
                } else if (isAlpha(c)) {
                    identifier();
                } else {
                    Lox.error(line, "Unexpected character.");
                }
                break;
        }
    }

According to several sites out there, the FA definition is:

Finite Automata(FA) is the simplest machine to recognize patterns.The
finite automata or finite state machine is an abstract machine which
have five elements or tuple. It has a set of states and rules for
moving from one state to another but it depends upon the applied input
symbol. Basically it is an abstract model of digital computer.
Following figure shows some essential features of a general
automation.

A DFS consists of the following:
Q : Finite set of states.
Σ : set of Input Symbols.
q : Initial state.
F : set of Final States.
δ : Transition Function.

and for NFA:
Q : set of all states.
Σ : set of input symbols. ( Symbols which machine takes as input )
q : Initial state. ( Starting state of a machine )
F : set of final state.
δ : Transition Function, defined as δ : Q X Σ --> Q.

My lexer can start in any state, does that mean it is either DFA or NFA? How can I conclude if it is one or the other?


texts: What is the nature of this algorithm and How to find its complexity ?

texts:
This algorithm computes the number of ways one can make change for n cents assuming one can use six types of coins. Singles, half dollars, quarters, dimes, nickels and pennies. In the following algorithm, what is this type of algorithm called ? Is it dynamic or greedy ? Also, how do I start about finding the complexity of such an algorithm ?

B(n)
count ← 0
s ← 0
while s ≤ n/100
   do srem ← n − 100*s
   s ← s + 1
   h ← 0
   while h ≤ srem/50
       do hrem ← srem − 50*h
       h ← h + 1
       q ← 0
       while q ≤ hrem/25
          do qrem ← hrem − 25*q
          q ← q + 1
          d ← 0
          while d ≤ qrem/10
             do drem ← qrem − 10*d
             d ← d + 1
             ni ← 0
             while ni ≤ drem/5
                 do ni ← ni + 1
                 count ← count + 1
return count

I have so far calculated:
Time complexity T(n) = 1 + a(1+b(1+c(1+d(1+e*1))))
a, b, c, d, e are the while loops.

In the worst case, s is n/100, so substituting that on a, and srem <- n - 100*n/100 = 0,

T(n) = n/100(1 + 0) = Big-O(n).

But when s = 0,

T(n) = 1 + 0(1+ ....)
     = Big-O(1)

How do I find the time complexity ? Which is the way to go? Thank you in advance.