texts: Longest path length in an undirected tree, can we prove this algorithm is correct (which it is)?

texts:
Hello I solved this leetcode https://leetcode.com/problems/tree-diameter/ question reserved for people who pay the subscription.

The question:

  Given an undirected tree (tree is not disjoint), return its diameter: the number of edges in
  a longest path in that tree.

  The tree is given as an array of edges where edges[i] = [u, v] is a
  bidirectional edge between nodes u and v.  Each node has labels in the
  set {0, 1, ..., edges.length}.

So the "easy" way to solve it is to start a dfs at each node in the tree and keep track of the longest path seen so far, which would be O(n^2). Given n = number of vertexes in the graph.

However I came up with the below solution that does the job in O(n), I was able to come up with it by going through examples on a piece of paper and then coded it and it passed all the tests, but I can't figure out why it formally works, can anyone help me prove it is correct ?

Here is my code:

   def treeDiameter(self, edges: List[List[int]]) -> int:
    def dfs(graph, vertex, prev, maximums):
        for neighboor in graph[vertex]:
            if neighboor != prev:
                tmp = 1 + dfs(graph, neighboor, vertex, maximums)
                if tmp > maximums[vertex][0]:
                    maximums[vertex][1] = maximums[vertex][0]
                    maximums[vertex][0] = tmp
                elif tmp > maximums[vertex][1]:
                    maximums[vertex][1] = tmp
        return maximums[vertex][0]

    graph = collections.defaultdict(list)
    for vertex1, vertex2 in edges:
        graph[vertex1].append(vertex2)
        graph[vertex2].append(vertex1)

    maximums = [[0, 0] for _ in range(len(edges) + 1)]
    dfs(graph, 0, None, maximums)

    res = 0
    for max1, max2 in maximums:
        res = max(res, max1 + max2)
    return res

The way I came up with this is I realized if I start my dfs at a node that is on the longest path, then the longest path is equal to the sum of the two longest pathes (because it is a tree there are no cycles) out of this node (which is why I store the two longest pathes max1, max2 out of a node in the maximums array) --> but what I fail to see is why that works in all cases.


texts: Disjoint paths in digraphs is NP-complete

texts:
In the article:

S. Fortune, J. Hopcroft, J. Wyllie, The directed subgraphs homeomorphism problem, Theoret. Comput. Sci. 10 (1980) 111–121.

link:

https://www.sciencedirect.com/science/article/pii/0304397580900092

It is proved that the 2-DIRECTED DISJOINT PATHS PROBLEM is NP-complete in general digraphs. The proof is pretty concise, but I have some difficulties with figuring the correctness of the given reduction from 3-SAT, mostly due to the old-fashion writing and omitted justification of details.

Does anyone here know a resource, say a textbook, in which a more comprehensible version of this proof (or maybe an alternative one) is presented?

Thanks in advance.


texts: regular expression to accept all strings other than one containing ads or adlib

texts: My intention is to select only those packages whose name do not contain  adlib or ads. But if i add *adlib* and *ads*  it  selects all packages containing the substring adlib and ads. So i need a regular expression to select all packages that do not contain substring adlib and ads.


texts: DFS algorithm and how do I show/put it into practice?

texts:
I'm new to DFS algorithm and I'm trying to figure it out.

The main concepts I get from it is that you have a stack of nodes, and they have a value, and can contain children-nodes (Even called branches or leaves) that can contains nodes with values.

So let's say that I have a Tree containing 15 nodes like this.

I would understand that the algorithm goes A-N-O-B-D-J-L-M-K-C-E-F-H-G-I, If you were to go in alphabetic order.

My confusion is this how to put this algorithm into practice (such as coding it). How should I see this tree like (Array, List?)

And if some of the children are connected to each other can it still be a DFS algorithm?


texts:
Is IP masquerade and Network Address Port Translation(NAPT) the same? I'm not sure whether it is the same thing or not but I realized the mechanism is almost the same where both IP masquerade and NAPT changes TCP/UDP port and many-to-one relation is allowed:multiple private addresses share one global IP address.
If it is different which part is IP masquerade and NAPT is different?


texts:
I’m a sucker for mathematical elegance and rigour, and now am looking for such literature on algorithms and algorithm analysis. Now, it doesn’t matter much to me what algorithms are covered, but very much how they are presented and treated.¹ I most value a very clear and precise language which defines all used notions in a stringent and abstract manner.

I found that the classic Introduction to Algorithms, by Cormen, Leiserson, Rivest and Stein is pretty neat, but doesn’t handle the mathematics well and is quite informal with its proofs and definitions. Sipser’s Introduction to the Theory of Computation seems better in that regard, but still offers no seamless transition from mathematics to algorithms.

Can anyone recommend something?

¹: The algorithms should at least invole the management of their needed data using classical non-trivial abstract data structures like graphs, arrays, sets, lists, trees and so on – preferably also operating on such data structures. I wouldn’t be too interested if the issue of usage and management of data structures was ignored altogether. I don’t care much about the problems solved with them, though.


texts: Proof that a guard digit bound the error of subtraction

texts:
I was reading What Every Computer Scientist Should Know About Floating-Point Arithmetic, which is extremely interesting. But I have some troubles understanding the proof of Theorem 9 (page 33).

First a pretty trivial question. When the formula $(15)$ say:
$$y - \bar{y} \lt (\beta - 1)(\beta^{-p} + \dots + \beta^{-p-k})$$
Shouldn't it be $\le$ instead of $\lt$, or did I miss something?

More importantly, I do not understand why it say that if $x-\bar{y} \lt 1$, then $\delta = 0$. How can there be no rounding error?

It is then said that:
$$x - y \ge 1.0 - 0.\overbrace{0 \dots 0}^k\overbrace{\rho \dots \rho}^k \; \textrm{with} \; \rho = \beta - 1$$

Why is that so? Can't the difference be arbitrarily small or even $0$? Why would there be as many $\rho$'s as there are $0$'s?


texts:
Wiki define Polynomial time as fallow:

  An algorithm is said to be of polynomial time if its running time is
  upper bounded by a polynomial expression in the size of the input for
  the algorithm, i.e., $T(n) = O(n^k)$ for some constant $k$

I understand that in general speaking the difference between Polynomial time and Exponential time is that exponential function grows strictly faster than any polynomial function, asymptotically(reference).

I am trying to understand the core definition of Exponential time.

What elements will make one algorithm to run in Exponential time?
What change do I need to do in the polynomial expression to make it Exponential time?(By it I am referring to the algorithm definition in the beginning of the question)


texts: About gradient descent on non-convex functions

texts:
There is this "folklore" result that gradient descent on a non-convex function takes $O(\frac n {\epsilon^2})$ steps to get to a point whose gradient norm is below $\epsilon$ and with SGD this takes $O(\frac {1}{\epsilon^4})$ steps.

Can someone share a reference where this is proven?

I am aware of the recent references where these numbers have been improved. But I am not able to locate a pedagogic presentation of these older results.


texts: Time complexity for balancing an unbalanced binary tree

texts:
The question here is that: There is an unbalanced binary tree with n-nodes. What is the time complexity to balance the tree?

The solution I thought of involved solving using Recursion where for the worst-case I took a maximally unbalanced tree like this

And then try to balance this using rotations.

But I cannot come up with an expression which will give O(log(n)) time complexity.

Can I get some help in solving this?
I am stuck on how to approach this problem.


texts: Are there infinite possibilities to the outcome of the P vs. NP question?

texts: The P vs. NP poll provides 3 possibilities: equal, not equal, and independent. This is reasonable, because despite the law of the excluded middle you must supply a proof for your answer, which itself is insufficient. But then the statement "P vs. NP is independent" itself can be independent, with a proof. And this process can go on indefinitely. One of them must be provable, or did I miss something? Anyway the number of possibilities is infinite, instead of 3. Is this correct?


texts: What's the meaning of this service specification

texts:
What's the meaning of the example statement here?

"A service specification S describes an interface: it specifies the behavior of certain program elements (functions or subprograms) through statements expressed in program logic. For instance, these might be such statements:

[...]
x, y : N[{x>0} y := x * x {y > x}]

"

The quote is from the article  "On The Hourglass Model"
By Micah Beck,
Communications of the ACM, July 2019, Vol. 62 No. 7, Pages 48-57


texts: What's the purpose of the non-deterministic Turing machine?

texts:
(*) Acronyms

NTDM := non-deterministic Turing machine.
TM := deterministic Turing machine.

(*) Consider the following idea

The NTDM is able to follow, in parallel, all paths of the tree of the universe of solution.  Suppose that in some point in time, for a certain problem, a new theorem is discovered that tells us that we need not worry about certain branches of the universe of solution because those branches yield no solution.  Then in some future point in time, a new theorem appears telling us we need not worry about some other branches of the tree and so on.  New theorems keep on being proved such that eventually there's only a single path to be followed in the tree of the universe of solution.  The problem therefore affords a polynomial solution since at every branch, it tells us where to go.

So the concept of NDTM accounts for all future scientific development.  Therefore, if a problem cannot be solved in polynomial time in the NDTM, then it's not in NP and therefore has no chance of being polynomial, no matter how science might advance.

This seems to be a good reason for the concept.  Is there any flaw in this argument?  In parallel, I'm interested in the question: why was the NDTM invented?


texts:
I have a multi-objective optimization problem (NP-complete). To solve it, I've decided to use the genetic algorithm.

I have 3 "areas" of optimization, say parameters a, b and c, so cost function for my problem is C(F) = a + b + c -> min.

I want to somewhat modify the genetic algorithm. In the classic workflow, the initial population is created randomly. For my problem, I want to create a "smart" initial population. Since I have 3 parameters to be optimized, I wanna create 1/3 of the initial population optimized for parameter a, 1/3 optimized for parameter b, and 1/3 optimized for parameter c. Then, in the while loop just "mix" these good individuals. Is this a good way to go? Is this still considered the genetic algorithm? Is this a good modification?

P.S. I'm doing research for my master's project so I need to provide some novelty in my solution. Would this modification be considered fine for that?

Thanks in advance.


texts: Equivalent DPDA that always halts for every DPDA with empty stack language

texts:
I want to show that for every deterministic pushdown automaton with the language of the empty stack there is a deterministic pushdown automaton that always halts.
my transition function of $P$ is

$\delta: \Gamma \times Q \times \Sigma_\lambda \to \Gamma^* \times Q$

I tried to use look ahead pushdown method. I think I should create a $DFA$ for every $q \in Q$ that recognize if $P$ is in the lambda-cycle starting from $q$ with input string reversing of containing the stack of $P$. I define NFA with states of set $\Gamma \times Q$ and it has transition from $(\alpha,p)$ to $(\alpha',p')$ reading $\beta$ if there is $(\beta\alpha',p') \in \delta(\alpha,p,\lambda)$ and start state is $(Z_0,q)$ and I think every state should be final state. then reverse $NFA$ and convert it to $DFA$. I don't know this works or not. I after that I can create $DPDA$ named $P'$ such that its stack simulate all $DFAs$ and also original stack of $P$ and after that I can decide if $P$ will be in the loop in future so in $P'$ it halts.

how can I edit creating $DFA$ that works well?

Edit

