texts: How shall I understand the undesirable consequences of dynamic scoping?

texts:
In Practical Foundation of Programming Languages by Harper

  8.4 Dynamic Scope

  Another approach, called dynamic scoping, or dynamic binding, is sometimes advocated
  as an alternative to static binding. The crucial difference is that with dynamic scoping the
  principle of identiﬁcation of abt’s up to renaming of bound variables is denied. Consequently, capture-avoiding substitution is not available. Instead, evaluation is deﬁned for
  open terms, with the bindings of free variables provided by an environment mapping variable names to (possibly open) values. The binding of a variable is determined as late as
  possible, at the point where the variable is evaluated, rather than where it is bound. If the
  environment does not provide a binding for a variable, evaluation is aborted with a run-time
  error.

  In the higher-order case, the equivalence of static and dynamic scope
  breaks down. For example, consider the expression

 e = (λ (x : num) λ (y : num) x + y)(42).

  With static scoping e evaluates to the closed value v = λ (y : num) 42 + y, which, if applied, would add 42 to its argument. It makes
  no difference how the bound variable x is chosen, the outcome will
  always be the same. With dynamic scoping, e evaluates to the open
  value v'  = λ (y : num) x + y in which the variable x occurs free.
  When this expression is evaluated, the variable x is bound to 42,
  but this is irrelevant because the binding is not needed to evaluate
  the λ-abstraction. The binding of x is not retrieved until such time
  as v' is applied to an argument, at which point the binding for x
  in force at that time is retrieved,and not the one in force at the
  point where e is evaluated.

  Therein lies the difference. For example, consider the expression

e' = (λ (f : num → num) (λ (x : num) f (0))(7))(e)`.

  When evaluated using dynamic scope, the value of e' is 7, whereas
  its value is 42 under static scope. The discrepancy can be traced to
  the rebinding of x to 7 before the value of e, namely v', is
  applied to 0, altering the outcome.

  Dynamic scope violates the basic principle that variables are given
  meaning by capture-avoiding substitution as deﬁned in Chapter 1.
  Violating this principle has at least two undesirable consequences.

  One is that the names of bound variables matter, in contrast to static
  scope which obeys the identiﬁcation principle. For example, had the
  innermost λ-abstraction of e' bound the variable y, rather than
  x, then its value would have been 42, rather than 7. Thus, one
  component of a program may be sensitive to the names of bound
  variables chosen in another component, a clear violation of modular
  decomposition.

  Another problem is that dynamic scope is not, in general, type-safe.
  For example, consider the expression

e' = (λ (f : num → num) (λ (x : str) f ("zero"))(7))(e)

  Under dynamic scoping this expression gets stuck attempting to
  evaluate x + y with x bound to the string “zero”, and no further
  progress can be made.

What does it mean by "with dynamic scoping the
principle of identiﬁcation of abt’s up to renaming of bound variables is denied" and "consequently, capture-avoiding substitution is not available"?

Why under dynamic scoping, "had the innermost λ-abstraction of e' bound the variable y, rather than  x, then its value would have been 42, rather than 7"? How does  "static scope  obey the identiﬁcation principle" here?

How "Under dynamic scoping this expression gets stuck attempting to evaluate x + y with x bound to the string “zero”"?  Isn't it that x in e' is bound to 7?

Thanks.


texts: If a DFA were implemented as a circuit, what would the empty string correspond to as input?

texts:
Say we have a DFA like the one shown below that accepts the empty string, $\varepsilon$.

Also suppose the functionality of this DFA has been implemented as a circuit so that an led lights up whenever an accepted word is detected as input.

While this hypothetical circuit is "idle", i.e. not receiving any a's or b's as input, is the led on? Is it appropriate to think of $\varepsilon$ as idling without real input? Is that what $\varepsilon$, an input string of length zero, represents?

As a follow up, for a circuit implementation of the next DFA, would it have an led that never turns on even while idle?


texts: Trilinear interpolation for distorted cubes?

texts:
Is there a variation of trilinear interpolation that works on a "cube" that has been distorted (by moving one or more of its corners by an arbitrary amount into an arbitrary direction)?

I know that I could use the inverse of the distance to each of the 8 corners as weights to get an interpolated point within the distorted cube, but that would involve taking a lot of square roots which would slow my algorithm way down. I like the elegant way of trilinear interpolation but I can't figure out how to adapt it to a distorted cube. Any hint on a fast interpolation method for this situation would be much appreciated.


texts: where should I begin : I need to predict power consumption of a household?

texts:
I have the power consumption values of a household for 2 year. To preserve privacy I am down sampling this data before sending it to the utility company. My goal is to get back the original data from the down sampled data. I am thinking I would need some kind of learning based predicting algorithm. My professor suggested Markov Chain model but I am not sure if that will work and don't know where to start from.

