texts: Levenstein distance and dynamic time warp

texts:
I am not sure how to draw parallel between the Wagner–Fischer algorithm and dtw algo.
In both case we want to find the distance of each index combination (i,j).

In Wagner–Fischer, we initiate the distance by the number of insert we'd have to do from one empty string to another.

let wagnerFischer (s: string) (t: string) =
   let m, n = s.Length, t.Length
   let d = Array2D.create (m + 1) (n + 1) 0

   for i = 0 to m do d.[i, 0] <- i
   for j = 0 to n do d.[0, j] <- j

   for j = 1 to n do
       for i = 1 to m do
          d.[i, j] <- List.min [
                           d.[i-1, j  ] + 1;
                           d.[i  , j-1] + 1;
                           d.[i-1, j-1] + if s.[i-1] = t.[j-1] then 0 else 1; ]
   printfn "edit matrix \n %A" d
   d.[m,n]

in the DWT we initiate the boundary at +infinity because we dont want to 'skip' any numbers of the sequence, we always want to match with another item.

What I dont see is what changes between the DWT and the WF algo that prevent use to update the distance in homogeneous way.
In DWT we systematically add the cost, whereas in the WF algo, we have this non homegenous function wrt different cases

I understand both algo, but dont make the connexion between those differences in the cost function update ..
Any idea to understand the difference intuitively  ?

let sequencebacktrack (s: 'a seq) (t:'a seq) (cost:'a->'a->double) (boundary:int->double)  =
   let m, n = s |> Seq.length, t |> Seq.length
   let d = Array2D.create (m + 1) (n + 1) 0.

   for i = 0 to m do d.[i, 0] <- boundary(i)
   for j = 0 to n do d.[0, j] <- boundary(j)

   t |> Seq.iteri( fun j tj ->
            s |> Seq.iteri( fun i si ->
                        d.[1+i, 1+j] <- cost tj si + List.min [d.[1+i-1, 1+j  ];
                                                               d.[1+i  , 1+j-1];
                                                               d.[1+i-1, 1+j-1]; ] ))
   printfn "edit matrix \n %A" d
   d.[m,n]
//does not work
let wagnerFischer2 (s: string) (t: string) =
   sequencebacktrack s t (fun a b -> if a = b then 0. else 1.) (id >> double)

let b = wagnerFischer2 "ll" "la"


texts: Differences among meta-data, catalog, data dictionary, and schema

texts: What is the exact meaning of  these terms? Very confusing. Most of the articles uses these terms interchangeably.


texts:
Given the following definition of Careful 5COLORING:

  A 5-coloring is careful if the colors assigned to adjacent vertices
  are not only distinct, but differ by more than 1(mod 5)

how would a reasonable reduction to prove NP hardness work? Suggestion is to reduce from standard 5COLOR, but I am not able to find a correct one.

I have tried reducing from an instance $G$ of the standard 5COLOR as suggested creating one extra vertex between every edge in $G$. That is, let $\{u,v\}$ be an edge in $G$, create a new vertex $w$ and add edges $\{u,w\}$ and $\{w,v\}$. Fix the color of every new vertex to the same color, for example 3. This results in a new graph $H$.

When proving "$G$ is 5COLORABLE iff $H$ is carefully 5COLORABLE", I can prove the first $G$ is 5COLORABLE $\rightarrow$ $H$ is carefully 5COLORABLE since $H$ actually requires only 3 colors (if every new vertex is colored as 3, I only need colors 1 and 5 for the original vertexes in $G$).

On the other hand, the proof doesn't work since there are instances where $G$ isn't 5COLORABLE but $H$ is carefully 5COLORABLE. This has led me to believe my reduction is wrong.


texts: Count number of linearly independent subsets of columns of a binary matrix

texts:
I have a binary $m \times n$ matrix of rank $m$ (hence $m < n$). I need to count how many subsets of its columns form matrices with a full column rank, i.e. columns in the subset are linearly independent.

Straightforward approach would be to iterate over all subsets of columns of size up to $m$ (because column rank cannot be higher than a row rank), and then check corresponding submatrix if it has full column rank. For instance, if $m=25$ and $n=50$, this way one needs to test
$$
\binom{50}{1} + \binom{50}{2} + \dotsb + \binom{50}{25} \approx 6.3 \times 10^{14}
$$
matrices. Hence one needs a really fast algorithm to test if a particular submatrix has a full column rank.

For example, assume I have 500 cores and I want to calculate the subject in 24h. Then I need to test $1.4 \times 10^7$ submatrices per second per core. Old good Gaussian elimination fails with this task (right?). Can I do something much faster than it?

Another approach might be some optimised method like branch and bounds, so that one does not need to check all the submatrices - but only a small portion of them. For example we can build the subsets recursively, and if we encounter a subset of columns that are linearly dependent, we can safely throw away all of the supersets of this subset - as they will never become linearly independent. However, I am not sure about either complexity or running time of this approach. I am to implement it now to see the running time behaviour.

P.S. All operations are over Galois field $\mathbb F_2$.

P.P.S. Do you think this problem is in NP?


texts:
I saw a question similar to this one, and it was answered but the answer was kind of vague and I'm looking for a little more detail than that. The question I'm referring to is this one.

The answer simply states that there are more page tables, one for each process. And the same thing is said in the book that I'm studying from.

Quote (translated myself, so might not sound so great):

  During the program execution, the CPU works with logical addresses.
  The logical address has to be translated into a physical address for
  which a special structure called page table is used. The operating
  system generates a page table for each process in execution.

Okay, so that seems to be clear. But the books seems to contradict itself later on, in the section which explains where and how these tables are stored. Here's what the book says:

  In the simplest case, a page table can be stored in a set of
  registers. However, using registers for storing page tables is only
  satisfactory when the table is relatively small. In the situation
  where the table is larger it is kept in memory, and a special base
  register points to its location (Page Table Base Register - PTBR).

I guess you can already see my confusion here: The plural and singular just keep alternating so I'm not sure whether there is in fact one or more page tables. Later on the concept of the Translation Lookaside Buffer is introduced and it gets even more confusing.

My questions come down to this:

Is there a single page table where all the pages from different processes are mapped into different memory frames, or is there a page table for each process currently being executed? If the latter is true, then does the CPU have a separate PTBR for each of these tables? I mean that seems kind of impossible, since that register is physical which would imply that there needs to be a finite number of them. Or maybe a combination of these cases, where there is in fact a table for each process but the CPU operates only with one at a time with some kind of context-switching mechanism?

Thanks in advance.


texts: Heuristic for Finding Multiple Goals in Graph - e.g. using Kruskals Algorithm

texts:
I'm a none-computer-science-student and get some knowledge on AI by taking the CS188.1x Course (Artificial Intelligence) on www.edx.org .

Currently, I am working on the "Search in Pacman" Project; the sources can be found online at Berkley CS188 . I have problems finding an good solution for "Finding All the Corners", so I need a good Multiple Goal Heuristic.

I allready tried the simple approach described in here. I used the minimum of all manhattan distances to all goals. This works, but is considered a rather poor heuistic, because my A-Star Algorithm expands 2606 nodes for the given maze. Using the same with euclidean distance expands even 103081 nodes. A good heuristic should expand 1600 nodes or less. A very good one 1200 nodes, an excellent one even 800 or less.

I got a hint by other students who use minimum spanning trees created with Kruskal's Algorithm. I wanted to investigate into that direction, but I am somehow confused how the Kruskal Algorithm can be used to get a Heuristic?
As far as I understood, this Algorithm returns a minimum spanning tree (MST) which is a path, right? So it is a solution to the Traveling Salesman Problem (TSP); it returns a sequence of nodes. But I need a heuristic, so a cost function which can be applied to this problem and called by an Algorithm (like A*).

Can anyone of you give me a hint on how to proceed? Every help is highly appreciated!


texts: Does interrupt (for I/O and etc) requires support of Preemption? What is the relation between interrupts and Preemption in O.S?

texts:
So i just don't understand the relation between interrupts and Preemption in O.S?

For example in Multi-programming, do we need the support of Preemption or not? when a process needs I/O and sends an interrupt, do we use Preemption here to remove that process in order to get another process running, or no need for Preemption ?


texts: Minimum edge weight k-exact cover with triangle inequality

texts:
Suppose you have a weighted graph $G = (V, E \subseteq V^2, w \in E \to \mathbb{R}^+)$, where $w$  satisfies the triangle inequality $w(x, y) + w(y, z) \ge w(x, z)$. Suppose $k \in \mathbb{N}$ (in practice, $k \le 6$ is common). I want to find a set $C \subseteq \mathbb{P}(V)$ (a set of subsets of $V$) such that:

$\max_{I \in C} \sum \{w(x, y) \mid x \in I \wedge y \in I\}$ is minimized.
For all $I \in C$, $\mathrm{card}(I) = k$.
No two elements of $C$ have nonempty intersection.
The union of all elements of $C$ is $V$.

Assume that $\mathrm{card}(V) = r \cdot k$ for some $r \in \mathbb{N}$.

Is there a polynomial-time approximation algorithm for this task?

I believe this problem is related to facility location problems, but I am not sure.


texts: Control of the combinatorial aspects of a dynamic programming solution

texts:
I am exploring how a Dynamic Programming design approach relates to the underlying combinatorial properties of problems.

For this, I am looking at the canonical instance of the coin exchange problem: Let S = [d_1, d_2, ..., d_m] and n > 0 be a requested amount. In how many ways can we add up to n using nothing but the elements in S?

If we follow a Dynamic Programming approach to design an algorithm for this problem that would allow for a solution with polynomial complexity, we would start by looking at the problem and how it is related to smaller and simpler sub-problems. This would yield a recursive relation describing an inductive step representing the problem in terms of the solutions to its related subproblems. We can then implement either a memoization technique or a tabulation technique to efficiently implement this recursive relation in a top-down or a bottom-up manner, respectively.

A recursive relation could be the following (Python 3.6 syntax and 0-based indexing):

def C(S, m, n):
    if n < 0:
        return 0
    if n == 0:
        return 1
    if m <= 0:
        return 0
    count_wout_high_coin = C(S, m - 1, n)
    count_with_high_coin = C(S, m, n - S[m - 1])
    return count_wout_high_coin + count_with_high_coin

However, when drawing the sub-problem DAG, one can see that any DP-based algorithm implementing this recursive relation would yield a correct amount of solutions but disregarding the order.

For example, for S = [1, 2, 6] and n = 6, one can identify the following ways (assumming order matters):

1 + 1 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1
1 + 2 + 1 + 1 + 1
1 + 1 + 2 + 1 + 1
1 + 1 + 1 + 2 + 1
1 + 1 + 1 + 1 + 2
2 + 2 + 1 + 1
1 + 2 + 2 + 1
1 + 1 + 2 + 2
2 + 1 + 2 + 1
1 + 2 + 1 + 2
2 + 1 + 1 + 2
2 + 2 + 2
6

