texts:
What will be a space complexity of a conversion of a sorted array to a balanced BST in case of a recursive solution?
Could you, please, check my reasoning. Is it correct?
Here is my algorithm for solving the problem:
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public TreeNode SortedArrayToBST(int[] nums) {
        return SortedArrayToBST(nums, 0, nums.Length - 1);
    }

    private TreeNode SortedArrayToBST(int[] nums, int low, int high) {
        if(high < low) {
            return null;
        }

        if(low == high) {
            return new TreeNode(nums[low]);
        }

        int center = low + (high - low)/2;

        return new TreeNode(
            nums[center],
            SortedArrayToBST(nums, low, center - 1),
            SortedArrayToBST(nums, center + 1, high)
        );
    }
}

The space complexity in this case will be equal to the amount of the call stacks + O(1). So, we need to find the amount of stacks, given that the nums.Length == n;
Each time there is a recursive call the array is split in two. That means that there will be as many stacks as we can divide n by two, until it is equal to 0. But also, since for each of the two splittings we run the recusion we need to multiply that by 2. That brings us to the O(2*log(n)) or simply O(log(n)) space complexity.
UPDATE
We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors." - the answer to the question What will be a space complexity of a conversion of a sorted array to a balanced BST in case of a recursive solution? is definitely not yes/no.
Can you edit your post to ask about a specific conceptual issue you're uncertain about? Sure I did. Let me repeat my conceptual issue: What will be a space complexity of a conversion of a sorted array to a balanced BST in case of a recursive solution?.
As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. I am not the only one who needs to know the space complexity of the conversion.
Coding questions and questions about code or that are specific to a particular programming language are off-topic here. I don't have coding questions.
Not everyone here knows Java. We would prefer to see concise pseudocode, not Java code. Not everyone knows pseudocode. E.g. I don't know it.


texts: Prove: If finite automata M with k states accepts a string with at least k characters, then the language L(M) is infinite

texts: I need to prove that if finite automata $M$ with $k$ states accepts a string with at least $k$ characters, then the language $L(M)$ is infinite. I have no idea where to start. Any suggestions?


texts: Minimize number of comparisons to discover a strict total order

texts:
$S$ is a set of $n$ elements with some unknown strict total order. The goal is to discover the greatest $k$ elements, where each step consists of comparing $m\ge 2$ elements at once (so if we compare $a, b,$ and $c$, we might get $b > c > a$). Any strategy for achieving this will have some worst-case number of steps $t$, and our strategy needs to minimize $t$ for the given $n, m,$ and $k$.

This is a generalization of the
fastest horses problem,
 the solution of which can be partially extended to any case with $n=m^2$, and we are left with finding the top $k-1$ elements of $k^2-1$ elements, with the same value for $m$, but we also already know how some of the elements compare, ending up with a structure like:

*>*>*>*

*>*>*>*
V
*>*>*
V
*>*
V
*

The problem is proving that a given solution is optimal without an exponential-time brute force search of strategies. Even just proving that starting with the initial strategy I described is always optimal would be very helpful.


texts: Binary tree algorithm asymptotic analysis problem

texts:
Assume we have a perfectly balanced Binary tree.
We have the following algorithm: For each passed node, traverse through all its ancestors and then do the same algorithm for the left and right child of the node.

So, the way I try to find the Big-O complexity is this: There are O(N) nodes in the tree and each has O(log2N) ancestors, so overall we'll have O(N*log2N) complexity if we start the algorithm from the root.

Now consider another problem for the same Binary tree: For each node, go to its left and right child. If the node doesn't have any children, for each ancestor, go through all the previous ancestors.

Now my attempt for finding the complexity: We basically keep going through every node until we reach the leafs. There are N/2 leafs in a perfect Binary tree with N nodes and for each leaf we have (log2N) ancestors. Since for each ancestor we have to traverse every previous, the overal compexity when we're on a leaf is O(Log2(N)^2), so overall complexity becomes O(N*log2(N)^2).

The problem is that I think the algorithms basically do the same thing. Why do I get different complexities for them?


texts: Prove that 2-Colourability is in L from Undir-Reachability is in L

texts:
Let Undir-Reachability be the following problem:
given an undirected graph G and two specified vertices s and t in G, is there a path from s to t in G?

I need to prove that the 2-Colourability is in L, by knowing that Undir-Reachability belongs to the complexity class L.

I don't know how to start.


texts: Mapping spherical coordinates onto faces of an icosahedron

texts:
I'm looking for an algorithm which takes spherical coordinates (say lat-long) and identifies which face of an icosahedron a ray moving in that direction would intersect.
My end goal here is to explore various cartographic map projections from a sphere onto an icosahedron (ex: Gnomic, Fuller Dymaxion, Snyder equal-area). All of these begin with the problem of identifying which face of the icosahedron a given coordinate belongs to and then mapping a standardized spherical triangle onto a standardized flat triangle.


texts: Is a balanced binary tree a complete binary tree?

texts:
Considering that the opposite is true it's not mentioned anything about this. I am assuming its not, but I need a very good distinction between these two types of binary trees.

All I know is this:

A binary tree is balanced (or height balanced), if the height of any node’s right subtree and left subtree differ no more than $1$.
A complete binary tree of height h is a binary tree that is full down to level $h-1$, with level $h$ filled in from left to right.


texts: Reinforcement Learning: An Introduction, A Gambler's Problem, Exercise 4.7 Solution

texts:
Currently reading a recent draft of Reinforcement Learning: An Introduction by Sutton and Barto. Really good book!

I was a bit confused by exercise 4.7 in chapter 4, section 4, page 93, (see attached photo) where it asks you to intuit about the form of the graph and the policy that converged. I do not understand why this policy is as it is, and was wondering if anyone has any insight into the problem or answers for this exercise in the book.

I have so far look extensively around Google for answer booklets or any work on the problem to no avail. I could not resolve why s=50 would be a bound with a high a=50 when surely any similar policy could be applied to s=51 with a=49? Any help is much appreciated, many thanks!


texts: A request for literature on Matching your partner problem

texts:
I need reference for a good book (a title and an author will do) or reference on the web which explains the problem of matching procedures of suitable partners between several
males and females based on filled questionnaire of the type

I require this property of my potential partner or
I would be very happy if my partner had this property or
I definitely do not want this property, etc.

say on the scale from 0 (definitely no) through 5 (may be) to 10 (definitely yes).
The property may be height between 170 and 185 cm, having a slim figure, blond hair, blue eyes etc.
This book I'm looking for may be from fields on expert systems of the above type, probability,
statistics or computer science, etc.
I'm looking for theoretical treatment in great depth not a particular programming language solutions.


texts:
I took an algorhytm course on coursera and there some optional questions for student enrichment. I can't solve the following task:

  Decimal dominants. Given an array with n keys, design an algorithm to find all values that occur more than n/10 times. The expected
  running time of your algorithm should be linear.

And authors provied following hint:

  Hint: determine the (n/10)-th largest key using quickselect and check
  if it occurs more than n/10 times.

Actually it is not cleat for me how can quick select help me. quick select is algorhitm which can help to find k-th largest element in linear time. In the lecture materials written that it work approximately linear.