Any help on what directions I can take will be of great help. Thanks in advance.

Some additional info: I know the type of house, number of residents and pets, type and number of appliances.


texts:
Determining whether two programs always return same output for same input is undecidable (easily reduced to the halting problem). My question is, is there a complexity class in which this problem is decidable for machines on that class?

Seems like it must be below PTIME, as Datalog is P-Complete and equivalence of Datalog programs is undecidable.


texts: Reducing directed hamiltonian cycle to graph coloring

texts: The 3-SAT problem can be reduced to both the graph coloring and the directed hamiltonian cycle problem, but is there any chain of reductions which reduce directed hamiltonian cycle to graph coloring in polynomial time?


texts:
The Unit type is a singleton type containing the constant unit. In functional languages with side effects, unit is used in functions that perform side effects. For example print is a function from string to Unit.

Unit also corresponds to truth. If you view the type of the expression as a proposition and the program as a proof, Unit corresponds to truth since you can always prove Unit by using the constant unit.

My question is aside from these two uses, is there any other uses of Unit?


texts:
I'm working through a few chapters on algorithms from the Discrete Math text by Rosen.

In the solutions manual there is an algorithm (specified in pseudocode) for finding the mode within a list of non-decreasing integers.

Here is the algorithm:

procedure find a mode(a_1, a_2, ... , a_n : non-decreasing integers)
modecount = 0
i = 1
while i <= n
    value = a_i
    count = 1
    while i <= n and a_i == value
        count = count + 1
        i = i + 1
    if count > modcount then
        modecount = count
        mode = value
return mode

Now, I immediately see a problem with this algorithm. For instance, take the list $<1,2,2,2,4,4,4>$ we see that the following steps are followed, counting the element $1$ twice when it only appears in our list once.

Steps below begin upon first entry of the body of the while loop:

Step 1. Assign $a_1=1$ to $value$.

Step 2. Assign $1$ to $count$

Step 3. Check that $i=1 \leq 7$ and that $a_1=1$ equals $1=value$.

Step 4. Increase the value of $count$ by $1$ so that $count := 2$.

But we only have $1$ appearing once in our list and we have counted it twice.

Is my interpretation of this algorithm incorrect? To me $count$ should first be set to $0$.


texts: Does a multi-agent system have to have a synchronous component in order for the agents to cooperate?

texts:
During my programming assignments in multi-agent systems, I noticed that it feels impossible to get distributed agents to cooperate without a synchronous component. Let me explain what I mean by these terms:

Cooperation: I would loosely define this as any process which a single agent cannot solve without receiving non-static information from one or more other agents.

Example: Consider a system where two identical agents are needed to change a lightbulb. One agent needs to change the lightbulb itself, and one needs to hold the ladder.

Naturally, the problem is how to decide which agent is going to be the lightbulb changer and which the ladder holder. I have somehow arrived at the conclusion that this is impossible without the presence of a synchronous component in the system.

Without such a component, the agents could always get into an inconsistent state - for example, both would consider themself the holder, no matter how you decided how to assign those roles - if you were to choose, for example, a message sending system, where an agent would send to another "I will change the bulb, you hold the ladder", they could still send such a message at the same time. Similarly, if there was to be a "Leader" of those agents who would assign those roles, how would you decide which one was to be the leader? You just move the problem up a level.

Therefore, such problems are normally solved by methods such as assigning an unique integer identifier to each agent, and deciding based on this value (agents with higher value will become the leader, etc). Similarly, I have seen people use things like the time of the agent's entry into the system, the position of the agent in the environment, and so on.

However! All of those things are what I consider to be a synchronous component. Some entity has had to synchronously decide them - there is only a single time, a single person who assigns the identifiers, a single universe by which the agents' locations are defined, and so on.

I am pretty sure this statement holds. My question is: does there exist a theorem which states this or something similar (one that has been formally proven)?


texts: Generating a Context Free Grammar from a Language

texts:
I am wondering how to go from a language such as this:

L = {a^n b^m c^k | n = m or m != k}

To a Context Free Grammar. I know that I would have to turn it into two separate languages but I don't know how to create the production rules for each of those languages.


texts:
Here's the question: Do more baby names start with "A" or "B"? Write code to count and print those two counts ("A" count, then "B" count).

I then write this code down:

table = new SimpleTable("baby-2010.csv");

count1 = 0;

count2 = 0;

for (row: table) {

// your code here

if (row.getField("name").startsWith("A")) {

count1 = count1 + 1; }

if (row.getField("name").startsWith("B")) {

count2 = count2 + 2; }

}
print("A count:",count1)
print("B count:",count2)

I ran the code which then came out like this: A count: 258
B count: 198

Any ideas as to why this might be wrong?


texts:
$PH \subseteq PSPACE$.

