texts: Data General MV/8000 virtues of "No mode bit"

texts:
I'm reading Tracy Kidder's "The Soul of a New Machine" where a team at Data General design a new machine (codenamed "Eagle", later named MV/8000). It is 32-bit extension of a previous architecture (the 16-bit Eclipse). One of the revolving themes seems to be, that they don't want to create a machine with a mode bit and that they succeeded in this.

However, it leaves out how this is technically achieved, and it also doesn't go into why it was so attractive to create a machine without a mode bit. The book is not a technical book so it could be that the details were somehow distorted. However, you get the feeling reading that book that a "mode bit" solution was common (and hence feasible) at the time, but was deemed unattractive by the engineers maybe for aesthetic reasons. The book also makes it seem like an immensely difficult task to create a design without a mode bit, which was somehow overcome by this particular team.

I found this description of how it was achieved:

http://people.cs.clemson.edu/~mark/330/kidder/no_mode_bit.txt

It seems to basically be about using a previously unused portion of the opcode space for the new instructions. I must admit I was a bit disappointed that it was "just that". Also I think this still leaves some questions unanswered:

Firstly, how did the 16-bit processes live in the 32-bit address space? Because I think that is the key challenge in making a 32-bit extension "without a mode bit". Extending the instruction set, on the other hand, is a relatively common undertaking. Since there's no description of how it happened one could assume that the 16-bit code simply access memory as it always did, maybe it sees some type of virtualized/banked view of memory (with new CPU registers controlling where the first address is) or something like that. But I don't know if there's more to it than that. In that case one could argue it sort-of was a "mode bit" solution. The 16-bit mode processes could run alongside the other processes by virtue of special features added to the CPU. Whether this might imply a new bit in a control register or just some new added control register is unclear.

Secondly, why was it so appealing to create a machine without a mode bit? Many  of the benefits touted in the book is that customers wanted to run old software. But this doesn't seem to speak against a mode bit, since the whole purpose of using a mode bit is to have backwards compatibility. When AMD extended x86 to 64-bits, at least according to my understanding of the word "mode bit" what they did was exactly to add a mode bit. A special bit that would make the CPU in 64-bit mode. And another bit that would make a process execute in a "sub-mode" of the 64-bit mode (to enable compatibility with 32-bit applications). The essence of the submode is that the CPU interprets the instruction stream as the old 32-bit instructions but that the 32-bit memory accesses made are resolved using the new page tables format (setup by the 64-bit aware operating system) and eventually mapped to the full physical address space. Also, the 32-bit code can be preempted by 64-bit code. Like the Data General solution this also allowed a 32-bit program to run along under 64-bit programs (16-bit vs 32-bit in the DG case). So from a customer point-of-view there appears to be no difference at all. Hence the only benefit could have been in the implementation, simplifying the design, but the book doesn't make it sound like that is the concern, since the mode bit seeemed to be common even at that time (and it seems later architectures have also employed it as the x64 case shows).

I'm sure there's something I missed, so it would be great if someone could discuss more on the technical details and virtues of this "no mode-bit" design.


texts:
As i See in ML Course a VC dimension calculation is very theoretical.

What is the VC-dimension of intervals in R?

The target function is specifieed by an interval, and labels any example positive i it lies inside that interval.

Answers:

VC-dim = 2. A set of two points can be shattered, since there's only a single block of positive examples that could lie within the interval. But no set of 3 points can be shattered, because it can not be labeled in alternating +; - ; + order.

so i'm get stuck with meaning of interval.

for example, it means {(a, b) | "a is lower than b", a,b is real number} has VC-dim = 2?

Any idea or solution would be highly appreciated.


texts: How to compute the Cycles in a pipelined single cycle processor

texts:
I'm an undergrad studying computer engineering and I'm in my first of many courses on computer organization/architecture. In the lectures and online I see diagrams like the one pictured below from the university of washington. In general, it seems that the number of cycles in a single cycle pipelined architecture can be derived by the equation
$C = \text{stages} + \text{Instruction Count} - 1\\\\$
That seems to fit with the diagram, each instruction must pass through the same 5 stages. The first instruction has no idle resources and so must use clock cycles equivilent the number of stages. Each other instruction may take advantage of the idle resources and so must only add a single cycle each to process.
My first question is whether my understanding is correct. My second question is what would happen if one of these instructions encountered a data hazard and was forced to stall? How would that affect the number of cycles required? I assume it would go up 1 cycle per stall, but I don't know for certain.


texts: Fastest algorithm that determines whether a given DFA is minimal?

texts:
NOTE - I can't find a good answer in the Similar question above ^

Given a DFA, is there a fast algorithm that determines whether it's minimal?

I'm looking for an algorithm that works faster than just minimizing the DFA and checking if the number of states changed. i.e, faster than Hopcroft's O(nslog(n)).

I already find the question here, but there was not any solution there.. No algorithm was presented as a solution.


texts: Making feature vector from Gabor filters for classification

texts:
My aim is to classify types of cars (Sedans,SUV,Hatchbacks) and earlier I was using corner features for classification but it didn't work out very well so now I am trying Gabor features.

code from here

Now the features are extracted and suppose when I give an image as input then for 5 scales and 8 orientations I get 2 [1x40] matrices.

1. 40 columns of squared Energy.

2. 40 colums of mean Amplitude.

Problem is I want to use these two matrices for classification and I have about 230 images of 3 classes (SUV,sedan,hatchback).

I do not know how to create a [N x 230] matrix which can be taken as vInputs by the neural netowrk in matlab.(where N be the total features of one image).

My question:

How to create a one dimensional image vector from the 2 [1x40] matrices for one image.(should I append the mean Amplitude to square energy matrix to get a [1x80] matrix or something else?)
Should I be using these gabor features for my purpose of classification in first place? if not then what?

Thanks in advance


texts: Construct a Circuit computing all boolean functions over n bits

texts:
Let $ n∈N $ . Construct a circuit with $ C_n(x_1,\dots,x_n) $ with $ 2^{2^n} $ outputs $ y_1,\dots,y_{2^{2^n}} $ which computes all
  distinct boolean functions $ f_i:\{0,1\}^n→\{0,1\}$ such that $ y_i $ is the
  output of $ f_i $ and satisfying $ Size(C_n)\in O(2^{2^n}) $

Remark: The circuit is in a model of fan-in 2.

I've already found a solution in $ O(2^{2^n + n}) $ but I can't find less even recursively.


texts: Find one-variable recursive formula for running time of Karatsuba multiplication

texts:
I'm currently trying trouble to set up the recursive expression for the Karatsuba multiplication of two integers with $n$ and $m$ bits (both having a different number of bits). Usually, the recursion for two $n$ bit integers for Karatsuba multiplication would be:

$T_{n} = \begin{cases} 3T_{n/2} + cn &\mbox{if } n > 1 \\ 1 &\mbox{if } n = 1\end{cases}$

However, when working with two integers with different number of bits, the expression would be different, as we would have $T_{n,m}$ as a recursion. Is there any way to reduce the problem of setting up the recursion in terms of only one variable $n$? I was thinking of letting $T_{n}$ be the maximum number of operations with the pairs $(n,m)$, and basically giving the same recursive formula as stated above. Would that change the running time of the program or is there a more clever way to change it into a one variable recursion?


texts: Performant algorithm to find edges without cross overs

texts:
I have a series of graphs with points plotted like this:

Like in the image, I need to join these points to create a complete edge. I am currently doing this with nearest-neighbour, but because I don't know the starting position sometimes this can result in crossed paths.

I could resolve this with more costly algorithms like 2-opt, but because this is being used in real time graphics it isn't quite performant enough.

It might help to know all of these graphs are mapping slightly deformed ovals and so they will have no intrusions. I basically need something that would act as if a rubber band was placed over the points on a graph.

I feel there's probably a better way to do this rather than relying on generic path optimisation algorithms?


texts: Are LL(1) grammars a subset of LR(0) grammars?

texts:
As far as I've understood it seems that LL1 are a subset of LR0, but studying the following grammar I end up in a contraddiction.

Grammar :

S -> (S) | [S] | {S} | ε

This is an LL1 while it seems to me that it isn't LR0 because of a conflict shift-reduce in the initial state I0 of the LR0 automa caused by this:

S -> . (reduce)

S -> .(S) (shift)

S -> .[S] (shift)

S -> .{S} (shift)

Going forward it seems that is an SLR(1) because we haven't any kinds of conflicts.


texts: Why this greedy algorithm fails in rod cutting problem?

texts:
Recall the rod cutting problem.

  Given a rod of length $n$ inches and a table of prices $p_{i}$ for $i=1,2,3,4,\,.\,.\,.$ determine the maximum revenue $r_n$ obtainable by cutting up the rod and selling the pieces.
  You may assume no cutting cost.

The following is a question from CLRS 15.1-2.

  Show, by means of a counterexample, that the following ‘greedy’ strategy does not always determine an optimal way to cut rods. Define the density of a rod of length i to be p_i/i, that is, its value per inch. The greedy strategy for a rod of length n cuts off a first piece of length i, where 1≤i≤n, having maximum density. It then continues by applying the greedy strategy to the remaining piece of length n-i.

Consider prices up to length $4$ are $p_1=1, p_2=5, p_3= 8, p_4 = 9$ respectively.
So, densities are $d_1=1, d_2 = 2.5, d_3= 2.67, d_4 = 2.25$ respectively.

If we are given a rod of length $4,$ then an optimal way of cutting the rod to maximize revenue is $2$ pieces of length $2$ each, generating $5+5 = 10.$

However, greedy algorithm above will suggest cutting the rod into 2 pieces of length $3$ and $1$, generating revenue $8+1=9.$

I obtain this example by merely following the same prices given in CLRS but do not understand why such greedy algorithm fails to provide optimal way of cutting  the rod.


texts: Longest palindrome substring in logarithmic runtime complexity

texts:
In a palindrome of size N, the amount of candidates for the longest palindrome is N^2. Therefore, the information theoretic lower bound (IBT) should be lg(N^2), which is equivalent to a runtime complexity of lg(N).

By IBT I mean that if we use a comparison based algorithm and you think about a decision tree to apply it, the leafs of that tree will be all of the possibilities (N^2 leafs), therefore the height of that tree is lg(N^2). However, I was not able to find any algorithm that is able to solve this question in this runtime complexity; the best I have found is Manacher's algorithm that solves the question in linear time.


texts: Is there a term for a tree where the values of the children add up to a fixed value?

texts:
I have a tree with percentages of the following form

        100
       /   \
      /     \
     /       \
    /         \
   25          75
  /  \       / | \
 15  10    35  10 30
    /  \      / \
   1    9    5   5
      / | \
     3  3  3

So child nodes are added up in the parent node.

Does a tree with this attribute has a already defined name in the algorithmic world?

Thanks for the positive feedback so far.

In this case the nodes hold actually values which are added up in the parent and the example tree shows the percentages of these values in comparison to the root.

I have to implement an algorithm to find those nodes which have the biggest impact and add up to 95 percent.

Since the problem description in case what "biggest impact" means, is pretty open I was thinking about setting the percentage in relation to its child nodes + itself.