Let's work with example. We have 100 elements array. We found 10-th elements.
( frankly speaking according the book we found such element order that all elements with index > 90 more or equals than elems[90] and all elements with index < 90 less or equals elem[90]

How can I calculate occurences?
Imagine, that we calculated occurences and it is less than 10. What would be the next step?

P.S.


texts: Dynamic Programming - Print all paths from (0,0) to (n,n) in Grid/Lattice

texts:
I'm trying to write an algorithm to print all the paths from point (0,0) to (n,n) in a grid.
The only possible moves are right and up.
Also, you can't move below the diagonal y=x. e.g if you're at (1,1) you can only move to (1,2), but not to (2,1), since it's below the y=x diagonal.

I wrote an algorithm that calculates the number of possible paths from (0,0) to any given (x,y), such that the above limitations are held, but I can't find a way to print out the paths that give these numbers.

The algorithm I wrote is a bottom-up one, as follows:

JUMP(x, y)
1.  M[x-1,y+1] ← 1
2.  for i=0 to x+1
        M[i,y+1] ← 0
3.  for i=0 to y+1
        M[x+1,i] ← 0
4.  for j=0 to y-1
        for i=j+1 to x
            M[i,j] ← 0

5.  for j=y to 0
        for i=j to 0
            M[i,j] ← M[i+1,j] + M[i,j+1]

6.  return M[i,j]

Please advise on this.


texts: Why does Coq include let-expressions in its core language

texts:
Coq includes let-expressions in its core language.
We can translate let-expressions to applications like this:
let x : t = v in b ~> (\(x:t). b) v
I understand that this does not always work because the value v would not be available when typechecking b. However this can be easily fixed by special casing the typechecking of applications of the form (\(x:t). b) v. This allows us to remove let-expressions at the cost of a special case while typechecking. Why does Coq include still include let-expressions? Do they have other advantages (besides not needing the special case)?


texts: Is every X3SAT instance with no cycles satisfiable?

texts:
Exactly 1 in 3 SAT (X3SAT) is a variation of the Boolean Satisfiability problem. Given a set of clauses, where each clause has three literals, is there an assignment such that in each clause exactly one literal is true?  X3SAT is NP-hard even if we assume all literals are positive (monotone) and no two clauses have more than one literal in common (linear).

A cycle is a set of clauses such that each clause has one free literal and two backbone literals. A literal is free if it appears in only one clause in the cycle. A backbone literal appears in exactly two cycle clauses.

My question: Is a linear and monotone X3SAT instance with no cycles always satisfiable?

Background: We can think of linear monotone X3SAT as the following problem:  we are given a set of clauses, where each clause has three positive literals and no two clauses have more than one literal in common; the goal is to determine whether there is a set of literals such that each clause contains exactly one literal from the set.

I have generated a number of unsatisfiable linear monotone X3SAT instances and they all have large numbers of cycles, so I'm wondering if every unsatisfiable linear monotone X3SAT instance will have at least one cycle.

The smallest linear and monotone cycle has three clauses:

$\quad$ 3-cycle: $(a,x_1,x_2)(b,x_2,x_3)(c,x_3,x_1)$
$\quad$ Free: $a,b,c$
$\quad$ Backbone: $x_1,x_2,x_3$

A cycle can have more than three clauses.  A cycle with $k$ clauses has $2k$ distinct literals, $k$ free literals, and $k$ backbone literals. A $k$-cycle has $\lceil F_{k+3} / 2\rceil$ satisfying assignments, where $F_i$ is the $i$-th Fibonacci number.

The smallest unsatisfiable linear and monotone X3SAT instance has six 3-cycles, but only five clauses:

$\quad (a,x_1,y_1)(a,x_2,y_2)(a,x_3,y_3)(x_1,x_2,x_3)(y_1,y_2,y_3)$

It contains the following 3-cycles:

$\quad(x_1,x_2,x_3)(a,x_1,y_1)(a,x_2,y_2)$
$\quad(x_1,x_2,x_3)(a,x_1,y_1)(a,x_3,y_3)$
$\quad(x_1,x_2,x_3)(a,x_2,y_2)(a,x_3,y_3)$
$\quad(y_1,y_2,y_3)(a,x_1,y_1)(a,x_2,y_2)$
$\quad(y_1,y_2,y_3)(a,x_1,y_1)(a,x_3,y_3)$
$\quad(y_1,y_2,y_3)(a,x_2,y_2)(a,x_3,y_3)$

X3SAT can be converted into a max weight independent set problem. Let each literal be assigned a vertex. Two vertices have an edge iff the two literals appear together in a clause. The weight of each vertex is the number of clauses the literal appears in (one half the degree of the vertex). The X3SAT instance is solvable only if there is an independent set with weight equal to the number of clauses. If the instance is satisfiable then the graph can be made bipartite by removing exactly one edge from each clause.


texts: Given an array of n unsorted integers, how can you check that any 2 elements within k distance of some element don't vary by a multiple of 2?

texts:
In O(n log k) time?

The input is the array of integers n, and some integer k. The output should be a boolean for whether or not the following condition holds for all elements: any two elements within k distance of this element cannot vary by a multiple of two (the maximum cannot be double the minimum).

The brute force solution would be to iterate over every element, and then iterate over all elements within k distance of it, finding the maximum and minimum, and checking to make sure the maximum is less than 2x the minimum.

However, that would take O(nk) time. Is there a way to do this in O(n log k)?

I was thinking about maintaining a min heap and a max heap (as insert and delete operations have a runtime of O(log k)), but it seems like a lot of extra work (you would have to keep a hashtable of element positions in the heap in order to remove them).

Any ideas?


texts: How is sound input and output data converted to use with machine learning networks?

texts:
Suppose one has a couple of .wav files with English spoken words, multiple ones for each word, and for each such set there exists a transcription of their right output, the pronunciation as ascii text.

As far as I know, machine learning neural networks use arrays of floats as input and output, and also internally.

What do one do in machine learning in order to convert such 'real world' data formats/data sets into another data structure that is meaningful and suitable for the machine learning neural networks?

Furthermore, what classifies a particular data structure as 'suitable', except the fact that it can be expressed as arrays of integers (what fits every digital data)?

(I suppose it could be more sophisticated than stripping the headers and feeding the uncompressed binary data in as integers, or is it?)

edit: in an other SE site's question (regarding how to filter out an image of Justin Bieber), an answer asserts that one "has some method of feature generation to transform the raw images into features that are useful for machine learning purposes", but it doesn't explain how this is done, or how does one begin to create a method for such a feature conversion.


texts: Formal Logic - Natural deduction: Problem with assumptions about exists-negation

texts:
I'm stuck on how to progress with this proof, despite I have tried, I cannot see the next move.
Given this proof without predicate:

So far what I've accomplished:

My idea is, as I can't see any other option using (-(Sv(P->Q)) as the first assumption in order to introduce a conditional, so the assumption must end in P ^ -Q ^ -S. As you can see I have obatined -Q and -S but, how do I proof P?
SOLUTION:


texts: Move tokens from s to t as fast as possible

texts:
Let $G=(V, E)$ be an unweighted and undirected graph, and $s, t \in E$.

The problems starts with $n$ tokens on $s$.

The goal is to move theses tokens to $t$ in a minimum of rounds with these rules :

Each token can be moved up to once per round (a movement being when you transfer the token from $v$ the vertex that holds it, to $w \in N_G(v)$).
Each vertex $v \in V\backslash \left\{s, t\right\}$ can hold at most one token ($s$ and $t$ are unconstrained).

So far, what I've thought to is :

If $N_G(s)=0$ or $N_G(t)=0$, it is not possible.
If $N_G(s)=1$ or $N_G(t)=1$, you can just apply a BFS from $s$ to find the shortest path, then transfer every token one by one trough this path.
If $N_G(s) \geq 2$ and $N_G(t) \geq 2$ you can apply a maximum flow algorithm on $G$ with $1$ as capacity for every edge. If the maximum flow is $1$ then you can apply a BFS and transfer every token through this path again. However if the maximum flow is $\geq 2$, then I don't really see what to do (having a maximum flow $\geq 2$ doesn't even guarantee there are multiple paths as nodes can hold at most $1$ token, while max flow tests only for edges, and even if there are multiple paths in some cases it can be better to use only the shortest path - e. g. for $2$ tokens if you have to paths but one is at least to edges longer -).

Does this problem have a name? What topic of graph theory does it belongs to? Are there efficient algorithms to solve it?


texts: Does the O(n) algorithm always run faster than the O(n^3) algorithm? Why?

texts: Assuming that the time complexity of the two algorithms $A_1$ and $A_2$ to solve the same problem are $O(n^3)$ and $O(n)$ respectively. If you write programs for these two algorithms and run them in the same environment, does the program of algorithm $A_2$ run faster than algorithm $A_1$ for sure? why?


texts: Hoare Calculus Incorrect Assignment Axiom

texts:
I'm currently preparing for an exam and recently came across the following exercise and would like to know whether my solution would be correct.

Exercise:
Prove that the following axiom is not correct in the Hoare Calculus:

{true} u:= t {u=t}

My Proof via Reductio ad absurdum:

Assumption:

Axiom is valid Hoare Calculus Axiom and therefore agrees with the other Axioms.

Proof:

Consider the Hoare Triple: {t = u+1} u:=t {u = t}

This triple is obviously invalid because it does not agree with the Assignment Axiom of the Hoare Calculus.

However, given our Assumption, we can derive it as a valid triple:

(t= u+1) => (true) (Weaken Precondition)

{true} u:=t {u=t} (Axiom of the Assumption)

=> {t = u+1} u:=t {u=t} <- contradiction! => Assumption was false, Axiom is not correct.

q.e.d


texts:
How can I prove that this language is regular, possibly by making a finite automata for this: $(ab)^*(cb^n)^*$, where $n\ge1$?

An automaton can easily be drawn for the part $(ab)^*$, but the part $(cb^n)^*$ doesn't seem to be regular because if the Kleene closure is taken $\ge2$ times, then it will be of the form $(cb^n)(cb^n)$, which reduces to string matching and is context-sensitive.

This was actually a question, solution to which said that the above language has the following regular expression: $(ab)^*(cbb^*)^*$.


texts: How to represent text for a program to add punctuation to a block of text?

texts:
I want to try and make a program where I remove the punctuation from a block of text and it then inputs it in the correct places.
I have started with a simpler element of just using text and spaces, no commas, full stops etc.
The first angle I have been taking this is with machine learning, neural networks and simpler word count probabilities.
However the thing I am struggling with is the representation of the block of text. At the moment I give it a block of text and it reads say 20 letters then breaks it into test based on where it thinks a word is. This is ineffective though because it may just cut off half a word at the start/end of the block.
Just wondering if anyone had an idea of a way to use the block of text in this way in a better way to do this task!
Many thanks


texts: Is it possible to solve the halting problem if you have a constrained or a predictable input?

texts:
The halting problem cannot be solved in the general case. It is possible to come up with defined rules that restrict allowed inputs and can the halting problem be solved for that special case?

For example, it seems likely that a language that does not allow loops for instance, would be very easy to tell if the program would halt or not.

The problem I'm trying to solve right now is that I'm trying to make a script checker that checks for the validity of the program. Can halting problem be solved if I know exactly what to expect from script writers, meaning very predictable inputs. If this cannot be solved exactly, what are some good approximation techniques to solve this?


texts: Terminology for a graph with ports on its nodes

texts:
A Graph is a well-defined concept in mathematics, computer science and engineering disciplines that depend on them. However, oftentimes a practical implementation of a (directed) graph in a certain domain or application requires that edges don't merely connect vertices, but instead connect ports that exist on these vertices. In a directed graph, this would imply separation between input ports and output ports, wherein typically an edge starts at an output port and arrives at an input port.

Examples are easy to find: shader design tools, signal flow graphs in compiler theory, electronic schemas, high-level ETL scripting... all these tools require that vertices have named or distinct inputs and outputs.

Now for my question: is there any theory and nomenclature on these kinds of graphs, or is this considered to be an "implementation problem" of the engineering sciences? As you notice from my question, I can't quite pinpoint what this kind of thing is called ("A Graph With Node Ports"), and I'd love to see that answered.


texts: given two vertices in an undirected graph find if there are two vertex disjoint paths connecting them

texts:
Why does the following procedure not work?

Let given vertices be $(u,v)$

Run a dfs from any vertex.
Compute : $low[u]$ for all vertices in the graph
$low[u] = min(disc[u], disc[w]) $
where w is an ancestor of u and there is a back edge from
some descendant of u to w.
In the tree formed by dfs, find the $lca(u,v)$ of given nodes.
If $lca$ is $u$ or $v$:

(Say $lca = u  $ wlog)  if $low[v] <= disc[lca]$  then yes else no.

If $lca$ is not any of the given nodes:

if $low[u]<disc[lca]$ and $low[v]<disc[lca]$   then yes else no.

Here one of the path is $u->lca->v$ and other is using the back edge.
Let $low[u]=low[p]$ where $p$ is a descendent of $u$
and $low[v]=low[q]$ where $q$ is a descendent of $v$.
$p$ to $low[p]$ is a back edge and so is $q$ to $low[q]$.

$u->p->low[p]->low[q]->q->v$ is the other path

Please provide with an example to show why does this not work?


texts:
Came across this question : State whether True or False

  A prime attribute can be transitively dependent on a key in 3NF