In order to prove it, one has to show that for a language $A \in \Sigma_k$ (for some $k \in \mathbb{N}$) there exists a turing machine $M_A$ that decides it in polynomial space.

I am having a hard time understanding why this is true. I'll try to explain:

Let's take for example $L \in\Sigma_2$: by definition, $x \in L \Longleftrightarrow \exists y_1\forall y_2 : V(y_1,y_2)=1$. But finding such $y_1$ and checking it against all possible $y_2$s has to take more than polynomial space! The machine has to remember each $y_2$ that it tried in order to make sure that it indeed tried out all of the options, and the number of possible $y_2$s is exponential, which makes it exponential space.


texts: Complexity of Context Sensitive Languages

texts:
I was reading above complexity classes from Formal Languages and Automata book by Peter Linz.

It gives following facts (in Theorem 5.2):

  Consider we have a CFG without null or unit productions. For parsing a string w, if restrict ourselves to leftmost derivation, we can have no more than $|P|$  sentential forms after one round, no more than $|P|^2$ sentential forms after the second round, and so on. Parsing $w$ in CFG without null or unit productions cannot involve more than $2|w|$ rounds. Therefore, the total number of sentential forms cannot exceed $M=|P|+|P|^2+⋯+|P|^{2|w|} =O(P^{(2|w|+1)})$

Then (in Example 14.5, citing back above theorem) it says

  However we cannot claim that
  $CSL \subseteq DTIME(|P|^{cn+1})$
  because we cannot put an upper bound on $|P|$ and $c$

I dont understand why it is trying to use the fact about CFLs to find time complexity of CSLs. Is it because if CFLs does not follow that DTIME complexity, CSLs will also not follow it as $CFL\subset CSL$? But then, given any grammar, $|P|$ is fixed, its not infinite and I feel $c$ is always 2 as given in the proof of the theorem 5.2.


texts: Proving the regularity of the following language

texts:
I have a question about the following problem:

  Prove that the language $\{a^nva^n | v \in \Sigma^*, n \ge 1\}$ is regular over
  $\Sigma = \{a,b\}.$

I know that in proving a language is regular I can either construct a DFA, give a regular expression or show the Nerode-Relation has finite index.

My main problem is, that I cannot understand why this should be a regular language, since $\{a^nb^n | n \ge 1\}$ is not regular and of similar form. Also, I do not understand how a DFA should recognize the same amount of a's at the front and at the end of a word.


texts: Turing machine algorithms for $\{0^n1^n\}$ using one and two tapes

texts:
I was tasked with finding a way to decide the language $A=\{0^k1^k \mid k\ge 0\}$ in $O(n\log n)$ time, and then to implement it on a deterministic Turing machine with one tape. Additionally, I was asked to check if it is possible to reduce the time from $O(n\log n)$ to $O(n)$ if using a determinstic Turing machine with two tapes (instead of one).

I am really stuck on it and don't know how to implement it. This is what I have so far:

First, we check that in the input word there are no zeros right of the ones. Then, for each zero in the input, we increase a binary counter and for the ones we do the same, creating a binary counter and increasing by one. if the counters are equal, accept, if not, reject. But i don't know how to implement it on a Turing machine, aside from the problem that if the counters of one and zero are far from the writing-reading head, then reaching it would take a lot of steps (time).

Regarding improving it to $O(n)$ time using a deterministic Turing machine with two heads: we go over with one head along the input string until we meet the first 1. then we count the number of one with one tape, and with the other the number of 0's. then we compare and accept if they are equal. So it is basically $k$ steps until the first 1, creating the counter, and counting each 1 $n$ times, then creating a counter with the second tape and comparing to the number of 0's in the beginning until the first one. So the total is $O(n)$. But how do I implement it on a Turing machine?


texts: Virtual Memory - Non-contiguous Memory Allocation

texts:
I'm studying for my operating systems final, and one question that my professor asked that I can't seem to find the answer to is the following:

"Why does virtual memory use non-contiguous memory allocation?"

The textbook only talks about virtual memory in the context of non-contiguous memory allocation, but never explains why. The only reason I can think of is because of page replacement, but I'm not even sure that's right. Anyone have any thoughts on this?


texts:
I'm reading Neil Gunther's Practical Performance Analyst, and he provides that when there's one queue and one server, the residence time (total time spent per request) is:

R = S + QS

S is service time
Q is number of customers ahead
R is residence time

Then he describes a case with a single queue and two servers and says that the equation becomes

R = S + 1/2 SpQ

p is per-server utilization 0 < p < 1.

I don't understand why p is a factor here. Wouldn't all servers be busy whenever there are customers waiting in line? Why is this different from the single-server case? The explanation given in the book is copied on slide 25 here. I don't understand the reasoning. Why do we need p?