I changed the way using above automata, first of all, I design $DFA$ to check if in future there is a sequence of lambda-transitions that empties stack? if there is so I should let process continues because it will stop in future. $NFA$ is like above example with final states in $(\lambda,q)$ for each $q\in Q$ and simply we can convert $NFA$ to $DFA$, if there is not such sequence I ask another question, is it possible that we have some non-lambda transition? checking this is also simple we create exactly same $NFA$ as above $NFA$ and after that, if in a state we have non-lambda transition we go to a special final state. if there is no such transition it means we will stock on loop in future.


texts: How to check a graph diameter in LOGSPACE?

texts: Given a graph G, how can I check that its diameter doesn't exceed log(n) (n is the number of vertices)- by using only O(log(n)) space? (adjacency matrix doesn't seems to help...)


texts: Why can't we simulate an NP oracle with an NP machine?

texts:
In this question : Does $NP^{NP}=NP$? ,
it says that one of the reason is that we don't know how to detect 'no' answers from the oracle.
Why is that true though? There is an NTM for any language L in NP, that runs in polynomial time. IIRC we can simulate the NTM with a deterministic TM M that runs in exponential time, that tries every non-deterministic option, and decides L... So why can't we simulate the oracle using that M in another NP machine?

Thanks.


texts: Is it possible to design a C++ like language without a Preprocessor?

texts:
According to the dragon book, one of the first steps the source code of a program goes through during compilation is the Preprocessor.

Assuming a language like C++ where there is no underlying virtual machine to abstract away the underlying platform, is there a way to deal with cross platform compilation without requiring the use of the Preprocessor?

Another use case would be code to remove code that should only be executed in "Debug Builds".

P.S: I'm not mentioning other uses of the preprocessor like defining a value for PI as these can easily be replaced with the use const global variables.


texts: Context Free Grammar for Try-Catch-Finally Statement and Throw

texts: I am currently working on a problem that is asking me to write the grammar productions for the try-catch-finally and throw C# statements. It states that "you can assume that there are nonterminals "Type", "Expression", and "Statement", as well as a terminal "Ident". I do not understand how this is possible using so few nonterminals and only one terminal


texts: How to prove that insert complexity in binary search tree is minimum O(log n)?

texts:
Is it connected to BST search O(log n) or height log n?
How to prove that insert will give give you correct BST in minimum O(log n) time?


texts: Least common ancestor relative to an arbitrary vertex as root

texts:
Consider following problem:

  Given an undirected tree answer following type of queries. (No. of
  queries and vertices can be as high as $10^5$)

  $\text{LCA}(r, u, v)$: Find the Lowest Common Ancestor of vertices $u$ and $v$ assuming vertex $r$ as the root.

Now, in solution it's given that answer will always be one this: $r, u, v, \text{LCA}(r, u), \text{LCA}(r, v), \text{LCA}(u, v).$

Where $\text{LCA}(u,v)$ denotes Lowest Common Ancestor of vertices $u$ and $v$ if we assume vertex number $1$ as the root.

So I'm looking for a proof for claim made in a solution.


texts: Is there any development in continuous-value computers?

texts:
Is there anything that hints at the possibility of a (modern) continuous-value computer, since modern computers are based on discrete arithmetic?

I guess the old analog computers were of this continuous-value type, but is there any modern development?

Do you know something about the issues regarding computability on such machine?


texts: Byzantine generals problem with signed messages (Lamport)

texts:
I have some trouble understanding Lamport's paper about the Byzantine generals problem when it comes to signed messages. He showed that, with signed messages, the number of generals must be at least $m+2$ to tolerate $m$ malicious units\faults (for fewer generals, the problem is vacuous).If that's fulfilled it's guaranteed that the loyal generals make the same decision.

Now, I read a lot of papers where at least $2m+1$ generals are needed. The argument in these papers is that the loyal generals have to outnumber the malicious ones to make a majority vote (to get not only the same but the right result). But why isn't it sufficient to have $n \ge m+3$ with three loyal generals for majority vote?

Moreover, if $2m+1$ generals are needed for the majority vote, how can that work with three generals and one traitor? In both cases I need $m+2=3$ and $2m+1=3$ generals and (from what I understand) then I can only agree on the same but not on the correct value (majority vote with two loyal entities?).

I know that I have an error of reasoning here, but I really don't get it. Maybe someone can help me with that problem?


texts: Using saved registers at the main function with no other function calls [RISC-V]

texts: The convention when a function is going to use a saved register is to save the contents of that register to the stack in case the caller (if there's one? the main function doesn't have one) had been using this register too and to restore the contents right before returning. Is this convention always obeyed? In the case of a really simple program, with just a main function and no other function calls, would the compiler prefer to optimize and disobey the convention, which means no saving before using the saved register? Of course, a convention is not a rule so i was wondering in which situations can these not be followed?


texts: How to convert a decimal number to ASCII representation

texts:
The question that was in my lecture notes said

    "Encode the decimal number 2370  in ASCII. "

and the answer given there is

    32 33 37 30 (ASCII code representation)

My question is how do we get this? Do we simply add 30 to each digit? I am sorry if this is a very obvious question I do not know the correct way to look up the ASCII table for conversions. Any help would be appreciated.

PS: This is not my homework, my course finished today morning. Just asking out of curiosity.


texts: Constructing an unrestricted grammar for a^n b^m c^n d^m

texts:
I've been trying to construct an unrestricted grammar which has the language:

L = {a^n b^m c^n d^m | n>0, m>0}

But I can't seem to figure it out without making the derivations run an unreasonably long amount of time.  Can anyone help me devise an elegant way to create this grammar?

Edit: In order to clarify, I was trying to find an Unrestricted Grammar that would run in O(n^2) time or better.  As it stood, all of my solutions were exponential, which made parsing very long strings prohibitively costly.


texts: Why mod operation can be used as hash function

texts:
I'm new here, and I'm currently trying to understand why mod operation can be used as a hash function.
For example, consider the function $h(x)=x\mod 2^{256}$, where $x$ can be a string of any length. The book says that this function will return a fixed size of 256 bits. To my understanding, $h(x)$ will return an integer in the interval $[0,2^{256})$, which can be expressed in 256 bits. My question is that, suppose $x$ is $5$, then $h(x)=5$, which can also be expressed in 3 bits (101). How do we guarantee that the output will be the size of $256$ bits? (I am just new to computer science and apologize if the question is too elementary).


texts: Is it possible to form this as a linear program?

texts:
My problem is as follows: I have some number $n\in \mathbb{N}$ of items all of size $s\in \mathbb{N}$ that need to be fit into a distributed storage of sizes $[b_1, b_2, ..., b_m], \forall i, b_i \in \mathbb{N}$. I want to fit as many of the $n$ items as possible. The constraints are

To place an item into a bin $b_i$, $s+1$ slots of $b_i$ are consumed
It's possible to split $s$ into multiple bins $i,j$, but doing so consumes in addition to the slots used for the item, 2 slots of $b_i$ and 2 slots of $b_j$. If a third (or more) split $b_k$ is required, 2 further slots from $b_i$ and $b_j$ are NOT required. That means only 2 slots are required from each of the bins $s$ is split into. At least one of the bins $s$ is split into also needs to allocate 1 additional slot.

I feel like this can be formed as a linear/integer program but I can't quite figure out how to accommodate the splitting part.
What I've come up with so far is:

$x_{ij}\in\mathbb{N}$: the number of units from item $i$ allocated to bin $j$
$y_{ij}\in\{0,1\}$: Number of units in bin $j$ for item $i$'s allocation cost
$z_{ijk}\in\{0,1\}$: Item $i$ is split between bins $j$ and $k$
$f_i\in\{0,1\}$: Item $i$ fits

I'd want to maximize $\sum_{i} f_i$. The constraints I came up with so far are:

$f_i \cdot \sum_{j}x_{ij} = s$ or $f_i \cdot \sum_{j}x_{ij} = 0, \forall i$
$\sum_{i,j} y_{ij} = \sum_{i} f_i$
$\sum_{i}x_{ij} + y_{ij} + \hspace{2mm}?z_{ijk}\leq b_j, \forall j$ (not complete)

And from here I'm quite stuck. I'm not so familar with linear programming so I'm not sure if this problem can even be formulated as one. Any advice is much appreciated.
Here's an example of how the storage would work:
Let's say I have $1$ item of size $8$ to store in a storage system of $[5,5,5]$. The distribution would have to be $[2, 3, 3]$. In the first storage system, $1$ unit is used for the cost of storing the item, $2$ are used to split the item between bins $2$ and $3$, and $2$ are used to store the item. In the second bin $2$ units are used to split the item between bins $1$ and $3$, and $3$ are used to store the item. Similarly with the third bin, $2$ units for splitting and $3$ for storage.
If instead I had $3$ items of size $4$, I could store them one in each bin, and the storage would be completely consumed because it costs $1$ unit of storage to store the item.


texts: Alternatives to the stack and heap-based memory models

texts:
The stack seems to be an optimization of memory use for a specific application. Whereas the heap is a general model that works in all cases. Wondering if there are any other types of models of computer memory allocation that are optimized for different use cases.

Following from this:

https://softwareengineering.stackexchange.com/questions/222564/are-there-alternatives-to-stackheapstatic-memory-model

  Way back in the day, that's exactly how it happened, programmers planned ahead of time exactly what each RAM location would be used for.

Wondering what might have been some of the techniques for allocating memory for specific use cases back in the day, or today.


texts: Understanding the proof of the halting problem

texts:
I came across the following example that proves that the blank tape halting problem is not decidable.

I understand the proof technique, but I just don't see how the blank tape problem is shown to be undecidable in the proof.

It says $M_{w}$ starts with a blank tape but then writes $w$ onto the tape, so there is no difference to the general halting problem.

How does this imply that the blank tape halting problem is not decidable? I can't find the logical conclusion. Couldn't we just replace the blank tape halting problem with another DECIDABLE problem and argue the same way?


texts: Relation between size of hashtable and number of values to keep expected number of collisions below/equal to 1

texts:
This is an exam question from my algorithms and data structures course.

You imagine an hash function with h: U->{0,..m} (this is from the original question, but i think m-1 would be correct) and n values to hash.
You want to keep the expected number of collisions below or equal to 1.
How do you determine m in dependence to n.

My initial idea was following formula to determine the number of collisions:
$n- E(\text{occupied locations}) = n-m+E(\text{empty locations}) \\$
$= n-m+m(1-\frac{1}{m})^n$

For our question this would give: $ 1 \geq n-m+m(1-\frac{1}{m})^n$

I know that following solution would have been correct (and i know why now):

$E[x]=\frac{n(n-1)}{2} \cdot \frac{1}{m} = m \geq \frac{n(n-1)}{2}$

Well i know i did not solve the first Equation for m (i do not know how), but my question is if both solutions would be correct and if not why?