Assumming order does not matter, we could count the following solutions:

1 + 1 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1
2 + 2 + 1 + 1
2 + 2 + 2
6

When approaching a problem solution from the Dynamic Programming standpoint, how can I control the order? Specifically, how could I write functions:

count_with_order()
count_wout_order()

?

Could it be that the need for order mattering implies choosing pruned backtracking over a Dynamic Programming approach?


texts: Virtual Memory: "Page Table or Page Tables?"

texts:
I am having a bit of a tough time grasping whether a computer system contains several page tables or just one page table.

Some sources speak of page tables in plural others in singular.

Intuitively it makes most sense to me that there is only one Page table containing all the physical addresses especially considered these addresses are to change over time. But I am not sure?


texts: Given RSA, why do we not know if public-key cryptography is possible?

texts:
I was on wikipedia on list of unsolved computer science problems and found this:
Is public-key cryptography possible?

I thought RSA encryption was a form of public-key cryptography? Why is this a problem?


texts: Prove that not all languages over unary alphabet are regular

texts:
Let the alphabet be $\{0\}$. I have to prove that not all languages over this alphabet are regular, using some countability argument.
My Ideas:
The set of all languages over $\{0\}$ is uncountable. This can be proved with the diagonalization argument. So to prove the statement, I have to show that set of all regular languages over $\{0\}$ is countable. Not sure how to prove that.


texts:
Let's suppose there are two banks, Bank A and Bank B. A transaction needs to happen that transfers money from an account in Bank A to an account in Bank B. Bank A and Bank B have separate banking systems which makes this transaction a distributed one. From what I understand following is what happens, I refer the system of bank A as A and the system of bank B as B,
A initiates the transaction
A sends a message including the amount to B
A waits for a response from B
B adds the amount to the account send a response to A
A receives the response and deduct the amount from account
Transaction completes.

A can complete the transaction if it received the response since it is a guarantee that B has done the addition, but if A doesn't receive a response, it cannot guarantee that B has done the addition, so it cannot complete the transaction. In that case, what if B has done the addition successfully but the response message was lost in transit. Now A hasn't done the deduction while B has done the addition which is an inconsistent state. How do we solve that problem?


texts: Two classes of documents. Find weighted relations between them

texts:
I have an NLP problem and a potential solution, but I’m a bit green here, so I’m looking for some validation or alternative suggestions.

Background

I have two types of documents: one is a set of short statements of an organization's goals and objectives (“Goals”, from here on. ~500 docs, ~100 words/doc. New documents monthly-annually). The other is a larger set of things they've actually done (statements of work, contracts, etc. “Work”, from here on. ~10M docs, ~300 words/doc. New documents daily-weekly.).

Problem

My objective is to assign each of these Work statements to one or more Goals, if possible with a weight indicating of how closely they fit.

The hypothesis I'm working from is that each Work document is created by someone with knowledge of the Goals, and therefore there's a hidden relationship between the two that should show up in a probabilistic approach.

There's no existing data of this sort, so that seems to eliminate most supervised approaches.

Solution?

I've done a lot of reading about ML/NLP, but this is the first time I've tried to do something beyond basic examples and use of pre-existing libraries. Most of my knowledge comes from Introduction to Information Retrieval, so I've been going through that trying to find something that fits.

Here's my current idea:

Build a term-document matrix of Goals.
Use singular-value decomposition to construct a low-rank approximation. The intention here is to narrow out both stopwords and terms common across all Goals. This part seems to be the most “magical” to me right now, so I might be misunderstanding its capabilities here.
Construct a term-document matrix of Work.
Compare the Goal matrix to the Work matrix (or the selection of the relevant terms from the Work matrix). Compute the distance from each Work document to each Goal document. The final result will be a matrix of Work x Goals with some kind of weight between each. My linear algebra is a bit shaky, so I can’t remember if there’s an obviously good distance function that I’m missing the intuition on. Or should it be something more like cosine similarity?

I came up with this after reading the Language models for information retrieval and Matrix decompositions and latent semantic indexing chapters in IIR. I don’t think what I’m describing falls exactly into any of those techniques like LSI, but I may be confused because they’re mostly talking about matching queries to documents, rather than other documents. Maybe my restricted-term Goal martix is actually a set of query vectors then? Or maybe this is a different technique that I picked up elsewhere?

Or maybe I’m way off and this won’t work at all? :-) I’d love some feedback. Thanks.


texts:
I have an example from a textbook using a language $L = \{ a^nb^ma^n : m, n \ge 0, n \ge m \}$.

  We can use pumping theorem to show that $L$ is not context-free. If it were, then there would exist some $k$ such that any string $w$, where $|w| \ge k$, must satisfy the conditions of the theorem. We show one string $w$ that does not. Let $w =a^kb^ka^k$ where $k$ is the constant from the pumping theorem [...]

Why have they chosen to use $k$? My understanding from the pumping theorem definition is that $k$ is an arbitrary integer $>1$
What is the relation of $k$ to $n$ and $m$ in the original language definition?
Members of $L$ can have more $a$'s than $b$'s, but $a^kb^ka^k$ will result in an equal number of $a, b$. Is it not necessary in this case because an equal number of $a$'s and $b$'s is still a member of L? What happens when $L = \{ a^nb^ma^n : m, n \ge 0, n > m \}$ and $a^kb^ka^k$ is not part of $L$?

I think this is holding me back from understanding how to prove my homework question of:

  Prove whether the language $\{a^xb^yc^xd^y: x, y \ge 0\}$ is context free or not

Apologies if these are basic. I've been racking my brain for days on these kinds of questions and I'm so lost. Thanks for any assistance.


texts:
My understanding is that a self-hosting compiler will take as input the language it is written in and a cross-compiler will output a language which runs on a platform which is different to what it runs on.

Can we combine these two compiler types into one?


texts: How can I prove the minimum pumping length of finite language?

texts:
Let L be the set of all strings over {0, 1} whose lengths are at most three. Since L is regular, the pumping lemma holds for L, and thus there is a pumping length p associated with L. What is the smallest possible pumping length associated with L?

For this problem, I think minimum pumping length for this language should be 4, because if pumping length is smaller than or equal to 3, then  $xy^{i}z$  may not be in the given language, because its length could be longer than 3. So, I want to prove that 4 is the minimum pumping length for the given language, but I have no idea how to prove it accurately. The explanation I wrote here is too informal, I think. Can anyone help me?


texts: Two word computer term ending in word "complex" meaning computers connected together

texts: I remember seeing a Computer Science jargon which means multiple computers connected together; a network. It ends in the word "complex" and the first word (I cannot remember this but I shall guess to the best of my memory) is taken from some science-fiction franchise or from mythology. It could also be a proper noun used in a way unrelated to Computer Science. I have spent days looking for this and any help is most welcome.


texts:
I am reading algorithms in a CS book where a potentially nil value is passed to a function, but neither the caller nor the callee check if the value is nil. Is this a common practice in algorithms?

To be more precise, I am implementing a red-black tree and the grandparent of a node is passed to a rotation function, but if correctly understand the algorithm, the grandparent might be nil at the time the rotation function is called.

I should probably warp such calls into a conditional block, but I was curious to know if this is common for algorithms to be specified that way, and if there are any additional advices on how to handle those cases.

Thank you


texts: Not getting the clear picture of Goto actions , reduce and shift actions in SLR Parsing

texts:
I am going through the following lecture notes on LR parsing :

https://www3.nd.edu/~dthain/courses/cse40243/fall2016/chapter4b.pdf

For the following grammar :

The following LR automation has been done :

and the following is the LR parsing table drawn for it :

In the table I can see that the alphabets "R" ,"G" and "S" denote the action being taken and the number following them is the index number of the state to which the transition is taking place .

Now , what I am unclear about is what exactly is a "goto"action ? I can see that goto actions , "G1" , "G8" , "G3", "G6" are occurring only in response to non- terminals "'E" and "T" . And all of them have two rules by using which we can reduce the expression to the start symbol.

But I am unable to draw any further patterns to interpolate what exactly is a "Goto action " .

Nevertheless , when at state 4 an input of "(" results in shift but how does an input of ")" or "+" result in reduction , which I ,with certain degree of confidence, guess to be , the action of replacing few symbols with the left hand side of certain production .

So , how exactly to make sense of this table ? What exactly is a GOto  and am I right about "reduction"?


texts: Does it make sense to work on DIMACS framework to test TSP algorithms?

texts: Are there any reasons to work with the DIMACS framework, such as to test algorithms, coding, and heuristics of TSP (Traveling Salesman Problem)? It is nearly 15 years since establishment of the benchmark in 2001.


texts: NP-hardness of finding a subset of vertices in a vertex-weighted graph

texts:
This is task from the German IT contest ("Bundeswettbewerb Informatik"), but since the deadline is past, asking this question is no cheating.

Given a vertex-weighted, directed graph $G=(V, E)$ and values $c_v$, find a subset of nodes $V_{res}\subseteq V$ that maximizes $$\sum_{v \in V_{res}} c_v$$ subject to $$\forall (u,v) \in E: u \in V_{res} \implies v \in V_{res}$$
Is this problem NP-hard?

I could prove that the problem is in P if every node has either no parents or no children by showing that in this case, it can be solved by Vertex Cover on bipartite graphs, but I failed in finding a reduction that proofes the NP-hardness of the original problem.

Can somebody give me a hint how to do this?

PS: In the contest, the task was only to find an algorithm that solves this problem, the original (German) definition is task 1 of this document: http://www.bundeswettbewerb-informatik.de/fileadmin/templates/bwinf/aufgaben/bwinf35/aufgaben352.pdf


texts: How asymptotically bad is naive shuffling?

texts:
It's well-known that this 'naive' algorithm for shuffling an array by swapping each item with another randomly-chosen one doesn't work correctly:

for (i=0..n-1)
  swap(A[i], A[random(n)]);