texts: How can I improve my algorithm for finding optimally balanced P-way partitioning of array

texts:
I have an array of $N$ weights $w_i$, say $w_i=\{4, 5, 12, 16, 3, 10, 1\}$, and I need to divide this array into $P$ partitions such that partitions are optimally balanced, i.e. that maximum sum of weights of any partition is as small as possible. Luckily the problem is constrained by the fact that the weights can't be reordered. If the number of partitions is three, the above example would give the optimal partitions: $\{4, 5, 12\}, \{16\}, \{3, 10, 1\}$.

I have found efficient recipes (e.g. partition problem, subset sum, Optimal Partition of Book Chapters, A partition algorithm, An algorithm for k-way array partitioning) for many similar problems for the cases where the weights are unordered sets and/or the number of partitions is fixed at 2 or 3, but none that seem to exactly address my problem where the number of partitions is arbitrary.

I have solved the problem myself using divide-and-conquer algorithm (written in Python below), but it seems to be awfully slow for many partitions (e.g. N=100, P=8). So I was thinking that there got to be a better way, using dynamic programming or some other clever tricks?

Does anyone have any suggestions?

Slow Python divide-and-conquer algorithm:

def findOptimalPartitions(weights, num_partitions):
    if num_partitions == 1:
        # If there is only one partition, it must start at the first index
        # and have a size equal to the sum of all weights.
        return numpy.array([0], dtype=int), sum(weights)

    # Initially we let all partitions start at zero, meaning that all but the
    # last partition gets zero elements, and the last gets them all.
    partition_offsets = numpy.array([0] * num_partitions)
    max_partition_size = sum(weights)

    # We now divide the weigths into two partitions that split at index n.
    # We know that each partition should have at least one element, so there
    # is no point in looping over all elements.
    for n in range(1, len(weights) - num_partitions):
        first_partition_size = sum(weights[:n])

        if first_partition_size > max_partition_size:
            # If the first partition size is larger than the best currently
            # found, there is no point in searching further.
            break

        # The second partition that starts at n we now further split into
        # subpartitions in a recursive manner.
        subpartition_offsets, best_subpartition_size = \
            findOptimalPartitions(weights[n:], num_partitions - 1)

        # If the maximum size of any of the current partitions is smaller
        # than the current best partitioning, we update the best partitions.
        if ((first_partition_size < max_partition_size)
                and (best_subpartition_size < max_partition_size)):
            # The first partition always start at 0. The others start at
            # ones from the subpartition relative to the current index, so
            # add the current index to those.
            partition_offsets[1:] = n + subpartition_offsets
            # Find the maximum partition size.
            max_partition_size = max(first_partition_size, best_subpartition_size)

    return partition_offsets, max_partition_size

EDIT: A trivial Greedy algorithm where the last partition will typically be too large.

def greedyPartition(weights, num_partitions):
    target_size = sum(weights) / num_partitions

    partition_offsets = numpy.zeros(num_partitions, dtype=int)
    partition_sizes = numpy.zeros(num_partitions, dtype=int)
    current_divider = 0
    for p in range(0, num_partitions - 1):
        partition_size = 0
        for n in range(current_divider, len(weights)):
            if partition_size + weights[n] > target_size:
                current_divider = n
                partition_offsets[p + 1] = current_divider
                partition_sizes[p] = partition_size
                break

            partition_size += weights[n]
    partition_sizes[-1] = sum(weights) - sum(partition_sizes[:-1])
    max_partition_size = max(partition_sizes)

    return partition_offsets, max_partition_size


texts: When can I use dynamic programming to reduce the time complexity of my recursive algorithm?

texts: Dynamic programming can reduce the time needed to perform a recursive algorithm. I know that dynamic programming can help reduce the time complexity of algorithms. Are the general conditions such that if satisfied by a recursive algorithm would imply that using dynamic programming will reduce the time complexity of the algorithm? When should I use dynamic programming?


texts: Is finding Kth largest element using selection algorithm taking O(n) only if K is fixed?

texts:
Wikipedia here https://en.m.wikipedia.org/wiki/Selection_algorithm shows an algorithm using sort of quicksort.. in order to find Kth largest or smallest element taking O(n) time only on average. The point which is unclear is whether K is required to be constant or at least independent of size of N.

I saw this issue being discussed on this site here : https://stackoverflow.com/questions/251781/how-to-find-the-kth-largest-element-in-an-unsorted-array-of-length-n-in-on
But people there in the comments seem to claim that K is fixed.

The point which I don't understand is, if k is indeed needed to be fixed.. then what's the point of this algorithm of select and quicksort?

Why can't we just perform like bubble sort K times if K is fixed it wouldn't be more than K*N  which is O(n) . So what's the problem of achiving it in O(n) if k is fixed.