Therefore node 25 would have a weight of 25/8, node 75 would have on of 75/6 and so on.

In the next step I would order by weight, min amount of children, in descending order and add up the percentages of the nodes until I reach 95 percent. Always removing a sub node from the result when the parent is added.

I hope I could make myself clear


texts: Please explain the algorithm for finding bridges in graph?

texts:
let, low[] and disc[] be two 1D arrays

disc[i] stores the discovery time of node[I]

low[i] stores the lowest value between disc[i] and discovery time of children of node[i]

I'm curious that what is difference between low[u] = Math.min(low[u], disc[v]);
and low[u] = Math.min(low[u], low[v]);

why is later incorrect?

The following is the code for finding the bridges in a graph.

    private static void dfs(int u, List<Integer>[] g, boolean[] visited, int[] parent, int[] low,
            int[] disc, List<String> bridges) {
        visited[u] = true;
        disc[u] = low[u] = ++time;

        if(g[u] != null)
            for (int v : g[u]) {
                if(visited[v] && parent[u] != v)
                    low[u] = Math.min(low[u], disc[v]);
                if(!visited[v]){
                    parent[v] = u;
                    dfs(v, g, visited, parent, low, disc, bridges);
                    low[u] = Math.min(low[u], low[v]);
                    if(low[v] > disc[u])
                        bridges.add(String.format("%d -> %d",u,v));
                }
            }
    }