I got the first Equation from Darthmouth ([Link]:https://math.dartmouth.edu/archive/m19w03/public_html/Section6-5.pdf)


texts: Is knapsack a Linear Programming problem?

texts: Since Knapsack give Optimal solution as LP so is it also a LP or not ?


texts:
I have a question that, no matter how much I think about, I do not have the answer to.  The question is what exactly is computer science?  The reason I am asking is that I went into college thinking computer science was going to be about software engineering disciplines and deep study in the realm of application and practicality; these excited me.  However, after taking core requirement classes for computer science, many so devoted to discrete mathematics (set theory, group theory (abelian properties, etc.), probability, etc.), I became disillusioned and frankly, sick of taking these abstract-concept related courses, asking myself daily when I would use these concepts in my daily life as a developer.

I've searched online for the answer, but none have satisfied me so far.  Several arguments have boiled down to essentially saying something like "If you want to do gaming, you have to be good at trigonometry, which is math"; clearly, this is not what I am looking for.  If someone could guide me into truly understanding why discrete math and structures is essential to the software engineer, and to the world outside the realm of the academia aspect of computer science, that would be awesome.  Thank you!


texts:
I have this recurrence equation:

$T(n) = T(n/4) + T(3n/4) + \mathcal{O}(n)$

$T(1) = 1$

I know that the result is $\mathcal{O}(n \log n)$ but i don't know how to proceed.


texts: Finding multiple paths through a grid such that every grid square is equally used

texts:
Setup

Here’s the setup: I have an $N$ x $N$ grid of tiles, and a list of $M$ agents that need to move across the grid. Each agent has its own start tile $S(a)$, end tile $E(a)$, and an exact number of steps $D(a)$ it must make.  Each step consists of a one-tile move horizontally, vertically, or staying in place.  For each agent, $D(a)$ is usually much larger than the Manhattan distance between $S(a)$ and $E(a)$, so the path the agent takes is not necessarily a straight line from $S(a)$ to $E(a)$.  Furthermore, the sum of all $D(a)$ is expected to be much larger than $N$ x $N$, so every tile will be used at least once.  Agent paths are allowed to intersect with other paths and with themselves, and the number of agents on a tile at any given time doesn’t matter.

The Problem

I would like to find paths for each agent that begin at $S(a)$, end at $E(a)$, and are exactly $D(a)$ steps long, with the goal of minimizing the maximum number of times any given tile is used.  More formally, given an agent path $P_0 \ldots P_n$, let $C(P, t)$ be the number of times tile $t$ appears in $P$, and let $A(t)$ be the sum of $C(P, t)$ over all agent paths. I would like to find agent paths that minimize the maximum $A(t)$ over all tiles $t$.

My intuition tells me that this problem is almost certainly NP hard, so I’m looking for some kind of approximation or heuristic.

First Attempt

My first stab at solving this was to find each path sequentially.  For each agent, I create a 3-dimensional $N$ x $N$ x $D(a)$ search space, then use A* search to find the min-cost path from $[S(a), 0]$ to $[E(a), D(a)]$.  The cost of each node in the search is the number of times that tile has been used by previous paths.  Then, once the path is found, I add to the cost of each tile used, and proceed to the next agent.  Of course, this leads to the problem that while the last agent path will be pretty good, the first agent path will be essentially random because the grid is yet totally unused.  So, I just loop this process a few times; once the last path is computed and the tile costs updated, I loop back to the first path, subtract from the grid the costs that agent contributed, then recompute that path and add the new costs in.  After 3 or 4 loops, I converge on a pretty reasonable solution.

But I’m hoping there’s a better idea out there.  Any ideas or references to similar problems that I could read up on would be very welcome.


texts: How to calculate the number of invalid strings given a constraint system on alphabet, word blacklist, and string length

texts:
If I have the following system, I am wondering how to calculate the number of valid strings it contains.

The system is something like this, which can have arbitrary variations.

Only consists of an alphabet $\Sigma$.
It can't spell any words in a blacklist word list $\rho$.
It can't have more than $n$ characters of the same type in a row.
Every word $\omega$ it generates is no more than $m$ in length.

So for example, we might have this system:

$\Sigma = (a, b, c, d, e, f, g, h)$
$l = \texttt{len}(\Sigma)$
$\rho = (\texttt{bed},\texttt{fad},\texttt{dad},\texttt{bead},\texttt{deed},\texttt{fade})$
$n = 3$ (so can't match /aaaa|bbbb|cccc|dddd|eeee|ffff|gggg|hhhh/)
$m = 20$

Say we have a random number generator, which uses a radix algorithm to convert it into a string using the characters in the alphabet $\Sigma$. The thing is, this random number generator might generate strings like the following, which we just have to drop and forget, then try generating another one until we get one that matches the constraints. Don't know of a better way to do that, but that's beside the point. So it might generate these ones, which are invalid.

afbcdeabeadbeaaaadaf
[bead and aaaa]
bedddddagheadfffeeee
[bed and dddd]

So the question is, how do I calculate how many strings are invalid? I know how to calculate the possible strings given the constraints, that is simply:

$$z = l^m = 8^{20}$$

I don't know how to calculate the number of strings that are invalid though, in a general way (so I can change the value of $m$, $n$, $\Sigma$, or $\rho$). Wondering how to formulate this problem mathematically or algorithmically so that I can figure out that "there are x number of invalid strings", and so I can calculate:

$$y = z - x$$

to get the total amount of possible strings given the constraints.


texts: Why isn't deque implemented as a dynamic array?

texts:
We know that std::vector in C++ is implemented as a dynamic array with specific pattern of reallocation (multiplying capacity by a constant), which allows it to reach O(1) amortized push_back time. But changing capacity of a vector is essentially allocation of new memory block and copying old data into it. That means we can as well implement a vector which can grow in both directions with amorized O(1) push_back and push_front time.

But std::deque is implemented in different, rather complicated way, not storing data in a contiguous manner and suffering from related issues (e.g. more frequent page faults when iterating). Why so? Are there any obstacles disallowing to implement deque as a dynamic array?


texts: How to make the standard DP algorithm for 0/1 Knapsack make larger steps?

texts:
The standard knapsack problem solution is O(nW) where we will increment the weight +1 at a time to get to the solution.

Is there any approach to the knapsack problem that does not require incrementing weight +1 at a time.

e.g. One way that I can think of is to divide all the numbers by its common

Capacity = 100 weights = [5, 10, 20] -> Capacity = 20 weights = [1, 2, 4]


texts: How to replace the max distance of a bounded set of points with a random point in less than $0(n^2)$?

texts:
Context
Let's say I have a finite set of points of size $N$.
I can represent the points in a metric space and then compute distances between them.
My goal is to replace a point in the set with another one (let's say a completely random point), only if the new point maximum distance is better than a set's point maximum distance.
For example let's say I have a set of size $N = 6$ points, with the following distances :

$S_1$
$S_2$
$S_3$
$S_4$
$S_5$
$S_6$

$S_1$
0
80
30
80
72
41

$S_2$
80
0
85
113
72
41

$S_3$
30
85
0
50
50
45

$S_4$
80
113
50
0
45
81

$S_5$
72
72
50
45
0
50

$S_6$
41
41
45
81
50
0

Now I randomly generate a point $S_k$ and compute the distances between it and the set's points :

$S_1$
$S_2$
$S_3$
$S_4$
$S_5$
$S_6$

$S_k$
54
36
71
112
81
32

The biggest distances in my set are respectively :

$S_1$
$S_2$
$S_3$
$S_4$
$S_5$
$S_6$

max($S_i$)
80
113
85
113
72
81

Now you can see that max($S_k$) is greater than max($S_1$) and max($S_3$) and max($S_5$) and max($S_6$).
What I want to do is replace the point with the smallest max($S_i$) with $S_k$, if max($S_k$) > max($S_i$).
In that example I can replace $S_5$ by $S_k$ :

$S_1$
$S_2$
$S_3$
$S_4$
$S_k$
$S_6$

$S_1$
0
80
30
80
54
41

$S_2$
80
0
85
113
36
41

$S_3$
30
85
0
50
71
45

$S_4$
80
113
50
0
112
81

$S_k$
54
36
71
112
0
32

$S_6$
41
41
45
81
32
0

My approaches
The naive approach to this problem is to compute the max distance between each point every time a new one is generated and to replace the one with the lowest max distance. As you can guess this approach is highly inefficient, $O(N^2)$, I assume.
My intuition leads me to use memoization to solve this problem efficiently. The maximum distance for each point is stored in memory, and updated whenever a point is replaced in the set. However, I have issues with this method :

The point erased from the set may contain the max distance for another point, thus changing the latter's max distance to something completely new. It means I have to go through the entire column/line for a solution to find its maximum distance again, inducing the worst complexity of $O(N^2)$. In the previous example, if I had to replace $S_2$ with $S_k$, this would happen.

If I try to get around that by storing the two biggest max distances for each solution, the issue is the same. If the solution erased is the second max distance of another solution, I have to go through the entire column/line again to find the second maximum distance for that solution.

Questions
Now I have several questions regarding this problem :

Is it possible that the case of erasing a point from the set leads to erasing the max for other points? I thought about that case but did not encounter it in my examples. Do some triangular inequality property prevents this from happening or can it happen?
Is memoization a good approach to that problem? If not, what other paradigm could I try to solve efficiently?


texts: Projecting points on a Pareto-front onto a (hyper)plane?

texts:
I'm trying to implement the Biased Crowding Distance in NSGA-II as described in the paper Integrating User Preferences into Evolutionary Multi-Objective Optimization by Branke and Deb.

Basically, from what I understand, given a set of points on a Pareto-front, we need to project the points onto a hyperplane with a direction vector $\eta$. Doing this will give the new crowding distance $d'$ based on the locations of the individualson the hyperplane with direction $\eta$.

To illustrate, see the figure below.

My question is simple: how do we obtain the hyperplane given a user-specified direction vector $\nu$? Is it simply by getting the perpendicular of the direction vector?

And a follow up question would be: how would I project the points onto the hyperplane? If $p$ is the point and $v$ is the vector representing the hyperplane, is it correct that the new location of $p$, call it $p'$ is $\frac{v.x(p.x) + v.y(p.y)}{||v||^2} (v.x, v.y)$ based on this?

Thanks and any information would be very helpful.


texts: Do Self Types make the Calculus of Inductive Constructions obsolete?

texts:
Self Types are an extension of the Calculus of Constructions [1] that allow the language to express algebraic datatypes encoded through the Scott Encoding. The Scott Encoding provides one the ability to pattern-match in O(1), which is one of the main motivators for the inclusion of inductive definitions on CC. Yet, Self Types are make for a much simpler and elegant base theory, and are seemingly no less powerful.

Do Self Types, under a theoretical point of view, make CIC obsolete, or is there still some aspect on which CIC is favorable in relation to Self Tyes?

[1] http://staff.computing.dundee.ac.uk/pengfu/document/talks/mvd-2012.pdf


texts: What is the time complexity of generating n-th prime number?

texts:
Say I want to find the n-th prime. Is there an algorithm to directly calculate it or must I do with sieving? I know always calculate the next prime with a sieve principle, but what if I want the n-th prime?

Duplicate:

https://math.stackexchange.com/questions/1257/is-there-a-known-mathematical-equation-to-find-the-nth-prime


texts:
Will a study of the mathematical proof of a (data structure and algorithm based) problem, when posed as a proposition, highlight peculiar properties of the problem which may help in designing an optimal algorithm?

I think that proofs should yield interesting insights, and therefore can be used in designing algorithms. Since the program is expected to return a true response for every input, proof must be, in some way, built into the program. Is there any text I can refer to in this regard which will help in real problem solving?


texts: Represent a DNF formula as a multivariate linear formula?

texts:
Lets say I have the following DNF: (x or y) and (z or i) / $(x\lor y)\land(z\lor i)$
How do I convert that into a polynomial form?


texts: Why does DFS only yield tree and back edges on undirected, connected graphs?

texts:
Prove that if G is an undirected connected graph, then each of its edges is either in the depth-first search tree or is a back edge.

Now, from intuition and in class lectures by Steven Skiena, I know that the above holds true, since it dives all the way down, and then throw a rope back to a previous vertex. I also know that DFS is great in finding cycles.

However, my problem here is that I don't know how to prove that the edge is either a tree edge or a back edge.


texts: Computing the minimal flexible distance of two vectors using dynamic programming

texts:
I can't figure out a recurrence equation for a dynamic programming assignment. Formally, we aim
to minimize the total sum of distances between matched points with the following constraints:

Every point from both vectors has to be matched at least once, but can be matched multiple
times.
A point i can only be matched with a point j if no point o is matched with a point u such that i < o and j > u or i > o and
j < u, i.e., the ‘lines’ of the matches are not allowed to cross.

In order to compute the distance between two matched points, we use the absolute difference.

(Easy) Example input:

1.0 2.0 2.4 3.5
2.0 2.1 2.0 3.2

Should output:

1.8

Because in this example |1.0 - 2.0| + |2.0 - 2.1| + |2.4 - 2.0| + |3.5 - 3.2| is optimal

The assignment hints to sequence alignment which I thoroughly studied and came across the Needleman-Wunsch algorithm. However, I can't figure out how to adapt it to this problem.


texts: A Question relating to a Turing Machine with a useless state

texts:
OK, so here is a question from a past test in my Theory of Computation class:

  A useless state in a TM is one that is never entered on any input string.  Let $$\mathrm{USELESS}_{\mathrm{TM}} = \{\langle M, q \rangle \mid  q \text{ is a useless state in }M\}.$$
  Prove that $\mathrm{USELESS}_{\mathrm{TM}}$ is undecidable.

I think I have an answer, but I'm not sure if it is correct.   Will include it in the answer section.


texts: What is the precise mathematical definition of n-iterated recusion?

texts:
Primitive recursion can be extended to double-recursion as in the following link:

http://www.andrew.cmu.edu/user/kk3n/recursionclass/1primrec.html

How can this be generalized to n-iterated recursion?  I got the term "n-iterated recursion" from Hans Hyttel on Quora.  The idea is that double-recursion extends primitive recursion in a manner similar to the way that (n+1)-iterated recursion extends n-iterated recursion.  I am looking for a clear function based definition, similar to the definition of primitive recursion and double-recursion in the link above.


texts: Terminology for worst-case N-complexity on $O(1)$ insert after amortisation

texts:
Normally, when discussing amortisation and worst-case complexity, amortisation negates the worst-case scenarios, and the BigO describes the average for the operation (the way it's used in interviews nowadays).

For example, when an insertion of an element requires reallocation and copying of the array, increasing the size in two, it is still said that insertion is $O(1)$, not $O(n)$; the worst-case performance is rarely mentioned.  Compare this with sorting algorithms, where the worst case could be $O(n^2)$, whereas the average case could be $O(n\log{}n)$, and this is always specified and discussed.

What is the terminology to express this N-level complexity for the $O(1)$ insertion that requires reallocation with copy of $O(N)$ elements?
What is the alternative terminology for expressing an optimisation approach, with delayed copy, where the worst-case complexity remains constant-time, provided the operation to allocate new chunk of memory itself is constant.  In other words, where you keep both arrays, and do a lazy-copy approach.

Specifically, both of the above could be described as amortisation.  But I'm having trouble finding out the absolutely correct terminology for this nuanced problem, as how do you distinguish between these two different scenarios in describing amortisation?!


texts: Can two minimum spanning trees for a same graph has different number edges?

texts:
(1) Let's say $T_1$ has $r$ number of edges and $T_2$ has $s$ number of edges; where $r \ne s$ but two trees has same weight since they both are MST.

I kind feel this kind not be true because to span $n$ vertices with minimum number of edges, we need $n-1$ edges. so MST must have at least $n-1$ edges; if some MST has more than $n-1$ edges, then there must exists a cycle which leads to non-MST.

However, I don't know how to show that if the number of edges is greater or equal to the number of vertices of an an undirected, connected graph $G$, then $G$ has a cycle.

What if the graph is directed? Is this hold as well?

Any hint?


texts:
I want to solve the following formula:
$T(n)=T(n-1 )+ c\cdot\log n $, $T(1)=d$

I though about master but then I realized there is no dividing here so it's not gonna do it,
I tried to expand the formula like this:

$T(n-1)=T(n-2) + c\cdot \log(n-1)$

$T(n-2)=T(n-3) + c\cdot \log(n-1)$

How do I find the general formula?
How do I proceed from here? My professor taught us only master theory, no iteration


texts: Are Petri Nets actually used in the industry

texts: I'm having a hard time finding any prominent applications of Petri nets in the industry. Can you name some, or are Petri nets still just an academic curiosity?


texts:
In Sipser's Introduction to the theory of computation (3rd edition), I found the following claim.

Consider the grammar:

$$
\begin{align*}
&R \to XRX \mid S \\
&S \to aTb \mid bTa \\
&T \to XTX \mid X \mid \epsilon \\
&X \to a \mid b
\end{align*}
$$

In this grammar, it holds that $T \Rightarrow^* T$.

Can anyone explain how this is true?


texts: Ideal number of participants for evaluation of development approach / software architecture

texts:
For my thesis, I have created a development approach (consisting of schemes, an application template and prototype code) that should make it easier to develop and adapt applications for a specific platform.

I have conducted interviews with developers of that platform to evaluate my approach. There have been 5 interviewees so far and the feedback that I got from them is sufficient for my scope, I would say.

However, in my thesis I would like to justify my decision that 5 evaluators are enough. Is there any scientific research or paper that suggests a certain number of evaluators for such a rather theoretical approach?

I know Nielsen's work about heuristic usability evaluation which says that with 5 participants, you discover around 75% of all problems in software usability / UI testing.

But as I said, my approach is no specific software product that has to be evaluated, but only the model itself, which is why I'm looking for research in that area.


texts: Turing machine state transition diagram vs finite state machine state transition diagram

texts: If you were given a state transition diagram could you tell, just by looking at the diagram, if the diagram represented a DTM or a DFA (especially if it was unlabeled, just a directed graph)? Would there be any difference between the diagram representing the deterministic Turing machine and the diagram representing the deterministic finite automata, or is the difference between them in the context that surrounds the diagram and in the labeling ie. one can read and write to the tape while the other can only read?


texts: Bisimulation, bisimulation equivalence and simulation equivalence?

texts: I got a little confused with these 3 concepts. Is there a difference between bisimulation and bisimulation equivalence and if yes, then what is it? Also, if we say that the LTS's X and Y are bisimilar, this implies they are simulation equivalent, right? Please, someone, clarify.


texts: When was the dynamic array first introduced as an example for amortized analysis?

texts:
I'm writing a report on amortized analysis, and I'm using the example of a dynamic array to explain each method. I think it would be nice to add a reference to when this example was first used, as it seems like it is a classic example.

I've been looking and can't seem to find a reference to it. Does anyone know when the example was first used?


texts: Rotating a set of points around two fixed points

texts:
I have a set of points that are used to draw a shape. I want to rotate this shape without moving its start and end points. I tried to illustrate what I want in the image below (original shape on left, interpolated on right). Are there any algorithms to do that? I researched Hermite Spline and Bezier Curves but I did not think they are applicable in my problem.

My goal is achieving this action with only 2D transformations:


texts: Is a unary language regular iff its exponent is a linear function?

texts:
While doing the current assignment for my formal languages and automata course, I kind of got stuck on exercises involving unary languages (I hope that's the right term), i.e., languages which build upon a single letter. I don't want to ask about the specific exercises, though, but rather about a much more general conjecture I've come up with:

Let $\Sigma=\{a\}$ and $L=\{a^{f(n)}\in\Sigma^*:n\in\mathbb N_0\}$. My conjecture is:
$$L\text{ is regular}\Leftrightarrow \exists x,y\in\mathbb N_0:f(n)=x\cdot n+y$$

Has this question seen any scientific treatment before? Is it "obviously" true / false?

To me, obviously the "$\Leftarrow$" direction is true because one can just construct a DFA with $x+y$ states that cycles through the $x$ states after having read through $y$ states and accepts iff it is at state number $y$.


texts: Can we compute the number of machine of two kind of transducers (mealy and moore) with $n$ states, and lenght of input symbols $m$, and lenght of output symbols $p$.


texts: Estimate distribution of a composite variable

texts: Suppose I have N sets of numbers (10 numbers per set) {a1, ....., a10}. I form a sum by taking one number at random from each set. SUM = num from set 1 +......+ num from set N. If I do this a large number of times I will generate a large number of different values for the SUM variable. How can I estimate the distribution of the SUM values (P10, P50, P90 etc.)?


texts:
I know that it is decidable for an NPDA to accept a string $w$, i.e. a TM can receive as input the description of an NPDA along with a string and test if the NPDA accepts the string.

But are there languages where given an NPDA description as input, the TM may not halt, i.e. since the simulated NPDA also does not halt...


texts: Algorithm for smallest String without a given prefix

texts:
How can I find the lexicographicaly smallest string that doesn't start with a given prefix AND is lexicographicaly bigger than the given prefix? Example:

prefix : cat;
next string : cau
prefix : cazz
next string; cb


texts: How to compute the first n coefficients using number theoretic transform (NTT)?

texts: I need to find the first $n$ coefficients of $$\prod_{i = 1}^{i = q}(1 + x^{a_i})^{b_i}$$ modulo a NTT favourable prime. Can someone suggest an algorithm with worst-case complexity $O(n\log n)$ or $O(q\log q)$? I think this is to be done using NTT but cannot get an exact method. I tried Divide and Conquer but it is $O(qn\log n)$.


texts: Converting Chomsky Normal Forms to Greibach Normal Form

texts:
Here is a passage from Kozen's Automata and Computability (pages 145-146) that I'm confused about:

Now we show how to convert an arbitrary grammar to an equivalent one  (except possibly for $ \epsilon $) in Greibach normal form.
We start with a grammar $ G = (N, \sum, P, S) $ in Chomsky normal form.  This assumption is mainly for ease of presentation; we could easily modify the construction to apply more generally.  The construction as given here produces a Greibach grammar with at most two nonterminals on the right hand side (cf. [60, Exercise 4.16, p. 104]).
For $ \alpha, \beta \in (N \cup \sum)^* $, write $$ \alpha \longrightarrow^{L}_{G} \beta $$ if $\beta$ can be derived from $\alpha$ be a sequence of steps in which productions are applied only to the leftmost symbol in the sentential form (wwhich must therefore be a nonterminal).  For $ A \in N $ and $ a \in \sum $, define $$ R_{A, \alpha} = \{\beta \in N^* \mid A \longrightarrow^L_G \alpha\beta \} $$ For example in the CNF grammar (21.1)*, we would have $$ C \longrightarrow^L_G SB \longrightarrow^L_G SSB \longrightarrow^L_G SSSB \longrightarrow^L_G ACSSB \longrightarrow^L_G [CSSB, $$ so $CSSB \in R_{C, [}.$
The set $ R_{A, \alpha} $ is a regular set over the alphabet $N$, because the grammar with nonterminals $\{A' \mid A \in N \}$, terminals $N$, start symbol $S'$, and productions $$ \{A' \longrightarrow B'C \mid A \longrightarrow BC \in P \} \cup \{A' \longrightarrow \epsilon \mid A \longrightarrow a \in P \} $$ is a strongly left-linear grammar for it.  This may seem slightly bizarre, since the terminals of this grammar are the nonterminals $N$ of $G$, but a moment's thought will convince you that it makes perfect sense.
Since $R_{A, \alpha}$ is regular, by Homework 5, Exercise 1 it also has a strongly right linear grammar $G_{A, \alpha}$; that is, one in which all productions are of the form $X \longrightarrow BY$ or $X \longrightarrow \epsilon$, where $X,Y$ are nonterminals of $G_{A, \alpha}$ and $B \in N$.
*CFN grammar (21.1) is $$ S \longrightarrow AB \mid AC \mid SS, \; C \longrightarrow SB, \; A \longrightarrow [, \; B \longrightarrow ] $$

I am confused starting at the paragraph "The set $ R_{A, \alpha} $ is a regular set over the alphabet..." Breaking this down phrase by phrase:
1.)The set $ R_{A, \alpha} $ is a regular set over the alphabet $ N $
Okay, so $ R_{A, \alpha} $ is some subset of $N^*$ and can be expressed as the language of a regular expression.
2.)because the grammar with nonterminals $ \{ A' \longrightarrow \mid A \in N \} $, terminals $N$, start symbol $ S' $, and productions $ \{A' \longrightarrow B'C \mid A \longrightarrow BC \in P \} \cup \{A' \longrightarrow \epsilon \mid A \longrightarrow a \in P \} $ is a strongly left-linear grammar for it.
Okay, so consider a newly formed grammar whose nonterminals are just the nonterminals of the old grammar but with an apostrophe, whose terminals are the old nonterminals, whose start symbol is $ S^{'} $, and whose productions are [blah] is a "strongly left linear grammar for it".  I know what strongly left linear means and it's obvious that these productions are left linear.  But it's a little unclear to me what they mean by "grammar for it".  Do they mean that the language of this new grammar is equal to  $ R_{A, \alpha} $?  If so, why?


texts: Why do Tarjan's and Kosaraju's algorithms for finding strongly connected components have the same running-time complexity?

texts:
I followed an explanation of Kosaraju's and Tarjan's strongly-connected components algorithms, and they say that both have O(|V|+|E|) time complexity.

That didn't make sense to me since Kosaraju uses two DFS passes and computes the transposed graph, but Tarjan's use only one DFS.


texts: The language $\{ww \mid w \in \{0,1\}^{*} \}$ is not a CFL

texts:
We have proved that the language $ L = \{\omega\omega \mid \omega \in \{0,1\}^{*} \} $ is not a CFL, and we did so by using pumping lemma. And the proof is clear to me. But I thought of the following CFG:

$ G = (\{S, S_{1} \},\{0,1\},R,S)  $ where R has the following rules:

$$\begin{align*} S &\rightarrow S_{1}S_{1} \mid \epsilon \\
S_{1} &\rightarrow 0S_{1} \mid 1S_{1} \mid \epsilon \end{align*}$$

It feels like that this CFG's language should be the language $L$ that I have defined above since each substitution adds the same letter on both sides. But it can't be since we can use pumping lemma on the word $0^{l}1^{l}0^{l}1^{l}$ (where $l$ is the pumping length). So either I'm not doing the substitution incorrectly, or the CFG's language contains $L$ and has more words that I'm not seeing currently...

Can someone help me out and point out where my mistake is?


texts: Understanding arguments in Haskell type classes and instances

texts:
I am trying to understand a Haskell class declaration and instance from a paper. I am trying to understand the class declaration:

class (Surfaces v o, Paths a b (v o)) => Vehicles v o a b

My current understanding is that the first occurance of types "v o" in the Vehicles context seems to refer to two distinct data types. I assume that it is the same for the "v o" on the right of =>.

Question 1

Is my understanding correct?  Does the bracketed "(v o)" in the Vehicles context refer a type constructor and its argument, rather than two independent types?

Question 2:

Is the instance OK? Why do I need FlexibleInstances

 instance Vehicles Boat Person Route (Water Source)

I apologize for the level of detail, but I believe that the context is important to my question.
Regards,
Pat

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}
data Person = Person deriving Show
data House a = House a  deriving Show
data Boat a  = Boat a deriving Show
data Route a b = Route a b deriving Show
data Source = Source deriving Show
data Destination = Destination deriving Show
data Water a = Water a deriving Show
data Land = Land deriving Show

-- The three top level classes are constructor classes, indicated by the signatures of the methods (not the class header).
-- The kinds in the class headers have kinds * and *->*
-- "Containers a b" stands for all container types "a" holding things of type "b".
class Containers a b where
 insert :: b -> a b -> a b
 remove :: b -> a b -> a b
 whatsIn :: a b -> [b]

-- Type "a" is the type of  surface
-- Type "b" is the type object on the surface e.g. boat is on water.
class Surfaces a b where
 put :: b -> a b -> a b
 takeOff :: b -> a b -> a b
 whatsOn :: a b -> [b]

-- The path class represents motion
-- Type "c" represents the moving object e.g Boat.
-- Type "a" route
-- Type "b" origin and destination place
class Paths a b c where
 move :: c -> a b c -> a b c
 origin, destination :: a b c -> b
 whereIs :: a b c -> c -> b

class People p
class HeavyLoads l
class Surfaces w o => WaterBodies w o
class Containers h o => Houses h o

-- The types "v o" in the Vehicles the context seems to refer to two distinct data types.
-- I assume that it is the same for the "v o" on the right of =>
-- But "(v o)" in the Vehicles the context seems to refer a type constructor and its argument??.
-- Vehicles are derived from surfaces (affording to ride on the vehicle) and paths (affording motion).
-- Vehicles type class has  parameters for
--  the type "o" of the transported object
--  the type "a" of the path,
--  the type "b" of the origin and destination places.
--  "o" has kind *, "a" has kind *->*->*,  "v" has kind *->*
class (Surfaces v o, Paths a b (v o)) => Vehicles v o a b

instance Surfaces Boat Person
instance WaterBodies Boat Person  -- Boats carrying people on water
instance Paths Route (Water Source) (Boat Person) -- boat moving on water carrying people
instance Vehicles Boat Person Route (Water Source)  -- Boat as a vehicle


texts: Regular languages closed under prefix operation

texts:
Suppose that $D$ is a regular language over an alphabet $A$. How can I prove that the following language is also regular?
$$ \mathrm{LANGUAGE}_2(D) := \{ d \mid d,t \in A^* \text{ and } dt \in D \} $$
(This problem is taken from Introduction to the Theory of Computation by Mike Sipser.)


texts: LogSpace reductions vs. PTime reductons for defining PSpace-completeness

texts:
Continuing Is every PSPACE-complete problem complete with respect to logspace reductions? : earlier, PSPACE-completeness was defined via logspace reductions (e.g., cf. http://www.cs.cornell.edu/~kozen/Papers/LowerBounds.pdf), whereas it is defined via ptime reductions nowadays (e.g., cf. https://en.wikipedia.org/wiki/PSPACE).

Why has it changed? Is it just because the folks after Dexter Kozen got too lazy even to say that one can go the extra mile to show that their reductions are actually logspace, let alone actually going that extra mile? Or is there a deeper, technical reason?

Crosspost: http://cstheory.stackexchange.com/questions/45709/logspace-reductions-vs-ptime-reductons-for-defining-pspace-completeness


texts: From in-order representation to binary tree

texts:
Is there a way to reconstruct a binary tree just from its in-order representation?

I've searched the internet, but I could only find solutions for reconstructing a binary tree from inorder and preorder representations, but none for only inorder.


texts: Gap between numbers in fixed-point vs. floating point arithmetic

texts:
If $r$ is a machine-representable number and $f(r)$ is the next larger machine representable number, are the following true or false?

In fixed-point arithmetic, the distance between $r$ and $f(r)$ is constant.
In floating-point arithmetic, the relative distance $|(f(r)-r)/r|$ is constant.

I believe that (1) is true, but I'm not sure about (2).  I am new to the world of numerical analysis and I'm just trying to hang on for dear life.  Could anybody point me to a resource that does a good job of explaining the basic introductory topics of machine mathematics?


texts:
I have a certain function that calculates numerically, for every $x \in [0,10]$, a value $y\geq 0$. I want to find an approximate minimum point of that function. A possible solution is to calculate $y$ for e.g. 10000 values of $x$ in the range $[0,3]$ and return the $x$ for which $y$ is smallest. I am looking for fastest solutions.

I know that the general shape of the function is like the following plot:

I.e, it is like a function with a single minimum point, but with some added random noise of bounded size. Without the noise, I could easily find the minimum point using gradient methods, but with noise gradients seem  useless. What other search algorithm can I use here?

NOTE: Naturally the approximation quality can depend on the noise size, for example, in the above plot, any answer between $\approx 0.3$ and $\approx 0.7$ would be considered good enough.


texts: Vandermonde matrix and its binary representation

texts:
Say one is given a Vandermonde matrix (https://en.wikipedia.org/wiki/Vandermonde_matrix) of dimension $2^q \times k$ such that the elements of the first column of it are $\{0,1,2,..,-1+2^q\}$. (This then uniquely specifies the matrix). Now say one enlarges this to a matrix of dimension $2^q \times (1+q(k-1))$ over $\{0,1\}$ by replacing all the entries (except the first column) by its bit-string in binary representation.

Are there known relationships between the two matrices?
Any easy way to relate them?
Like I believe it remains true that every subset of $k$ rows of the new matrix are also linearly independent (over $\mathbb{F}_2$?). How does one see this?

EDIT : In the original matrix itself assume that all arithmetic are being done "mod $2^q$" so that all entries in the Vandermonde matrix are elements of $\mathbb{F}_{2^q}$ and hence everyone has a $q-$bit representation.


texts:
I'm trying to design an algorithm which will accept two natural numbers: a and b.
Its purpose is to get b from a by making the following operations: *3 and /2.
For example, if a = 10 and b = 7, then:

10/2*3/2 = 7

I decided to use branch and bound, since I believe there's no better suitable algorithm for this.

My program works, but I'm having really trouble finding a heuristic.

What could it be?

Thank you.


texts: How to cover holes with disks of a fixed radius?

texts:
So you have a sheet / area of a given dimension, and within this area are holes (their center point(x,y) and radius are given). The problem is you need to cover these holes with patches. These circular patches have a fixed radius (ie: radius of 5) and are not allowed to overlap with each other (but can touch). You're allowed to use as many as you like, the goal is not to find the most optimal number, but to see if it's possible to cover every single hole.

I've solved a similar problem with a KD tree, but due to the 3D dimensional nature of the holes in this problem, I'm unsure on how to approach it. Just looking for a pointer in the right direction, not the coded solution :)


texts:
I have spent a lot of time understanding these two issues. If you can help me, please.

Prove that the restriction of SAT to CNF formulas in which each variable xi appears at most twice is solvable in polynomial time.
Prove that the restriction of SAT to CNF formulas in which each variable xi appears
at most three times is NP-complete by showing $SAT \leqslant_p SAT_3 $
(hint: find a way to
create “clones” of each variable with different names.)

Thanks.


texts: Has this model of random directed graphs been studied?

texts:
Youtube recently added a feature called autoplay, where each clip is assigned a (presumably related) clip that follows it. This, in effect, defines a directed graph on the set of youtube clips, where each vertex has outdegree 1. The user starts at a vertex of his choice and takes a walk along this graph.

This got me thinking. Since the graph is finite, the user will eventually get stuck in a loop. Each loop acts as a sink, and each vertex will eventually lead the user to some sink. This raises some questions - how many sinks are there? How many steps does it take before the user reaches the loop? What is the distribution of the sink sizes? And so on.

Here is a random graph model that can be used to model this process: For each vertex $v$ we choose a single neighbor $w$ uniformly at random and add the edge $(v,w)$ to the graph. It might be interesting to investigate the properties of this model and to see if they can teach us anything about the Youtube network. Have people looked at this type of thing before?


texts: Efficient Data Structure for Closest Euclidean Distance

texts:
The question is inspired by the following UVa problem: https://onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&category=18&page=show_problem&problem=1628.

  A network of autonomous, battery-powered, data acquisition stations has been installed to monitor the climate in the region of Amazon. An order-dispatch station can initiate transmission of instructions to the control stations so that they change their current parameters. To avoid overloading the battery, each station (including the order-dispatch station) can only transmit to two other stations. The destinataries of a station are the two closest stations. In case of draw, the first criterion is to chose the westernmost (leftmost on the map), and the second criterion is to chose the southernmost (lowest on the map).
  You are commissioned by Amazon State Government to write a program that decides if, given the localization of each station, messages can reach all stations.

The naive algorithm of course would build a graph with stations as vertices and calculate the edges from a given vertex by searching through all other vertices for the closest two. Then, we could simply run DFS/BFS. Of course, this takes $O(V^2)$ time to construct the graph (which does pass the test cases). My question, though, is if we can build the graph any faster with an appropriate data structure. Specifically, given an arbitrary query point $p$ and a given set of points $S$, can we organize the points in $S$ in such a way that we can quickly find the two closest points in $S$ to $p$ (say, in $\log V$ time?).


texts: Prove by Pumping Lemma that Language $L=\{a^ib^kc^k : i\geq k\geq 1\}$ isn't Context-Free

texts:
I'm new to this forum. I have some difficulties on using Pumping Lemma to prove non-CF language.

Let $L=\{a^ib^kc^k : i\geq k\geq 1\}$ and the followings are my attempt.

Proof. Suppose by contradiction that $L$ is a context-free language. Let $p$ be the constant given by the P.L. We choose a string $s=a^pb^pc^p$. Assume $s\in L$ and it satisfies properties of a context-free language.
i.e. $s$ can be written as $s=uvwxy$ where $|v|\neq\varepsilon$ and $|x|\neq\varepsilon$. Further $|vwx|\leq q$ and $uv^iwx^iy\in L,\  \forall i\geq 0$.

If $v$ contains at most one symbol and $x$ contains at most one symbol (e.g. $v=a$, $w=b$, $x=c$.) Consider $s=uv^0wx^0=b\notin L$. And we reached contradiction.
If $v$ contains more than one symbol or $x$ contains more than one symbol (e.g. $v=ab$, $w=\varepsilon$, $x=ca$.) Consider $s=uv^2wx^2=ababcaca\notin L$. And contradiction reached.

Therefore, the language $L$ is not context-free. Q.E.D.

I'm sure I could have missed important cases, and my confusion raises here as what is a general approach to find all cases that could be contradictions. Thanks.


texts: Worst case analysis of bucket sort using insertion sort for the buckets

texts:
Suppose I am using the Bucket-Sort algorithm, and on each bucket/list I sort with insertion sort (replace nextSort with insertion sort in the wikipedia pseudocode).

In the worst case, this would imply that we would have $O(n^2)$ performance, because if every element was in one bucket, then we would have to use insertion sort on $n$ elements which is $O(n^2)$.

So the first thing that comes to mind to fix the worst case running time is to not use insertion-sort, because it is $O(n^2)$. Instead we could use merge-sort or heap-sort m, because the worst case running time for both of those algorithms is $O(n\log n)$. However, if we use merge-sort and heap-sort, do they preserve the expected linear running-time of bucket-sort?


texts: Who was the first to define Flow Shop / Job Shop problem?

texts:
I spent some time to search in internet who was the first to formaly define Flow Shop and Job Shop problems but with no effect. I'm especially interested in article/book so I can mention it in my master thesis.

I'm guessing that there may be no author of this problems but this information also would help me a lot.


texts: Can any constant-time operation be applied N times in O(log(N)) time?

texts:
Suppose f is a constant-time function. Is it always possible to apply it n times in O(log(n)) time?

Example

If f is not, then, apply_not_n_times(n,bool) = if n % 2 == 0 then bool else !bool, which is O(log(n)), since it is linear in the number of bits. That means the answer is yes for that particular choice of f. I wonder if it can be proven that, for any choice of f, there is always a O(log(n)) implementation of apply_f_n_times(n,x).


texts: Fast ways to compute the smallest prime with a given substring?

texts:
So, I've got this problem:

  Given a string $\omega\in\{0,\ldots,9\}^*$, find the smallest prime number (in base 10) that contains that string, or otherwise returns 0.

What I'm asking is a fast algorithm for the problem?


texts: Design a Turing Machine Checking if Apples and Bananas are Even

texts:
I am having trouble with a past exam paper. I have to design a Turing Machine to do the following, but I don't really know where to start with this question. Any help would be very much appreciated.

Design a Turing Machine TM checking if the numbers of sold apples and bananas are even. Formally, given a string w over the alphabet {a,b}, TM should terminate with the following result string.

ab if the number of apples and bananas are even
a if the number of apples is even but bananas are odd
b if the number of apples is odd and bananas are even
ϵ if the number of apples and bananas are both odd

Thanks


texts: What are some of the practical applications of CSP process algebra?

texts:
CSP is used for the description and representation of concurrent systems, how it is used in practice (theoretically and programmatically)?

What are the application areas (other than concurrent and parallel systems) where it is used?


texts: Perceptrons: Functions not learnable without bias

texts:
I am trying to determine which functions are not learnable without a bias when building a perceptron. The set of functions I need to evaluate is {NOT, OR, AND}.

Could someone help interpret these results?

AND FUNCTION

https://imgur.com/a/OTFUT

OR FUNCTION

I get a divide by 0 error in my script.

NOT FUNCTION

https://imgur.com/a/wZnxT

It would appear that the AND function does not crash like the OR function but the end result is incorrect. The OR function simply won't graph due to a divide by 0 error. The NOT function appears to still be learnable.

If desired, I can post my python script with how I generated these graphs. I am using a sigmoid activate function.


texts: Linear programming maximizes the minimum distance problem

texts:
I have a problem with creating an equation for linear programming solver.

Company wants to open stores in k cities. For the purpose of even coverage of the entire area, these cities should be selected from the available n candidates in such a way that it maximizes the minimum distance between any pair of selected cities.

I don't know how to define maximizes the minimum problem in graph in linear equation.
Can any one give me some hints?

Thank you very much.


texts:
I believe that the following NPDA accepts the language
$$\{w : w \in \{a,b\}^*,n_a(w)= n_b(w)+1 \}\,,$$
where $n_a(w)$ represents number of symbol $a$'s in string $w$.

Is there a two-state NPDA that accepts the same language?


texts: Count pairs of nodes in a tree that are connected by a path whose labels have gcd 1

texts:
Given an un-rooted tree with N nodes, numbered from 1 to N. Each edge of the tree has a positive integer, associated with it. We need to calculate the number of unordered pairs (S, T) of tree's nodes such that the greatest common divisor of all the integers associated with the edges of the path between S and T is equal to one. Of course, we consider only the pairs where S isn't equal to T.

But main problem is N (Number of nodes in tree is 100000) So is their any better solution than O(N^2) as I currently have O(N^2) approach to do this problem using LCA between 2 nodes of tree.

So given a tree with N nodes and N-1 edges can we have a better algorithm ?


texts: Traveling Salesman with Held and Karp Algorithm

texts:
I am well aware of the DP solution to the traveling salesman problem; also known as the Held and Karp algorithm for TSP.

I have implemented it with bitmask, and it's something like this:

int TSP(int pos, int bitmask) {
    if (bitmask == (1<<(K+1))-1)
        return dist[pos][0];              // Completing the round trip

    if (memo[pos][bitmask] != -1)
        return memo[pos][bitmask];

    int answer = INF;
    for (int i = 0; i <= K; i++) {
        if (i != pos && (bitmask & (1 << i)) == 0)
               answer = Math.min(answer, dist[pos][i] + TSP(i, bitmask | (1 << i)));
    }

    return memo[pos][bitmask] = answer;     // Storing the best dist for the set of traveled cities and untraveled ones.

This algorithm is quite fast; computation of 15 cities is relatively fast enough. However, I notice that it could be further improved to accommodate around 20 cities.

1) If the dist matrix is symmetrical, perhaps we can make use of this property to prevent repeated calculations. (e.g a->b->c->d->a == a->d->c->b->a)

2) Using both a upper and lower bound to prune. The above algorithm is able to get its first possible optimal solution in a very short time, might be able to use that.

I have tried to improve the algorithm based on the aforementioned two principles. However, I don't get a better algorithm.

Am I making a futile attempt at improving something impossible? What do you think?


texts: Unbanked access, banked access and common memory access

texts:
What are they and what are their differences?

Unbanked access
Banked access
Common memory access

[EDIT]
This question is originated from my reading of MPLAB XC8 PIC Assembler User's Guide where the latest XC8 compiler requires a preprocessor directive to contain or wrap assembly codes in sections called PSECT. I have a basic understanding of memory management where instructions are stored in program memory (ROM), variables are stored in data memory (RAM) and temporary instructional data are stored in the stack etc. My understanding of memory banking is to divide the RAM into pair just so to enable writing or reading two bytes from two different memory location simultaneously in one cycle, but I'm not sure if this mechanism is device dependent or is that a general concept in computer science. And the term of unbanked, banked and common access is rather confusing - is that a grouping mechanism of memory or different ways of accessing memory? Hence my question.


texts:
Select where the source operands are located for the following two LC-3 instructions:
0001 111 010 0 00 011
1010 010 110011110
For source operands located in memory, distinguish the addressing mode used to access that memory.

I think the correct answers are fourth and fifth respectively because for the ADD instruction it's apparent that the source operands are directly from a register. Also, the LDI instruction, the second one given, has the source operands from memory using indirect addressing mode. Am I correct in understanding this?


texts: Is the language given by a context-free grammar always context-free?

texts:
Consider the language generated by the following grammar:

$S \to aSBb \mid \epsilon$

$B \to aB \mid bB \mid \epsilon$

Is the above language context-free?

The above language looks like $\{ w \in (a+b)^* : a^n w_1b w_2b ... w_nb \}$.

I tried using the pumping lemma to show that this language is not context-free, but I was unable to do so.


texts: Sizing a Cuckoo filter for a subset of elements

texts:
Question

I am considering the use of Cuckoo filter for a business case. To simplify the explanation here is an analogy of my needs:

There are over $n = 30 000$ first names that exists in the whole world
I have a Cuckoo filter storing the names of people who gave me a gift at least once
I am certain that the Cuckoo filter will not have to store more than 600 names
The names the Cuckoo filter will store are evenly distributed across the 30 000 names
Of course the final goal is to be able to know which names gave me a gift at least once, I might have to query for any of the 30 000 names.

I would like to design my filter for 600 elements; however the original paper about Cuckoo filters considers that the number of buckets $m$ is a multiple of $n$.

  Now consider a construction process that inserts $n$ random items to an empty table of $m=cn$ buckets for a constant $c$

Am I supposed to size the filter according to set of all names in the world ? Is there something I am missing ? This is not addressed in the original publication.

Constraints

Size : The Cuckoo filter will be transmitted over the network. But it will be done in an asynchronous way (let's say an update every 2 hours). So this will weigh in the size constraint.

Time : The real constraint is time. When I query the filter I would like my response in less than 5 seconds.

False positive : I also hope to have false positive rate of at most 20%.

Security : In my example I store names, but in reality I will store sensitive data that should be protected and anonymized under GDPR. After a statistical analysis I concluded that the data's entropy is too low to store as a list of hashes.

Other options : I'm open minded by nature. I always welcome other options.

Attempt at a self answer

Considering that the fingerprint is $f$ bits long, and I have $m$ buckets, the probability that the name Bob has the same features (index and fingerprint) as the name Alice is :

$$
\frac{1}{2^f} \cdot \frac{1}{m}
$$

Which means that the probability that there is another name colliding with the name  Anna is:

$$
(n - 1) \cdot \frac{1}{2^f} \cdot \frac{1}{m}
$$

With 30 000 names, a fingerprint of 8 bits and 600 buckets, the result is $0.39$ which means a false positive rate of 39 %.

To reduce the false positive rate I can either increase the fingerprint size or the number of buckets. Using 6000 buckets instead of 600 gives me a false positive rate of 3.9%. This hack might be working in my example case but in reality we are talking of $10^{19}$ names in the whole world and $10000$ names to store in the filter.

It seems to me that Cuckoo filter were not designed with this use case in mind, and when people are using Cuckoo filter, they hope to store almost every existing item in there at some point.


texts: Normal order sequencing combinator - why does it work?

texts:
Notes on lambda calculus (part 2.7) and book Programming Distributed Computing Systems: A Foundational Approach by Varela present the sequencing combinator for normal order reduction:

$$\mathit{Seq} = \lambda x. \lambda y. ((\lambda z.y) \: x)$$

In the following example

$$((\mathit{Seq} \; (\text{display "hello"})) \; (\text{display "world"}))$$

it should guarantee that $(\text{display "hello"})$ is evaluated before $(\text{display "world"})$. But I don't understand why is $(\text{display "hello"})$ evaluated at all — why it isn't simply thrown away when evaluating

$$(\lambda z. (\text{display "world"})) \; (\text{display "hello"})$$

My reasoning: $z$ doesn't have free occurence in $(\text{display "world"})$ so substituting $(\text{display "hello"})$ for $z$ in $(\text{display "world"})$ results simply in $(\text{display "world"})$.

My question is related to Normal order sequencing vs applicative order sequencing.


texts:
I'm having difficulties understanding the solution to the following question:

  Consider the following description of a LAN:

  The main Internet connection is connected to our gateway router. This
  in turn is part of the backbone network on the 65.21.1.0/24 subnet.
  The backbone also supports two further routers SALES and RESEARCH.
  There is one Sales subnetwork 65.21.6.0/23, and two research
  subnetworks 65.21.100.0/24 and 65.21.200.0/26.

If the Interface addresses are:

• i1–65.21.1.1
• i2–65.21.1.2
• i3–65.21.6.1
• i4–65.21.1.3
• i5–65.21.100.1
• i6–65.21.200.1

  What are the routing tables for the SALES and RESEARCH routers?

How is the via and interface column derived in the solution?

Thanks in advance.


texts: Are there problems with complexity between $O(n^c/\log^b n)$ and $O(n^{c - \varepsilon})$?

texts:
I am having an extremely tough time with this homework question, wondering if anyone could help me (for all you theory aficionados, this one's for you).

There is a language $L$ with the following property: There is a Turing machine that decides $L$ in time $O(n^{2013}/\log^{2012} n)$, but there is no Turing machine that decides $L$ in time $O(n^{2012.9})$. Is this statement TRUE or FALSE?

My notion/idea is to use this Corollary that stems from the Time Hierarchy Theorem: For any two real numbers $1 \le e_1 < e_2$, we have $\mathrm{TIME}(n^{e_1}) \subsetneq \mathrm{TIME}(n^{e_2})$. I think I am on the right track but I need some help with this proof.


texts:
Sorry, I'm really new to neural networks and this question is probably pretty obvious. If you have any resource that can help clarify these concepts to me it would be much appreciated.

The way I understand neural networks is that each input node, x i  goes to each hidden layer. Is there a unique weight for each input that goes into each hidden node?

with xi being inputs, h being hidden layers, and O being the output. Would the weight from x1 to h1 be different from the weight from x1 to h2? If I'm not on the right track, please correct me!


texts: An online algorithm to maintain the Pareto frontier elements

texts:
I'm looking for an online algorithm/datastructure that is able to maintain a pareto frontier for two dimensional elements in an online scenario where elements can be added and deleted.

For example:

insert((3,7))

since the pareto front is empty it has to be added to it
set of elements E={(3,7)}
pareto frontier P={(3,7)}

insert((7,3)) and insert((10,2))

both have to be added to pareto frontier (since they arent dominated)
set of elements E={(3,7), (7,3), (10,2)}
pareto frontier P={(3,7), (7,3), (10,2)}

insert((8,4))

is dominated by (7,3) so do not add it to the pareto frontier (but keep it in the set of elements E because its maybe going to be part of the pareto frontier later)
set of elements E={(3,7), (7,3), (10,2), (8,4)}
pareto frontier P={(3,7), (7,3), (10,2)}

remove((7,3))

remove (7,3) from the set of elements and from the pareto frontier. The pareto frontier has to adjust accordingly and therefore (8,4) is added to the pareto frontier now.
set of elements E={(3,7), (10,2), (8,4)}
pareto frontier P={(3,7), (10,2), (8,4)}

This question is similiar to An online algorithm to find the Pareto frontier elements, but in the scenario described above points can also be removed. A brute force algorithm would have quadratic time complexity and I am looking for something better.


texts: Expressing an arbitrary permutation as a sequence of (insert, move, delete) operations

texts:
Suppose I have two strings. Call them $A$ and $B$. Neither string has any repeated characters.

How can I find the shortest sequence of insert, move, and delete operation that turns $A$ into $B$, where:

insert(char, offset) inserts char at the given offset in the string
move(from_offset, to_offset) moves the character currently at offset from_offset to a new position so that it has offset to_offset
delete(offset) deletes the character at offset

Example application: You do a database query and show the results on your website. Later, you rerun the database query and discover that the results have changed. You want to change what is on the page to match what is currently in the database using the minimum number of DOM operations. There are two reasons why you'd want the shortest sequence of operations. First, efficiency. When only a few records change, you want to make sure that you do $\mathcal{O}(1)$ rather than $\mathcal{O}(n)$ DOM operations, since they are expensive. Second, correctness. If an item moved from one position to another, you want to move the associated DOM nodes in a single operation, without destroying and recreating them. Otherwise you will lose focus state, the content of <input> elements, and so forth.


texts:
I am trying to understand why the formula

$$ \frac{\log(1+x)}{(1+x)-1} \times x,$$

which simply reduces down to $\log(1+x)$, is considered as more stable to compute than $\log(1+x)$.  In my head it doesn't make sense to me as my brain automatically simplifies it to $\log(1+x)$, which I am guessing a computer doesn't do, but then why does adding in "extra" calculations make it more stable for the computer?  My intuition would have been the opposite, the more calculations performed, the more error is introduced.  Why is this not the case here?


texts: How was multiprogramming brought into computer languages

texts:
I am going through the book operating system principles by Hansen . Hansen begins the third chapter on concurrent programming by discussing interleaving of the machine instructions of processes being run at the same time .

Then it begins with providing the language notation for multiprogramming  and writes the following program whose purpose is to copy  records from one sequence to another .

procedure copy (var f, g: sequence of T);
var s, t: T;
     completed: boolean;
begin
    if not empty(f)
    then
        begin
            completed:= false;
            get(s, f);
            repeat
                 t:= s;
                 cobegin
                       put(t, g);
                       if empty(f)
                       then
                            completed:= true
                       else
                            get(s, f);
                 coend
            until completed;
        end
 end

(If possible please tell me the name of the language ,was it Algol60 ?Anyways let's call it X )

All fine till here , a keyword or statement was introduced into the language X , which would perform multiprogramming. But I would like to know how was the language changed so as to incorporate this new keyword or function for multiprogramming . What changes were done to language X,owing to which X which was capable of supporting one execution at a time could now support more than one at a time ?

P.S : Hansen described about a single -user operating system called "Solo ".There he somehow means Pascal supports development of concurrent programs. The answer to the question in this post can be approximated by an answer to "what were the differences between languages which supported concurrent programs and those who didn't "?

I could have written "what are the differences" in the auxiliary question but I wanted to know how languages started having constructs for concurrent programming ,that's why I wrote "What were the differences".


texts: Lower bound $\Omega$ grows quicker than upper bound $O$ of a recurrence relation $T(n)$?

texts:
In my analysis of algorithms class we were given the following recurrence relation:
\begin{eqnarray}
T(n) &=&
\begin{cases}
    T\left(\displaystyle\frac{n}{2}\right) + 1, &n \ \mbox{is even number}& \\
    2T\left(\displaystyle\frac{n-1}{2}\right),　&n \ \mbox{is odd number}&
\end{cases} \nonumber \\
T(1) &=& 1
\end{eqnarray}
I have proved by iteration (expand) that when $n = 2^k$ (always the even case), $T(n) = O(\log{n})$; when $n = 2^{k+1}-1$ (always the odd case), $T(n) = \Omega(n)$.
Is this actually possible? After looking at some other posts, I am thinking this is possibly because the $\Omega(n)$ obtained here is the lower bound runtime of the worst case scenario, and the $O(\log{n})$ is the upper bound runtime of the best case?
Am I confusing something? Or is there any other conclusion can be drawn from the result that $T(n) = O(\log{n})$ and $T(n) = \Omega(n)$ for the recurrence?


texts: Is there a way to find a simple regular expression for this language?

texts:
Let $\Sigma$ be 0,1,2. I am interested in the language of all strings $w$ such that the sum of $w$ characters (where the char 0 is treated as the number 0, the char 1 as the number 1 etc) is divideable by 5. Obviously this is a regular language, and I can also find a simple linear grammer.

My idea for a regular expression was to check all the combinations where I can receive sum zero (in modulo 5) with the digits 1 and 2 and put 0* in between. But is there no better way? Something more elegant?

Edit:
My expression is $0^* 1 0^* 1 0^* 1 0^* 1 0^* 1 0^* \cup 0^* 1 0^* 1 0^* 1 0^* 2 0^* \cup 0^* 1 0^* 1 0^* 2 0^* 1 0^* \cup 0^* 1 0^* 2 0^* 1 0^* 1 0^* \cup \ldots $ and so it goes on for all the possible combination. My question is if there is a way to simplify this - Or maybe a different approach?


texts: Is the last step in the Christofides' algorithm necessary

texts:
I am using Christofides' algorithm to calculate the best route from one location to another given multiple nodes on a map that the route must pass through.
The last step in the algorithm requires the route to connect back to the first node, right?
Is this step necessary? If no, why?
Edit:
I essentially want the data that can achieve the following:
Each red node must be visited once before the green node, and the illustration assumes the start of the route is directly on top of a red node but it could be anywhere (assuming these are directions).


texts: Show Recognizing two Regular Expressions as equal is in PSPACE

texts:
If I have $EQ_{REX} = \{\langle R,S \rangle|\text{ $R$ and $S$ are equivalent regular expressions}\}$, how do I show that $EQ_{REX}\in PSPACE$ ?

What I know so far is that there are decidable algorithms for transforming a regular expression into a NFA and then into a DFA, but these algorithms can take a long time and produce a DFA that takes up exponential space. I also know that $EQ_{DFA}$ is decidable.

So $EQ_{REX}$ is provably decidable because you can turn R and S into DFAs and then show that the DFAs are equivalent. But I'm not sure how to analyze the complexity of a machine like this, and something tells me that it is not in NP.

Is there a way to show that this particular machine is in PSPACE (or NPSPACE, because they are equivalent)? How would I analyze its complexity? Or am I taking the wrong approach entirely, and should instead try to show that this problem is reducible to some other PSPACE-complete problem?


texts: Regular expression for all words not containing 222

texts: I need to find a regular expression for the language of all words over $\{0,1,2,3\}$ which do not contain $222$ as a substring.


texts: Polynomial-time reduction of Primality and 3-SAT

texts:
Is 3-SAT $\leq_{p}$ Primality? And/or is Primality $\leq_{p}$ 3-SAT? I think the answer is no and yes, respectively, but I'm not sure. Any help would be appreciated.

Thank you.


texts:
I am having some issues proving a problem I am working on. I have been sketching out examples but the proof is not jumping out at me.

Question:
Let $G = (V,E)$ be an undirected $r$-regular graph (that is each vertex has a degree of $r$) for some $0 < r < n$, where $|V| = n > 1$. Prove that either $G$ or its complement $G^*$ has a hamiltonian path.

Now the reason it's asking for $G$ or $G^*$ is because if it's not a connected undirected graph then taking the complement will make it connected.

So lets assume that it's a connected $r$-regular graph. We start at a vertex $v$. From this vertex we can visit up to $r$ adjacent vertices. So we visit one of them, say $u$, and from there we have $r-1$ vertices to choose from because we do not want to go back to vertex $v$.

Now I am trying to formulate a proof by going from vertex to vertex until all vertices are visited exactly once (hamiltonian path). But I do not see how to formulate the proof. Somehow each new vertex I visit will always have an uninformed neighbour until I reach the final vertex on the path.

Am I on the right track?


texts: Capacity of binary not symmetrical channel

texts:
I have to solve this exercise in information theory:

A binary not symmetrical channel has probability of transition from 0 to 1 $P(output=1|input=0)=p$ and probability of transition from 1 to 0 $P(output=0|input=1)=q$.
I have to calculate the channel capacity and the input distribution that leads to this capacity value.

I thought that the channel was the following:

So:
$$P(Y|X)=\begin{pmatrix}
1-p & p\\
q & 1-q
\end{pmatrix}$$

Then I tried to calculate the capacity:

$$C=\max_{p(x)}I(X;Y)$$

where

$$I(X;Y)=H(Y)-H(Y|X)$$

where

$$H(Y)=-(1-p+q)\log (1-p+q) - (p+1-q) \log (p+1-q) = ?$$

I don't think is correct. How do I calculate $H(Y)$ and $H(Y|X)$?

I tried to solve the exercise in this way.

$$\pi = Pr(X=0), 1 - \pi = Pr(X=1)$$

$$H(Y)=H(\pi(1-p)+(1-\pi)q, \pi + p(1-\pi)(1-q))$$

If I call:
$$\pi(1-p)+(1-\pi)q = a$$
$$\pi + p(1-\pi)(1-q) = b$$
then
$$H(Y)=H(\pi(1-p)+(1-\pi)q, \pi + p(1-\pi)(1-q)) = -a \log a - b \log b$$

Now I have to calculate:
$$H(Y|X)=Pr(X=0)H(Y|X=0)+Pr(X=1)H(Y|X=1) = \pi H(Y|X=0)+ (1- \pi)H(Y|X=1)$$
where

$$H(Y|X=0) = -P(Y=0|X=0) \log P(Y=0|X=0) - P(Y=1|X=0) \log P(Y=1|X=0) = -(1-p) \log (1-p) - p \log p$$
$$H(Y|X=1) = -P(Y=0|X=1) \log P(Y=0|X=1) - P(Y=1|X=1) \log P(Y=1|X=1) = - q \log q-(1-q) \log (1-q) $$

So:
$$H(Y|X)=Pr(X=0)H(Y|X=0)+Pr(X=1)H(Y|X=1) = \pi [-(1-p) \log (1-p) - p \log p]+ (1- \pi)[- q \log q-(1-q) \log (1-q)]$$
and if I call:
$$[-(1-p) \log (1-p) - p \log p]=c$$
$$[- q \log q-(1-q) \log (1-q)]=d$$
then
$$I(X;Y)=H(Y) - H(Y|X)=-a \log a - b \log b + \pi c + (1-\pi)d$$

it's right? Thanks


texts: What do assemblers translate macros into during assembling?

texts:
I have dug in simple binaries, such as though like x86 bootloaders, sega video game binaries, etc. I know that these files tend to use assembler macros to define data, etc.
What I am having trouble figuring out is what assemblers tend to translate macros into exactly (are they instructions, custom formatted data entries used statically, addressing mode/special opcodes, etc.).

I do not know if this is the wrong place to ask. If so,  I am saving time by double-posting on reverse engineering 's SE.


texts: Solve a recurrence using the master theorem

texts:
This is the recursive formula for which I'm trying to find an asymptotic closed form by the master theorem:
$$T(n)=9T(n/27)+(n \cdot \lg(n))^{1/2}$$

I started with $a=9,b=27$ and $f(n)=(n\cdot \lg n)^{1/2}$  for using the master theorem by $n^{\log_b(a)}$, and if so $n^{\log_{27}(9)}=n^{2/3}$ but I don't understand how to play with the $(n\cdot \lg n)^{1/2}$.

I think that the $(n\cdot \lg n)^{1/2}$ is bigger than $n^{2/3}$ but I'm sure I skip here on something.

I think it fits to the third case of the master theorem.


texts:
I need some help with the following question:

One of the languages

$$L_1 = \{a^pb^{q+r}c^sd^{q+t}e^{p+r} \mid p, q, r, s \ge 0\ , s > t\}$$
$$L_2 = \{a^{p+q}b^rc^sd^{q+r}e^s \mid p, q, r, s \ge 0\}$$

is context-free and the other is not. Build a context-free grammar for the one that is. For the other one provide a proof that it is not regular, or that it is not context-free.

How do I approach this problem ? I think that L2 is context-free because no comparisions are made. L1 is not context-free.

Thanks in advance


texts: Linear time algorithms on regular graphs

texts:
For each constant $k$, the number of $k$-regular graphs is of the order of $n^{\Omega(n)}$. Therefore, we need $O(n\log n)$ bits to represent k-regular graphs unambiguously.

Let $k=3$ for simplicity. There are several algorithms
that run in time $O(n)$ on $3$-regular graphs with at most $n$ vertices.
For instance, determining if a graph is bipartite.

How is that possible, if only to read the input we need to read $O(n\log n)$ bits?


texts: Shortest path problem where edge weight depends on path taken

texts:
I am attempting to find the most efficient route to get from a source to a destination in a bus network. Each stop is a vertex in a graph, and each edge between vertices represents a route between stops.

The weights of the edges represents how long it takes to complete a particular journey between stops. For example, if the next bus for a particular route is 10 minutes away, and the journey takes 5 minutes, then the edge weight for that route would be 15.

However, in order to know the amount of time until a particular bus arrives at a stop, it is necessary to know the current time—defined as the sum of the weights of the edges previously taken, plus the time at which the journey started.

What algorithm would allow me to know what vertices have been previously visited, so I can compute the sum of the edge weights? Obviously I could compute every single possible path in the graph, but that seems terribly inefficient.


texts: How can I find a number whose sum of digits' cube is equal to n

texts: I'm given a number $n$ and I have to find the smallest number possible whose sum of digits' cube is equal to $n$. For example $n=9$ then output should be $12$, because $1^3 + 2^3=9$.


texts: CFG for words that are not a concatenation of the same word

texts:
I am teaching myself formal languages, and yesterday i got stuck at an exercise asking for a context free grammar for the language:

$ L = \{x  \in  \Sigma ^{+} | \ \forall w \in \Sigma ^{+} \ x \neq ww\} $ with $ \Sigma = \{a,b\}$

I am trying some rules of the form

$L \Rightarrow a | b $

$S \Rightarrow aSbS\ |\ bSaS\ |\ L\ |\ ab\ |\ ba $

However this is wrong since for example the grammar does not accept 3-symbol strings.
I am a little bit stuck with it so any help would be greatly appreciated.


texts: Free variables of (λx.xy)x and bound variables of λxy.x

texts:
I was solving exercises on Lambda calculus. However, my solutions are different from the answers and I cannot see what is wrong.

Find free variables of $(\lambda x.xy)x$.
My workings: $FV((\lambda x.xy)x)=FV(\lambda x.xy) \cup FV(x)=\{y\} \cup \{x\}=\{x,y\}$.
The model answer: $FV((\lambda x.xy)x)=\{x\}$.
Find bound variables of $\lambda xy.x$.
My workings: A variable $y$ has its binding but since it is not present in the body of the $\lambda$-abstraction it cannot be bound and thus $BV(\lambda xy.x)=\{x\}$ only.
The model answer: $BV(\lambda xy.x)=\{x, y\}$.


texts:
Given is DFA M:

1.) abb and bbb

2.) baa and ab

3.) a and ε (where ε is the empty word)

4.) abb and baa

If I understood correctly, x and y are equivalent to each other (in terms of Nerode), if you add the same suffix for both such that they can be read by the DFA, e.g. they are in L(M)

Thus 1.) is false because abb throws us into the "endless" state 5, there is no escape and thus no suffix.

2.) Is true, simply add suffix aa and both words will still be accepted.

3.) True, take a as suffix.

4.) False, same reason as 1.) you get into the endless state and there is no escape, thus no suffix.

Can you confirm if this is correct? Or did I understand the entire concept wrong? :o