Specifically, since at each of $n$ iterations, one of $n$ choices is made (with uniform probability), there are $n^n$ possible 'paths' through the computation; because the number of possible permutations $n!$ doesn't divide evenly into the number of paths $n^n$, it's impossible for this algorithm to produce each of the $n!$ permutations with equal probability.  (Instead, one should use the so-called Fischer-Yates shuffle, which essentially changes out the call to choose a random number from [0..n) with a call to choose a random number from [i..n); that's moot to my question, though.)

What I'm wondering is, how 'bad' can the naive shuffle be?  More specifically, letting $P(n)$ be the set of all permutations and $C(\rho)$ be the number of paths through the naive algorithm that produce the resulting permutation $\rho\in P(n)$, what is the asymptotic behavior of the functions

$\qquad \displaystyle M(n) = \frac{n!}{n^n}\max_{\rho\in P(n)} C(\rho)$

and

$\qquad \displaystyle m(n) = \frac{n!}{n^n}\min_{\rho\in P(n)} C(\rho)$?

The leading factor is to 'normalize' these values: if the naive shuffle is 'asymptotically good' then

$\qquad \displaystyle \lim_{n\to\infty}M(n) = \lim_{n\to\infty}m(n) = 1$.

I suspect (based on some computer simulations I've seen) that the actual values are bounded away from 1, but is it even known if $\lim M(n)$ is finite, or if $\lim m(n)$ is bounded away from 0?  What's known about the behavior of these quantities?


texts: Curry howard isomorphism "proof as program"

texts:
I'm reading CH Isomorphism.

Let's divide into two stages:

Prop corresponds to types. so a proposition A $\wedge$ B corresponds to type A $\times$ B.
Proof corresponds to the program. What is the corresponding proof and program in this case ?

As far as I can guess the proof is a pair  but how we denote program ? Is that a lambda term "pair" ?? What we mean by a proof here. coz proof is a complete derivation in case a pro example exists ?? Very confused . Can someone help ?


texts: Databases and B-Trees: What are Keys and how are they related

texts:
I confused about the description & definition of "key" occuring as terminology for databases and b-trees.
In first case dealing with theory of databases a key is defined as a choice for a in certain sense minimal (see below) subset $K \subset A := \{A_1,A_2,...,A_n\}$ of a fixed set of attributes $A_i$ parametrizing a data table (consisting of relations; a single relation is abstraction of a row in the table), where each attribute is literally a column specifying a property of objects = relations.
A key is characterized by property that there exist no two different relations (a relation is a row) which have exactly the same values for all attributes which belong to the key. And a key is a minimal subset with this property, ie there not exist a proper smaller subset of attributes contained in the key and having the property described in last sentence. Clearly keys are not unique. So the set of a keys is certain subset of the power set $\Omega(A)$ of the set attributes $A_i$. See also here: https://en.wikipedia.org/wiki/Unique_key
On the other hand the key concept occures as well for b-trees: https://en.wikipedia.org/wiki/B-tree#Definition
Here keys are a priori numbers or integers and different knots of b-tree contain different totally ordered subsets of keys where the total order on the space of keys is inherited from the order "$\ge$" for integers $\mathbb{Z}$. Especially the set of keys is a totally ordered subset of integers.
Question: How are the two concept of 'key' related to each other? My first idea was that if we consider in light of for definition (as elements of power set of attributes), we can simply randomly enumerate all the keys (that is associate to each key an number; formally speaking to specify an injection $f:\mathcal{K} \to \mathbb{Z}, K \mapsto f(K)$ where $\mathcal{K} \subset \Omega(A)$)
and then treat them as numbers when working with b-trees. Is this exactly the correct connection or is there another deeper one and my approach is wrong?


texts: A doubt regarding the acceptance of $\epsilon$ by an automaton testing divisibility of numbers

texts:
As we know, $\epsilon$ is the empty string, with length 0. It is not part of any any alphabet by default, unless specifically defined so. However, it is a string over any alphabet.

For example, Given that I need to design a Deterministic or Nondeterministic finite state automaton (without $\epsilon$ transitions) that accepts decimal numbers that are say, divisible by 2, would I have to account for the empty string as an input word as well? If so, how does divisibility work for null input?


texts:
Let's say I have a 64 kB Cache provided (i,e 2^18) which is direct mapped and block size is 16 byte = 2^5

Now, in the solution it says
m=size of cache in blocks = 4096 = 2^12. This hasn't been provided in the question. So, how do we assume / derive size of cache in blocks was 2^12.

If this is a static value, then does that changes if block size is increased to 32 bytes?


texts: Are JS regexes really not able to parse HTML?

texts:
Many people have seen this fantastic meme answer
 before about how we should use a parser to parse HTML instead of using Regex. The argument is that HTML is not regular and thus cannot be parsed using Regex.

However, a closer look at JS regexes, it seems JS regexes can indeed describe irregular languages via backreferences. Languages such as $a^n|a^n\ \{\ a \in \Sigma, n \in N\ \}$ can be described with:

/(.+)\|\1/

The regexes JS has are really "enhanced regular expressions", but I'm not sure if that's enough to parse HTML which is obviously irregular. I'm also not sure if they at least cover every CFG languages.


texts: What helpful solution does the Halting Problem give to computing?

texts:
What problem does the halting problem solve in computing, whether theoretical or practical?

It is very easy to debug code which loops forever, just signal the debugger to break if the program is running for too long? What purpose / good is the halting problem? Why was Turing praised for it?


texts: What would show a human mind is/is not reducible to a Turing machine?

texts:
In computer science it is often assumed that a human mind can be reduced to a Turing machine.  This is the assumption that underlies the field of artificial intelligence.

However, it is an assumption, one that has neither been proven or disproven.

Is there any kind of test within our current capabilities where we can prove/disprove this assumption?

If not, is there any evidence that would suggest one way or another?

Here is a similar question I asked awhile back on theoretical computer science:

https://cstheory.stackexchange.com/questions/3170/human-intelligence-and-algorithms


texts: Does it make sense to have both the concept of 'null' and 'Maybe'?

texts:
While creating a client for a web API in C#, I ran into a problem regarding null as a value where it would represent two different things:

nothing, e.g. a foo may or may not have a bar
unknown: by default the API response only includes a subset of properties, you have to indicate which additional properties you want. So unknown means that the property was not requested from the API.

After some searching I found out about the Maybe (or Option) type, how it's used in functional languages and how it "solves" null dereferencing problems by forcing the user to think about the possible absence of a value. However, all of the resources I encountered talked about replacing null with Maybe. I did find some mentions of three-valued logic, but I don't fully understand it and most of the times its mentioning was in the context of "it's a bad thing".

I'm now wondering if it makes sense to have both the concept of null and Maybe, to represent unknown and nothing respectively. Is this the three-valued logic I read about, or does it have another name? Or is the intended way to nest a Maybe in a Maybe?


texts: Im sorry if this question has some trivial answer which I am missing. Whenever I study some problem which has been proven undecidable, I observe that the proof relies on a reduction to another problem which has been proven to be undecidable. I understand that it creates some kind of an order on the degree of difficulty of a problem. But my question is - has it been proven that all problems which are undecidable can be reduced to another problem which is undecidable. Is it not possible that there exists a undecidable problem which can proved to have no reduction to any other undecidable problem (Hence to prove the undecidability of such a problem, one cannot use reductions). If we use reductions to create an order on the degree of computability then this problem cannot be assigned such a degree.


texts: Why is the optimum vertex cover problem interesting? Are there practical applications, or is it just another theoretical NP-hard problem?


texts: First-order logic arity defines decidability?

texts:
I've read first-order logic is in general undecidable, and that could be decidable only when working with unary operators. (I think that's propositional logic, correct me if I am wrong)

The question is why arity leads to undecidable problems?

I would like to see some reference material, or at least some simple example of it, as a way to think in this passage from unary to n-ary and why it leads to undecidable problems.


texts: Is Applicative-order and Normal-order evaluation model's definition contradictory as per sicp text book?

texts:
As per this explaination, it defines applicative and normal order evaluation in one form saying:

  This alternative "fully expand and then reduce" evaluation method is known as normal-order evaluation, in contrast to the "evaluate the arguments and then apply" method that the interpreter actually uses, which is called applicative-order evaluation.

while this explanation defines the other way around

  applicative-order language, namely, that all the arguments to Scheme procedures are evaluated when the procedure is applied. In contrast, normal-order languages delay evaluation of procedure arguments until the actual argument values are needed

They seem to contradict each other. Do these definitions mean the same thing?


texts: Turing machine deciding $\{1^{2^n+1} : n \geq 0 \}$

texts:
Plz draw. Turing machine if
Design a Turing machine in the following three ways of descriptions that decide
the language
L = {12n+1 : n ≥ 0},
 the language consisting of all strings of 0s in given
exponential function.
1. The Formal description of Turing machine
2. Implementation level description of the Turing machine
3. High level description of the Turing machine
Some example words of the language are as follows:
a. 11
b. 1111
c. 11111111


texts: What is a good example to illustrate the difference between isomorphic and homomorphic representations?

texts:
I am learning about "knowledge representation" in my intro to AI course and one of the key ideas has to do with isomorphic vs homomorphic representations. The examples I find when I google around are mainly on the topic of mathematical graphs, which are over my head.

Can someone give me a simple, non-mathematical example of homomorphic vs isomorphic knowledge representation to help me wrap my head around the idea?


texts: Is writing a number as two squares and writing the factors of a number equally hard?

texts:
Let $L_1$ and $L_2$ be the following:

$L_1=\{r:\exists x,y \in \mathbb{Z} \text{ such that } x^2+y^2=r\}$

$L_2=\{(N,M): M<N,  \exists 1<d\leq M \text{ such that d|N} \}$

Claim $L_1 \leq_P L_2$

Sketch Proof

If I want to know whether $r\in L_1$.

The number of integer solutions to $x^2+y^2=r$ is given by

$g(r)=\sum_{d|r}{\chi{(d)}}$ where $\chi (x)=sin(\frac{\pi x}{2})=\cases{ 1\text{ when }x\cong 1 \text{ mod }4 \\ -1 \text{ when }x\cong 3 \text{ mod }4 \\ 0 \text{ when } 2|x }$

Then $L_1=\{r: g(r)\neq 0\}$. So then to answer is "$r\in L_1$?" is at most as hard to answer as "what are the divisors of $r$?"

$\square$

What I would like to know is if this is true the other way around. Is it true that if I had a machine which could tell me in constant time whether $r\in L_1$ could I create a machine which could answer "is $(M,N)\in L_2$?" in polynomial time?

Motivations

This question came out of a discussion on this question.

Apologies
I am really just a math.se member who has gotten lost and wandered on to cs.se. Let me know if my question is clear and up to the standards of this site. I am happy to make corrections.


texts:
In directed graph, to find strongly connected components why do we have to transpose adjacency matrix (reverses the direction of all edges) if we could use reversed list of nodes by they finishing time and then traverse original graph.
In other words, we would find finish times of all vertices and start traversing from lowest finish time to greatest (by increasing finish time)?

Additionally, if we do topological sorting on some DAG, and then reverse edges (transpose adjacency matrix) and do topological sorting again - should we get to equal arrays, just in reversed order?

EDIT:
Algorithm description from other topic:
Correctness of Strongly Connected Components algorithm for a directed graph


texts:
I have 2 different datasets with similar objects, one where each object is 50 pixels wide and the other where they are 150 pixels. Each photo is 512x512 for both datasets. These two datasets have the same number of photos. Taken with the same camera, so same focal length, resolution etc...
So far, we agree that only the size of the objects differs.

I segment with U-net, for each dataset. It's all right, I have good predictions.
For fun, I train with 150 pixels dataset and test on 50 pixels dataset, and vice versa.
Again, everything is fine, the results are bad so we deduce that the results are better when the size of the objects is similar. Logical.

Now I train a model on a dataset composed of both the 50 and 150 pixels objects (half 50 and half 150), and in total the same number of images as before.
When I test my model on a set of the images composed exclusively of 50 pixels objects (respectively 150), I get better results than when I trained my network using only 50 pixels object to train (resp 150)
Is this due to scale-(in)variant features issues? Is there a similar case you dealt with ?
Thanks a lot


texts: Given many partial orders, check them for consistency and report any that are not consistent

texts:
Inputs. I am given a finite set $S$ of symbols.  I know there should exist some total order $<$ on $S$, but I'm not given this ordering and it could be anything.

I am also given a collection of assertions.  Each assertion takes the form $s_1<s_2<\cdots<s_m$, where $s_1,\dots,s_m$ form a subset of the symbols of $S$.  The assertion probably won't mention all of the symbols of $S$, just a subset.  Each assertion will probably cover a different subset.

Warmup problem. The starter problem is: Given $n$ assertions, identify whether they are all internally self-consistent, i.e., whether there exists a total order on $S$ that is consistent with all of the assertions, and if so, output an example of such a total order.

The real problem. In practice, a few assertions might be faulty.  Almost all of them should be correct, though.  So, the real problem is: if the assertions are not all internally self-consistent, find a minimal subset of assertions to label as "probably-erroneous", such that if you remove the probably-erroneous assertions, the remainder are all self-consistent.

What I know. I know how to solve the warmup problem (just compute the transitive closure of the union of the partial orders given by each assertion, and check that the result is antisymmetric; or, in other words, create a graph with $S$ as vertex set and an edge $s\to t$ if $s<t$ appears in any assertion, then check for cycles).  However, I don't know how to solve the real problem.  Any ideas?

Real-world parameters. In the application domain where I've run into this, $S$ might have up to a few hundred symbols, and I might have up to a few thousand assertions, with each assertion typically mentioning dozens of symbols.


texts: Given a binary matrix, how to find the starting coordinates of a sub matrix?

texts:
Say, I have an image of bit depth 1 (i.e. binary matrix) and I cropped the image to form a smaller matrix. From the cropped matrix (of a reasonable size). I need to know the starting coordinates from where the matrix was cropped from.

I encoded some lines at regular intervals. The position of the lines follow the equation $y = x^2$. This way when I find the difference between the distance of two lines i.e. $dy/dx = 2x$, I can calculate the value of x and y. This gives me the position of the pixel at that point. So I can subtract the offset and find the starting coordinates.

The multiple lines are for redundancy sake and colours for illustration.

In this way, I can find the coordinates of cropped images of a reasonable size. My question is, "Is there a proper way of doing it?" Also this technique does not work for lossy file compression techniques like jpeg, does a method exist that is more robust?

I have been reading into Space filling curves but I have no idea how to solve this problem using them.

EDIT: I found a thing called m-sequence. I will add it for future reference.


texts: Is it semidecidable to test whether a Turing decidable language is empty?

texts:
I'm not sure how to go about solving this.

I tried this:

Suppose L is a Turing decidable language.
Turing Machine M1 is a decider of L and M2 is a decider of the complement L
We construct a TM U that simulates M1 and M2 on a word w.
For any word w in complement L (this is infinite as it is the set of all possible words), M1 will always reject but M2 will always accept w. However, we cannot test this for all words in complement L as it is infinitely large, therefore it is undecidable.

I'm not sure if that is even remotely correct, would really appreciate some guidance on obtaining the correct answer


texts: Big O Notation Simplification in the fraction form

texts:
How should I approach this one a(n) =  $\frac{n^3}{log^{3}(n)}$. As We can tell that $n^3$ grow much faster than $log^{3}(3)$. All of sudden, not sure what to do, found this [post][1], which is also in the fraction form, Do we calculate out $\frac{n^3}{log^{3}(n)}$ or just pick $n^3$. Eventually, the accurate number is not needed, but I somehow understand what it can simplify to and compare with other Big O,  such as \begin{equation} 2^{n^{0.008}} \end{equation}
      Any hint is appreciated

Sorry for my first typo while using LaTex it is  \begin{equation} 2^{n^{0.008}} \end{equation} instead of  $(2^{n})^{0.0008}$


texts: Is there an example of an oracle A such that P = NP but $\mathsf{P}^A\neq\mathsf{NP}^A$?

texts:
The question is stated in the title, I would like to see a counter example if there is any.
Thanks.


texts: Function that is not Space Constructible

texts:
I'm reading Sipser's Introduction to the Theory of Computation, and I'm reading about space-constructible functions. He gives the following definition:

  A function $f: \mathbb{N} \to \mathbb{N}$ is space constructible if the function that maps the string $1^n$ to the binary representation of $f(n)$ is computable in space $O(f(n))$.

He follows up by saying,

  All commonly occurring functions that are at least $O(\log n)$ are space constructible, including the functions $\log_2 n$, $n \log_2 n$, and $n^2$.

My question:  What is an example of a function that is $\Omega(\log n)$ that is not space constructible?


texts: Finding least number of line segments with length $L$ that cover $N$ points

texts:
The problem is defined as:

  Given $N$ points on an infinite line, find the least number of line segments of length $L$ that cover all points (including endpoints) after changing one point.

That means that if I have the points $P = 1,10,15,28$ , $L = 10$ , 3 line segments are needed , changes will occur that the point $i$ will move to position $X$ , after each change , get the number of line segments needed.

Example:

$P = 1,5,11,21,25$ , $L = 6$
, Changes are

$$
1 , 29
$$

$$
2,36
$$

after change #1 : $P = 5,11,21,25,29$ , number of line segments needed is 3

after change #2 : $P = 11,21,25,29,36$ , number of line segments needed is 4

What would be the best approach to do this? , Given that number of points can be $50,000$ and the number of changes can be $50,000$.


texts: Delivery Algorithm - Find shortest paths

texts:
Given -

A center(lat=x,lng=y) 'C' from which a delivery boy makes a round
trip.
A delivery boy has a bag which may contain at the most 10
boxes to deliver.
A set of points Di (lat=xi,lng=yi) around 'C'
where the delivery has to be done. D=number of Di & 1<=D<=10
Each Di either belongs to time window(30 minutes) W1 or W2 where W1 is
something like 11-30 am to 12 pm and W2 like 12 pm to 12-30 pm
Each delivery has to meet an SLA (service level agreement). Eg-  If the order O1 at drop point D1 belongs to W1 then it must be delivered within W1 window.

Task - Find the shortest time path such that the delivery boy meets SLA for maximum number of orders. The best path is the one where SLA is met for all orders..

I think it will be better if I start with a couple of variations.. Use these variations in dry runs and gather some data for each of the variations..

What I am looking for - Any other cues/variations that I can use.. The greedy approach is already up and running. I am gathering real time data to measure its performance..

CLARIFICATIONS

If SLA's can't be met, do the deliveries still need to be made? - Yes, in those cases the best algorithm will be the one with  minimum SLA breaches..followed by minimum time..

Are there algorithm constraints/metrics (I.E. execution speed, memory used,etc) that must be considered? - Speed - not so much an issue - even if it takes 1 minute to run algo its ok, memory - it may take upto 0.5 gb.. Also if it turns out to be very compute intensive.. I can buy a new machine for running this algo..

Will you need to scale up beyond the relatively small inputs stated - NO. The delivery boys capacity is fixed. It may at the most become 15 (from 10 earlier)


texts: Graph with $\Theta(2^n)$ minimum $(s, t)$-cuts

texts:
Is there any graph with $\Theta(2^n)$ minimum $(s, t)$-cuts?
Given an undirected graph $G = (V, E)$ and two distinct vertices $s$ and $t$ of $G$. A minimum $(s, t)$-cut is a $(S, T)$ cut of G which has the minimum cost over ALL cuts of G, and which also satisfies the additional requirement that $s \in S$ and $t \in T$.   A minimum $(s, t)$-cut does not neccessary have to be a global minimum cut.


texts: How can Lagrange Multipliers and Penalty Method be applied to optimize algorithms?

texts:
I have a programming assignment which I was told that is solvable with some DP algorithm. The question is a variant of LIS problem where at most $k$ exceptions (restarts) are allowed.
But I know that there is a better solution. My professor mentioned Lagrange Multipliers and giving a penalty for each restart. But after googling these terms I wasn't able to find out anything related to algorithms. Every article is about Calculus and function optimization.
I also read about them on Wikipedia but I can't figure out how to use them.
Is there a keyword that can describe better what I want to read?


texts: permuting points for range compression between subsets

texts:
For $k = 0,\ldots, K - 1$, $M_k$ is a subset of $\{0, \ldots, N - 1\}$, and the subsets $M_k$ are not necessarily disjoint. I want to find a permutation on $\{0, \ldots, N - 1\}$ such that the range of values of each subset is as small as possible after permuting everything. Formally speaking, let $\sigma(M) = \{\sigma(m): m \in M\}$, define

$\text{range}(M, \sigma) = \max\sigma(M) - \min\sigma(M)$;

then we want to find $\sigma$ that minimizes the maximum range, i.e.

$\max_k\text{range}(M_k, \sigma)$.

For two subsets $M_0$, $M_1$ the problem is easy: put anything in the intersection of $M_0$ and $M_1$ in the middle of the range, and for the remaining numbers put them in the bottom and top of the range for $M_0$ and $M_1$ respectively. I can imagine how one might build a greedy algorithm off of this idea.

Something that might help in my specific case is that, for any two subsets $M_k$, $M_l$, the size of their intersection (if any) is much smaller than the size of the set in question, i.e. $|M_k \cap M_l| \ll \min\{|M_k|, |M_l|\}$.

I'm not very knowledgeable in CS, so I imagine that this is a well-known problem; what is it called? I'm guessing it's NP-complete in general. What might be some sensible heuristics?


texts: Are there any more complex problems than the Totality Problem that appear in the practical world?

texts: We know the Halting Problem is in the 1st level of arithmetical hierarchy. We know that the Totality Problem is in the 2nd level of arithmetical hierarchy. What are some examples of problems in the 3rd (or higher) level of arithmetical hierarchy. +1 for problems which instances are solved in the practical world (programmers, mathematicians, etc.).


texts: Computing follow sets conservatively for a PEG grammar

texts:
Given a parsing expression grammar (PEG) grammar and the name of the start production, I would like to label each node with the set of characters that can follow it.  I would be happy with a good approximation that is conservative -- if a character can follow a node then it must appear in the follower set.

The grammar is represented as a tree of named productions whose bodies contain nodes representing

Character
Concatenation
Union
Non-terminal references

So given a grammar in ABNF style syntax:

A := B ('a' | 'b');
B := ('c' | 'd') (B | ());

where adjacent nodes are concatenated, | indicates union, single quoted characters match the character they represent, and upper case names are non-terminals.

If the grammar's start production is A, the annotated version might look like

A :=
  (
    (B /* [ab] */)
    (
      ('a' /* eof */)
    |
      ('b' /* eof */)
    /* eof */
    )
  /* eof */
  );

B :=
  (
    (
      ('c' /* [abcd] */)
      |
      ('d' /* [abcd] */)
    /* [abcd] */
    )
    (
      (B /* [ab] */)
      |
      ( /* [ab] */)
    /* [ab] */
    )
  );

I want this so that I can do some simplification on a PEG grammar.  Since order is important in unions in PEG grammars, I want to partition the members of unions based on which ones could accept the same character so that I can ignore order between partition elements.

I'm using OMeta's grow-the-seed scheme for handling direct left-recursion in PEG grammars, so I need something that handles that.  I expect that any scheme for handling scannerless CF grammars with order-independent unions that is conservative or correct would be conservative for my purposes.

Pointers to algorithms or source code would be much appreciated.


texts:
I am reading Handbook of Satisfiability in which they say:

  An algebraic structure, or simply structure, consists of a non-empty set of
  objects existing in the world $w$, called the domain and denoted below by $D$, and
  a function, called an interpretation and denoted below by $R$, that assigns to each
  constant an entity in $D$, to each predicate a relation among entities in $D$, and to
  each functor a function among entities in $D$.

  A sentence $p$ is said to be true in $w$
  if the entities chosen as the interpretations of the sentence’s terms and functors
  stand to the relations chosen as the interpretation of the sentence’s predicates.

In this context, could you help me with some example of predicates of a sentence? And what does "stand to" mean here?

I am not a native English speaker, maybe this is why I can not understand this claim.


texts:
Question:

  Suppose you have a list of integers and it might contain duplicates. Build a Max Heap using this list. Where would the duplicates of the max integer reside in this Max Heap data structure? Where would the duplicates of other integers reside in the heap?

My Answer:
   The duplicates can reside below (as children of) the value considering a heap (tree structure).
Or if we are using arrays to implement this Max Heap, then the duplicates would reside on the indices H[2i + 1] and H[2i + 2] where i is the index of the parent node.

Or we can even make a pointer to a link list of duplicates from that node which has duplicates.

The teacher said that there is another way.

Could you please give me hints on how to do it? Or at least how to answer this question?


texts:
We are given a set of $n$ coins with denominations $v_1,v_2,\ldots,v_n$ and a number $x$.

The coins are to be divided between to persons, with the restriction that each person's coins must add up to at least $x$.

For example, if $x=1$, $n=2$, and $v_1=v_2=2$, then there are two possible distributions: one where Person 1 gets coin #1 and Person 2 gets coin #2, and one with the reverse. (These distributions are considered distinct even though both coins have the same denomination.)

I'm interested in counting the possible distributions. I'm pretty sure this can be done in $O(nx)$ time and $O(n+x)$ space using dynamic programming; but I don't see how.


texts: How to reduce the original partition problem to one of its variation?

texts:
Here's a statement of the set partition problem:
The set partition problem takes as input a set $S = \{ a_1, a_2, ..., a_n \}$(all positive integers). Can $S$ be partitioned into two sets $A$ and $B$ such that the sum of the numbers in $A$ is
equal to the sum of the numbers in $B$?
Here's a statement of a variation of the set partition problem:
Given an input set $S = \{ a_1, a_2, ..., a_n \}$ (all positive integers), can you partition $S$ into $A$ and $B$ such that $| \sum_{i \in A} a_i - \sum_{i \in B} a_i| < 1000$?
My goal is to show that the variation is NP-complete by reducing the set partition problem to the variation, and here's what I've tried:

Given an instance of the set partition, $S$, let the total sum of its elements be $s$, then create a set $S \cup \{ s + 1000, s \}$ as an instance for the variation. But this doesn't seem to do the trick.
Given an instance of the set partition, $S$, do something to the elements in $S$ (for example, multiply by 2, subtract by 1000). This path feels promising but I'm again stuck.


texts: How are variables stored in and retrieved from the program stack?

texts:
Apologies in advance for the naivety of this question. I am a 50 year old artist trying to properly understand computers really for the first time. So here goes.

I have been trying to understand how data types and variables are handled by a compiler (in a very general sense, I know there is a lot to it). I'm missing something in my understanding of the relationship between storage in "the stack" and value types, and storage on "the heap" and reference types (the quotation marks are meant to signify that I understand that these terms are abstractions and not to be taken too literally in such a simplified context as the way I am framing this question). Anyway, my simplistic idea is that types like Booleans and integers go on "the stack" because they can, because they are known entities in terms of storage space, and their scope is easily controlled accordingly.

But what I don't get is how variables on the stack are then read by an application- if I declare and assign x as an integer, say x = 3, and storage is reserved on the stack and then its value of 3 is stored there, and then in the same function I declare and assign y as, say 4, and then following that I then use x in another expression, (say z = 5 + x) how can the program read x in order to evaluate z when it is below y on the stack? I am clearly missing something. Is it that the location on the stack is only about the lifetime/ scope of the variable, and that the whole stack is actually accessible to the program all the time? If so, does that imply there is some other index that holds the addresses only of the variables on the stack to allow the values to be retrieved? But then I thought the whole point of the stack was that values were stored in the same place as the variable address? In my puny mind it seems that if there is this other index, then we are talking about something more like a heap? I'm clearly very confused, and I'm just hoping there is a simple answer to my simplistic question.

Thanks for reading this far.


texts:
Egg drop. Suppose that you have an $n$-story building (with floors 1 through $n$) and plenty of eggs. An egg breaks if it is dropped from floor $T$ or higher, and does not break otherwise. Your goal is to devise a strategy to determine the value of $T$ given the following limitations on the number of eggs and tosses:

  Version 3: 2 eggs and $\sim 2 \sqrt{n}$ tosses.
  Version 4: 2 eggs and $\sim c\sqrt{T}$ tosses for some fixed constant $c$.

  Solution:

  Version 3: find an interval of size $\sqrt{n}$, then do sequential search. Note: can be improved to $\sim \sqrt{2n}$ tosses.

  Version 4: $1 + 2 + 3 + \dots + t \sim \frac{1}{2}t^2$. Aim for $c = 2\sqrt{2}$.

Can someone explain to me versions 3 & 4? And let me know of any resources to go about learning this.

I'm doing Princeton university's algorithm part 2 on Coursera.


texts: Amortized analysis for doubling resizing array is ~3n

texts:
I'm brushing up on stuff related to analysis of algorithms. And I have a question about this PDF I found. This is where I'm confused:

Question 2: What if instead we decide to double the size of the array when we resize?
Answer 2: This is much better. Now, in any sequence of n operations, the total cost for resizing is $1 + 2 + 4 + 8 +. . .+ 2^i$ for some $2^i <  n$ (if all operations are pushes then $2^i$ will be the largest power of $2$ less than $n$).  This sum is at most $2n−1$.  Adding in the additional cost of $n$ for inserting/removing, we get a total cost $<3n$, and so our amortized cost per operation is $< 3$.

How did we arrive at $2n-1$?
I know that the sum of powers of $2$ is $2^{n-1}-2$, but does that matter at all here? I know that $2^{n-1} -2$ is very different from $2n-1$, but I'm not seeing how you can get $2n-1$ from the sum of $1 + 2 + \dots +2^i$  where $2^i$ is largest power of $2$ before $n$ item.
If anyone can give concrete examples, that would be great because that's how I understand better.
I know where the remaining $n$ comes from which makes this whole operation $3n$.


texts: Karp hardness of a clique with given number of outer-incident edges

texts:
A clique in an undirected graph $G(V,E)$ is a subset of vertices $\mathcal{C}\subseteq V$ every pair of which is adjacent $u,v\in \mathcal{C}\implies uv\in E(G)$.

Given a clique $\mathcal{C}\subseteq V(G)$ in a graph $G$, an outer-incident edge of $\mathcal{C}$ is an edge $uv\in E$ with $u\in \mathcal{C}$ and $v\not\in\mathcal{C}$. In other word, an outer-incident edge is an edge connecting one vertex in the clique with one other outside of the clique.

Our problem $\mathrm{CLIQUE}$-$\mathrm{OUTWARD}$-$\mathrm{EDGES}$ is formally defined as:

  Input: An undirected graph $G(V,E)$ and a natural number $k$

  Output: YES if $G$ has a clique $\mathcal{C}\subseteq V$ such that $\mathcal{C}$ has exactly $k$ outer-incident edges, otherwise
  NO

The question is what the complexity of $\mathrm{CLIQUE}$-$\mathrm{OUTWARD}$-$\mathrm{EDGES}$ is.


texts: Definition of Strongly Parsimonious Reduction

texts:
There is a well known definition of parsimonious reduction.

The standard definition of parsimonious reduction is very intuitive. It simply means that the two problem have the same number of solutions, when on input of one of them we applied function $f$.

We say there is a parsimonious reduction from #A to #B if there is a polynomial time transformation $f$ such that for all $x$, $|\{y,(x, y) \in  A\}| = |\{z : (f(x), z) \in B\}|$.

I am interested in definition of strongly parsimonious reduction.

The only definition I found:

"Strongly parsimonious reduction of $R'$ to $R$ is a parsimonious reduction $g$ that is coupled with an efficiently computable 1-1 mapping of pairs $(g(x), y) \in R$ to pairs $(x, h(x, y)) \in  R'$ (i.e., $h$ is efficiently computable and $h(x, ·)$ is a 1-1 mapping of $R(g(x))$
to $R'(x)$). For technical reasons, we also assume that $|g(x)| ≥ |x|$ for every $x$."

The problem is I simply don't understand what this definition means. I tried to separate it to smaller block, but so far with no success. According  to the definition there are two function $g(x)$ and $h(x,y)$ are they are applied simultaneously to two different problem $R$ and $R'$. How the usages of two function can be explained. What is the difference between two reduction, parsimonious reduction  and strongly parsimonious reduction.

I would appreciate any help in understanding the definition of strongly parsimonious reduction.


texts:
Can an IEEE-754 floating point number < 1 (i.e. generated with a random number generator which generates a number >= 0.0 and < 1.0) ever be multiplied by some integer (in floating point form) to get a number equal to or larger than that integer due to rounding?

i.e.

double r = random() ; // generates a floating point number in [0, 1)
double n = some_int ;
if (n * r >= n) {
    print 'Rounding Happened' ;
}

This might be equivalent to saying that does there exist an N and R such that if R is the largest number less than 1 which can be represented in IEEE-754 then N * R >= N (where * and >= are appropriate IEEE-754 operators)

This comes from this question based on this documentation and the postgresql random function


texts: What's the right way to think about a CFG symbol with an infinite null derivation?

texts:
I'm curious about the right way to characterize symbol $A$ in a CFG like this one:

$$
\begin{align*}
A &\to A B\\
A &\to x\\
B &\to y\\
B &\to \varepsilon
\end{align*}
$$

$B$ is certainly nullable. However, should $A$ be considered nullable? It feels like the answer is probably "no" (and most first-follow implementations I've seen either agree or crash on this). However, you can derive an infinitely large parse tree for the null symbol sequence like $A \to A(A(A(...) B()) B()$.


texts: Turing machine - infinite tape - does that thing exist?

texts:
Can we use a Turing machine with infinite tape as a basis to prove anything disregarding the fact that such a thing can never exist?
Do we have the right to regard a machine (a construct) in the same way we regard a number or a set (an abstract)?

If yes could I similarly use a Turing angel with infinite scroll instead, would that be ok?

EDIT: since I cannot comment.
This question is somewhat different from infinity in mathematics because a set even infinite can have a finite representation. On the other hand there is no finite representation for an infinite tape  That is the algorithm that generates the output.

Computation requires resources, that means that it takes place in a time-space, not in an abstract timeless dimension.
While it could be ok to draw on demand more time for the computation pushing on to infinity, space has a cap on the amount of information it can hold, and before reaching that point the tape would revert to write only, that is implode into a black hole. So even if an algorithm is "finite" its output could be big enough to become "unreadable".
For example lets say we have a machine that counts all numbers at some Number H when trying to add more information on the tape the tape colapses forms a black hole and number H+1 becomes unreadable.
Counting up to H+2 is a finite process but cannot be completed.
One could argue that space and time restrictions should not concern us but I m not convinced that is true when dealing with objects embedded in spacetime

I could accept a definition of a machine with sufficiently large tape. But I think that the size does matter.
Can for example 2 Turing machines with different tape-size considered equivalent?


texts: Finding maximum takes at least $\lceil n/2 \rceil$ comparisons

texts:
We are given an array $A$ with $n$ elements, $n \in \mathbb{N}$ and all elements are in the set $\{1,2,3, \cdots, n \}$.

I want to prove that finding the maximum in $A$ (that is, outputting the index at which the maximum is found in $A$) takes at least $\lceil n/2 \rceil$ comparison by assuming that there exists an algorithm that can find the maximum in at most $\lceil n/2 \rceil -1$ comparisons.

I tried assuming that there is such an algorithm, then took as an initial input some particular array $A$ (just a basic one, namely $1,2,3,\cdots,n$) and then tried changing it somehow so that the the algorithm follows the same path in the decision tree, but outputs the wrong index.

I do not know how I should change the array such that we have the same path in the decision tree. Also, maybe this is not the best array to try such a thing.

I thank you in advance!


texts: Reduction — Do they work for unrelated problems?

texts:
I think I understand that a P class problem is reducible to an NP class problem (P≤NP).

I´d like to understand if I need to figure out a potential algorithm which could solve the NP class problem to know if it can be used as a subroutine for a P class problem.

So for example, if I ask you if the problem from class P —sum of integers— is reducible to a problem of class NP —Clique graph problem—, how would you reply to it?

Is this a valid reduction as the more complicated Clique problem is NP and the easier problem sum of integers is a P problem even though they deal with different math branches (one being algebra and the other one being graph theory)?


texts: Printing words starting with a given letter with the least amount of appearances with the print itself being an another appearance

texts:
I've had problems with this one and was unable to solve it on my Algorithms 1 exam:

Input:
-n words
-k letters

Problem:
For each letter print out the one word which starts with that letter and has the least number of appearances. If there are more than one, write the lexicographically smallest one.
The printing of a word counts as an appearance.

Complexity:
Time: O (nlogn + k)
Space: O ( n + k )

This is the first algorithm I am unable to solve in given time complexity and it is driving me crazy.

Appreciate the help!

Example:

n=6 words:
dog bark dog woof doggy doggy

k=2 letters and corresponding outputs:
d - 2 is the least number of appearances of a word starting with d , dog and doggy - dog is the lexicographically smaller one so we print dog

if we say d again, since we printed out dog, that counts as another appearance so the only word appearing twice is doggy, and we print that one


texts: Effective computation on linear data without random access

texts:
recently I've started thinking about caching problems in modern CPUs, where they struggle to adequately fetch program data (not instructions) in time, so that it can be computed further.
   So then I came up with the idea, why don't we restrict random access on program data and make it all as a continuous stream (input and all eventual locals), which moves strictly in one direction through some "processing head", where you only have a possibility to read in some x amount of symols, write, let through and append symbols at the head position (this is a data stream, not an instruction stream).
The question is, whether you can effectively run computations in that system:
    Is it possible to order all functions and allocate all local data/variables at compile time in such order that they will produce usable stream of data for all further functions, so that you will never need to "loop" the tape to access some particular element? (thus, emulating random access, by waiting for desired element to come by)
I've tried to look up this topic on the internet and found nothing. And maybe it is because this idea is obviously stupid, so no one bothers with it :)
Thank you for your help!


texts: Bounded pairwise distance on moving points

texts:
Suppose you're writing a video game that takes place on a large rectangle (2d).  You have a large list of entities (monsters, spells, and so forth, represented as points) living on this rectangle, and you need to know which pairs are within Euclidean distance 1 of each other, and for each such pair, what their distance is, so you can figure out how each affects its neighbors.  This information must be updated every frame of the game.

In this particular case, the entities are moving rapidly, but we can assume that they often retain their relative positions.  For example, groups of them may move in formation, or entities may move like cars on a highway.  We can also assume that their minimum distance has some bound, or at very least, there is an upper bound on the number of neighbors each node can have.

Brute force is O(n^2) per frame.  Using a data structure such as a KD-tree or a Delaunay triangulation, we may be able to improve that to O(n log n).  But since the relative structure of the group is roughly constant, is there a way to achieve typical-case linear time?

If I were to get serious about this problem myself, I'd start with a Delaunay triangulation, see if I could use it to efficiently find the pairs of points of less than unit distance, and then see if there was an efficient way to use the previous frame's Delaunay triangulation to accelerate generating the current frame's triangulation.

This is mostly academic for me, since my tests in Python so far reveal that brute force has the best wall clock time.  But surely I can't be the only person curious about this problem -- anyone who has ever written a game must have given it some thought.  SciPy's KDTrees can produce the data I'm looking for with sparse_distance_matrix but the wall clock time for building and querying a KD tree was much worse than brute force in the cases I tried.  Perhaps KDTrees involve more Python and less C than the brute force code I used (scipy.spatial.distance.pdist), or perhaps the time coefficient for the KDTrees is just very high on its own.


texts:
I'm working on nandgame's website found here. I'm working on the ALU and here is an image of my implementation:
My Implementation:

And I compared it to this website's solution:
Solution

However when I try to submit this... The website gives me this message and error:

And for the life of me, I don't see where any of the connections are misplaced... Maybe a second set of eyes might help...
Edit
I even tried the solution from this website:programmersought and I still can't seem to get it to accept it as being correct... It's giving me the same exact error message as above. Could this be a potential bug on the website app?
I even posted this issue to Github's solution page found here regarding this...


texts: Proving a randomized algorithm that sums array elements

texts:
I am trying to prove the following algorithm to be correct:

Sum(A[1..n], s)=
    sum = 0

    for r=1 to s
        i = some random index i in interval [1, n]
        sum = sum + A[i]

    return n(sum/s)

where A is an array consisting of $n$ integers, where each integer A[i] belongs to the interval $[1, M]$ and $s=1/\epsilon$ ($\epsilon$ is some constant) is a fixed integer value.

Simply put, the algorithm wants to estimate the sum of all array elements that are contained within A by sampling $s<n$ random elements. Afterwards, we then take an arithmetic average over those s sample values and then multiply with number of array elements (i.e. $n$) to get the estimated sum of all array elements.

I was advised by some people I know to check into either of Chernoff's bound and Hoeffding's inequality to prove a randomized algorithm, but I am not sure about how to apply them on this randomized algorithm (I am not experienced with proving randomized algorithms and thus I maybe need a few guidelines here to better understand the application of them).

If it is none of them, then what other alternative theorems are there to use to prove this algorithm to be correct?


texts: Solve the recurrence $a_n - 3a_{n-1} + 2a_{n-2} = 6 \cdot 2^n$

texts:
Consider the recurrence

  $$ a_n - 3a_{n-1} + 2a_{n-2} = 6 \cdot 2^n. $$

I tried to solve this as follows. First, I found the homogeneous solution:
$$
a_n^{(h)} = r^2 - 3r + 2r \\
(r-2)(r-1) = 0 \\
r = 2,1 \\
a_n^{(h)} = A \cdot 2^n + B
$$

While trying to solve for the particular solution (adding $n$ for linear independence), I get an answer which is a false statement:
$$
a_n^{(p)} = Cn2^n \\
Cn2^n - 3[C(n-1)2^{n-1}] + 2[C(n-2)2^{n-2}] = 6\cdot 2^n \\
4Cn - 3[2Cn-2] + 2[Cn-2] = 6 \cdot 2^2 \\
4Cn - 6Cn + 6 + 2Cn - 4 = 24 \\
0Cn+2 = 24 \\
0Cn = 22
$$

I’m not sure where the issue lies. Am I performing the problem incorrectly, or does the problem have an issue?


texts:
I've been looking at implementing a local rate limiting solution satisfying certain guarantees. I've found surprisingly little literature on the extensions of the token bucket algorithm to hierarchies. I'm hoping that someone would know the name of this algorithm and similar algorithms for solving the same problem as well as know any analysis of right approach for "donating" tokens to your parent.
Assume that we have request handler A and request handler B handling e.g. HTTP requests and handler A is given 40% of the capacity while B is given 60%. Assume the server can handle 10000 requests / second and we want to donate any unused capacity. In other words, if A doesn't currently need much capacity, but B is going over the limit, B can take any capacity unused by A. The rate limiting algorithm I've thought about would then work as follows with a 1 second window:

Have a root bucket R with child buckets A and B.
Each second A is reset to contain 4000 tokens and B to contain 6000.
A and B can choose to donate some of their tokens to the root bucket R.
If A or B is out of tokens, the respective handler can borrow tokens from R.

The actual interesting question is now the logic for how many tokens A and B choose to donate to R. Some approaches I can think of:

Donate unused: If e.g. A only tried to use 3000 tokens during the previous window, then donate 4000-3000=1000 tokens to R.
Exponentially moving average: Donate an exponentially moving average of how many donated last time and how many were unused last time around (the first is a special case of this).

There's some tradeoff here between donating too many tokens if traffic ends up increasing and donating too few if traffic is dropping. Another concern is efficiency, i.e. using as few locks as possible for the implementation.
Does anyone know any papers that discuss algorithms similar to the one above?


texts: How to Determine Existence of Turing Reducible Languages?

texts:
Are finite and recursive instances of $L$ possible with the following constraints?

$\text{L $\subseteq$ {0,1}*}$ and $L \leq HALT \leq \overline L$ where $\overline L = \{\text{ x $\in$ {0,1}* : x $\notin$ L }\}$.

NOTE: Raphael and Yuval kindly pointed out that I was overlooking $\overline L$ is undecidable. Aside from this oversight, are there any other issues, e.g. conceptual misunderstandings, logical fallacies, etc. in the explanation below?

As I understand it:

A finite instance of $L$ is possible. Since the language is finite, an evaluating Turing Machine (TM) could not loop indefinitely on input, and consequently would halt either in an "accept" or "reject" state. Since the language stops on all inputs, it is recursive and thus can be reduced to $HALT$, which is recursively enumerable.
Since a finite instance (which is recursive) is possible, logically a recursive $L$ must also be possible.


texts: How to solve Bluetooth intermittent connectivity in multi hop communication?

texts:
In a specific area mobile devices are connected with Bluetooth multi-hop connectivity with intermediate mobiles for data communication purpose as per in below figure.

Now in scene 1 from source (MD1) to destination(MD5) all devices are working fine, so data reached destination successfully.
And in scene 2 from source (MD1) to destination(MD5) MD3 disconnected, so data failed to reach destination.
Let consider some other mobile devices are available at different distances in that area.
My question is

How to solve the scene 2 problem?

Is mobile device clustering technique helps to solve this problem?

Thanks.


texts: How to get the calculate the binary logarithm of a fixed-point number with 18 decimals?

texts:
Suppose that:

You're using a programming language that doesn't support fixed-point or floating-point numbers.
The said programming language rounds down divisions, e.g. 12 / 5 = 2.
You're adding 18 trailing decimals to represent fixed-point numbers in your algorithm. for instance, you'd represent 0.5 as 500000000000000000, equivalent to 5e17 in scientific notation.

Now, say you want to calculate the integer part of the binary logarithm of a number x that adheres to the format above.
If x is greater than or equal to 1e18, then the calculation is easy: you just divide x by 1e18, and calculate the most significant bit of the rounded down result. For example, 4e18 / 1e18 is 4, of which the msb is 2. The integer part is thus 2.
But what if x is between 0 and 1e18 (both exclusive)? For example, 1e17? The binary logarithm of a number between 0 and 1 is negative ..


texts: How does automatic differentiation work?

texts:
What is the intuitive idea behind automatic differentiation?

If I have a program which computes $f(x, y)=x^2+yx$, which steps lead to the program which computes the derivative $df/dx$ of f?

double f(double x, double y)
{
    double res = x*x;
    double res2 = x*y;
    double res3 = res + res2
    return res3;
}

If I read the corresponding Wikipedia entry correctly I need nothing besides the chain rule, but I don't understand how this can be done in practice.

My understanding so far is that I use a table of the derivatives of all involved basic functions, such as:

$dx/dx=1$
$dy/dx=0$
$d(x*y)/dx=y$
$d(x+y)=dx/dx+0$
$d(x^2)/dx=2x$

How do I get the final function from this?

I would expect something like this:

double f(double x, double y, double* dx)
{
    *dx = 0;
    double res = x*x;
    ? *dx = 2*x ?
    double res2 = x*y;
    ? *dx = *dx ?
    double res3 = res + res2
    ? *dx = ??? ?

    return res3;
}

Edit: I have found this video "Beautiful Differentiation" of a talk at the International Conference on Functional Programming (ICFP) 2009, by Marcom Wallace which explains the topic quite well.


texts: Should your heuristic for an A* search algorithm be the same scale as your actual weights?

texts:
I'm a bit confused about the scale of heuristics for implementing A* search. $f(n)$ is the total cost of travelling to a node $n$. It is calculated by $f(n) = g(n) + h(n)$. $g(n)$ is the cost of the path to node $n$ from the source node. $h(n)$ is a heuristic function that estimates the cost of the cheapest path from n to the goal. (Roughly summarised from the wikipedia article on A*)
My question is should $h$ and $g$ be on the same scale? e.g. if g(n) to node n is 10 is it ok if the h(n) is 800?
I've read some conflicting takes on it where one example of using A* for plane routes had $g$ values in the range of 10-50 but $h$ values in the range 100 - 900 but elsewhere I read that they should be the same scale to avoid changing an A* search into a greedy best first search?


texts: Are all Deterministic Finite Automatons also Non Deterministic Finite Automatons?


texts:
Problem statement: Given a graph G(V,E) which is not acyclic and may have negative edge weights (and thus may possibly have negative-length cycles), how does one detect if the graph has a zero-length cycle, and no negative-length cycles?

Background information: The question came up when I tried to implement in code the solution to what is called the "tramp steamer" problem: Given a graph G(V,E) in which each node is associated with a cost $c_i$ and each edge is associated with a time (number of days) $t_i$, find the cycle with the smallest ratio of cost to time $\frac{\sum_i(c_i)}{\sum_i(t_i)}$ (i.e. minimal cost/day cycle).

One solution is to do a binary search with the range of possible rations, trying to identify the minimum cost-to-time ratio $\mu$. In each iteration of the binary search in the range $[left...right]$, you "guess" a value of $\mu = \frac{left+right}{2}$ and then run Bellman-Ford:

if a negative cycle exists then the value of $\mu$ is too high; the range is reset to $[left...\mu]$
if all cycles are positive then the value of $\mu$ is too low; the range is reset to $[\mu...right]$
if there is a zero-length cycle (with all other cycles being positive), then we have found the best value for $\mu$ and we can stop, returning the zero-length cycle as the answer

How exactly is the third case detected? Assume the graph A->B->C->D->{A,B}  with two cycles (fro D back to A or B) where the cycle B->C->D->B is the optimal one and yields zero length for some selection of $\mu$ for which the other cycle is positive. Suppose we happen to try this particular value of $\mu$ (let's assume it's during the very first iteration because we got lucky). If I am using vertex A as the fixed point from which I run Bellman-Ford on each iteration, it will complete successfully without detecting a negative cycle. But how would the zero-length cycle be identified?

Currently I only handle the first 2 cases and my implementation keeps iterating until the $[left...right]$ range becomes becomes too small, so that floating point precision can't handle a smaller range. At that point I detect that $\frac{left+right}{2}$ is equal to one of the range limits (either left or right) and stop the binary search. How would I go about detecting that a particular value of $\mu$ has produced a zero-length cycle?


texts:
I want to normalize elements in an array. The solution I found is to take the sum of the elements and divide each element with this total. Can you find more efficient way of doing this?

The runtime I achieve is 2N. Any better idea?

normalize(array)
{
   sum = 0;

   for i = 0 to array.size() do
      sum += array[i];
   end

   for i = 0 to array.size() do
      array[i] /= sum;
   end
}


texts: k-th smallest element in sliding segment

texts:
Consider an array $a[1\ldots n]$ and another array $l = a[0]$ (initial value). At each turn we may add next element to array $l$, or remove first element from array $l$. F.e. after first iteration it could be empty or could become $a[0, 1]$. We want to find k-th smallest element at each iteration in array $l$.
First of all if size of $l$ is less than $k$ the answer is 'No'. Let's consider more interesting case.
I've decided to have two heaps (one min and one max heap).
Max heap contains all k-th smallest elements from $a[l..r]$ and min heap contains elements which are greater than the k-th smallest element. Then answer is head of max-heap (we can take it in O(1)).
But there is a small problem. What if need to consider $a[l+1 .. r]$ (so we need to push left bound). Now of course if $r - l < k$ the answer is 'No', but what should we do otherwise? I thought we should do following: if $a[l] > maxheap[0]$ then the answer doesn't change (because we will delete element greater than k-th smallest element), but what should we do with our heaps? Unfortunately I can't delete in heap by position (it takes a long time). The best we can do is delete root node in O(log n). How should I affect them?


texts:
I have an array of length $n$ representing a time series of data. I want to implement a moving (sliding) window of length $k < n$ and calculate things like sliding median, sliding quantile, sliding trimmed mean, etc. Each of these requires the data to be sorted prior to calculating the statistic of interest.

Therefore I need a data structure which has the following 2 properties:

It must easily allow a new sample to be added and the oldest sample to be deleted as the window slides along the time series.
When a new sample is added, it should efficiently insert the sample into a sorted position in the data structure, so that things like the median and trimmed mean can easily be computed.

For #1, I am currently using a ring (circular) buffer of length $k$. This makes it easy to add new samples and overwrite old samples in $O(1)$ time simply by updating the head and tail pointers of the buffer.

For #2, I had thought to keep a separate array called perm to keep track of the permutation of the ring buffer entries needed to sort them. In other words, if array is the ring buffer array with head and tail pointers, then array[(head + perm[i]) % k] is the sorted array for i = 0,...,k-1. I tried using an Insertion Sort algorithm to update the perm array each time a new sample is added to the sliding window. The code for this is below.

/* sort ringbuf entries with insertion sort algorithm */
void
ringbuf_isort(const ringbuf *rbuf, int *perm)
{
  const int n = ringbuf_n(rbuf);
  int i, j;

  for (i = 1; i < n; i++)
    {
      int id = perm[i];
      double v = rbuf->array[(rbuf->head + id) % rbuf->size];

      for (j = i; j > 0; j--)
        {
          if (rbuf->array[(rbuf->head + perm[j-1]) % rbuf->size] < v)
            break;

          perm[j] = perm[j-1];
        }

      perm[j] = id;
    }
}

This code works correctly and sorts the ring buffer entires, however it is far too slow. I have tracked the slowdown to the modular arithmetic (rbuf->head + id) % rbuf->size in each loop iteration. This can be moderately improved by doing a comparison of id < head ? head + id : head + id - size, but this is still too slow.

In fact I have found it is faster to simply copy the ring buffer entries to a linear array and use a quicksort algorithm than using the above code.

Can anyone suggest a data structure which will solve the sorting problem and still be fast?


texts:
I'm implementing push contour feature for web application. It is an ability to change the contour by touching it. Mouse pointer becomes a circle that bumps contour (like in Photoshop). Contour is polyline object and pushing circle is some point with defined radius.

Sequence of actions on mousemove is following:

Detect points in polyline that are closer to pushing point than defined radius
push those points or just draw circle segment in the defined area.

Questions:

How to determine points that are need to be pushed? I can iterate all segments in polyline (300-600 segments) and calculate distance for each like here: https://gist.github.com/mattdesl/47412d930dcd8cd765c871a65532ffac . But in this case full iteration 60 times per second is quite performance hard. May by some algorithm can do it more afficient?
How to push the point? we can't just change it position. As 1 point finally can become 2 points. It is more like drawing circle segment.


texts: Can high-order unification be applied to programming by example?

texts:
In 2007, it has been proven that high-order unification is decidable on the pattern matching case. If that is true, what is stopping someone to write an equation like:

(F [1,3,2], F [4,1,3,2], F[3,1]) = ([1,2,3], [1,2,3,4], [1,3])

If the unification works, wouldn't it probably find an F which implements a sorting algorithm - essentially generalizing the programming by example technique and, to an extent, replacing a programmer's job?


texts: Efficient serialization/deserialization of huffman tree

texts:
I have implemented huffman encoding in the form

struct node
{
    node * left;
    node * right;
    double freq; // the frequency
    string letter;
    string binary_code; // the variable length code
};

that works fine, eg:

Data: electric eels
Compressed: -σ» //doesnt render in this text editor sorry
Decompressed: electric eelss
Ratio: 38%

But I have no idea how to efficiently encode the tree itself (needed for the decompression) to send over socket, and then decode it.

Can someone help me with some c code/pseudocode style explanation?

Any help appreciated.


texts: Convert an IF statement in Mixed Integer Programming

texts:
I want to convert an IF statement for my optimization problem. I want to minimize the total price. I want 800 tones of salt and 3 suppliers offer me their prices.
Supplier $1$ offers me $100$ tones at $\\\$150$ a tone.
Supplier $2$ offers me $400$ tones at $\\\$170$ a tone, if I take $300$ tones (or more)the price drops to $\\\$150$.
Supplier $3$ offers me $1600$ tones at $\\\$170$ a tone.
Here is my model without the if statement :
$x_i$ is an integer variable representing the quantity bought to the supplier $i$,
$p_i$ is the price of the supplier $i$, $c_i$ is the maximal capacity offered by the supplier $i$.
$Min( p_1\times x_1 + p_2\times x_2 + p_3\times x_3)$
$s.t.  x_1 + x_2 + x_3 = 800$
$ x_1 \leq 100$
$ x_2 \leq 400$
$ x_3 \leq 1600$
Now I want to use the Big M method the convert my if statement but I don't know how to do it.
I tried this method : Express a "complex" IF-Statement to Linear Programming to find the constraints but I don't know how to modify my prices. I tried this :
If $x_2 \geq 300$, Then $p_2 = 150$, Else $p_2 = 170$.
i.e.
If $x_2 \geq 300$, Then $b = 1$, Else $b = 0$ and $p_2 = 150b + 170(1-b)$
In addition to this I code in python the the mip library, do you know a better library to do this?
Thanks a lot !


texts: Can we implement every algorithm using only immutable variables?

texts: Can we implement every algorithm using only immutable variables such that their space and time complexity is the same as using mutable variables?


texts:
This line from Wikipedia made me want to ask this question:

  There is, however, no general procedure for determining whether an expression involving looping instructions will halt, even when humans are tasked with the inspection. The theoretical reason for this is the undecidability of the Halting Problem: there cannot exist some algorithm which determines whether any given program stops after finitely many computation steps.

Wondering what this is and what it means. Why is the Halting Problem undecidable. I don't understand, I feel like I could tell if a program terminates or not. Wondering what an example is of a program you can't tell will terminate or not.


texts: Can one truly build a schedule from graph coloring?

texts:
I know that with graph coloring we can build a simple schedule with maybe 9 students and 9 lectures (i.e. these notes) and determine the minimum number of meeting times, but is this feasible in a real world scenario? Say I have 30 professors and 200 students, can we determine a minimum number of meeting times with a graph this size? And does the graph tell us when they need to meet? Pointing to any available examples would be greatly appreciated.

In addition, could the graph take into account some lectures twice as long as other lectures?


texts: Implementing an efficent priority queue using only stacks

texts:
Is it possible to implement an efficient priority queue (as efficient as a heap) only using the stack data structure?

The usual efficiency for a priority queue which is implemented using a heap is :

get min - $O(1)$
extract min - $O(\log n)$
add - $O(\log n)$

Would it be possible to do something with the same complexity using only stacks?

I want to implement A* (which uses a priority queue to prioritize nodes) as a pathfinding algorithm inside Minecraft, but Minecraft doesn't allow random access, and the most efficent dynamic structure that can be implemented in it is a stack.


texts: Is it really possible to prove lower bounds?

texts:
Given any computational problem, is the task of finding lower bounds for such computation really possible? I suppose it boils down to how a single computational step is defined and what model we use for the proof, but given that, do we really prove a lower bound then in general? What I means is that can we prove something like "problem $X$ cannot be solved faster than $t(X)$ time" rather than "problem $X$ can be solved in $t(X)$ time or faster"?

I have tried to find information specifically on lower bounds and proofs of them, but I can't really find any of interest, any recommendations on books/papers/websites on the subject?


texts: Logic applications and security protocols references request

texts:
I'm a student of logic and I'm interested in looking at logic applications, of which I am told there are many, in computer science and allied areas. I've seen some applications. More specifically, I keep seeing little things about security protocols which use logical methods. I'd like to learn some more about this material, although I suspect it may require I obtain a knowledge of networks and cryptography which I currently lack (although hopefully not for long!). I have recently obtained Ryan and Schneider's textbook on Security Protocols.

Are there any other suggestions for reading and self-teaching in this and / or other areas in computer science which use logical techniques  / formal methods? (I expect there are many; just looking to be pointed in a couple of amenable directions which are reasonable for someone who knows some pure logic.)


texts: Why don't Artificial Neural Networks Commonly Diverge?

texts:
Introduction:
I'm using divergence here as to mean that the gradient is getting further and further from zero in stochastic gradient descent. I've written my own feed-forward neural network and tried to use it to solve several incredibly basic problems of binary classification such as:

Being given two random real numbers from zero to one and having the first neuron in the output layer have a higher net output if the two numbers add up to be greater than 1 and else having the second neuron have a higher net output.
The same problem as the first but the two numbers have to add up to at least 2 (which is impossible).

My visualisation:
In the case of both problems the network does succeed at solving them within a couple of seconds. Since it's binary classification I made a way of visualising the data similar to Tensor Flow Playground which you can see in the following image:

The light blue area represents area which the network believes has met the condition
The dark area is area that according to the network has not met the condition
The red and blue circles represent training data. (There are 200 individual pieces of training data). The red circles are ones that fail to meet the criteria and vice-versa.
The error at the bottom is updated after every backpropagation step.
My settings:
Weights and biasses are randomly generated between 1 and -1 and activation functions are linear. Batch size is 50 and backpropogation happens 10 times per second. Quadratic Error function is used.
My problem:
Once the network solves the problem (or gets quite close, better than in the picture.) The error stagnates for a second or two before jumping to something massive like 400 (When I say jumping, it goes up really fast but it does climb it's not instantaneous). Then over a second it works its way back down to 1. After a second it works its way back down to something manageable like the error in the picture. Then this continues several times until eventually the error climbs a bit too high goes past infinity and ends up as NAN.
With reference to the visualisation: The line between the dark and the light-blue jumps back and forward rapidly from either side only once it gets close to the answer. Then it either settles back down close to the solution or the solution or if the error goes to NAN it goes entirely light blue or entirely dark.
My diagnosis:
Obviously the weights and biasses follow suit. It appears to me that the network is overshooting steps once the error gets really small, making the error bigger, the gradient bigger, the weights bigger, the biasses bigger and thus the next error bigger. If by chance this continues it will eventually snow ball in to an unstoppable divergence.
Before you say, "make your learning rate smaller!":
I've tried learning rates of 0.0001 to no prevail, it just takes a bit longer to go wrong. I've also tried a learning rate that scales down as the error does: return (error > 0.7) ? 0.05 : Math.pow(error,0.8) / 14;
My question:
My question here is what could be wrong? Based on my paragraph where I tried to explain what I thought the problem was myself is there something wrong with my fundamental understanding of how backpropgation should work that I could have transferred into my algorithm? My biggest question is why doesn't this always happen in people's neural networks. How do you stop divergence inevitably happening be sheer probability? What part of this am I not correctly understanding?
If you read all this I'm eternally thankful... I'd love if you'd share whatever knowledge you have. Thanks in advance.


texts: Time complexity in relation to data size

texts:
Not sure if I completely understand this problem that was presented in class.
We were given function $$f(n) = 2*f(n-1) + n$$
The base case for all these functions $f(1)$ is equal to 1.
Assume $T(x)$ is equal to the running time of $f(x)$.
Recurrence of this algorithm is solved as $$T(n) = T(n-1) + 1$$

This is bounded by $$T(n) = \theta(n)$$

I thought this was the time complexity, but then we were given that the
time complexity, where time complexity = $TC(r)$, in relation to the size of the data is: $$TC(r)=\theta(2^r)$$
I read somewhere this has to do with bits possibly, but I'm not sure how they got to this bound. Space complexity, where space complexity = $SC(r)$ was also given as: $$SC(r)=\theta(2^r)$$


texts: Data hazard after in load word after addi

texts:
5 stage pipline

addi $t1,$zero,0x30
lw $t2,0($t1)
sw $t2,0xff18($zero)
addi $t2,$zero,100

Question is to find hazards existing in the code and the answer is:

Hazard 1: Between lines 1 and 2. Register t1. Solved using
forwarding.
Hazard 2: Between lines 2 and 3. Register t2. Solved using
forwarding.

But I found the answer is rather strange,

So there is a hazard between line 1 and 2, in the first line t1 writes back in the fifth stage, and in the second line t1 uses in the decode stage, in my opinion there should be a stalling first and then forward to have access to t1 in the second line.
I don't see a hazard between line 2 and 3? line 2 t2 write back in the fifth stage, and line 3 fetches t2 in the first stage

Am I thinking something strange, why the correct answer seems not correct to me?


texts: Why is $n \log \log n$ not tightly bounded by $n$?

texts:
I don't understand why $n \log \log n $ is not $\Theta (n)$.

Suppose we give $n$ a value of $10,000$. Then $n \log \log n$ is $6020.6$. So isn't $n \log \log n$ upper- and lower-bounded by $n$, as $n \log \log n \geq Cn$?