```


texts:
Let $U$ be a universal Turing machine that on input $<M,w>$ simulates a Turing machine $M$ on input $w$. I have a question about what would happen if $U$ "operated" on itself.

That is, what happens when we consider the input $<U, <M,w>>$?

Or what about the input $<U, <U, <M,w>>>$?


texts: How to solve for a problem using a primitive function in toc

texts:
I have been searching on the internet how to multiply a function but I cannot find any. I have only found solution in adding but not in multiplication.

$add(2,3) = s(s(s(add(2,0)))) $

$add(2,3) = s(s(s(I(2))) $

$add(2,3) = s(s(s(2)) $

$add(2,3) = s(s(3)) $

$add(2,3) = s(4) $

$add(2,3) = 5 $

For example, Using the multiply primitive function, how to compute $multiply (5, 3)$.

Does anybody know?


texts: Literature request: Generating all vertex subsets of a graph

texts: I am working in an algorithm which finds a unique maximal independent set of vertices. Then, using this set, one can construct all other vertex subsets. I assume this might have some applications outside mathematics, especially in computer science, but I am not sure where I can read about such applications. Does anyone have any good literature suggestion which describes scenarios where this could be useful?  The idea is somehow similar to that of using edge activities as defined by Tutte in order to construct all possible subgraphs of a given graph by using the set of its trees.


texts: Finding the $k$-smallest elements in a min-heap

texts:
Given a min-heap $H$, I am interested in finding the $k$ smallest elements efficiently. The simplest solution would be to call delete-min $k$ times which would give us the solution in $O(k \log n)$ time. This can be improved to $O(k \log k)$ time by maintaining a separate heap $H'$ as follows. Start by inserting the root of $H$ in $H'$. Then when performing a delete-min operation, you add both children of that node in $H'$, and repeat until you have all $k$ elements. Is there a way to do better? I have a feeling that $O(k)$ should be possible, but I can't come up with an algorithm - though certainly you cannot hope to do better than $\Omega(k)$.

Edit: I would just like a hint please.


texts: Are there graphs for which A* cannot be admissible?

texts:
Wikipedia states that "On infinite graphs with a finite branching factor and edge costs that are bounded away from zero $ (d(x,y)>\varepsilon >0$ for some fixed $\varepsilon$), A* is guaranteed to terminate only if there exists a solution."

Does this mean that, if I have such a graph, then there is no admissible A* which exists for this graph? When one says that A* is not admissible, this means that its heuristic is not admissible, right?

Furthermore, is it correct to say that a heuristic is only admissible with respect to a graph - not generally admissible?

For example, if I have a infinite graph which has a finite branching factor, and the cost of each edge is
half of the cost of the edge preceding it (something like this: $goal\leftarrow_{_{c=2}} start \rightarrow_{_{c=1}}q1 \rightarrow_{_{c=1/2}} q_2 \rightarrow ...$), the heuristic and therefore the A* is necessarily inadmissible as there exists no fixed $\epsilon>0$ that is less than the cost of any edge?

To generalize, the $epsilon$ constraint is to make sure that there is no infinite path who's total cost converges, thereby assuring termination?

Any clarification is appreciated. Thanks!


texts: Are divide and conquer searches applicable to unimodal decision problems?

texts:
Given a sorted list of booleans with consecutive 0s followed by consecutive 1s such as [0,0,0,0,1,1,1], binary search is able to find the first 1 after all the 0s in log(n) time.

Is this technique generalizable to find the index to the maximum of a unimodal boolean list with a single 1 sandwiched between 0s such as [0,0,0,0,0,1,0,0]?

It seems like any search algorithm would have trouble narrowing down the search range with all the duplicate 0s surrounding a single 1, however binary search copes well with duplicates, so I'm having trouble explaining why this is impossible.

In addition, the unimodal property required by ternary / Fibonacci search is met, where an array A with indices i < j satisfies A[i] <= A[i+1] until maximum at A[j] then A[j] >= A[j+1].

From what I've read this is possible with a list of integers, so it can't be impossible due to just discrete versus continuous functions.

What am I missing here?


texts: "Ways to make change for a dollar": How to optimize with constraints

texts:
I'm working on an algorithm that takes a number of unit coins ([1, 2, 5, 10] for example) and a certain amount of money (13 in this case), and figures out how many ways there are to provide change for it. In the case of this testset the solution is 16.

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2
1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2
etc
5, 5, 2, 1
10, 1, 1, 1
10, 2, 1
Total number of ways: 16

I've first tried making a list of these permutations, but that generally was slow and unwieldy. There is no need to give every permutation just the amount of them: 7/10 test cases were able to be done under 5 seconds.

So I went looking around and found this. Where a Haskell solution to a similar problem was used. I just had to make it more general for my needs and translate it in a language I could actually run (e.g. Python). I did and I ended up with the following:

def change(list, number):
    if (number is 0):
        return 1
    if (len(list) is 0):
        return 0
    if (number < list[0]):
        return 0

    return change(list, (number - list[0])) + change(list[1:], number)

print(change([1, 2, 5, 10], 13)) #prints 16 (list needs to be in order btw)

This solution is better then the first one: 9/10 test cases succeeded. However this can be done better! I've yet to talk about the constraints of this assignment.

There are no more then 8 unit coins (len(unit_coins) <= 8)
The unit coins are never more then 250 (unit_coin <= 250)
The amount of money is between 0 and 300 (0 < money < 300)
There is always a unit coin with a value of 1

The last part is important (you can tell, because I've highlighted it). The current solution is absolutely not taking advantage of that, and I thing there's a lot to be gained when this is used in the function.

Does anyone have an idea how to to the thing I just described. Any help would be greatly appreciated. More general answers are also welcomed as this type of optimization isn't exclusive to this perticular algorithm.

P.S. I know Python isn't a very quick language, but that's not the point of this exercise. This exercise is about making the whole algorithm better, not just a specific implementation in a certain language.


texts: can more than two arrows point towards the same state from other states in a DFA?

texts:
Is something like this possible:

You have state A,B,C all pointing towards accepting state D.
Is this allowed?
Where online can I find a list of rules that define how an automata must be drawn or conceived?


texts: implementation of human like hearing skills algorithm

texts:
I am a musician/producer and very interested in the way humans are able to identify sounds.

I am interested in a way to have an algorithm identifying different instruments that were originally mastered as stereo or mono.
Maybe computers would be able in future to isolate different instrument tracks and remaster them.

Questions:
Do you think if it is possible for computers to emulate human hearing skills?
Do you know if there are any projects/algorithms around that focus on this subject?


texts: Decomposing a bipartite graph of maximal degree d to d matchings

texts:
I have tried for the last few days to prove that any bipartite graph of maximal degree d may be broken into (at most) d matchings.

My main approach is to prove this inductively over the maximal degree d. This would require me to show that there must exist a matching which contains an edge for every one of the maximal degree nodes. (Such that the removal of this matching will leave me with a bipartite graph of maximal degree d, for which my inductive claim holds)

What I do know is to find a maximum matching (Via either some max-flow algorithm, or using the augmenting paths method, and arriving to the Gallai-Edmonds decomposition of the graph), but can't augment it to a maximum matching in which all maximal degree nodes are necessarily matched.

I was not able to prove it nor find a counter example for this subclaim, and would appreciate help. Thanks


texts: What is the difference between exactness and optimality of an algorithm?

texts:
I'm studying some papers related to graph partitioning (GP). It is well-known that the GP problem is NP-Complete. Based on my understanding, it means that there is no polynomial time solution to solve this problem, or there is no optimal solution for that.
The following paper mentioned this fact in its introduction:
"An exact algorithm for graph partitioning"

However, they provided an exact solution for GP using branch-and-bound algorithm. Isn't it a paradox?, I mean I assume that if a problem is NP-Complete, there is also no exact solution for that, right?


texts:
I wanted to ask if there is a way to use KMP (Knuth-Morris-Pratt) algorithm to find the longest palindromic prefix of a word.

I've seen this algorithm used for determining if a word is rotation of the other for example. We can concatenate first word with itself and look for a pattern which would be the second word (and if found, the answer is yes). But I cannot imagine how could I use KMP for my problem. I am not sure what would the pattern be etc. Can it also be done in linear time using KMP? Thank you.


texts: liskov substitution principle seems to have two conventional meanings

texts:
This is a question about the semantics of the name, rather than about the principle itself. What is the Liskov Substitution Principle (LSP)?

LSP seems to have two meanings in the literature I've seen.   One statement is the rule that determines whether one function type is a subtype of another?   I.e, A->Y is a subtype of B->X, if B is a subtype of A and Y is a subtype of X.  The other statement is that in an object oriented language, a method in subclasses should be element of the subtype of the type of the method in the parent class.

The principle that B<:A, X<:Y implies A->X <: B->Y was a known principle well before the name "Liskov Substitution Principle" was ever coined.  I have found references to this principle from the early 80s.

For example, https://cl-su-ai.cddddr.org/msg04614.html, here is an email from 1987 where the author describes what he calls "PROBLEM II".  It is the definition and justification for the definition of arrow types described above.   Furthermore, this presentation, http://www.softwarepreservation.org/projects/LISP/crisp_ibm370_sdc/CRISP-talk.pdf, claims it was known in the early 1970s.


texts: Recursion Davis' Staircase understanding

texts:
I'm going through a hackerrank challenge on recursion https://www.hackerrank.com/challenges/ctci-recursive-staircase

and I'm having difficulty understanding how the solution below solves the problem. Here's the tree (the recursion calls) like you would with the fibonacci problem but I don't see the insight

With N = 3 the possible choices are

3
1,1,1
2,1
1,2

But I don't see these states represented in the tree, I guess I'm not following the logic which makes it hard for me to solve recursive problems

func f(int n){
   if (n < 0) /* base case */
    return 0;
   if (n == 0) /* base case */
    return 1;

   return f(n-1) + f(n-2) + f(n-3)
}


texts: sorting numbers on Babbage's analytic engine

texts: I read that Babbage analytic engine is Turing complete. I wonder, how could I sort array of numbers on it? Imagine that I have numbers in storage and I want to sort them. How can I do that? The biggest problem is, in my opinion, the fact that analytic engine does not have a card which fetches a number into ingress column from a column in storage where column's number is taken from the other ingress column.


texts: What is the approximation ratio of this randomized algorithm for finding matchings?

texts:
I would like to analyze the following algorithm in terms of its approximation ratio.

Here is the algorithm:

Input: A positive number T and two disjoint sets of nodes V={v1,...,vn} and W={w1,...,wn}.
Output: A matching S.
1: O = [] # An empty array.
2: for t = 1 to T do
3:     Create a set E of edges from V to W randomly
4:     A = LA(G) # G is the bipartite graph G=(V U W, E) and LA is
                 # an algorithm that takes as input a bipartite graph
                 # and outputs a matching A.
5:     O[t] = A # Put the matching A in the t-th element of O.
6: end for
7: S = max(O) # S is the maximum cardinality matching in O.
8: return S

In the algorithm above, called BA, there is a call to another algorithm LA, on line 4. We know that LA is a constant factor approximation algorithm for an NP-hard problem $\Pi$. An instance of $\Pi$ is a bipartite graph and we would like to return a maximum matching that respects some constraints. Therefore, LA will return a matching of size no less than a constant factor times the size of the optimal matching.

Note that BA is trying to solve another NP-hard problem $\Pi_1$ that has an instance of two sets and we would like to return a maximum matching between these two sets that respects the same constraints as for $\Pi$. The only difference between $\Pi$ and $\Pi_1$ is that $\Pi$ has as input a bipartite graph (nodes and edges) whereas $\Pi_1$ has as input a set of nodes only.

I am not trying to hide the constraints. I still cannot write them explicitly in a readable way. I will give some examples to clarify the problem.

Say, for problem $\Pi$, we are given the following graph (it is represented by set of edges):

Instance of II = { {1, 3}, {2, 2}, {3, 1}, {4, 4} }

In this special instance, say, the optimal solution is

OPT of II = { {1, 3}, {2, 2}, {4, 4} }

Hence edge {3, 1} cannot exist in the solution because of the constraints.
If we apply LA to this instance we could have selected, say

A = { {1, 3}, {2, 2} }

Therefore, the algorithm failed to select the edge {4, 4}.
Now, for problem $\Pi_1$, we are given the following two sets:

Instance of II1 = (V = { 1, 2, 3, 4 } and W = { 1, 2, 3, 4 })

In this special instance, say, the optimal solution is (brute-force on all possible edges between V and W and apply the optimal algorithm for $\Pi$)

OPT of II1 = { {1, 4}, {2, 3}, {3, 1}, {4, 2} }

Hence, since we do not have the set of edges initially, the optimal solution for $\Pi_1$ is to select 4 edges unlike 3 edges for $\Pi$. In fact, it is clear that |OPT of II| <= |OPT of II1|.

Now, at iteration t=1, if we apply BA to this instance we could get, say

formed edges in line 3 of BA = { {1, 2}, {2, 2}, {3, 4}, {4, 3} }.

Now we apply LA to this instance and we could obtain
A = { {1, 2}, {4, 3} }

We continue until t=T, and then select the maximum cardinality set A obtained, which is S in line 7 of BA.

Knowing that LA is $O(1)$-approximation algorithm for $\Pi$, can I say that BA is an approximation algorithm for $\Pi_1$?

I think I can say that BA is something like $O(1+\frac{1}{T})$-approximation algorithm for $\Pi_1$ because as $T\to\infty$ and the 3rd line of BA is generated uniformly random, the solution produced by BA is no less than a constant factor times the optimal solution.

The pseudo-code is also given in more clearer way here:


texts: Can a Turing machine decide if a LOOP program stops for the integer input 0

texts:
This is a question I found in a practice exam while I am preparing for my mid term exam.

The answer needs justification, either a pseudo code or a logical explanation why not.

What puzzled me about that question is that we already know that all LOOP programs terminate at some point, the question seems odd to me.

Any references about LOOP and/or WHILE programs are  welcome. Our professor didn't give much.


texts: Modelling a dependency of multiple transitions on data in one place

texts:
We are modeling our process using a colored Petri net. One of the limitations we have is that when multiple transitions depend on one place, only one of those transitions will fire because then the token and data is consumed.

How can we model our process, or what type of Petri net property can we use, to facilitate the fact that multiple transitions can depend on one place and all have to be able to consume the same token?


texts: Algorithm to check the distance between integers

texts:
I have the next problem, and I was wondering whether it exists a way to solve it without having to iterate around all the array in the worst case.

I have a sorted array of pairwise distinct integers, say $[1,2,4,5,7,8]$
I need to know if there is a gap of at least two between two consecutive integers, i.e., if there are successive integers $a$ and $b$ in the list with $b>a+2$.

For example in the array given, the algorithm should return false, but for $[2,3,6,7]$, it should return true. Is it possible to solve it by mathematics instead of iterate and compare the integers one by one?

I will add some inputs and the desired output:

[1,2,4] -> false
[1,2,5] -> true
[1,2,4,6,8] -> false
[1,3,4,6,8] -> false
[1,4,6,8] -> true
[1,3,5] -> false


texts: Where can we put primitive recursive functions in Chomsky hierarchy?

texts:
I am currently studying recursion theory, but I cannot really understand where to put the Primitive Recursive functions in the Chomsky hierarchy.

In my understanding, Primitive Recursive functions contain all finite languages but are not contained in Regular expressions.
For instance, I think that $\{a^nb^n | n \in \mathbb{N}\}$ can be computed by a partial recursive function but not by a DFA. But DFA can express the always undefined function, while the primitive recursive function cannot, because they are total.

Am I completely wrong?


texts: What makes type inference for dependent types undecidable?

texts: I have seen it mentioned that dependent type systems are not inferable, but are checkable. I was wondering if there is a simple explanation of why that is so, and whether or not there is there a limit of "dependency" where types can be indexed by values, below which type inference is possible and above which it is not?


texts:
I find very interesting the problem of existence of a machine $H$ which given as input any algorithm $P$ outputs whether $P$ halts or not. Alan Turing disproved the existence of such an $H$ machine in the following way:
"Assume $H$ exists. The input of $H$ is any algorithm $P$. The output of $H$ is $YES$ if $P$ halts and $NO$ if $P$ doesn't. Create another machine $N$ with input in the set $\{YES,NO\}$ and without output. The machine $N$ does this: if the input is $YES \to \text{loop for ever}$ otherwise, if input is $NO \to \text{halt}$. Let us call the composition of $H$ followed by $N$ as $X$. We will simply write $X(P) = N(H(P))$. Now $X$ has as input a machine and no output (it either halts or loops forever). What Turing does is to "feed" $X$ with itself ... and reason as follows: if $X(X)$ halts then $X(X) = N(H(X)) = N(YES) = \text{loops for ever}$ from which somehow the contradiction arises ..." but here one should assume (in order to obtain a contradiction) that $X(X) = X$ ...
Question
I do not know why such an assumption, $X = X(X)$ would be made. In fact, in my opinion, $X \neq X(X)$ for any input $P$ (that is all Turing is proving actually). Indeed assume $P$ is a machine which halts (runs for ever). Then $X(P)$ does not halt (does halt) when $X(X(P))$ does (does not). I do not understand therefore, why $H$ cannot exist! Where is my mistake ?


texts: What does "Kan" mean in "Kan operations"?

texts:
I'm studying Cubical Type Theory and I see the word "Kan operations" (ref1, ref2, ref3, and there are many more), which is related to "adding a cap to a tube" (can be also explained as "given a path between a and b, and two paths that are between a and c/b and d respectively, we can use Kan operations to get a path between c and d").

I wonder if there's any references that can explain where this "Kan" word come from -- what does it mean? Is that "Kan extensions" in Category theory?


texts: Distribute a number of tasks into multiple days (scheduling)

texts:
This is about scheduling. I have N tasks of different length and I have to schedule them into M days. Indeed, each day has a max capacity (usually they are the same). Parameters are tight in the sense, that the sum of taks' length is exactly the same as the sum of day's capacity, e.g. tasks of total length 150 must be scheduled into days of total capacity 150.

Resource sharing is not involved, but the ordering of task is important. Idealy, for every j > i, task Tj must be processed in the same day or later than task Ti. But then, the solution does not exist for the most cases. Thus, as few as possible tasks are allowed to be processed at most one day before a task with smaller index. If there is still no solution, as few as possible tasks are allowed to be processed at most two days before a task with smaller index, and so on.

This seems to me as an NP-hard problem. I have created an algorithm based on Binary Decision Diagrams, which performs an exhaustive search over all schedules but, of course, is quite limited by the size of the problem. I need a comparison with other solutions. Can you, please, suggest me some state-of-the-art approach to solve the given problem.

EDIT: I want to minimize how much the solution violates the natural ordering over how many times it violates the natural ordering.


texts: Using a binary heap to solve an equation

texts:
I have to find a solution for this equation:

I have to find the set of solutions a, b, c, d for all possible combinations of values 1 <= x <= n.

$a^5 + b^5 = c^5 + d ^ 5$

I first thought about using a heap, because it is what I am learning, but I can't seem to come up with a pattern.

I was told that my algorithm should run in $O(n^2\log(n))$ so I know I would have to use a heap of size n, with n*2 inserts into its structure.

That's as far as I got, can someone hint me?


texts: Help in understanding how to apply nonlinear function in hashing

texts:
Can somebody help in brainstorming how to apply the map as a hashing function?
I am aware that chaos is used in cryptography but I fail to understand how to apply it. Most popular hashing techniques is the modulo hash function Why is it best to use a prime number as a mod in a hashing function?
A modulo chaotic function that comes to my mind  is the Dyadic map $\theta = 2 \theta mod 1$.
  Not getting into the details of collision resolution and other technicalities, it shall be of immense help if the application of chaos map is shown in generating hash codes.
Chaos based cryptography link to paper shows that the equation on page
3 $S^t = (u^t + 2S^{t-1} + t) mod 256$ is the hashing function for cryptography. $t$ are the number of sub-blocks of the message (plaintext) and $u_0$ is the decimal value of the first block of the message.  Please help! Thank you


texts: Precise definition of oracle classes $A^B$

texts:
I was reading in Papadimitriou's "Computational Complexity" book Chapter 14, about Oracle Machines. Papadimitriou defines, in definition 14.3, page 339-340, Oracle Turing Machines with oracle a language $A \subseteq \Sigma^*$:

  The computation of $M^{?}$ with oracle access $A$ in input $x$ is denoted $M^A(x)$.

So far so good.

In the next paragraph, he writes:

  If $\mathcal{C}$ is any deterministic or non-deterministic complexity class, we can define $\mathcal{C}^A$ to be the class of all languages decided by machines of the same sort and time bound as $\mathcal{C}$, that have oracle access to $A$.

My question is:

  Given any complexity class $B$ and $C$, can we always define $B^C$?

This is motivated by a question I posted (and deleted) at TCS.stackexchange where , using Papadimitriou's notation, I defined $B^C$ for a complexity class $B$ and $C$ but I received criticism (besides the context of the question) that I am not allowed to do that because oracle is not an operation defined on languages and hence complexity classes. Does this contradict the extract from Papadimitriou's book (where he explicitly defines $B^C$ for a _complexity class $B$)?

My understanding is that

  We can define $B^C$ for a complexity class (i.e., a set of languages) $B$ if $B$ can be defined by a Turing Machine model.

If yes, why it is not explicit in Papadimitriou's book?


texts: Datastructure for insertion and scored extraction

texts:
I have a simple program (assume a shop) that is actually just returning the $m$ most active customers from a total list of $n$ users (so $m \leq n$). I only use this program on one machine with one process, so assume no distribution of data to be necessary.

I require a data structure storing $\mathrm{userId}$ and $\mathrm{score}$, where $\mathrm{score}$ is an unsigned integer. In the beginning it's $\mathrm{score}:=0$  for all $n$ users. I can extract $m$ users beginning with the highest $\mathrm{score}$ (filling up with any other user, so the first extract just returns any $m$ users).

I have an increment(x) function that is called often. It increases $\mathrm{score}$ of the user with $\mathrm{userId} = x$ by $1$. Afterwards I want to call extract again, where the result may differ by $1$ user (the last incremented score may lead to that $\mathrm{userId}$ replacing another $\mathrm{userId}$ within the $n$ members).

At the moment my prototype uses a hashmap for the scoring and a linear min-search, so complexity for increment is $O(1)$ and for extract is $O(n\cdot m)$. I feel like there should exist a data structure where extract is $O(m)$ (min-heap maybe?) while increment is either $O(\log n )$ or even $O(1)$. Assuming $m = \log n$, this would lead to a speedup of $n$ which would be immense even for small datasets.

What data structure should I use? Is there such a data structure for the operations extract and increment(x)? And if not, is there a theoretical proof that there is none?


texts: Finding the element that occurs the most in a very large file

texts:
I've heard this interview question asked a lot and I was hoping to get some opinions on what good answers might be: You have a large file 10+ GB and you want to find out which element occurs the most, what is a good way to do this?

Iterating and keeping track in a map is probably not a good idea since you use a lot of memory, and keeping track as entries come in isn't the greatest option since when this question is posed the file usually already exists.

Other thoughts I had included splitting the file to be iterated through and processed by multiple threads and then have those results combined, but the memory issue for the maps is still there.


texts:
I really need help with this task here. Im stuck at it and I really would appreciate your help
Here is the task:

Give a recursive function $r$ on $A$ that reverses a string. For instance,
$r(logikk) = kkigol$ and $r(moro) = orom$. (given that $A$ the amount of
letters in the Norwegian alphabet which has 29 letters.). Define the
function in such a way that it is correctly regardless of what $A$ are.

Also $logikk$ means $logic$ in norwegian, and $moro$ means $fun$ in norwegian in case you're wondering.
Edit:
I tried to solve one of the recursive functions, $r(logikk)$, but i'm not sure if all of it is correct:

$\Lambda =$ The empty string
$r(\Lambda) =$ $\Lambda$, $r(k) = k$, $r(k) = k$, $r(i) = i$, $r(g) = g$, $r(o) = o$, $r(l) = l$
For any word $w$ and letter $a$, $r(wa) = wa$

Can someone please check if this is correct for $r(logikk)$ I feel like i'm missing something but i'm not sure what.


texts: Datastructure for a set of axis aligned rectangles that enables querying for point containment

texts:
I am trying to find a reasonable data structure for representing a
partition of an (axis aligned) rectangular domain into a set of (axis aligned) rectangles.

I need to be able to look up for a given point which (unique) rectangle contains it.

So far I have taken a look at Quadtrees, and this seems reasonable to me - where I recursively subdivide the domain into patches.

People have also mentioned RTrees, but I do not see how these can help me in such single point queries.


texts:
This question relates to timing threads to go at a very precise rate. Consider the following scenario; A program creates a series of threads that continually add a random set of elements to their local storage. The program finishes and returns the thread that received the shortest number of elements in its random set. If one thread was to go faster than another, the program would be incorrect. Is there a way to "lock" the threads to go at the same speed? If so would it be possible for someone post a quick python or other language script that performs this task?

If more info is needed, please post


texts: Task scheduling algorithm that limits concurrency

texts:
My prof introduced us an algorithm with semaphores that was used to solve the "dining philosophers" problem.
The algo is ok, apart from that it limits concurrency.

What does mean that it "limits concurrency" and why this happens ?


texts: Non-Interactive Zero Knowledge Proofs: zk-snarks and zk-stark

texts: I read up on an abstract example of ZKPs (the cave and the door), but I'm trying to understand NIZKs (specifically zk-snarks and zk-stark). All the examples I can find online seem to have some interactive component even when trying to explain nizks. I don't particularly fancy reading some 300 pages of papers to understand this topic. Is there some sort of example (perhaps abstract) a la the cave for regular ZKPs that I could use to understand nizks?


texts:
This game is a simplified version of Shut the Box. There are 9 tiles (1,2,3,4,5...9). The initial tiles are unflipped. You have 2 dices.
Each round, the player rolls the 2 dices and their sum is S.
After that, there are two options. The first option is to find the tile equal to S.
If it is unflipped, you can flip it so that the tile becomes flipped up.
The second option is to find two tiles that are unflipped such that the sum of the two tiles is S and flip them. You keep rolling the dice until one of the 2 situation happens:

If all 9 tiles are flipped at any time, the player wins.
If the player rolls a sum and cannot find any tiles to sum up to it
or be equivalent to it, the player loses.

The problem is to simulate the game 100,000 times and improve the win percentage.

My current strategy is to check if S is unflipped and flip that. If a tile equal to S is not available, I try to find 2 tiles that equal to S, starting from the biggest available number. I'm thinking it's best to eliminate numbers like 9,8.. asap because the frequency of S being smaller than that is high.

Currently, my strategy has around a 5% win rate but it can apparently be optimized further to hit 10%. Are there anyways to optimize it further?


texts: I am trying to solve this by using Substitution method. My solution must work both for even n-s and odd n-s. For evens case I have solved it. But for the odd's case I am stuck at this point. Hot to continue?


texts: Difference between forward/backward slicing and reaching definition - def/use - use/def chains

texts:
I'm a little bit confused about the difference between forward/backward slicing and the use/def-def/use as part of the reaching definitions technique. Isn't the use-def chain supposed to be equivalent to the backward slicing?

Let's assume we have a line that uses some variables. Like: x = y + z.

If we try to find all the code locations that influenced the given code line (backward slicing), shouldn't it be the same as all the entries of the use-def chain of the variable x?


texts: Prove Subset-Sum is NP-complete - Alternative reduction?

texts: It is well known the Subset-Sum problem is NP-complete. This can be shown using a reduction from the 3SAT problem. I am wondering: is there any other NP-Complete problem that could be reduced to the Subset-Sum problem?


texts:
So I've seen that most NP-Complete problems seem to take the form of decision problems - problems which require only a yes/no answer. However, how can this be reconciled with the requirement that the solution of an NP problem can be checked in polynomial time?

For example, for a graph G, the max cut decision problem: "Does a cut of size at least k exist?" is NP-Complete. However, given a particular solution, "yes", the problem of checking that the solution is "yes" would require you to find a max cut of size k, so how can this be in NP?


texts: How are conditionals implemented at hardware level?

texts:
Can anyone explain how are conditionals implemented in the CPU?

Is special circuitry used?


texts:
I would like to determine if the following language is decidable or not.
L = { w $\in$ $\Sigma^*$ | $T(M_w)$ is recognized by a Turing machine with at most 42 states}.

I know that every finite language is decidable, but I am not sure if this has anything to do with this particular problem.

Every help is appreciated, I am a little lost.

Thank you


texts: Heap down - What is math logic and intuition behind $\sum_{i=1}^{\log n}(\log n - i) \times 2^i $

texts:
In heap (bubble down) we have the formula :
\begin{eqnarray*}
  \sum_{i=1}^{\log n}(\log n - i)\times 2^i & = & \log n\sum_{i=1}^{\log n}2^i -\log n\sum_{i=1}^{\log n}i\times2^i \\
& = & \log n\times2^{\log n+1}-(\log n\times2^{\log n+1}-(2^{\log n+1}−2)) \\
& = & 2n−2\in Θ(n)
\end{eqnarray*}

Why we have $\sum_{i=1}^{log(n)}(\log n - i)\times2^i$ ?
How we get to $2−2\in Θ()$ ?

Please explain details!


texts: Minimum number of scenarios to run to fully test a page

texts:
I run a testing application that, using Selenium, runs testing "scenarios" each of which visits a bunch of pages on a website. Each page is modeled by a Java file that contains locators, each of which are used to locate certain elements on the page maybe to verify that they exist or, beyond that, that they work as intended. Some elements may always show up, and some may only show up depending on the scenario you are running. Let's say the page we would like to test in question is the "login" page, and we are talking about all the scenarios that visit that page.

Bear in mind, some scenarios may visit the login page, but only a small subset of those scenarios are actually intended to test the login page.

Let's say each page is modeled by a Java source file that contains a bunch of locators intended to locate elements on that page.

Each scenario is intended to test a different overall functionality on the website, but as far as the login portion of each scenario is concerned, multiple scenarios might be totally redundant (only one of these redundant scenarios need to be run to achieve the exact same level of interaction). Let's say one set of redundant scenarios only minimally enters a username/password and then clicks the log in button. So our Java page always has the exact same sets of locators locating the same elements and not locating any elements for those redundant scenarios.

Let's say 100 of your scenarios visit the login page. Let's also say you ran all 100 scenarios to fully interact with that page, but only 10 of them needed to be run to achieve the same thing, that is, only 10 needed to be run to fully test the page.

Let's say each locator in the Java file modelling the login page is marked with the scenarios where it successfully located an element on the page. Each locator could have anywhere from 1 to 100 scenarios tagged to it.

Having already run the 100 scenarios, how do you go about knowing what those 10 scenarios are for future benefit? What sort of algorithm would achieve this? Thanks!


texts: Converting connected graph to disconnected graph by removing minimum vertices

texts: How to find the minimum number of vertices that need to be removed from a graph so it makes a disconnected graph?


texts: A Turing Machine that exclusively accepts an infinite string

texts:
While reading some of proofs in Computability Theory, I came up with following conclusion:

We can design a Turing Machine which exclusively accepts finite strings (obvious).

Now while trying the same for infinite string, I came up with the following conclusion :

There exist no Turing Machine which exclusively accepts infinite strings.

Proof : Since acceptance in context to Turing Machine is defined in terms of finite amount of time, therefore every time we say that an infinite string $w$ is accepted by a Turing Machine, we usually talk about searching a "finite pattern" in $w$. So while designing a machine for $w$ there exist a $w'$ which is finite and contains the same "finite pattern" which we try to find in $w$.

Example of "finite pattern" : A string that contains a 0. (Assuming Binary Strings)

So my question is that is my proof right? and if yes, is there a better way to prove this?


texts:
As stated in the title:
Fix two primes p and q. Given input a number of the form $p^aq^b$, find the immediate next number of the same form.

For example: when $p = 2$ and $q = 3$
Next of $2^2*3=12$ is $2^3=16$ and after that is $2*3^2=18$

Question [edited]:

Can this be done in poly-time of the representation of $a$ and $b$?

I believe so and I do have a sketch for this, but I want to see what a "proper" answer to this question is.


texts:
I have this problem, and I don't really understand how am I supposed to do this. Could someone please help me with this? I know what left quotient is. I also know about regular, irregular languages. But still I don't know how to show this... Any help would be appreciated, thanks in advance! Also sorry if something is not correctly in English, not my first language.

Problem:

  Show that for any language $L ⊆ Σ^*$ and any DFA $A = \langle \Sigma, Q, q_0, \delta, F \rangle$,
  the left quotient $L \diagdown L (A)$ is a union of languages $L_q = \{v | \delta(q,v) \in F\}$ for selected states $q \in Q$, and explain what are those selected states.

Could someone please also demonstrate on a small (but non-trivial) example, in which the $L$ would be irregular?


texts: Loop invariance insertion sort algorithm

texts:
I have the following pseudo code for a insertion sort algorithm
INSERTION-SORT

1 for j = 2 to A.length
2    key = A[j]
3    // Insert A[j] into the sorted sequence A[1..j-1]
4    i = j -1
5    while i > 0 and A[i] > key
6        A[i+1] = A[i]
7         i = i -1
8    A[i+1] = key

I am trying to convert it into executable code written in Python
def main():
    A = [5,2,4,6,1,3]
    for j in range(1,len(A)):
        key = A[j]
        i = j - 1
        while i >= 0 and A[i] > key:
            A[i + 1] = A[i]
            i = i - 1
        A[i + 1] = key
        print A[0:j+1]
    return A

main()

is this a correct translation? I'm not sure if I messed something up with the indexes because it seems as though I'm not getting the end index with range. Furthermore I'm going to be testing correctness with initialization, maintenance and termination.
I added the line print A[0:j] to show initialization and maintenance but I'm not sure if it should be print A[0:j-1].
Any help is greatly appreciated!


texts: What exactly is execution-time address binding?

texts:
According to these two definitions:

Logical address: every memory address generated by the CPU.

Physical address: address which identifies uniquely a (real) memory cell.

my textbook (Operating systems concepts - Silberschatz, Galvin, Gagne) says that address binding at compile-time and load-time both generate identical logical and physical addresses, while execution-time binding produces different logical and physical address.
I've googled a lot, but every article which tries to explain this concept is not that clear. I can't understand what happens in the practice. I'll give you an example to let you understand what I mean:
The source code (high-level language instructions) contains symbolic addresses (like count) that are replaced (by the compiler) by:

physical addresses (compile-time binding) if the location in memory of the process can be known in advance (non-multi-programmed systems);
relocatable addresses (load-time binding) in the opposite case (most common).

Once the loader puts the obj into memory it replaces relocatable addresses with physical addresses (if there are any) and the program can be finally executed. The CPU can read and refer to physical addresses, so logical and physical addresses are the same. In both previous cases the binding is static: once loaded, the process can't be moved from one segment of memory to another.
In order to manage the memory in an efficient way, the system should be able to move a process from a location of the memory to another: this means that the process physical addresses can change at run-time. In order to implement this mechanism logical addresses and physical addresses must be different: logical addresses can change in an interval [0, max] and physical ones between [r, r+max], where r is the relocation register.
Does this mean that, in execution-time binding, the obj file contains virtual addresses ([0, max]), which are converted time by time by the system into physical ones? In other words, is true that the obj file doesn't contain any physical address (but a data structure of the OS keeps the informations about the process address binding) so each time the CPU reads (for example) ADD 100 105 the addresses 100 and 105 are converted into physical ones by the system (using MMU and data structures)?
Please correct any mistake I made, the textbook is not so clear.


texts: Computational complexity comparison of floating-point Euclidean distance calculation with binary fixed-point Hamming-distance calculation

texts:
This could relate to different applications, but my application of interest is in similarity-search systems based on high-dimensional feature vectors. In these systems, since search  based on Euclidean distance is costly, the vectors are encoded as binary vectors. Then the search is done based on Hamming distance computation which is supposed to be faster than the Euclidean counterpart. My question is, practically, how much is this speed-up for an average architecture?

More formally, suppose we have a database $\mathrm{X} = [\mathbf{x}_1, \cdots, \mathbf{x}_i, \cdots, \mathbf{x}_N]$ of $N$ vectors of dimension $n$, and a vector $\mathbf{y}$ of the same dimensionality. Now imagine two cases:

Vectors are real-valued, i.e., $\mathbf{x}_i \in \Re^n$. We are interested in finding the $\mathbf{x}_i$ from $\mathrm{X}$ with the minimum Euclidean distance to $\mathbf{y}$, i.e.:

\begin{equation}
i = \underset{{1 \leqslant i \leqslant N}}{\text{argmin}} ||\mathbf{y} - \mathbf{x}_i||_2.
\end{equation}

Vectors are binary, i.e., $\mathbf{x}_i \in \mathcal{B}^n$ with $\mathcal{B} = \{0,1\}$. We are interested in finding the $\mathbf{x}_i$ from $\mathrm{X}$ with the minimum Hamming distance to $\mathbf{y}$, i.e.:

\begin{equation}
i = \underset{{1 \leqslant i \leqslant N}}{\text{argmin}} \sum_{j=1}^n \big( \mathbf{y}(j) \oplus \mathbf{x}_i(j) \big),
\end{equation}
where $\oplus$ denotes the XOR operation.

Both of these operations have complexity of $\mathcal{O}(Nn)$. However, the real case requires doing the operations in floating-point arithmetic while the binary case enjoys the fixed-point binary operations which are faster.

My question is, in practice, how are these complexities different? Can we say, very roughly though, that they have different constant factors and the ratio of these factors is a constant value? What would that constant value be then? Around 10 or 100 maybe? And how much is it architecture dependent?


texts: How to find kth largest element in (max) priority queue in O(m) time?

texts:
Here is my exercise.

  FINDLARGEST(k): return the elements in the heap with key >=k" ... "expand the priority queue (max-heap) so that it supports FINDLARGEST(k) in O(m) time, where m is the number of elements with key>=k.

Can anyone elaborate on this maybe?

I stumbled upon this on the wikipedia entry on min-max heap: "The structure can also be generalized to support other order-statistics operations efficiently, such as find-median, delete-median,[6]find(k) (determine the kth smallest value in the structure) and the operation delete(k) (delete the kth smallest value in the structure), for any fixed value (or set of values) of k. These last two operations can be implemented in constant and logarithmic time, respectively." However, that did not help much.


texts: Can a CS grad student work on quantum field theory and string theory problems?

texts:
The mathematical aspect of particle physics theory are interesting and there seems to be a lot more connections being made to computation and information (like with complexity theory having some impact of physics and the whole quantum computation thing). Does it make sense (or is even possible) to work on some of these connections as a grad student in a theoretical computer science department or should I be looking at mathematical physics programs instead?

My main concern is with finding advisors and departments that are game for something like this (given that this makes any sense in the first place).


texts: how the instructions are stored in relocatable format on disk

texts:
I understand how the instructions are kept in relocatable format in RAM. It is done so by keeping a base register and a limit register. Physical address = base register value + logical address. And logical address = the logical distance from the starting location of process's address space, just like an array.

But what I don't understand how are they kept in relocatable format on the disk, is there some base value there too. Plus how are they linked to a computer program say C Program or Java program using dynamic loading of shared libraries.

Please help me understand !!

Thanks.


texts: Add on interval, Query for number of elements less than val

texts:
We have an array of numbers and we are supposed to do the following queries on it:

Add number x to all elements on the subarray with indices [ L, R ] of the array.
Query for number of elements less than number x of the whole array.

Note that x is given in each query and is not fixed.

I have a solution with time complexity $O(q \cdot log(n) \cdot \sqrt n)$ where $n$ is the size of the array and $q$ is the number of the queries (Storing sorted subarray in each block). However for constraints $n, q < 1e5$ with time limit of 2 seconds this is not efficient enough. So how to solve it on these constraints?

The only constraint is that the solution should work for 2 seconds when $n, q < 1e5$ and you can answer queries offline. Total complexity should fit in the constraints and the complexity for each query is not important.


texts: Maximum weight independent set in a King's graph

texts:
I would like to find a maximum weight independent set in a finite section of a King's graph.

For an $m\times n$ King's graph where $n \ll m$, we can use an $O(2^{2n} m)$ bitmask dynamic programming solution. We proceed row by row, and on each row, we try all possible ways to select cells.

On the other hand, it is not obvious to me whether this problem is NP-hard. Just like how the problem on a grid graph may be solved by bipartite matching, I suspect that there may exist some sort of blossom algorithm or similar which would admit a polynomial time solution to the King's graph case.


texts: Do there exist any problems with optimal algorithms beyond $O(n)$?

texts: Blum's Speedup Theorem famously shows that there are problems which admit no fastest algorithm. This raises an obvious question: are there any problems that do admit a fastest algorithm? In other words, does there exist a language $L$ which is decided by some algorithm within $f(n)$ steps so that any other algorithm which solves the same problem also runs in $\Omega(f(n))$ steps? If $f$ is linear, this is trivially the case. But what about beyond linear? Just a nonconstructive existence proof would already be cool.


texts: How similar are two DFAs? -not just binary equivalence-

texts:
Are there any measures to compute similarity (or distance) between two DFAs?

If yes, which are the main references?

I need a measure of similarity, not only a (binary) equivalence test.

"Similarity" is an intuitive concept. There are different ways to formalize it; i'm looking for ready-to-use formalizations with regard to DFAs (not NFAs, weighted automata, or general graphs!).
Furthermore, good solutions may exploit recognized languages.

I found some studies about this problem, which help to clarify the question. They involve two approaches: one from model-testing field aiming at compare languages, a second defined by authors aiming at compare structure of DFAs.

Bogdanov, Kirill, and Neil Walkinshaw. "Computing the structural difference between state-based models." Reverse Engineering, 2009. WCRE'09. 16th Working Conference on. IEEE, 2009.
Walkinshaw, Neil, Kirill Bogdanov, and Ken Johnson. "Evaluation and comparison of inferred regular grammars." Grammatical Inference: Algorithms and Applications. Springer Berlin Heidelberg, 2008. 252-265.
Walkinshaw, Neil, and Kirill Bogdanov. "Automated comparison of state-based software models in terms of their language and structure." ACM Transactions on Software Engineering and Methodology (TOSEM) 22.2 (2013): 13.

They compute exactly what I was looking for, a metrics among DFAs, adopting the techniques developed in the model-testing field.

Does there exist any other approaches, ready-to-use, to compute similarity between DFAs?
(Both in terms of language both of structure).


texts: Why is testing if x > y primitive recursive?

texts:
$f(x,y)= 0$ if $x>y$ and $1$ otherwise.

How can prove formally that this function is primitive recursive?


texts: Mathematical function vs Computer program

texts:
In mathematics , an $n$-ary relation is subset of cross product on $n$ sets took under consideration.

Let us take $A_1,A_2,A_3 \cdots A_n$ be the n sets.

Then relation $R \subseteq A_1\times A_2\times A_3 \times A_n$ .

Here $X$ represents cross product betwen two sets.

If we consider first $k$ sets as input domain and next $n-k$ sets as output range.

Then $R$ is an $k$-ary function that returns $n-k$ multiple outputs. $0 \le k \le n$

As we know function is a well-behaved relation. i.e.., A relation can assign same input to any number of outputs.

In the case of functions (well-beahaved relations)  one input at most maps to one output.

My doubt is whether

Any program written in any program language ultimately a mathematical relation.
Any program written in any program language ultimately a mathematical function.
Some programs written in programming languages cannot be a mathematical relation.
Some programs written in programming languages cannot be a mathematical function.

We know that 2. $\implies$ 1. and 3. $\implies$ 4.

Which of the four arguments above are true for all set of programs in all programming languages?

I am arguing with my colleague that 1.,2. are true independent of programming language and program.

But his argument is that procedural languages like c, c++, pascal etc.., doesn't obey 2. but in case of functional programming languages like Haskell it's true.

So, is  functional programming is syntactical extension of mathematical functions or conceptual extension?


texts: Is checking if the length of a C program that can generate a string is less than a given number decidable?

texts:
I was given this question:

Komplexity(S) is the length of the smallest C program that generates the string S as an output. Is the question "Komplexity(S) < K" decidable?

With respect to decidability, I only know about the Halting Problem and just learned about Rice's Theorem while searching online (though I don't think it can be applied here?). I couldn't reduce the problem to any undecidable problem I know about. Thanks in advance for any help


texts: Showing that algorithm has STOP property and finding its computational complexity function

texts:
The task is to show that given algorithm has STOP property and to find its computational complexity function.

$\alpha:$ $n \ge 0$

void fun(int n) {
    a=0;b=n+1;
    while ((a + 1) != b) {
        p = (a + b)/2;
        if (p ∗ p > n)
            b = p;
        else a = p;
    }
}

I have already proven its partial correctness as it was also part of the task, however I do have problem with these things that I have mentioned above.

I think it can be easily seen that it is gonna stop as 'a' is getting bigger and bigger, but I don't really know how to notate or show it in more mathematical way.

Thanks for your help.


texts: Prove (p → ¬q) is equivalent to ¬(p ∧ q)

texts: I need to prove the above sequent using natural deduction. I did the first half already i.e. I proved $(p\rightarrow\neg q)\rightarrow \neg (p \wedge q)$, but I'm stuck on where to start for the reverse i.e. proving $\neg (p \wedge q) \rightarrow (p\rightarrow\neg q)$. I figured I would start by assuming $\neg (p \rightarrow \neg q)$ and then working towards a contradiction, but I'm still at a dead end. Can someone point me in the right direction? Thanks.


texts: Regular Expression for All strings which contain no runs of a's of length greater than two.On L={a,b,c}

texts:
My attempt is

We can fairly easily build an expression containing no a, one a, or one aa:
(b+c)(€+a+aa)(b+c)
but if we want to repeat this, we need to be sure to have at least one non-a between repetitions:
(b+c)*(€+a+aa)(b+c)*((b+c)(b+c)*(€+a+aa)(b+c)*)*

Therefore the final answer is
(b+c)*(€+a+aa)(b+c)*((b+c)(b+c)*(€+a+aa)(b+c)*)*

Is this ok?


texts: Why can we not obtain a unique solution for orientation from Essential Matrix?

texts: In computer vision, why cannot we obtain a unique solution for the projection matrix given an Essential Matrix. Why is it said that it can only be obtained upto 'scale' and what does this mean?


texts: Nondeterministic automaton accepting only words whose first letter is identical to their next to last letter

texts:
I was asked this question and could not come to the correct answer:

Let $L$ be the language of all words over $\{a,b\}$ where the first letter is identical to the letter that is next to last. (Pay attention – every word with length 2 is in the language.)
Sketch a nondeterministic automaton that accepts this language.

Any help would be appreciated.


texts: Towers of Hanoi with sufficiently many stacks, show that $T_k(n)=\Theta(n)$ for all $k\geq 2 + \frac{n-1}{2}$

texts:
I'm trying to show that for the following Towers of Hanoi general algorithm that $T_k(n)=\Theta(n)$ for all $k\geq 2 + \frac{n-1}{2}$, I'm not sure how to incorporate the restriction on  $k$ into my proof.
generalTH(n_disks,k_stacks)
  if n<k:
    ### in 2n-1 moves reassemble ###
    return
  m = n-2
  generalTH(n-m,k)
  generalTH(m,k-1)
  generalTH(n-m,k)

To solve towers of Hanoi, I know it takes the following number of moves:
$$
T_k(n) =
\begin{cases}
2^n-1,  & k=3 \\
2n-1, & n<k \\
2T_k(n-m)+T_{k-1}(m), & n \geq k
\end{cases}
$$
Going through it - how can I show that the boundary case of $k=3$ can be within $\Theta(n)$?
Since $m = n-2$ : When I expand the recursion it seems easy to show that the first half is in $n$ - but I'm not sure how to show the boundary case will be in $n$?
$$T_k(n)=2T_k(n-(n-2))+T_{k-1}(n-2)=2T_k(2)+2T_{k-1}(n-2-(n-4))+T_{k-2}(n-4)$$
$$...$$
$$T_k(n)\approx\Theta(2\cdot\lfloor\frac{k}{2}\rfloor)+\Theta(\text{boundary case})$$


texts: What is the difference between strong normalization and weak normalization in the context of rewrite systems?

texts: In the context of rewriting systems, how does strong normalization differ from weak normalization?


texts: How to access the bit at a particular index?


texts:
In class we saw examples of reductions like from Independent Set (IS) to Longest common subsequence (arbitrary number of sequences) (LCS)

$V = \{v_1,\ldots,v_n\} E =\{ e_1,\ldots, e_m \}$
The reduction is $(G(V,E),k)$ to $\{S_0,S_1,\ldots, S_m\}$, where

$e_k = (v_i,v_j)$ gives $S_k = \langle v_1v_2 \ldots v_{i-1}v_{i+1}\ldots v_n \text{  } v_1v_2 \ldots  v_{j-1}v_{j+1} \ldots v_n \rangle $

I understand the reduction for edge $(v_iv_j)$ we don't include $v_i$ in the first part of the sequence and don't include $v_j$ in the second part of the sequence.

They claim $G$ has an IS of size $k$ if and only if LCS has a solution of size k.

This reduction fails when $k$ is not a maximum independent size set. In that case we get longest common subsequence of size $< k$.

Even in another reduction from VC to a minimization problem Y, the same problem persists for me, their claim is size $k$ vertex cover gives a $k-1$ size solution for Y.

But if $k > \mathit{opt}$ vertex cover size then we don't get a minimum size for the other problem Y. I have verified this. Here optimal for Y $ < k-1$. I am happy to provide more details on this as well. Y is the Exemplar breakpoint distance between two genomes.

I am missing something in my understanding. I get that there is no contradiction and this does not prove Y, LCS are NPC, as we would still need to check LCS, Y  could be verified polynomially.

Are we doing something wrong in class or am I missing something?


texts:
I found a question while studying compilers :-

Given a grammar E->E+E/E×E/number

The above grammar is fed to a YACC with semantic rules for parsing. What will be the action of the YACC.

1) it detects recursion and eliminates recursion.

2) it detects RR conflict and resolves

3) it detects SR conflict and resolves in favour of Shift over Reduce action

4) it detects SR conflict and resolves in favour of reduce over shift action

The answer given is option 3. But I have read that LALR parser cannot parse ambiguous grammar, while the above grammar is ambiguous.

A) So how can YACC(which is a LALR parser) parse the given grammar?

B) What about other ambiguous grammar, I.e. can YACC parse all the ambiguous grammars?


texts: Can a Turing machine be both decidable and undecidable relative to itself?

texts:
Consider the language:

$A'_{TM} = \{\langle M,w\rangle: M \mbox{ is a TM with access to an oracle for } A_{TM} \mbox{ and } M \mbox{ accepts } w\}$

Clearly, we expect that any language is decidable relative to itself, including $A'_{TM}$. So let $F$ be an oracle decider for $A'_{TM}$ that has access to an oracle for $A'_{TM}$. In particular, we can construct $F$ as follows.

$F = $ "On input $\langle M, w \rangle$, where $M$ is a TM and $w$ is a string:

Query the oracle for $A'_{TM}$ with $\langle M, w \rangle$.
If the oracle replies YES, accept. If the oracle replies NO, reject."

Now, consider the following TM, $D$.

$D$ = "On input $\langle M \rangle$, where $M$ is a TM.

Check if $M$ is an oracle TM with an oracle for $A'_{TM}$. If it is not, reject. Otherwise, proceed to the next step.
Simulate $F$ on $\langle M, M \rangle$. If it accepts, reject. If it rejects, accept."

Now, suppose that we feed $\langle D \rangle$ as input to $D$. Then clearly, computation proceeds to Step 2, since $D$ has an oracle for $A'_{TM}$. But Step 2 yields a contradiction, since we are forced to conclude that $D$ accepts $\langle D \rangle$ if and only if $D$ rejects $\langle D \rangle$. So it seems we must conclude that $A'_{TM}$ is both decidable and undecidable relative to itself, which seems absurd.


texts:
$$L = \big\{ (0^{m^2})^* \ \big \vert \ m \ge 1 \big\}\,.$$

I've given answer as regular but i am not sure. How? Please explain.


texts: Median of list of difference of elements

texts:
I have a list. I have to find median of absolute difference of all pairs of array.

Eg - A={1,2,10}

Difference for all distinct pairs  :

1-10=9

1-2=8

2-10=8

The new list is A'=[8,8,9] and the median is 8.

Now I took all the pairs and made a list with difference of them and median is A'.length()/2th element i.e. 8.

But is there a way to do without taking all the pairs as the time complexity is O(n2) and I want to reduce the time complexity to O(nlogn) or less.


texts: Are there grammar classes between Chomsky level 1 and 2?

texts: Are there any grammar classes which are true subsets of Chomsky level 2 but not equal to level 1?


texts: Closure of a CFL under specific operation

texts:
Consider the following operation on language $L$:
$\mathrm{inv}(L) = \{ xy^Rz \mid x,y,z\in \Sigma^*, xyz\in L \}$
I understand that if $L$ is regular, then $\mathrm{inv}(L)$ is regular too, and proved it by guesing when $y^R$ starts and running it on the inverse DFA. However, if $L$ is a CFL, then $\mathrm{inv}(L)$ is not, and I don't understand why. Can't we just also guess when $y^R$ starts, insert all of it into the stack, then simulate the DFA of $L$ on each item we take out, then continue on $z$ when it's empty?
thanks.


texts:
Given an undirected graph  $G=(V,E,p,c)$ and a positive integer $k$,   $p: V \longrightarrow R^+$  which associates a positive weights $p(v_i)$ to every node $v_i \in V$, and $c: E \longrightarrow R^+$  which associates a positive cost $c(e_{i,j})$ to every edge $e_{ij} \in E$. How can I find a  subgraph $G'=(V_{G'},E_{G'})$,  $V_{G'}\subseteq V$,  under constraint $ \forall v_i,v_j \in V_{G'}$ , $e_{i,j} \in E_{G'}$  with  the minimum number of vertices such that:

\begin{equation}
\sum_{v \in V_{G'}} p(v)-\sum_{e \in E_{G'}}c(e) \geq k
\end{equation}

I think this problem  is NP-hard (because it is an optimization problem), as there is a reduction from k-clique, is it true?   if yes, there is an approximate algorithm to find a near optimal solution? I try to solve this problem using ILP integer linear programming on cplex :

$min \sum_{v_i \in V} v_i$

subject to :

$\sum_{v_i=1} p(v)-\sum_{i\ne j,v_i=v_j=1 }c(e_{i,j}) \geq k$

$v_i,v_j \in \{0,1\}$

, but this solution is not useful when it comes to a very large graph .

Context of the problem :

Given a collection of $n$ sets $S=\{S_1,...,S_n\}$ and a integer $k$ how to find the minimum number of sets $m$ whose size of their union is greater than $k$ $ |\bigcup_{i=1}^{m} S_i|≥k$ .
I model this problem in the form of a graph where the $S$ represents the set of vertices, $p(v_i)=|S_i|$ and $c(e_{i,j})=|S_i \cap S_j|$ . So i obtain the problem described above.

For example,

if $k=12$ the solution is G'with $V_{G'}=\{v_2,v_5,v_6\}$  and $E_{G'}=\{e_{5,6}\}$.


texts:
Consider a special case of the knapsack problem in which all weights are integers, and the number of different weights is fixed. For example, the weight of every item is either 1k or 2k or 4k. There is one unit of each item.

The problem can be solved using dynamic programming. Suppose the knapsack capacity is $C$, and the most valuable item of weight $w$ has a value of $v_w$. Then, the maximum value of KNAPSACK($C$) is the maximum of the following three values:

KNAPSACK($v_1$,$C-1$), KNAPSACK($v_2$,$C-2$), KNAPSACK($v_4$,$C-4$).

Is there a more efficient algorithm? Particularly, is there a greedy algorithm for this problem?

I tried two greedy algorithms, but they fail already for weights 1 and 2. For example, suppose there are 3 items, with values 100, 99, 51 and weights 2, 1, 1:

If the capacity is 2, then the greedy algorithm that selects items by their value fails (it selects the 100 while the maximum is 99+51).
If the capacity is 3, then the greedy algorithm that selects items by their value/weight ratio fails (it selects the 99+51 while the maximum is 100+99).

However, this does not rule out the possibility that another greedy algorithm (sorting by some other criterion) can work. Is there a greedy algorithm for this problem? Alternatively, is there a proof that such an algorithm does not exist?


texts:
First, for the sake of notation, suppose a finite set A, where A is a set of real numbers. Then the function f(A) is defined as the sum of all the elements in A. Then here's the following problem.

I have a set X = {x_1, x_2, ..., x_n}, where x_i is a real number in (0,1], and I want to partition X into C_1, C_2, ...., C_m such that f(C_i) is a real number in (0,1] for all i <= m, and m is as small as possible.

I believe there is no polynomial-time algorithm for solving this problem exactly. So I have to design a greedy that approximates the solution (desired: 2-approximation)

So I came up with the following greedy algorithm. Consider x_1,x_2,...,x_n in any arbitrary, fixed order. Then the natural thing to do (in a greedy manner) is to fill C_1 as much as possible (until f(C_1) is greater than 1), and then we move onto C_2 and do the same, and so on. You continue until every element in X is assigned. Suppose C_1, C_2,..., C_k is returned by the algorithm, and I want to know how large k could be.

First, it's easy to see that k is at least f(X), which is the sum of all the elements in X. But I have difficulty deriving an upper bound on k (desired: 2 * f(X), and hence this is going to prove that the algorithm is 2-approximation). Any key insight on how to derive the upper bound would be greatly appreciated.

Edit: I realized that that there are at least k-1 C_i such that |C_i| >= 1/2. This observation led to an upper bound opt >= 2*k!


texts: About the connection of pipelined execution and latency

texts:
Let's consider we want to calculate a[i]=a[i]*c for a vector the size of N=12 on some random processor.
We do assume that c is some given constant already present in the register. We do not consider any superscalarity or vectorization.
We also know the latencies for the following instructions:

Load operand to register (4 cycles)
Multiply a(i) with c (2 cycles); (a[i],c in registers)
Write back result from register to mem./cache (2 cycles)
Increase loop counter as long as i less or equal N(0 cycles)

The result my class gives me for the pipelined execution of this is the following, where each line represents one CPU cycle:

Why is this correct? Or is this even correct?
If we consider the first load (load a[1]) shouldn't it block my only load unit on the processor for 4 cycles?   How can I even load a[2]in cycle 2then?
Or is latency only the time to that is needed to send information that something is e.g. loaded, and the actual load unit is only busy for one cycle for each load operation?


texts: Term for an A*-like pathfinding strategy where only the heuristic goal distance matters

texts:
I am trying to find a proper term for the A*-like best-first pathfinding strategy where the node to expand next is the one with the least estimated distance from the goal, regardless of its distance from the source.

In best-first search algorithms, the node to expand next is the most promising one according to some evaluation function (which may take into account the current global knowledge).  In the normal A* algorithm, the evaluation function is the sum of the length of the currently know shortest path from the source and the heuristic estimate of the distance to the goal.  Is there a standard term for a similar strategy where the evaluation function is just the heuristic distance to the goal?

I was thinking about greedy and hill-climbing, but greedy in this context seems to be just a synonym of best-first, and in what is commonly referred to as hill-climbing, there seems to be either no backtracking, or just one-step backtracking, that is, old unexpanded nodes are discarded at each step.


texts:
The book I am learning about compilers from states that $M \to \alpha N \beta$
will generate a constraint that $\mathrm{FOLLOW}(M)$ is contained in $\mathrm{FOLLOW}(N)$ when $\beta$ is nullable.

This is a bit confusing because there can be other productions such as $M\to \gamma K \theta $.  Logically, then, the set of symbols which can follow $M$  can also be the set of set of symbols that can follow $k$ if $\theta$ is nullable and can be different from $\mathrm{FOLLOW}(N)$.

As such both $\mathrm{FOLLOW}(N)$  and $\mathrm{FOLLOW}(K)$ should be included in $\mathrm{FOLLOW}(M)$. Shouldn't it be like this?
What might be the reasons behind the statement in the book?


texts: Is there a universal metric of "size of a program"?

texts:
There is a universal metric of information: amount of bits. It's universal in the sense that if we write a piece of information in DNA (4-ary digits), we can simply multiply by 2-log-4 to get the amount of bits.

I'm wondering if there is also a universal measure of the size of a program. I know about Kolmogorov complexity, but this is defined in terms of the size of a Turing machine.

But if we compare this to some other computational model, will the equivalent complexity measure be equivalent to the Kolmogorov complexity measure, in the same way that the 4-ary information metric is equivalent to the binary one?

For example, suppose instead of a Turing machine we used a modern CPU, and we define a similar metric of the size of programs, will it agree with Kolmogorov complexity?

I think what I mean by the metrics being equivalent is that there is one canonical metric for each universal model of computation, and that the order of complexity of programs is the same in each model of computation, or even that it is some scalar multiple of it.


texts: Sort deck of cards with least no of moves

texts:
We have n cards with each card numbered from 1 to n.

All cards are randomly shuffled but all cards are visible

We are allowed only operation MoveCard(n) which moves the card with value n to the top of the pile.

We need to sort the pile of cards with minimum number of MoveCard operations.

The brute force approach which i can think of is start with MoveCard(n), MoveCard(n-1), MoveCard(n-2).... MoveCard(1).

This approach will solve the problem in n MoveCard operations.

But can we optimize it.

For instance, If the input is like: 3 1 4 2

As per my approach:

4 3 1 2
3 4 1 2
2 3 4 1
1 2 3 4

MoveCard operations is 4.

But we can solve this problem with minimum number of moves:

Optimized solution is:

2 3 1 4
1 2 3 4

MoveCard operations is 2.

The aim is to find the first card which has to be moved. In this case its 2


texts:
As a preperation of an exam about algorithms and complexity, I am currently solving old exercises. One concept I have already been struggling with when I encountered it for the first time is the concept of amortised analysis. What is amortised analysis and how to do it? In our lecture notes, it is stated that "amortised analysis gives bounds for the "average time" needed for certain operation and it can also give a bound for the worst case". That sounds really useful but when it comes to examples, I have no idea what I have to do and even after having read the sample solution, I have no idea what they are doing.

  Let's add up 1 in base 2, i.e. 0, 1, 10, 11, 100, 101, 110, 111, 1000, ... Using amortised analysis, show that in each step only amortised constantly many bits need to be changed.

(the exercise originally is in German, so I apologise for my maybe not perfectly accurate translation)

Now the standard solution first defines $\phi(i) := c \cdot \# \{\text{1-bits in the binary representation}\}$ for some constant $c > 0$. I think this is what is called the potential function which somehow corresponds to the excessive units of time (but I have no idea why I would come up with this particular definition). Assuming that we have to change $m$ bits in the $i$-th step. Such a step always is of the form

$$\dots \underbrace{0 1 \dots 1}_m \to \dots \underbrace{1 0 \dots 0}_m.$$

This statement is understandable to me, however again I fail to see the motivation behind it. Then, out of nowhere, they come up with what they call an "estimate"

$$a(i) = m + c(\phi(i) - \phi(i-1)) = m + c(-m + 2)$$

and they state that for $c=1$, we get $a(i)=2$ which is what we had to show.

What just happened? What is $a(i)$? Why can we choose $c=1$? In general, if I have to show that in each step only amortised constantly many "units of time" are needed, does that mean that I have to show that $a(i)$ is constant?

There are a few other exercises regarding amortised analysis and I don't understand them either. I thought if someone could help me out with this one, I could give the other exercises another try and maybe that'll help me really grasp the concept.

Thanks a lot in advance for any help.


texts: Why is DFS not suited for shortest path problem?

texts:
I am sorry for the repetition of the question. I understand that this question has already been answered before by the community, but most answers tend to focus on unweighted graphs. I want to know Can DFS we used to find the shortest path for weighted graphs? I know that Dijkstra's algorithm is used to find the shortest path for weighted graphs. But, what I want to know is what is fundamentally different in using DFS for unweighted graphs compared to Dijkstra (which is BFS + priority queue/set) and why can't we create DFS + priority queue/set implementation for shortest path problem?
Ref link: Shortest Path using DFS on weighted graphs,
Why can't DFS be used to find shortest paths in unweighted graphs?
Any help would be really appreciated.
Thanks!


texts: How to calculate time complexity of KD-tree data structure

texts:
I have made a KD-tree data structure for a project I've been working on. But I can't seem to figure out the query complexity for it.

What I know: I know that KD-tree is using BST structure, so for a search for the single element it would be O(log(n)), but we know that for a KD-tree the longer down it goes down the tree, the more recursive calls to that sub-tree are made, because of the intersects method and that's how it searches in a specified interval. I see a lot of different articles about the query complexity, but all of these are on balanced KD-trees, what about unbalanced trees?

My thoughts:
I know the search for a best-case in an unbalanced tree of a query is O(log(n)) since to be able to find 1 element is O(log(n)) on a BST, and therefore the same for a KD-tree where the interval is large enough for 1 element. But this is almost impossible.
I know that worst-case should be O(N) for an unbalanced BST since the structure would look like a linked list. And this could theoretically happen for an unbalanced KD-tree.

Question:
How would I go about finding the avg case for query search since both best-case and worst-case is not that likely to happen.
And how are people achieving O(k + sqrt(N)) query complexity for balanced KD-tree?

Update

The KD-tree is not balanced, so the height is not guaranteed O(log(N))

After some more research, the MAX complexity is sqrt(N) for a balanced kd-tree, not the avg as I originally thought. But if its sqrt(N) for balanced KD-tree it must be N for unbalanced KD-tree since it will make a structure that looks like a Linked list?


texts:
I am wondering why this

$T(n)=3T(n/4)+n⋅lg(n)$

recurrence can be solve by Master Theorem case 3 but this
$T(n)=2T(n/2)+n⋅lg(n)$
recurrence can not be solve by Master Theorem what is the difference between this two recurrences.
When I searched on google I found tow questions related with this two recurrence
First Question:
Solving $T(n)= 3T(\frac{n}{4}) + n\cdot \lg(n)$ using the master theorem
Second Question:
T(n)=2T(n/2)+nlognT(n)=2T(n/2)+nlogn and the Master theorem

But both of them say something in contrast with  each other and I could't find out the main reason.


texts: How to prove a statement in regular expression?

texts:
I cannot figure out how to go about proving this statement in regular expression.

$$ L(R_1) \subseteq L(R_2) \subseteq L(R_3) \implies L(R_1^*+R_3)^* \subseteq L(R_2^*+R_3^*) $$

Here's what I have so far:
Since $L_1 \subseteq L_2 \implies L_1^* \subseteq L_2^*$ then $L(R_1) \subseteq L(R_2) \subseteq L(R_3) \implies L(R_1)^* \subseteq L(R_2)^* \subseteq L(R_3)^*$. If $x$ belongs to $L(R_1)$ then $x$ also belongs to $L(R_2)$ and $L(R_3)$ and if $y$ belongs to $L(R_1)^*$ then $y$ also belongs to $L(R_2)^*$ and $L(R_3)^*$. I'm not sure how to go from here to show that $(y+x)^* \subseteq (y+y)$.


texts: Turing machine that recognizes the language $\{a^{n}b^{2n}c^{3n}|\ n\ge0\}$

texts: I'm pretty sure that the Turing machine state diagram I drew accepts all strings in the language $\{a^{n}b^{2n}c^{3n}|\ n\ge0\}$, but how do you verify this? Likewise, how do you verify that this machine rejects any string not in the given language?


texts: How to find the virtual pages and physical memory frames?

texts:
So i am given a system of 20 bits virtual addresses and 18 bits physical addresses using paging with pages size 4Kbytes.
I am told to find the maximum number of virtual pages that a process can have and the maximum number of physical memory frames the system can have.

So 2^12 page size makes 12 bits for offset and 8 bits for page number right?
and 2^8 is 256 is the maximum virtual pages that a process can have? Correct me if im wrong.

And for the second one im having kind of trouble.
Ive seen a post about a similar question but didn't really understand it.
Is it 2^18 bits for physical address multiplying it with the page size like
(2^18)*4096 to get the maximum physical memory frames?

Also a last part gives me the following:

00110110011110111100

and says the virtual page containing the address is mapped onto physical frame 45, give the corresponding physical address in binary format.
How do i find that?


texts: LL(1) CFG for triple amount of b's compared to a's?

texts:
I would like to construct a LL(1) context-free grammar for a formal language $A$ = "strings where the amount of character b is exactly triple compared to the amount of character a" for $\Sigma = \{a,b\}$.

I've tried to figure it out so that if we consider a string $w$ to have one a, then the acceptable presentations for $w$ considering language $A$ would be abbb, babb, bbab and bbba.

But how do I build the CFG rules for that? I have tried something like $$S \rightarrow A$$ $$A \rightarrow \epsilon | aAbbb |baAbb | bbaAb | bbbaA$$ but I think it's not very good because at least I cannot build an LL(1)-parser out of it (which would be good) because of ambiguity. And it doesn't quite work out for a string like bbbbbbaa $\in A$.

Is it possible to build a CFG for this language that can be parsed using a LL(1) parser?  If not, why not?


texts: How do you analyse the time complexity of a piecewise function?

texts:
Is there a method to apply when trying to finding out the time complexity of a piecewise function?

\begin{align*}
F(x) &= \begin{cases} 2^x & x < 8, \\ x^2 & x \geq 8. \end{cases} \\
\end{align*}

This case seems straightforward as the function is $\Theta(x^2)$ for a large enough value of $x$, but what should be done in a more complex case... for example a function that gives a result for an odd value of $x$ and another one for an even value of $x$?


texts: Closed-Form Expression for Recursive Function

texts:
Let $k \in \mathbb{N}$ and $m \in \mathbb{R}$. Consider the following function $S\colon \mathbb{R} \times \mathbb{N} \to \mathbb{R}$:
  $$
S(m,k) = \begin{cases} 3m & \text{if } k = 0, \\ 4S(\tfrac{m}{2},k-1)+3m & \text{if } k \geq 1. \end{cases}
$$
  Find a closed-form expression for $S(m,k)$ using repeated substitution.

  Prove the correctness of the expression you obtained.

When using repeated substitution, I found the formula
$$ \sum_{i=0}^{k} 4^i\frac {3m}{2^i}, $$

whereas the solution has the formula,

$$ 6m2^k - 3m.$$

I wrote my sum (as well as the original recurrence relation) in Python, and plugged in values from 0 to a 100 for both $m$ and $k$.

For some reason, the sum gets wrong values starting at $m, k = 47, 47$, and follows a weird pattern after that.

Does anyone have any idea what is going on?


texts: Regular of language of all words of length 3

texts:
Consider the language $$L = \{ x \in \{0,1\}^* \mid |x| = 3 \}.$$
I think the above language is regular. A DFA can be used to determine the above language.

Am I correct? Is the above language regular?

If this language $L$ is regular, then it should satisfy the pumping lemma. Then there exist $w = xyz$, where $xy^nz \in L$ for all $n \ge 0$.
But on the other hand, if we pump more letters then the resulting string will not be in the language. The language $L$ only contains words of length 3.
The pumping lemma states that for every regular language there exists an integer $p$, such that string $w$ of length at least $p$ can be written as $w = xyz$ and $y$ can be pumped.
Here are my doubts.

Is this language $L$ regular?
If so, does it satisfy the pumping lemma?
The pumping lemma states that every regular language has a pumping length $p \ge 1$. Does this language not have one?


texts: What is the exact algorithm to find maximum clique of a given unit disk graph?

texts:
A unit disk graph is an intersection graph $G = (V,E)$, such that given $n$ disks on the plane with identical radius. Each disk $d_u$ corresponds to a vertex $u \in V$, and there is an edge $uv \in E$ if, and only if $d_u$ and $d_v$ intersects.

In 1990, Clark, Colbourn, and Johnson showed that the problem can be solved in polynomial time. However, the linked paper does not provide an exact algorithm.

I have been studying the paper for some time, and I still don't see how the observations in Section 3 can be utilized to develop an algorithm. Mostly because point sets that are used to prove the claims are infinite.

Moreover, I have scanned through many papers, and all of them mention the polynomial-time solvability only. I could not even find a verbal definition of the algorithm anywhere.

I am not asking for coding or some well-defined algorithm, but I would really appreciate a roughly written complete algorithm.


texts: Is the complement of this decision problem in $P$?

texts:
Are there any two primes that are NOT a factor of $M$ that multiply up to $M$?
Fact: Any two primes that multiply up to $M$. Must be factors of $M$!
Thus because of the fact above an $O(1)$ algorithm exists. It always outputs $NO$
Complement
Are there any two primes that are a factor of $M$ that multiply up to $M$?
Fact: A complement of a decision problem does not always require to always return $YES$ or $NO$. It can be either one!
(eg. $M$ = 6 and two primes that multiply up to $M$ are $3$,$2$.)
Well, this I find interesting this is deciding $Semi-Primes$.
Question
Shouldn't $Semi-Primes$ be in $P$, because what was shown above?


texts: Growth of exponential functions according to the big O notation

texts:
I'm preparing for an exam and trying to make some sense of the growth of the different exponential functions. I picked the trickiest functions for myself and tried to sort them according to the big O notation. Since it's hard to use L' Hospital's rule on exponential functions I at least want to get a feeling for the order of growth.

$$
n^2 = O(ln(n) ^ {ln(n)}) = O(n^{ln(n)}) = O(2^{\sqrt{n}})=O(2^{(n/2)}) = O(n ^{\sqrt(n)}) = O(n!) = O(n ^n)
$$

I'm particularly unsure about the right place of fac(n). Can anyone verify if that is correct?


texts: Evaluation of Information extraction a task

texts:
I have to evaluate my information extraction program. I have to evaluate it by the expectation-driven way.

I don't know what that means.

I would appreciate if you could help me.

Thx.


texts: Given that f(n)>0 and constant c>0 Prove that f(n)+c = O(f(n)) or provide a counter-example if it's false

texts:
Question:

Given that f(n)>0 and c>0

Prove that f(n)+c  =  O(f(n)) or  provide a counter-example if it's false.

My Effort to solve: \begin{eqnarray*}
f(n) + c \space  \leq \space d\cdot&f(n)\space for \space all\space n \geq n_0\space and \space d>0\\
\end{eqnarray*}
So i believe there can be found some large d that satisfies this equation, but i am not sure about it.


texts: Number of states in NFA and DFA accepting strings from length 0 to n with alphabet Σ= {0,1}

texts:
The question is in title. Let me repeat:

  What are the number of states in NFA and DFA accepting strings from length 0 to n with alphabet $\Sigma = {0,1}$

I feel both NFA and DFA will take following form:

and thus both have $n+1$ states. Am I correct with this? Or the DFA needs to take following form?

I feel its not necessary to have transitions defined for every symbol for every state, mainly because it does not eliminate "deterministic" nature of the automaton. Am I right?