Answer: True
How could this be true? Because as far as I know, A relation initially in 1NF is said to be in 3NF when partial and transitive dependencies have been eliminated. Correct me if I'm wrong.
Also, would it be correct to say that given a relation which doesn't have any non prime attribute along with no partial dependencies, then the relation is in BCNF ?
(I don't have any knowledge beyond BCNF).


texts: Reduction: Vertex Cover to Binary Integer Program (Decision Problem)

texts:
I am stuck with the following task:
Show that the Decision Problem "Vertex Cover" is polynomial-time reducible to the Decision Problem "Binary Integer programming".

I have the feeling that there must be a very easy way.

My approach until now:

We can convert any decision problem to an optimization problem in polynomial time.
We can reduce the optimization problem of vertex cover to a linear program in polynomial time. (https://en.wikipedia.org/wiki/Integer_programming#Proof_of_NP-hardness)
We can convert any optimization problem to a decision problem in polynomial time.

Is this approach ok? And/Or is there a better/easier way?

kind regards
James

EDIT: I think the following solution should work

Let $a_{i,j}$ be 1 if vertex $j$ is connected with edge $i$ and otherwise 0. Let $r=|E|$ and $n=|V|$.

A=
\begin{bmatrix}
     a_{1,1} & a_{1,2} & \dots & a_{1,n} \\
     a_{2,1} & a_{2,2} & \dots & a_{2,n} \\
     \vdots & \vdots & \ddots & \vdots \\
     a_{r,1} & a_{r,2} & \dots & a_{r,n} \\
     -1 & -1 & \dots & -1 \\
\end{bmatrix}

Let $b_i = 1$  $\forall i \in 1..r$

b=
\begin{bmatrix}
     b_1 \\
     b_2 \\
     \vdots \\
     b_r \\
     -k \\
\end{bmatrix}


texts: Is discrete math enough for computer science ? Or there other Math topics that I should also learn With it?

texts:
I want to learn computer science, SO is discrete math enough for computer science ? Or there other Math topics that I should also learn With it ?
I don’t have specific topic that I care more about than others (like cryptography) ,Just CS.


texts: if $L_1$ and $L_2$ are languages over the same alphabet and $L_1 \cap L_2$ is context free, at least one of them must be context free

texts: I am having a hard time understanding if this would be true or false, can someone point me in the right direction?


texts: Do you get DFS if you change the queue to a stack in a BFS implementation?

texts:
Here is the standard pseudocode for breadth first search:

{ seen(x) is false for all x at this point }
push(q, x0)
seen(x0) := true
while (!empty(q))
  x := pop(q)
  visit(x)
  for each y reachable from x by one edge
    if not seen(y)
      push(q, y)
      seen(y) := true

Here push and pop are assumed to be queue operations. But what if they are stack operations? Does the resulting algorithm visit vertices in depth-first order?

If you voted for the comment "this is trivial", I'd ask you to explain why it is trivial. I find the problem quite tricky.


texts:
I stumbled upon the following post while learning about turing machines:

Right moving turing machine

I kind of understand the intuition behind why a TM that only moves to the right works like a FSA but I can't think of a general way to create a let's say DFA (or NFA, doesn't really matter) which accepts the same language as a given right moving TM.

So my question would be:

Given an only right moving TM $M$, what would be a general method for constructing a DFA $D$ such that $L(M) = L(D)$?

Alternatively, given an only right moving TM $M$, how to construct a NFA $N$ such that $L(M) = L(N)$?


texts: Proving the language of non-primes is in NP

texts:
I am learning about NP problems and found this problem in my textbook that I was not sure how to answer, and was looking for some help on how to start the question.
Show the following language is in NP:
Not-Prime = {n ∈ N: n is not a prime number}
So far, I have created an efficient decider for the language with a certificate, but I'm not sure how to prove that the language is actually in NP. Thank you for any advice!


texts: Intersection of a recognizable language and a decidable language is decidable?

texts:
I'm having trouble with proving that "Intersection of a recognizable language anda  decidable language is decidable.

I assume this is true although I have no idea how to proof it. Can somebody point me in the right direction?


texts: Regular expression for $\{x : \#_{01}(x) \mod 3 = 0\}$

texts:
Let $L_1$ be the language over alphabet $\{0, 1\}$ defined by $L_1 = \{x : \#_{01}(x) \mod 3 = 0\}$.
Give a regular expression that denotes $L_1$, and justify its correctness

Attempt
Believe this is asking for number of $01$'s in $x$ but $|x|$ must be an even number. Like $x = 0101$, $|x| = |0101| = 4 \mod 3 = 1$ wouldn't work. However $x = 010101, |x| = 6$ would work?
How would I make a regex for this?
$R_1 = (01)^*$. How would I do the mod condition?


texts: Find a point inside the difference of ellipsoids

texts:
Given two ellipsoids $\mathcal{E}_1 = \{ X | X^T A_1 X + 2B_1^T X + C_1 \leq 0\}$ and $\mathcal{E}_2 = \{ X | X^T A_2 X + 2 B_2^T X + C_2 \leq 0\}$ both non-empty, it is possible to test if $\mathcal{E}_1 \subseteq \mathcal{E}_2$. Indeed, by the use of the so called S-procedure, $\mathcal{E}_1 \subseteq \mathcal{E}_2$ $\iff$ $\exists \lambda > 0$ such that
$$ \begin{bmatrix} A_2 &B_2\\ B_2^T &C_2\end{bmatrix} \preceq \lambda \begin{bmatrix} A_1 &B_1 \\ B_1^T &C_1\end{bmatrix}$$

Question

Assume that $\mathcal{E}_1 \not\subseteq \mathcal{E}_2$. I want to find a point in $\mathcal{E}_1 \setminus \mathcal{E}_2$. How can I do that? I think one should follow the proof of the S-procedure (the necessity part) and eventually construct one on those lines ... Can someone help?


texts: What's the difference between Adaptive Control and a Kalman Filter?

texts:
From my basic understanding of Adaptive Control, I understand that it uses the error and the velocity of the error to approximate the error in the solution space of a problem, thus allowing for guaranteed convergence under certain conditions and rapid adaptation to changing conditions. I've accumulated this knowledge basically from anecdotal evidence and from this video.

From my basic understanding of a Kalman Filter, it takes into account the error from past measurements to estimate the current state with greater accuracy.

From my flawed perspective, they seem almost identical, but what's the difference between the two? I've heard anecdotally that they are duals of each other, but that the Kalman Filter is only for linear systems? Is this close to the truth?


texts:
In Formal grammars course we have a task to implement an extended NPDA (a pushdown automata where taking any amount of symbols from the stack is allowed (including ε) and it can be in several states at the same time) in any programming language. It can be one that accepts with a state or an empty stack.
I have looked around and all on the implementation algorithms I have found do not allow for transitions like (ε/ε)/A (read nothing, take out of stack nothing, just add A to stack). The problem of course is that there is (as far as I know) no sure way to terminate this kind of branch and, if indeed, imput string does not belong to this language, it would just infinitely try to loop and loop these kinds of transitions.
So, my question is - how to implement an extended NPDA? How to know when to stop generating a branch and say "this branch goes nowhere, terminate it"?
Here is an example automata - accepts palindromes.


texts:
I read in this assembly programming tutorial that 8 bits are used for data while 1 bit is for parity, which is then used for detecting parity error (caused by hardware fault or electrical disturbance).

Is this true?


texts: Can a weaker version of the Halting Problem be solved?

texts:
I've been learning about the Halting Problem and the proof that it is undecidable in its general case. The proof that it cannot be solved generally goes something like this:

Assume that some machine $H$ exists that can solve the halting problem on a given machine $A$ with input $x$ ($H$ determines whether the machine $A$ halts on input $x$).
Now build a machine $Q$ which consists of $H$ and an extra component that takes in the output of $H$ and functions by never halting whenever $H$ returns "true", and halts whenever $H$ returns "false".
Then feed into $Q$ itself as both its given machine and the machine's input. Now, what does $Q$ return? If the machine $H$ inside $Q$ determines that the system halts, thereby returning "true", then $Q$ does not halt, as outlined above. However, if $H$ determines that $Q$ does not halt, then it does halt, as outlined similarly above. Therefore $H$ cannot exist.

I understand how this prevents any machine from existing that provides a general solution to the halting problem for any input, but does it also prevent solutions to certain smaller problems as well?

Specifically, could there theoretically be a 1000-state or larger Turing machine which can solve the halting problem for all Turing machine inputs with 50 states or fewer (the specific values aren't relevant)? That way, the machine cannot be input itself as a parameter, and the contradiction above would not be relevant.

To be clear, I'm not asking whether such a machine could be feasibly built, but rather whether is it theoretically possible for such a program to exist that solves the problem for machines smaller than a certain limit?


texts: difference between minus and subtract microoperation

texts:
While reading Computer Architechture book by M.Mano. I came across Arithmetics Microoperations sections which has two microoperations which confuses me a lot,

R3 <- R1 - R2      ( Minus Microoperation )

R3 <- R1 + complemented(R2) + 1   ( Subtract Microoperation ).

Can someone tell me the difference?


texts: Destination-based vs source-based routing

texts:
I understand that destination-based routing builds the "route" from the destination backwards to the source (e.g. if using a spanning tree, then the tree is routed at the destination). With source-based routing the opposite is true: the route is build from the source onwards towards the destination.

However I don't understand the practical difference. How does it make a difference if I base my decision on the source or on the destination. Say, a shortest path algorithm such as Dijkstra's should give the same result regardless?

Could someone explain?


texts: Is it possible to use $USTCON$ log-space decision algorithm in order to show reduction from $USTCON$ to some other decision problem $A$? I mean - the reduction will run $USTCON$ decision algorithm and then produce some output $x ∈ A$ or $x ∉ A$ accordingly?


texts: Count Unique Subsequences to Destination?

texts:
I am looking at this post:
Jamie is walking along a number line that starts at point 0 and ends at point n. She can move either one step to the left or one step to the right of her current location , with the exception that she cannot move left from point 0 or right from point n.
In other words, if Jamie is standing at point i,she can move to either i-1 or i+1 as long as her destination exists in the inclusive range [0,n]. She has a string, s, of movement instruction consisting of the letters l and r, where l is an instruction to move one step left and r is an instruction to move one step right.  Jamie followed the instructions in s one by one and in order.  For example if s=‘rrlr’, she performs the following sequence of moves:
one step right ->one step right ->one step left -> one step right.  Jamie wants to move from point x to point y following some subsequence of string s instruction and wonders how many distinct possible subsequence of string s will get her from point x to point y. Recall that a subsequence of a string is obtained by deleting zero or more characters from string.
It has four parameters

A String , s giving a sequence of moves using the characters l( i.e. move left one unit ) and r (i.e. move right one unit)
An integer n, denoting the length of the number line.
An integer x, denoting Jamie’s starting point on the number line
An integer y , denoting Jamie’s ending point on the number line.

The function must return an integer denoting the total number of distinct subsequence of strings that will lead Jamie from point x to point y as this value can be quite large.
Sample Input
rrlrlr
6
1
2
output = 7
Let's add few more constraints to simply the questions:

1 <= length of s <= 10^3
0 <= x, y < n <= 2500

I wonder what the runtime is for the proposed solution there:
int distinctSequences (int n, int a, int b, const std::string& actions) {
    std::unordered_map<int, int> readyForR, readyForL;
    auto res{0};

    if (a > 0) {
        readyForL.emplace(a, 1);
    }

    if (a < n) {
        readyForR.emplace(a, 1);
    }

    std::unordered_map<int, int> nextReadyForR, nextReadyForL;

    for (auto c: actions) {
        nextReadyForR.clear();
        nextReadyForL.clear();

        if (c == 'r') {
            for (auto [pos, count]: readyForR) {
                auto pp1{pos+1};

                nextReadyForR.emplace(pp1, count);
                readyForL[pp1] += count;

                if (pp1 == b) res += count;
            }

            nextReadyForR.erase(n);
            std::swap(readyForR, nextReadyForR);
        } else {
            for (auto [pos, count]: readyForL) {
                auto pm1{pos-1};

                nextReadyForL.emplace(pm1, count);
                readyForR[pm1] += count;

                if (pm1 == b) res += count;
            }

            nextReadyForL.erase(0);
            std::swap(readyForL, nextReadyForL);
        }
    }

    return res;
}

What's its runtime complexity?


texts: How to prove transitivity of < (Software Foundations exercise)?

texts:
I'm working through the "Properties of Relations" chapter of Software Foundations, but have got stuck on one of the exercises, lt_trans'':

Theorem lt_trans'' :
  transitive lt.
Proof.
  unfold lt. unfold transitive.
  intros n m o Hnm Hmo.
  induction o as [| o'].
  (* FILL IN HERE *) Admitted.

The base case for the induction is straightforward, but I'm stumped as to how to progress on the successor case. Proof state is:

  n, m, o' : nat
  Hnm : S n <= m
  Hmo : S m <= S o'
  IHo' : S m <= o' -> S n <= o'
  ============================
  S n <= S o'

To apply the induction hypothesis, I need S m <= o', but I only know that S m <= S o', and so it feels there is no way to make progress. Hoping someone can point me in the right direction as to how to solve this exercise.


texts: What is the relation between universality and chaotic behavior in Elementary Cellular Automata?

texts:
So i know that rule 110 from Elementary Cellular Automata is universal but i am wondering if we had other chaotic behaviors let's say there exists a system that shows nearly infinite chaotic behaviors {a structure at a time} similar to ECA structures, how can we prove or disprove universality from that system ?

Suppose we have a system with one specific rule to execute and the input can be defined by different number of cells {i.e input = 5 cells} these 5 cells for example can show (2000) chaotic behavior... 4 cells can show nearly (1800), for example to get a structure from the (1800) structures, i can change the 4 cells by changing the rule set of these 4 cells just like in ECA => 'two white cells will result in a black cell', i can define a similar rule set on the 4 cells, 5 cells or more generally on x cells where x < infinite.

That system with same input {4 cells} with different rule set can simulate most of the structures in Elementary Cellular Automata like rule 30, 90 & 60 and others, what can be proved about such system and how universality is related to it ?


texts:
Given a weighted digraph with positive and negative edge weights, what is the complexity of finding the shortest (uses the least number of edges) negative weight cycle in the graph?

I know that I can detect negative weight cycles using Bellman-Ford. Has this variation be studied before? Can you point me to a reference?


texts: Which graph partitioning algorithm can solve this problem?

texts:
In brief:
Here I have a cyclic graph above. I want to partition the graph vertices into 3 clusters. (With the mindset of cluster-wise "load balancing")
Constraint: All the vertices in each cluster should be directly connected.
Goal: the deviance of the cluster-sums should be as small as possible. (In other words, the sum of loads of all clusters should be as balanced as possible.)

Examples:
An infeasible example: ADG CE BF. Reason: The vertices are not directly connected within each cluster.
A feasible but bad example: AB CD EFG. Reason: The load is not optimally balanced (Difference 14 14 59 is too large).
The optimal solution: ABCD EF G. Reason: the difference among three cluster-sums (28 29 30 respectively) is the smallest.
Which algorithm can get the optimal solution?


texts: Why does it take $O(f(n)^2)$ to simulate a 3-tape $O(f(n))$-time TM on a 1-tape  TM?

texts: This looks like a fundamental result but I can't find a resource online that gives an intuitive interpretation of this complexity. Any basic explanation is appreciated.


texts: How to satisfy bounded waiting in case of deadlock?

texts:
I have a doubt regarding bounded waiting.

Deadlock implies no Progress because the processes take indefinite time to decide who will enter the critical section .

But, Does deadlock implies no bounded waiting ?

I think No because bounded waiting is per process and deadlock is for the system.

Moreover, In a deadlock, bounded waiting conditon is not violated and bounded waiting is not with respect to time, but with respect to the number of times the processes enter the critical section before intended process enters the critical system .

Would anyone at least care to correct me or suggest what is right and not right?


texts: Detecting palindromes in binary numbers using a finite state machine

texts:
In my first algorithms class we're creating these patterns that are supposed to model a finite state machine. We were given a task to think if we can figure out a way to detect palindromes in binary sequences (no points if we do, it's just a food for thought).

I specifically asked the professor, knowing a little about CS and that palindromes aren't regular, and that a finite state machine can only detect a regular language. But his answer surprised me, since he said that it is indeed possible and that he thinks we should be able to come up with a sotluion.

This brings two questions:

Maybe the binary sequence is a special type of palindrome that is regular? (I'm a little fuzzy on this)
Or the technique we're using to represent the state machine is more powerful than I think.

In case it's 2), I'll try to explain how we're representing the problem.

Imagine a finite wall, which is supposed to be filled with a predefined types of tiles. Each tile has four colors

You can design any tile you want, and as many as you want, but there has to be a finite number of tiles. They can be arranged in a single row, or into multiple rows, but the topmost row has to always match against the 0 and 1 colors. The end colors of the wall also have to be defined ahead of time, and the tiles have to match those, and they also have to match the adjacent tiles.

Here's an example of a pattern that detects a sequence of 01010101...01

The question is, is this pattern more than just modeling a finite state machine? If not, how can I use this to detect palindromes?

Update: There has to be a finite number of tile designs, and the number of tiles has to be finite as well (the input will always be finite as well). As for the rows, there can be an arbitrary number of rows, the only condition is that the tiles on a second row must match in the top color with the tiles on the row above them. The number of colors isn't limited as well, though it can't be infinite.


texts: How is the directory implementation done using a linear list?

texts:
I am reading Operating System Concepts by Silberchatz, Galvin, Gagne and they write that a directory can be implemented using a linear list. [pg 470, 8th ed]

However, I visualize directories as a rather hierarchical data structure which can be implemented using a B-tree.

Also, when they say that the nodes contain a pointer to the data blocks, what do they mean?


texts: Simple paths with halt in between in directed graphs

texts:
I have two problems related to paths in a directed graph. Let $G=(V,E)$ be a directed graph with source $s \in V$ and target $t \in V$. Let $v \in V \setminus \{s,t\}$ be another vertex in $G$.

Find a simple directed path¹ from $s$ to $t$ through $v$.
Find a simple directed path from $s$ to $t$ that goes through two fixed edges in $G$.

I do not know if there are polynomial time algorithms for them. Does anyone have solutions or references for them?

A simple directed path does not allow any vertex to appear more than once.


texts: For the time hierarchy theorem, how is the input translated efficiently?

texts:
I'm trying to understand the proof of the time hierarchy theorem appearing in sipser's book.  The proof requires a TM M to simulate an arbitrary TM N without too much slowdown. In particular, it is assumed that the encoding of N's tape alphabet using M's alphabet causes only a constant factor slowdown. This seems plausible since if N's alphabet is size k then M can use $\log k$ cells to represent each symbol that N writes to the tape.

But my question is this: If this is how the simulation works then before the simulation starts M will have to change the input so that each bit is repeated $\log k$ times and I don't know how to do this without adding a quadratic term to the time. I should say its assumed that N's computation is no faster than $O(n\log(n))$.


texts: How do the Guard, sticky, and round bits work and affect floating point Representation?

texts:
I've got a test on this tomorrow, my instructor's lectures aren't up, and the notes are ambiguous...

Anyhow, we've been covering floating point operations, specifically addition, and he mentioned these three bits. While I can surmise their meaning to a degree, I'm wondering if anyone could explain concretely what they are and perhaps provide some examples showing how they work?

If it would be useful, the language I'm learning this in is MIPS, which does Round-to-Even.


texts: Is this special case of a scheduling problem solvable in linear time?

texts:
Alice, a student, has a lot of homework over the next weeks.  Each item of homework takes her exactly one day.  Each item also has a deadline, and a negative impact on her grades (assume a real number, bonus points for only assuming comparability), if she misses the deadline.
Write a function that given a list of (deadline, grade impact) figures out a schedule for which homework to do on which day that minimizes the sum of bad impact on her grades.
All homework has to be done eventually, but if she misses a deadline for an item, it doesn't matter how late she turns it in.

In an alternative formulation:

ACME corp wants to supply water to customers.  They all live along one uphill street.  ACME has several wells distributed along the street.  Each well bears enough water for one customer.  Customers bid different amounts of money to be supplied.  The water only flows downhill.  Maximize the revenue by choosing which customers to supply.

We can sort the deadlines using bucket sort (or just assume we have already sorted by deadline).
We can solve the problem easily with a greedy algorithm, if we sort by descending grade impact first.  That solution will be no better than O(n log n).
Inspired by the Median of Medians and randomized linear minimum spanning tree algorithms, I suspect that we can solve my simple scheduling / flow problem in (randomized?) linear time as well.
I am looking for:

a (potentially randomized) linear time algorithm
or alternatively an argument that linear time is not possible

As a stepping stone:

I have already proven that just knowing which items can be done before their deadline, is enough to reconstruct the complete schedule in linear time.  (That insight is underlying the second formulation where I am only asking about certificate.)
A simple (integral!) linear program can model this problem.
Using duality of this program, one can check a candidate proposed solution in linear time for optimality, if one is also given the solution to the dual program.  (Both solutions can be represented in a linear number of bits.)

Ideally, I want to solve this problem in a model that only uses comparison between grade impacts, and does not assume numbers there.
I have two approaches to this problem---one based on treaps using deadline and impact, the other QuickSelect-like based on choosing random pivot elements and partitioning the items by impact.  Both have worst cases that force O(n log n) or worse performance, but I haven't been able to construct a simple special case that degrades the performance of both.


texts: Clarification on evenly dispersing modular hashing

texts:
I'm going over "Algorithms fourth edition" by Robert Sedgewick and Kevin Wayne.
In the chapter on hash tables I have encountered an easy hashing method called "modular hashing"
hash = k % m

Where k is the key and m - 1 is the size of array (minus 1) that stores the values. Authors suggest to use primary numbers for m because:

If m is not prime, it may be the case that not all of the bits of the key play a role, which amounts to missing an opportunity to disperse the values evenly.

I get why non-primary numbers might be a bad m. If we take a look at m = 10 and k = {17,27,37...}. They will all produce hash equal to 7.
However, I'm not entirely sure as to why primary numbers are superior alternative.
Is it because primary numbers are (due to their definition) never a divisor to the keys that we want to hash (ignoring instances where key=m)?


texts: Which nodes do I give the input to in a Liquid State Machine?

texts:
I’m trying to make a Liquid State Machine in python and I already read many articles about it, but still there are many points I don’t understand.

(I had trouble putting 'LSM's in context to see what it actually is, but looking at PyBrain's feature list and the description of aureservoir I could classify LSM like this: 'Machine Learning' > Networks > Recurrent Networks (RNN) > Reservoir Computing > Liquid State Machine (LSM).)

However I don't understand how do I give the input to the liquid?

Should I give it to all the neurons, or just to a selected (how?) few, or only to one?**


texts: what is difference between multilayer perceptron and multilayer neural network?

texts:
When do we say that a artificial neural network is a multilayer Perceptron?

And when do we say that a artificial neural network is a multilayer?

Is the term perceptron related to learning rule to update the weights?

Or It is related to neuron units?


texts: How many states are examined in the most wins heuristic for tic-tac-toe (9-grid)?

texts: I'm new to AI, and have a hard time to understanding how to count the total states are examined in the most wins heuristic for tic-tac-toe two plys deeper(9-grid)? Need help


texts: Points at distance $k$ or less in 2D grid

texts:
How can we prove that the total number of mesh points k or fewer jumps away from an arbitrary point in a 2D mesh is: $2k^2 + 2k + 1$.

I tried making a $3 \times 3$ mesh.

     a --- b --- c
     |     |     |
     d --- e --- f
     |     |     |
     g --- h --- i

For point $e$, the number of points $k=1$ jump away is four: $b$, $d$, $f$, $h$.
But, according to the formula, it should be $2\times1^2 + 2\times1 + 1=5$.
I am stuck!


texts:
1)"Given a CFL L and a regular language R, is the intersection of L and R an empty set?" decidable?
2)What if we replace L with the complement of L?
Either 1 or 2 is decidable and the other is not.
For the one that is decidable, give an algorithm. For the other, give an undecidability proof.
Intuitively, i think that 1 is decidable and 2 is undecidable.
However, I don't have a concrete reasoning behind it.
Can anyone explain why or why not this is the answer?
(PS this is not for an assignment, this is a practice final question)


texts:
Why are there $2^{2^{n}}$ possible boolean functions of n inputs? How to derive that?

For 3,
I can only write down 16 and cannot go further.

8 of

$f(x_{1},x_{2},x_{3})=0$

000 = 0

001 = 0

010 = 0

110 = 0

111 = 0

110 = 0

101 = 0

011 = 0

and

8 of

$f(x_{1},x_{2},x_{3})=1$

000 = 1

001 = 1

010 = 1

110 = 1

111 = 1

110 = 1

101 = 1

011 = 1

That's the maximum I can go. How do I proceed?


texts: I've read that the human eye can only really decipher around 10 million different colours, so what's the point in technology that uses 48-bit colour, which allows for $2.81\times 10^{14}$ colours. Is this not like giant, super inefficient overkill?


texts: Complexity analysis using big - O, Omega and Theta notation

texts:
I was reading a research paper and there I read the following:

$t=O\left(d^{2} \log _{d}^{2} n\right)$ matches the lower bound $\Omega\left(d^{2} \log _{d} n\right)$ in the regime where $d=\Theta\left(n^{\alpha}\right)$ for some $\alpha \in(0,1)$.

It also says $t=O\left(d^{2} \log n\right)$ outperforms $t=O\left(d^{2} \log _{d}^{2} n\right)$ in the regime where $d=O(\operatorname{poly}(\log n))$

I am not sure how to verify these statements? I understand the basics of all the complexity notations, but how can we mathematically prove this?


texts: Minimal subset of rows that generate smaller polyhedron

texts:
Given a matrix $[A|B]$ I want to find a minimal matrix $[A'|B'] \subseteq [A|B]$ (i.e. the rows in $[A'|B']$ are also in $[A|B]$) such that $A'x < B' \Rightarrow Ax < B$.

Geometrically, I want to discard the half-planes $X_i$ which contain the intersection of rest of the half-planes i.e. $X_i \supseteq \cup_{j \neq i} X_j$.

For now my solution is, for each row in $[A|B]$, flip the sign (i.e., multiply by $-1$) and check if the new $[A''|B'']$ is infeasible. If it is, that row is discarded, otherwise it is kept. This would take $n$ calls to a LP solver, on inputs of size $[A|B]$, where $n$ is the number of rows in $[A|B]$. Is there a more efficient way to do this?


texts: How to prove an implication about an upper bound mentioned in the proof of master theorem?

texts:
How can we prove rigorously the proposition "Suppose the if in case 1 is true, the equation 4.23 is true"?
For given constant b and j, the implication in green makes sense. If the upper bound of j was fixed, the equation 4.23 follows directly. However, when n increases, the upper bound of j also increases, though is slower. It is where I find difficult to prove there always exists a value m > 0 such that for all n >= m, equation 4.23 is true.


texts: When to add and when to multiply to find time complexity

texts:
I am trying to learn how to determine time complexity. Sometimes, I see complexity as $\log n + \log n = 2\log n$ but sometimes I see complexity as $\log n\cdot\log n$ which is $(\log n)^2$.

Suppose I need to do two binary searches to find two different elements, in one algorithm. Is this $\log n + \log n$ time, or would it be $(\log n)^2$ time?


texts: Adding a vertex in graph in adjacent matrix repersentation

texts:
In website geeksforgeeks i read that adding a vertex to graph in adjacent matrix takes O(V^2) time but i am not getting it. It requires adding a row and a column which should take linear time ?
I am a beginner hence forgive me for such a question

Link:- https://www.geeksforgeeks.org/graph-and-its-representations/


texts: Bucket Priority Queues with large integers for $O(1)$ insert and extract~min?

texts:
I recently got into a discussion about Priority Queues when the requirements allow for "best effort" removal (i.e. the removed key may not always be THE very highest priority, but it is relatively close).

After thinking about it a bit I stated "I could probably make it $O(1)$ by using buckets" and approximating the minimum (to bucket size precision). I was politely told that I was wrong. Not taking no for an answer, I later went to Google and found the ample literature on the subject, which seemed to confirm I was wrong :-|

Note that the closely related question, Unique integer priority queue with both $O(1)$ insert and extract-min?, does not allow for approximation, so the answers don't apply to my question.

I was told the standard solution to this problem is to use a queue where keys are appended to the end in $O(1)$ and read from the head in $O(1)$ and which is then periodically sorted in $O(\log N)$ or whatever sorting algorithm you can find.

Assuming 64-bit integers as keys, and a precision of $ \pm 127$ (a 56-bit bucket)... Can't you just hold the buckets in a sparse array (so as not to require $2^{56}$ words of memory)... problem solved?


texts:
I've seen to explanations for the quick sort algorithm.

One in which a pivot is chosen, and put into place, before both sides of the pivot are recursively pivot-sorted.

Another involved a more complicated solution involving two pivots which interchanged.

What are the benefits of either solution, why was the dual-pivot solution created? Is it faster?


texts: Proof of correctness of A star search algorithm

texts:
I've been looking for the proof of correctness for the A star (A*) algorithm but none of the texts and websites offer it. Mostly they are talking about the proof of optimality of the A* algorithm. I'm looking for a proof that if the heuristic is admissible, A* will always give an optimal path.

Please help me understand.

To clarify, I want a proof that the path found by A* is correct (i.e., is the cheapest/shortest path to the destination), not a proof that the A* algorithm is optimal (i.e., that any other algorithm that uses the same heuristic will expand at least as many nodes as A*).  Also, I'm looking for a proof that only uses the assumption that the heuristic is admissible (without assuming that the heuristic is monotonic or consistent).  I've looked in CLRS and haven't found any such proof.


texts: Why DCFL is not closed under kleene star?

texts: I have read somewhere that DCFL is not closed under kleene star. but I haven't found any example


texts: What is the point of (Compactness theorem in the) Overspill principle?

texts:
The principle (called a Löwenheim–Skolem theorem by Huth and Ryan) states

  Let $\phi$ be a sentence of predicate logic such that for any natural
  number $n \geq 1$, there is a model of $\phi$ with at least $n$
  elements. Then $\phi$ has a model with infinitely many elements.

IMO, it basically states that if you can always name a number larger than mine arbitrary natural number then your model is infinite. What needs to be proven here? There are no other options obviously for any school kid.

PS The answers state that there is a difference between having infinite amount of models and single infinite model. But this is similarly stupid. At first, I do not see whether I claim that I have a single infinite model or approach it by having all denumerable models. Secondly, it does not matter since in any case you should have an infinite model in order to respond to any natural number.

Nevertheless, I started to understand why people (mistakenly) ask me to differentiate between infinite amount of models and models of infinite size. They fail to recognize that principle "The fact that I can always name a number larger than yours implies that we have an infinite model/set", which is intuitive and used to prove the overspill theorem, also implies that the model of infinite size exists. The set of models $A = \{M_k, M_l, M_m \ldots\}$ has sizes $S = \{k, l, m, \ldots\}$ correspondingly. When you speak about size of models, you basically speak of the numbers in $S$. When you say "a model of size n" you just say "n". Thus, we can forget about set of models and speak only about S. Now, you say that "whatever integer you have, set S contains a larger one." This basically means that S contains an infinite number (i.e. $A$ contains infinite models). What to be proven here?

In other words, what is the point of expanding $\phi$ with infinite set $\{I_1, I_2, \ldots\}$ in the proof and applying the Compactness theorem? This says that there is an infinite model. But this is obvious without even without it, right from the the premise of the overspill principle.


texts: k-Closest pairs in Delaunay triangulation

texts:
Assume there is a set of points $S$ in $\mathbb{R^2}$.
In this set of points there is a pair of points which are the nearest neighbors, the second-nearest neighbors and the third-nearest neighbors.

I want to show that the pair of points which represent:

the nearest neighbors,
the second nearest neighbors,
the third nearest neigbors

are also an edge in the corresponding Delaunay Triangulation.

Any hints on how to prove this?


texts: Lowest single common ancestor in a Directed Acyclic Graph?

texts:
I was reading how to find the Lowest common ancestor in a DAG. A DAG can have scenarios where the LCA yields multiple solutions and I feel the accepted answer explains that pretty well.
However, one of the answers also mentions a paper that talks about because of the given scenario above, for DAGs there may be cases where you would want to find the lowest SINGLE common ancestor.
From the limited Abstract linked in the answer above, the paper says this:

We derive a new generalization of lowest common ancestors (LCAs) in dags, called the lowest single common ancestor (LSCA). We show how to preprocess a static dag in linear time such that subsequent LSCA-queries can be answered in constant time. The size is linear in the number of nodes.
We also consider a “fuzzy” variant of LSCA that allows to compute a node that is only an LSCA of a given percentage of the query nodes. The space and construction time of our scheme for fuzzy LSCAs is linear, whereas the query time has a sub-logarithmic slow-down. This “fuzzy” algorithm is also applicable to LCAs in trees, with the same complexities.

Clarification I will look more into this to confirm this is what LSCA is but given the picture below

The LCA of this picture for nodes 8 and 9 is straight forward (it would be 6) but for nodes 3 and 4, the LCA could yield either 1 or 2 because they are at the same level and are both common ancestors. In this case, perhaps it makes more sense to find the LSCA which would be 0 since its the single ancestor of the two.
Specifically I would like to know:
How does finding the LSCA of a DAG affect time complexity compared to finding the LCA which could yield multiple solutions and what are the best methods to achieve it?


texts:
I'm having trouble understanding a part of Manber's graph-partitioning algorithm, presented in A Text Compression Scheme that Allows Fast Searching Directly in the Compressed File.

Generally speaking he wants to divide vertices of a weighted, directed graph $G=(V,E)$ into two sets $V_1$ and $V_2$ in such a way, that the sum of the weights of the edges that go from $V_1$ to $V_2$ is maximized.

He states that since this is a NP-problem he chose to first partition the graph randomly and then examine each vertex to see if switching this vertex to the opposite set would improve the total. This whole process is repeated several times for several random initial partitions to see which one of them yields the best results.

The following pseudocode is provided:

Best_Non_Overlapping_Pairs(G: weighted graph)
    repeat k times { k is a constant; we used 100 }
       randomly assign each vertex to either V1 or V2 with equal probability;
       for each vertex v in V do
          put v on the queue;
       loop until the queue is empty
          pop v from the queue;
          if switching v to the opposite set improves the sum of weights then
             switch v;
          if switching v caused other vertices, not already on the queue, to
          prefer to switch then put them on the queue;
       store the best solution to date;

I'm not sure what I'm supposed to code for the bolded part. How do I check for the "preference" of non queues vertices? Is it even needed? I've implemented the algorithm without this part and it seems working as intended.


texts:
Given a sorted array of integers $x$ and a target value $t$, determine if there exists a pair $x_i, x_j \in x \wedge i \neq j$ such that $x_i + x_j = t$.

What is the lower bound for this problem?

I know for the generalized $k$-sum (unsorted) there is a lower bound of $\Omega(n^{\lceil \frac{k}{2}\rceil} )$. This would mean if the array were unsorted we could prove a lower bound of $\Omega(n)$. I would assume sorting it would give us some sort of extra information. I also haven't seen any lower bound claims of this problem so feel free to link a solution if one already exists.

It is relatively easy to show  a lower bound of $\Omega(\log_2 n)$ using an adversary:

Create $x$ such that every sum of each pairs of integers is unique (hint: Fibonacci Numbers).
We also have that the target $t$ is larger than all values so no values can be preemptively discarded (hint: add a reasonable constant to all values).

Now we have $\frac{n(n-1)}{2}$ possible target values. Using an optimal binary search of these target values it takes $\Omega(\log_2 (n^2)) = \Omega(\log n)$. So it's easily lower bounded by $\log n$.

Although the algorithm can't necessarily perform an optimal binary search, because it takes at least $\Omega(n^2)$ to create all the unique sums of pairs. Unless it could figure out the median of all sums of pairs in less time than it takes to create them (another interesting question).

I would assume we can take advantage of this lack of knowledge in some way to establish a greater lower bound, possibly $\Omega(n)$. The standard algorithm to solve this takes $O(n)$ using two pointers. It does this because it's difficult to discard particular values without explicitly checking them. Any help would be greatly appreciated.


texts:
I am new to operating systems and have been wondering about this.
Consider a normal text editor, and it's process running in the CPU. Since text editors include IO operations, do the process keep switching it's state from Wait -> Run -> Wait etc. While the user is typing and the same is reflected on the screen or some processing such as auto-correct etc. And while the current process is in Wait, other process is in Run state (Context Switching).
OR
Text - Editor itself creates multiple processes, one for handling IO operation and other for processing the data and it is being established through Inter-Process Communication.
New to OS and stuck with this, thank you for any kind of help .


texts:
Let A = {  | M is a DFA which doesn't accept any string containing an odd number of 1s}. Show that A is decidable.
The questions seems simple so I designed the following TM D that decides whether there exists a DFA with this property or not.
D = "On input  w:

Construct a DFA B that accept any string containing an odd number of 1s.
Construct a DFA C s. t. $L(C) = L(B) \cap L(M)$
Call $E_{DFA}$ with input C.
If T accepts, then reject. If T rejects, then accept."

$E_{DFA}$ is defined as following:
$E_{DFA} = \{ <A> |$ A is a DFA and L(A) = $\phi \}$ So assume there is a TM T that decides language $E_{DFA}$. I.e., T accepts if A is empty, otherwise rejects.
Now, my questions is related to the step 4. In Sipser's textbook, he states that if T accepts, then accept and if T rejects, then reject. I don't understand why it says so. For example, If $L(M) \cap L(B) = \phi$, then this means that there are different. So, this is what I said in step 4 above. But in Sipser's answer for this exercise in page 187, it says that if they are empty, then accept. Can you explain to me where is my mistake?


texts:
I just have general questions about sets and determining if they are regular languages.

i) If A is regular, and A is a subset of B, then B must be regular.

ii) If B is regular, and A is a subset of B, then A must be regular.

iii) If A and AB are regular, than B must be regular

iv) If Ai is an infinite family of regular sets, than the union  of all those sets is regular.

For the third one, I know that AB can only be regular if B is regular, because a regular set * a irregular one is not regular.

Lost for the other ones.


texts: Enumerating weighted permutations in sorted order problem

texts:
Let $S$ be a set of $n$ integers. Consider the following weighted permutations problem.

  Let $m<n$ be an integer. What is an efficient algorithm to enumerate all subsets of $m$ integers of $S$ such that they are listed in order of the sum of the integers in each subset?

Each subset is a permutation, and each permutation has a total weight that is the sum of the integers in the permutation.

The idea is to come up with an algorithm that is not the trivial algorithm of enumerating all subsets, and then sorting them, i.e. more of a "streaming" type algorithm. That is, efficiency in terms not so much of time but of "small" space.

Maybe this is published somewhere in the literature although I have not seen it.


texts: Proof strategies for linearizability of implementations

texts:
Background:

In section 4.2 of the paper Linearizable Implementations Do Not Suffice for Randomized Distributed Computation@STOC'2011, the authors mentioned two typical proof strategies for linearizability of implementations. In the following, Let $O$ be the implemented object and let $H$ be a history over $O$.

In one proof strategy, for each operation $op$ on $O$ a unique "linearization point" $pt(op)$ is assigned, which is a shared memory operation that occurs during the execution of operation $op$. A sequential history $S$ is formed by ordering the operations on $O$ in $H$ so that $op_1$ precedes $op_2$ in $S$ if and only if $pt (op_1) \prec_{H} pt (op_2)$. The construction of $S$ guarantees agreement with the "happens before" order of operations on $O$ in $H$, and so the proof obligation for linearizability is only to show that $S$ is valid for $O$.

In the second general proof strategy, the operations in a history $H$ are first ordered somehow into a valid sequence $S$, and the proof obligation is to show that $S$ is consistent with the "happens before"
order of $H$.

For instance, the practical constructions of sets and lists such as the "FineList", "OptimisticList", and "LazyList" described by Herlihy and Shavit in their book "The Art of Multiprocessor Programming" fall into the first category while the classic construction of atomic snapshot object and the implementation of atomic multi-writer register from atomic single-writer ones are in the second category.

My problems here are as follows:

  Are there some implementations in the literature whose linearizability can be proved by both of the above-mentioned proof strategies? Such examples may be useful to help people understand and compare these two proof strategies better.
  Are there any other proof strategies for linearizability used in the literature? It need not be general and can be specific to its particular problem.


texts:
I wonder how can I find out what is context-free grammar of the following language?

$$
L_4 = \{w_1\#w_2 \mid w_1,w_2 \in \Sigma^*, w_1 \neq w_2^R \}
$$


texts: Why did MIPS include shamt and distinguish funct/opcode?

texts:
I'm confused as to why the MIPS designers would include 5 bits dedicated to shifting and have separate opcode and function bits.

Because MIPS is so RISC I assume that only shifting would be done in a few instructions, so those 5 bits seem like they're wasting space when they could be put in the immediate. I assume that opcodes and funct are seperate for distinguishing R- and I- type instructions, but this could be done by extending the opcode by 1 bit. With both of these R-type instructions could be 22 bits long. This won't work if the I-type and J-type instructions want to keep their immediate and address, but both seem unnecessary.


texts:
I was going through the text Introduction to Algorithm by Cormen et. al. where I came across an excerpt which I felt required a bit of clarification.
Now as far as I have learned that that while the Best Case and Worst Case time complexities of an algorithm arise for a certain physical input to the algorithm (say an input $A$ causes the worst case run time for an algorithm or say an input $B$ causes the best case run time of an algorithm , asymptotically), but there is no such physical input which causes the average case runtime of an algorithm as the average case run time of an algorithm is by it's definition the runtime of the algorithm averaged over all possible inputs. It is something I hope which only exists mathematically.
But on the other hand inputs to an algorithm which are neither the best case input nor the worst case input is supposed to be somewhere in between both the extremes and the performance of our algorithm is measured on them  by none other than the average case time complexity as the average case time complexity of the algorithm is in between the worst and best case complexities just as our input between the two extremes.
Is it correct or incorrect to say that an input say $C$ causes an average run-time of an algorithm?
The excerpt from the text which made me ask such a question is as follows:

In context of the analysis of quicksort,
In the average case, PARTITION produces a mix of “good” and “bad” splits. In a recursion tree for an average-case execution of PARTITION, the good and bad splits are distributed randomly throughout the tree. Suppose, for the sake of intuition, that the good and bad splits alternate levels in the tree, and that the good splits are best-case splits and the bad splits are worst-case splits. Figure(a) shows the splits at two consecutive levels in the recursion tree. At the root of the tree, the cost is $n$ for partitioning, and the subarrays produced have sizes $n- 1$ and $0$: the worst case. At the next level, the subarray of size $n- 1$ undergoes best-case partitioning into subarrays of size $(n-1)/2 - 1$ and $(n-1)/2$ Let’s assume that the boundary-condition cost is $1$ for the subarray of size $0$.
The combination of the bad split followed by the good split produces three sub- arrays of sizes $0$, $(n-1)/2 - 1$ and $(n-1)/2$ at a combined partitioning cost of $\Theta(n)+\Theta(n-1)=\Theta(n)$. Certainly, this situation is no worse than that in Figure(b), namely a single level of partitioning that produces two subarrays of size $(n-1)/2$, at a cost of $\Theta(n)$. Yet this latter situation is balanced!


texts: Lexicographical position of a string in its type class

texts:
I have the following problem:

Given a string $x\in\{1,...,M\}^+$ of length $n$.
Let $S$ be the set of all words with exactly the same numbers of occurences of smybols as in $x$. In fact, $S$ consists of all permutations of $x$. We call this set the type class of $x$.

My question:

  How to compute the position of $x$ in the lexicographical ordering of $S$?

I found the paper "Enumerative source coding" written by Thomas M. Cover, where this position function $i_{S}$ is shown for binary alphabets (in the following the alphabet is  $\{0,1\}$):

$i_S(x_1x_2\cdots x_n)=\sum\limits_{k=1}^{n}x_k\cdot$ $n-k\choose n(w,k)$

with $\;\;n(w,k)=w-\sum\limits_{j=1}^{k-1}x_j\;\;\;$

and $\;\;w$ is the number of occurrences of $1$ in $x\;\;$ ($w=\sum\limits_{k=1}^{n}x_k$).

Unfortunately, i do not know how to extend this formula to alphabets of size $M$. Any help?


texts: Is it possible to solve the critical section problem with an atomic subtract operation?

texts:
In my Operating Systems class, our professor asked us to solve the critical section problem with the following atomic operation:

int sub(int &x, int val){
  x -= val;
  return x;
}

The homework was already due and nobody in my class could come up with a solution. The professor's solution does not even work. Here it is:

int x = 1; //let x be a shared variable between threads
entry(){
  int loop = sub(x, 1);
  while(loop < 0){
    loop = sub(x, 1);
  }
}

exit(){
  x = 1;
}

This solution suffers from the fact that the critical section may be very long, and thus x may loop all the way back around to positive values and eventually become zero before another thread calls exit(). I do not believe it is possible to solve the CS problem because this implementation of sub() does not return the original value of x, but the new value with val subtracted. The professor is convinced that it is possible, even though neither he nor the TA could come up with a proper answer.


texts: Assume there is a Shopping Mall x and all the roads in the city are one way such that, irrespective of the path you take starting from x, you will always end up at vertex x. Device an algorithm to test the same. This seems to be the opposite of a mother vertex, where x is reachable from all vertices instead of all vertices being reachable from x. One way I can think of solving it is to perform DFS on all the vertices and check whether x is visited. An alternate solution which I'm not very sure of, would be to perform the Kosaraju's strongly connected algorithm and prove that there is only 1 connected component. As the question dictates that irrespective of the path you take, you always end up at x, would mean that every vertex would eventually, connect to a vertex connecting to x followed by x itself. Is this intuition correct?


texts: Dynamic All Pairs Shortest Paths algorithm

texts:
I heard about the following problem in a competitive programming camp:

Given an undirected weighted graph $G$ with one vertex initially.

Suppose you are given two types of queries:

Add a new vertex to $G$ with some undirected weighted edges between this vertex and subset of vertices added previously to $G$ in time complexity $O(n^2)$, where negative weights are allowed.
Find the length of the shortest path between two vertices in $O(1)$.

Note: Floyd Warshall's algorithm is $O(n^3)$ for each query of type 1.

I'm looking for (in addition to your answer):

Any useful reference to solve such a problem.
Links for similar problems in online judges (Codeforces, SPOJ .. etc).


texts:
I have been reading up on the Count Sketch algorithm, and I stumpled upon the Count Sketh algorithm explained in section 5 of https://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf. Then, I tried to solve some of the exercises. However, exercise 5-3 is causing me some problems.
If we let $\hat{f}_a$ denote the estimated frequency associated with a key $a$ and $f_a$ be actual frequency associated with key $a$, then it can be show that $E[\hat{f}_a]=f_a$. Furthermore, for $j\in[n]$, we let $\mathbf{f}_{-j}$ be the $(n-1)$ dimensional vector obtained by dropping the $i$th entry of frequency vector $\mathbf{f}.$ It can then be shown that
$$
\text{Var}[\hat{f}_a]=\frac{||\mathbf{f}_{-a}||_2^2}{k}
$$
when we use the hash function $h : [n] \rightarrow [k]$. Thus, using Chebyshev's inequality, it can be shown that
$$
\text{Pr}[|\hat{f}_a - f_a| \geq \epsilon ||\mathbf{f}_{-a}||_2] \leq \frac{1}{3}
$$
for $k=\frac{3}{\epsilon^2}$.
In exercise 5-3, $\textbf{f}_{-a}^{\text{res}(\ell)}$ denotes the $(n-1)$-dimensional vector obtained by setting the $\ell$ largest (by absolute value) entries to zero in $\mathbf{f}_{-a}$. The exercise then essentially asks the reader to show that
$$
\text{Pr}[|\hat{f}_a - f_a| \geq \epsilon ||\mathbf{f}_{-a}^{\text{res}(\ell)}||_2] \leq \frac{1}{3}
$$
where $k=\frac{6}{\epsilon^2}$ and $\ell=1/\epsilon^2$. However, I don't know how to show that the inequality above holds. I have tried using Chebyshev's inequality, but I still can't seem to make it work. Any help would be appreciated.


texts: Find a sequence of $n$ integers with $\Omega(n^2)$ inversions

texts:
So right off the bat, this is in fact a homework question. I've been banging my head on this problem for hours. From my naive understanding of inversions, I feel that this is not possible.

Considering for $n=1$ elements, there are no inversions, it already seems like this won't work, but maybe it's just for $n > 1$, so we try $n = 2$. And the best I can seem to get is $1$ inversion, where the set is $\{2,1\}$, thus there is one inversion, since $0 < 1$ but $S[0] > S[1]$. The best I can seem to get is $\{n, n-1, \dots, 2, 1\}$, where there are $n(n-1) - 1$ inversions.

Am I missing something in my approach?


texts: How to validate a connect X game (Tick-Tak-Toe,Gomoku,...)?

texts:
Currently I am working on a Gomoku AI (or generally Connect-X games).

Implementing the search tree was no problem, but then I got to the point where I had to implement the value function and was surprised how difficult this is to make with a decent performance.

My question is what is the most efficient algorithm to check for a win in a connect-x game.

So basically I tried 2 things:

Firstly I created an Array where I saved all board coordinates (at compile time) into a 1D Array. This means all rows,cols and diagonals point for point and traversing this array and checking the corresponding on the actual board until (if any) a X long sequence was found.

My second approach was to calculate all patterns (horizontal,vertical,diagonal) with X points each at compile time (with Template-Meta-Programming) and traversing only those for each point played on so far and terminating if any member of the sequence was missing.

The first approach was way too slow and the second one was too complex for this problem I think.

What algorithm suites this problem best?


texts: Can the heaviest edge ever be in an MST?

texts:
Is it true that the heaviest edge in a directed graph can not be in the MST of that graph?

I don't think it is true because we might end up with a heaviest edge that is not part of a cycle.

Can anyone confirm?


texts: Why are regular expression used in lexical analysis instead of grammars?

texts: Even though grammars can do what regular expressions do, why are regular expression employed instead of grammars in lexical analysis?


texts:
How should I compute efficiently a matching of maximum size in a tree?

My thoughts so far: since from a path we can get a matching, then just finding the longest path in the tree should be enough to answer the question.

Am I wrong? another approach?


texts: Intuitive explanation of Hoare assignment axiom

texts:
$\small\textit{''The obvious things are the most difficult to understand''}$

May be the question does not make sense, but let me ask it anyway.

The Hoare assignment axiom is
$$
\dfrac{}{\{Q[v \mapsto expr]\} \;\; v:=expr \;\; \{Q\}}
$$

Is there an intuitive explanation of the axiom?

I "agree" with the Floyd assignment axiom:
$$
\dfrac{}{\{Q\} \;\; v:=expr \;\; \{\exists old: Q(old,..) \land v=expr(old,...)\}}
$$
which can be thought as "if Q holds before the assignment, then after the assignment we know that the variables should satisfy: 1) Q(old) holds for some old variables (since we assume Q holds), 2) variable v has the new valueexpr(old,...)".

Is there a similar intuition for the Hoare assignment axiom?


texts: How to prove for that a given non-regular language its given super-set is also non-regular?

texts:
Consider the non-regular language $L_1$ = {$a^n$b$a^n$:  $n \geq 0$} and its super-set language

L = Language of strings with equal number of trailing and leading a's,

or in other words,

$$L = \{a^n b w b a^n : n \ge 0, w \in \{a,b\}^*\} \cup \{a^n b a^n : n \ge 0\}.$$

How would we prove that L is also non-regular?

I have the idea that I should use the help of $L_2 = L - L_1$, but I'm stuck at the following step:

$L_1 \cap L_2 = \phi $ , thus $L_1 \cap L_2$ is a regular language.

I was trying to prove it using contradiction.

Let, L to be regular which is $L_1 \cup L_2 $ is regular.

And tried to prove, $L_1$ or $L_2$ is equal to a set union or intersection or complement operation over the regular sets $L_1 \cap L_2 $ and $L_1 \cup L_2$

But stuck at

$L_1 = [(L_1 \cup L_2) \cap (L_2)^c] \cup (L_1 \cap L_2)$

With Myhill-Nerode theorem: I might be incorrect please fix me if I am wrong.

Take S  =$a^*(b+b.(a+b)^*.b)$
Pick x and y from S such that $x \neq y$.

x = $a^n b$
y = $a^m b$
Take, z = $a^n$

$x.z \in L$ but $y.z \notin L$. Thus, by Myhill_Nerode one can conclude it to be non-regular.


texts: Reason behind declaring iteration variables on a method level

texts:
Lately, I have been in touch with some C++ snippets, and I have a very strange observation on the tiny detail:
Most of the times, I see, that people declare iteration variables outside of the for/while definitions, and then initialise them inside for/while definitions, like:
int i, j, k;

for(i = 0; ..; ..) { } //note, this omits declaration of "i"

I wonder what is the reason behind this? why would one want to scope a loop-level temporary variable and its identifier on a method-level?
Is this conventional? does it help compilation's lexical translation? an optimisation for static code analysis? what is the purpose?
It (important) certainly looks ugly, especially when there are numerous variables in the method; it (important) reserves variable identifiers (on a method-level); and (less important) it definitely occupies more space in the memory.
Any points?
Appreciations.


texts: What is the difference between LRU implemented for a cache and for page replacement?

texts:
I have read that true LRU page replacement requires significant hardware support, so only approximation of LRU is implemented for page replacement.

So I wanted to contrast LRU that is implemented for cache, and that for page replacement. Like - Is LRU properly implemented for cache?


texts: Thought process for the following problem?

texts:
We are given a 1-d array and we have to return  the smallest array attainable after removing all the continuous same numbers. We can only eliminate those numbers which repeat continuously more than or equal to 3 times.

So for eg. [1, 3, 3, 3, 2, 2, 2, 3, 1] should return [1, 1] i.e. first the elimination of 2's occuring three times and after its elimination there is 3 for four times at stretch. After eliminating 3's we are left with 1's which occur less than three times, so no elimination.

Similarly [3,1,2,2,2,1,1,1,2,2,3,1,1,2,2,2,1,1,1,2,3] should return [3,1,3,2,3]. Here we can jumble the eliminations in different ways but no order of eliminations can lead to an array less than in size than [3,1,3,2,3].

The time complexity should have a tighter upper bound than $O(n^2)$.

I am thinking of this problem but I haven't been able to identify a specific technique for solving it. I am thinking of hashing, graphs and also recursion but till now I have failure tackling the order of eliminations as the eliminations can happen in random order. More than the solution I would like to know the technique and thought process walkthrough of this problem.


texts: Algorithm Comparison with Theta-notation

texts:
We consider two algorithms, Algo1 and Algo2, that solve the same problem. For any input of size n, Algo1 takes time $T_1(n)$ and Algo2 takes time $T_2(n)$.

Prove or disprove each of the following statements.

To prove a statement, you should provide a formal proof that is based on the definitions of the order notations. To disprove a statement, provide a counter example and explain it.

Suppose that $T_1(n)$ ∈ $\theta(n^2)$ and $T_2(n)$ ∈ $\theta(n^3)$.

Does it imply that there exists $n_0$ such that for $n$ ≥ $n_0$, Algo1 runs faster than Algo2 on inputs of size $n$?

By definition of $\theta$-notation,$\\$

If $T_1(n)$ ∈ $\theta(n^2)$, then $c_1 n^2 \leq T_1(n) \leq c_2 n^2$ for all $n \geq n_1$for $c_1, c_2, n_1 > 0$.

If $T_2(n)$ ∈ $\theta(n^3)$, then $d_1 n^3 \leq T_2(n) \leq d_2 n^3$ for all $n \geq n_2$ for $d_1, d_2, n_2 > 0 $.

We choose $n_0 = max(n_1, n_2)$

Then, $\\$
$\frac{c_1 n^2}{d_1 n^3} \leq \frac{T_1(n)}{T_2(n)} \leq
\frac{c_2 n^2}{d_2 n^3} \text{ for all } n \geq n_0$

$\lim_{n \rightarrow \infty} \frac{c_1 n^2}{d_1 n^3} = 0$ and $\lim_{n \rightarrow \infty} \frac{c_2 n^2}{d_2 n^3} = 0$

Hence, by Squeeze Theorem, $\lim_{n \rightarrow \infty} \frac{T_1(n)}{T_2(n)} = 0$.
Therefore, Algo1 runs faster than Algo2 for $n >= n_0$

This is my solution, and I am wondering if this is right way to solve this question.

Any help is appreciated, thank you,


texts: How do I stop "cheating" in reinforcement learning (MLP+Evo. Algorithm)?

texts:
I have a two hidden-layer MLP. I am trying to teach it classification of the sine function. For instance, if there is an [x,y] point above the sine function, the ANN should classify that point as a 1. Otherwise, it should be classified as a 0.

It should end up like this. Points above y=sin(x) should be blue. Points below should be red. The network is just outputting 1s or 0s, so we are plotting the point along with a binary value (0=red,1=blue).

Graphic done with Matplotlib.

I feedforwarded my ANN thousands of random points, calculated the error between desired and output, and used that as fitness for an evolutionary algorithm that would evolve the network weights. The lower the error, the more likely the weights would be bred and preserved for the next round.

Unfortunately, the algorithm found a way to "break" the network. It was able to minimize the error while outputting the wrong values. For instance, one network and weight iteration I evolved outputted 0 for all inputs I would give it, even though I got the error down to 0 when I evolved the weights. It's a beauty. The plot is below.

My Python code is pretty big, so I will spare how I wrote the MLP and show you just a few snippets of relevant code.

Here, we have lists of random points and are feeding them through the MLP. If it is trained properly, the error will be close to 0 because the MLP correctly classifies each point.

    i=0
    error = 0
    while i < 100:
        output1 = feedForward(neuralNet, [xValsAbove[i], yValsAbove[i]]) # feedforward a point that is above the sine function.
        output2 = feedForward(neuralNet, [xValsBelow[i], yValsBelow[i]]) # feedforward a point that is below the sine function.

        if output1 < 0.99:
            error += 1 - output1
        if output2 > 0.01:
            error += output2
        i+=1
    return error

So, let's start evolving. Generate a bunch of random weights. Feed them a few thousand random points each in a range of -50 to 50 on both axes. Select the ones with the lowest classification error. Continue. After 50 generations, my error is down to 2 or 3. Looks good. Let's feed it a bunch of test points and see how it did.

???

Can anyone help me here?


texts: Is a matching $M$ maximum iff the graph doesn't have an augmenting path wrt $M$?

texts:
Berge's theorem: a matching $M$ is maximum if and only if the graph doesn't have an augmenting path with respect to $M$.

I don't understand this theorem. For instance the following matching is maximum but has an augmenting path, doesn't it?

The matching $M$ is in gold here and the augmenting path is the one in dotted lines.


texts:
I have to find the efficiency class of this algorithm

b = 3
a = 4
for i = 4 to n^2
    if (i mod 2 == 0)
        a = a+2
    else
        b = b*3
end for

I solve it like this, first I find the time for executed a then b and the total is the addition, is it right? I'm not sure if I have to do it like this or not, I let $n=\frac{n^2}{2}$ because of the $\bmod 2$ is it right?

$t_a(n)=\sum_{j=1}^{n^{2}/2}1=\dfrac{n^{2}}{2}$

$t_b(n)=\sum_{j=4}^{n^{2}}1-\dfrac{n^{2}}{2}=n^{2}-\dfrac{n^{2}}{3}-3$

$t(n)=\dfrac{n^{2}}{2}+n^{2}-\dfrac{n^{2}}{3}-3=\Theta (n^{2})$ by the polynomial theorem.


texts:
I'm having troubles with this question.
If $L\in R$, there there is a turing machine $M$ that decides it.
My idea is to build a turing machine $M'$ that somehow goes over all the possible permutations of the input word, in a way that separates it to groups of smaller words for $M$ to test. If there is a permutation that is accepted by all the invoked $M$s, $M'$ should accept this word. (or if it is $\epsilon$)
Since the number of permutations is finite, we can traverse all over them and reject the word eventually, hence $L^*\in R$.
But I'm not sure how to formulate it.


texts: How can I compare two different neural networks, from a theorical point of view?

texts:
Let's say I have a problem (i.e. Given f(x), find x) and two neural networks(i.e. feedforward and recurrent). I would like to know if one works better than the other one. I could run the twos on a computer, but other programs might interfere and I wouldn't know if the implementations I'm running are really the best ones humankind could create. Moreover, how could I be sure that the feedforward network worked better than the recurrent, when it might have just been "lucky"?

So, here is the question: can I compare the efficiency of two neural networks(with known sizes, structures and functions) from a theorical point of view? And if the answer is yes, how?

Thank you in advance.


texts: Is it possible to do face recognition with just the eyes?

texts:
Assuming the input photo is focused on a person's face, if the person is wearing a surgical mask, most face recognition software fail to identify the subject's face.
Most facial landmark models are trained to identify at least the eyes and the tip of the nose (for example, dlib's 5 point landmark).
Is it possible to construct a model that is trained to identify a face based on only the eyes?


texts: Time complexity of a function with while loop

texts:
What is the time complexity of the following procedure?
for $x \in \{1,\ldots,n\}$:
$\quad$ $i \gets \lfloor n/2 \rfloor$
$\quad$ while $i \neq x$:
$\quad\quad$ if $i > x$ then $i \gets i -1$, otherwise $i \gets i + 1$.
According to me, the time complexity is $O(n^2)$.
The inner while loop starts at $n/2$ and moves towards the value of $x$, worst case it runs $n/2$ times, and best case it runs $0$ times.

What is the exact time complexity of this procedure?


texts: On the generalization of two recreational problems: request for references, if there's any

texts:
I wonder if two famous (and, IMHO, very nice) recreational problems are been studied in some general form.

Here's the first.
We have 13 balls, all looking absolutely the same, with 12 of them having the same weight; we don't know whether the ball that has a different weight is heavier or lighter. We have a balance with two arms and, using it at most 3 times, it is required to identify the ball with different weight.
For the generalization below, I will consider a slightly different version of it: same scenario, but requesting the needed minimum number of times by which, in all cases, using the balance we can identify the different ball.

Here's the second.
We have three card and we are in front of a door with three slot in which we can insert the cards. Each card is the correct one for exactly one slot and vice versa.
Each slot is connected to a hidden circuit and, at the beginning, we don't know wheter a circuit is opened or closed (but at least one of them is opened).
The door will open only if all three circuits are closed.
We can change the state of a circuit solely by inserting all the three cards; when we insert all the cards, the circuits change state according to these rules: if a circuit is closed, it will open; if a circuit is opened, it will close only if the correct card is inserted in its slot.
In general, without knowing the initial states of the circuits, what is the minimum number of insertions by which the door will certainly open?

We can generalize the above problems in obvious ways: the first problem by having $n$ balls (possibly, with $k$ of them having different weight), the second problem by having $n$ cards/slots/circuits (possibly, each card being correct for more than a slot/circuit).

Are these general problems new? Any similar and well-studied one?


texts: What complexity class is the TSP problem?

texts: Is the travelling salesman problem (TSP) $FNP$-complete or is it $FP^{NP}$-complete?


texts: Is it possible to produce different shortest path trees using bellman ford and Dijkstra algorithm?

texts: Given a graph G=(V,E)  with positive edges weights, Is it possible to produce  different shortest path trees for the Bellman-Ford algorithm and Dijkstra's algorithm?


texts: Is Hamiltonian path NP-hard on graphs of diameter 2?

texts:
Let $G$ be a graph of diameter 2 ($\forall u,v\in V: d(u,v)\leq2$).

  Can we decide if $G$ has Hamiltonian path in poly time? What about digraphs?

Perhaps some motivation is in place:

the question arises from Dirac's theorem which states that if $\forall v\in V:d(v)\geq \frac{n}{2}$ then the graph is Hamiltonian, as well as it's generalizations (the Ghouila-Houri theorem and the result from Bang-Jensen and Gutin's book).

I've shown here that these degree requirements imply that the graph has diameter 2, and was wondering if such graphs can be decided without the degree requirements (strong gut feeling: No).


texts: If a language is m-reducible to a regular language, does it mean that this language is also necessarily a regular language?

texts:
I've been going back and forth with this for a dew days, can't quite be sure.

When I look at the pumping lemma method, I think a context-free language could possibly be reduced to a regular language.


texts: Intuitive Explanation on Converting BNF Grammar to LR(1)

texts:
Consider the following BNF Grammar G:

object-expression   ::=     id | id ( object-expression ) | object-expression . id
                            | object-expression [ object-expression ]
                            | object-expression . id ( object-expression )

I am attempting to construct a set of LR(1) items based on G.

Attempt:

Let's represent Grammar G as:

O -> id
O -> id ( O )
O -> O . id
O -> O [ O ]
O -> O . id ( O )

Item Set 1:

O' -> • O, $
O -> • id, $
O -> • id ( O ), $
O -> • O . id, $
O -> • O [ O ], $
O -> • O . id ( O ), $

Can someone provide an intuitive explanation in simple language on how to finish obtaining a set of LR(1) items given a BNF Grammar such as G?

Please let me know if I can provide any more information.


texts: Find the maximum (longest) delay to last user in a multicast T. NP complete proof

texts: Given a un-directed weighted graph G=(V,E) where V is the set of vertices and E is the set of edges between vertices, and weights are the time delays on each link between two user. The goal is to construct a multicast tree T (that connects source node to a set of nodes say K) such that to minimize the maximum (longest) delay of the last user in the multicast tree T. The maximum (longest) delay of the multicast tree T should be less than or equal to say d. Thus it seems a an NP-Complete problem but I don't know how to prove it or reduce it. I will appreciate your kind feedback. Thank you