How can I efficiently find the optimal order to apply special offers to a shopping cart? Given a list of items which represent items in a shopping cart, and a list of available special offers which replace one or more regular items to lower the cost of those items, how can I decide the order to apply the special offers to minimize the final basket price?

For example, I have in my cart 4 items:

Coke \$2
Coke \$2
Sandwich \$3
Chocolate bar \$1

Total: \$8

There are two special offers in store:

Buy one get one free coke (\$2 saving).
Coke, chocolate bar and a sandwich for \$4.50 (\$1.50 saving).

One method of determining the order offers are applied might be to sort them by the savings they give. After applying the offers using this method my cart now looks like this:

Buy one get one free coke \$2
Sandwich \$3
Chocolate bar \$1

Total: \$6

There is no meal deal offer applied because after the Coke deal is applied there is not any coke items left to make a meal deal. This method of sorting by savings may seem to work, but there are cases in which it can fail, for example if the same deals were in place and my cart looked like this:

Coke \$2
Sandwich \$3
Chocolate bar \$1
Coke \$2
Sandwich \$3
Chocolate bar \$1

Total: \$12

After deals are applied, the two Coke items are substituted for the promotional offer first (it being the deal with the greatest saving). There is no other applicable deal so the algorithm ends, reducing the basket price by \$2. Obviously there is an error here because if two meal deals were applied before the coke deal, the price would have been reduced by $3.

The naive solution to this problem would be to enumerate each possible permutation of the list of special offers, and find the one that minimizes the basket total when applied. This would have a factorial runtime based on the number of special offers available.

Is it possible to improve on a factorial runtime and if not, are there any efficient approximate solutions?

Interesting problem. As noted, you can easily turn this into an integer programming problem. But if your numbers are small and nobody buys a warehouse full of goods an easy algorithm may work.

All you need to decide is how often each offer is applied. Sort the offers by percentage saved in descending order. Then an outer loop where the most saving offer is applied first as often as possible first descending. Then the second highest percentage saving etc. You reject a search path if it cannot be optimal.

In your example the first offer saves 50% and the second just 25%, so you  would apply the first offer as often as possible,

It gets a bit more complicated if you accept offers where you deliver more than ordered. For example delivering an extra chocolate bar if it saves money

In your second example you would first try to apply the first deal once, then try again without it.


Heapsort for sorted input What is the running time of heapsort when the input array is in increasing order? How about decreasing order?  (I came across these questions in CLRS.)

Here is what I have done so far ...

For the increasing order (i.e. the order opposite to the output order) I am completely stuck and haven't been able to make any progress because as I see it as soon as we build the max heap the structure completely changes and I cant reason about what the final heap will look like.

For the decreasing case I feel like I understand what is going on and will try to describe that below, but its also a long way from a proof.
A decreasing array is already a max heap so the array is unchanged by building the max heap.
WLOG assume a complete binary tree (else just remove some elements until you get one)

Remove the first $n/4$ largest elements. The first element will then be lifted to the top and fall back down a distance of $\log n$ falling to the left each time (the left element is always the largest).

But now the right is larger for each vertex that this last element fell through. So the next vertex will first fall right then fall left the rest of the way. No vertex will fall the same path until this has been rectified. So elements moved to the top of the tree continue to fall the full length of the tree. Rectifying the tree seems like it will take a linear time because it has length logn and it feels like you have to go down a constant fraction of the other routes before it is done. But this is really wordy and sort of garbage.

I apologise if this could be written better but I tried my best to say what I mean.

Note I have read the proof for the general best case but I was looking for something more straightforward due to the extra information.

Thanks

Time complexity of heapsort is $O(n \log n)$ for all types of input. If we have all input we need $O(n)$ time to build the max-heap. Then for sorting the the data, we need to remove the first element of the array then heapify the remaining data and repeat it for $n$ times. Which the act of heapifying for all steps needs $O(n \log n)$ time.


Turing machine that can tell if it ends in standard position? Suppose we have a TM $M$ with alphabet $\{0, 1 \}$ with n states. Say $M$ halts in standard position if it is scanning the left-most $1$ of a non-broken string of $1$s (and everything else on the tape is $0$.

Suppose the tape is initially consists of a bunch of $1$s, a $0$, a bunch of $1$s, a $0$, and so on for a finite number of $1$ and then the rest is $0$. $M$ is initially scanning the left-most $1$.

Is there a turing machine that can appended to this guy so that, whenever it is about to halt, it checks if it is in standard position? If it is standard position, then it returns to standard position and halts. If it is not in standard position, then it does not halt. This standard position checking could depend on the turing machine (and probably had to depend on the number of states at least) but should not depend on the initial state of the tape.

I thought that arguing that the TM only has to check $n+1$ $0$s beyond the last $1$ in either direction because the turing machine cannot add a $1$ that far away from the last $1$, but there are counter examples. For example, there is a 3-state machine that, when given the tape 100 _ 1, it changes $1$ to $0$ for "spots" 2-100 and then halts at the second argument.

In most of the models of Turing Machines there is a separate blank symbol $B$. Sometimes we may even have a start symbol $\rhd$. This makes it easy to check if $M$ halts in standard position.

If $0$ is also treated as the blank symbol, and the tape is initialized with 0's on both side of inputs (with no separate blank symbol) then the analysis of computation becomes a little bit difficult (Where is the boundary?).

In your case, it is doable without much hassle as 0's in the input always occur singly. First rewrite the whole input as 2-bit alphabet, converting 0 to 10 and 1 to 11, B will be 00 and start symbol $\rhd$ will be 01. Now we are happy to go. We just need to modify the Turing Machine to consider 2 bits at a time.


Direction of restriction for NP hard proves I have a very silly question, as I am reading through all the proofs showing a problem is NP hard, one of the techniques is by showing an already-proven NP complete problem is a special case for that problem.

I am wondering shouldn't that be another way around? I mean if you show your problem is a special case of a NP-complete problem, then you showed it is NP complete as well? I know this logic is wrong but why?

What is the advantage and disadvantage of this technique.

Comment: this question actually contents the answer for why we need to reduce a problem to a NP hard problem to prove its NP hardness.

The technique your top paragraph shows NP-hardness. The technique in your next paragraph shows membership in NP.


Global variables and frame stack The below program will read a positive integer from keyboard and print the binary equivalent. This program is using only one variable.

If global variables are not stored in frame stack, how this is working.

#include<stdio.h>
int n;
void binary(n)
{
    if(n>0)
    {
        binary(n/2);
        printf("%d",n%2);
    }
}

void main()
{
    scanf("%d",&n);
    binary(n);
}

The program is actually using two variables. There is a global variable n, which is used by main(). There is a local variable, confusingly also named n, which is used by binary() and allocated on the stack.

Here are some excerpts from the code generated on my machine:

_binary:
...
        movl    %edi, -4(%rbp)
        cmpl    $0, -4(%rbp)
...

_main:
...
        movq    _n@GOTPCREL(%rip), %rsi
        movl    (%rsi), %edi
        movl    %eax, -4(%rbp)          ## 4-byte Spill
        callq   _binary
...
        .comm   _n,4,2                  ## @n

The first excerpt contains part of the code generated for binary(). The parameter n is passed in the register edi, and is then stored on the stack. The following command compares it to zero, implementing part of n>0.

The second excerpt contains part of the code generated for main(). The global variable n is allocated as a common symbol. The excerpt consists of the function call binary(n). You can see that n is pulled out of the global storage and put into edi, before calling binary().


Are generational garbage collectors inherently cache-friendly? A typical generational garbage collector keeps recently allocated data in a separate memory region. In typical programs, a lot of data is short-lived, so collecting young garbage (a minor GC cycle) frequently and collecting old garbage infrequently is a good compromise between memory overhead and time spent doing GC.

Intuitively, the benefit of a generational garbage collector compared with a single-region collector should increase as the latency ratio of main memory relative to cache increases, because the data in the young region is accessed often and kept all in one place. Do experimental results corroborate this intuition?

Here are a few papers that talk about the cache implications of generational garbage collectors:

Caching Considerations for Generational Garbage Collection
The Effect of Garbage Collection on Cache Performance

From what I can gather, the primary issue is that garbage collected systems trade off space in memory to avoid up front collection. The same thing applies to cache memory. As you suggested, the things in the first generation are most likely going to be sitting in cache, and so their allocation and collection will be much faster than something in main memory, or paged out to disk. The main issue is the size of the first generation with respect to the size of your cache. If your cache fills up before the first generation does, then you start to lose those benefits as the misses start piling up.


Turning generative recursion results (leaves of a tree) into connected components (where each neighbour differs by one element) I'm generating valid timetables for my uni with a simple generative recursion algorithm like this (disregarding handling of course-specific labs and tutorials)

def generate(current_timetable, unallocated_courses):
    if conflicts(current_timetable):
        return
    if not unallocated_courses:
        results.add(current_timetable)
        return
    course = first(unallocated_courses)
    for section in course:
        new_timetable = copy(current_timetable) + section
        generate(new_timetable, rest(unallocated_courses))

(Storing results as a flat list for now)

Probably room for memoization in there, but that part of the program is fast enough already.

Now, since this generates too many timetables to easily compare, I decided to group them into 'families', which are connected undirected graphs of timetables in which you can navigate between any two nodes by swapping one section at a time for another. As a result, I get around ~10 very differently shaped timetables that I can subjectively compare.

My naive O(n^2) approach was to take every single combination of 2 nodes, build an adjacency list based on the delta between each pair, and then find connected components with BFS.

If I store results in a tree (i.e. non-leaves are incomplete timetables, root is empty, each child has 1 more course allocated than its parents, and the leaves are the completed timetables), is there any insight about this structure that could make finding connected components faster?

I realize that immediate siblings would be connected in the final graph, since their only difference is which section (of the course that their parents is missing) was picked, but there can also be leaves that are identical except for e.g. their grandparents, and those are the ones that I can't seem to detect without the O(n^2) approach.

To clarify: Each course has a bunch of sections. At each level of the tree, a certain course is considered, and for each section in that course, a subproblem is created.

For example:

At level 1, different sections of course A are considered. At level 2, different sections of course B are considered.

Here's sample output with 2 families (sorry about the current interface): https://dmitry.lol/public/timetablor/

EDIT My initial interpretation was clearly incorrect although some of the content may be useful to someone so I'll leave it at the bottom of all this.

With that, it seems like each step further into the tree will lead you to a mutually exclusive path (e.g. timetables can't have $A_1$ and $A_2$). This split is what we can call a "decision point". Assuming all your leaf-node timetables are stored in a list, you could figure out where the decision point was, and then bounce over to the corresponding node with the alternate decision.

Example: Let's say, similar to your example we have courses $A$ and $B$, with sections $A_1, A_2, A_3, B_1, B_2$. We then get a decision tree:

You can see the decision point of course $A$ is at the first level. Similarly you see the decision point of course $B$ is at the second level. The red line in there represents an example of two timetables that differ only by their grandparent, rather than just their parent. We can use some math and indexing to figure out how they're related.

As long as your course decision at each level is consistent, we can use some math and indexing to figure this out pretty easily.

Let's say you have $n$ courses: $c_1, c_2, \dots, c_n$.

Now let's define the size of a course as the number of sections = $|c_i|$.

It's pretty clear to see that, in the end, the number of leaf node timetables we'll have is $m = \prod_{i=1}^n |c_i|$. Let's assume courses are decided in increasing order (i.e. $c_1$ is decided at level 1 in the decision tree, $c_2$ is decided at level 2, etc.). If your leaf nodes are contained in a list, we can easily find related nodes based on the level of a particular course decision.

Let's say we look at leaf node timetable $j$. If we want to find all timetables that only differ at course $i$, we know they will be $\frac{m}{\prod_{k = 1}^i |c_k|}$ away.

An example might help, it's extremely clear if we're only dealing with a binary tree (each course has 2 sections). Let's say we have 3 courses: $A, B, C$. We then end up with a list of leaf nodes:

$$\left[(A_1, B_1, C_1), (A_1, B_1, C_2), (A_1, B_2, C_1), (A_1, B_2, C_2), (A_2, B_1, C_1), (A_2, B_1, C_2), (A_2, B_2, C_1), (A_2, B_2, C_2)\right]$$

We can represent these in binary:

$$\left[000, 001, 010, 011, 100, 101, 110, 111\right]$$

If we wanted to find where $111$ differs at course $B$. We find the distance between them is:

$$
\begin{align}
d & = \frac{m}{\prod_{k = 1}^i |c_k|}\\
& = \frac{8}{\prod_{k = 1}^2 |c_k|}\\
& = \frac{8}{2 \cdot 2}\\
& = 2\\
\end{align}
$$

Now deciding whether to subtract or add this distance is left up to simple edge case handling. But we see that 2 indices away from $111$ is $101$, which is the difference at course $B$ we were looking for. You should be able to take this approach to determine each differing timetable without having to compare everyone.

Misinterpretted Response Below

This algorithm seems similar to itemset lattice generation in association rule mining. Not the actual machine learning part, just the itemset generation. With this in mind, memoization in general would help downsize the repeated timetables. If you find that a child subproblem has already been solved, you can link the parent to that memoized solution, reducing the amount of links in your tree while keeping the children/parent connections consistent.

Memoization could also help with the "one section swap" connection. You already know all siblings will be "one section swap" connections. From there, it's simple to see that all leaf siblings will be connected. Using memoization these leaf-to-leaf sibling relationships will be much tighter and should basically figure themselves out.

Let's take an example with 5 sections $A, B, C, D, E$, assume a timetable is full when it gets 3 courses and just to add some variation let's say section $A$ conflicts with section $E$. If my understanding is correct your graph should look like the following, where green edges are "memoized" edges from parent to memoized child. Red crossed nodes are conflicting timetables.

Then, you may notice that we can construct a sibling graph of the leaf nodes:

Interestingly (but expected) the sibling graph connects all valid complete timetables and all connections are "one section swap" connections! So I definitely think memoization is the way to go.


How does an automaton actually "compute"? In my studies in computability I have come across the notion of the "machine", an abstract representation of a device that essentially computes. I have read about Turing Machines and Wolfram's binary cellular automata and I understand them.ie. the rules, states, colours, etc. and how they work. They begin in some state and run forever(unless a terminating state is specified). The point I'm trying to make here is that they receive no external input and are essentially functions of themselves:their current state is some function of its starting state, unlike realistic computers.

For the above reasons I'd like to know why automata are used to represent computers. More generally how can a machine be used to represent a computation?

Most generally, an automata is a model of computation that describes the process how to convert an input to a solution. Converting means that there is a certain set of finite, elementary, local transformation rules, that is applied to the input. The idea behind the automata might be motivated by mechanical designs, however the concept is purely mathematical. In other words an instance of an automaton is a simplistic form of an algorithm. The concept of an automaton describes the way how computations in this model are carried out. Different models have different computational powers.

A realistic computer can be also described as a mathematical model. However the setting here is slightly different, since you will not want to build a new computer for every algorithmic problem you encounter. Also a computer is an interactive system, whereas classical automata are not. The closest model for a computer is the DFA. A computer has a large but finite set of ressources, hence the status of the system can be determined by a fixed-size description (think of a huge core dump). Depending on the input (clock, user input, etc.) the computer jumps form one state to a new state in a certain well-defined and unique way.

You might be disappointed, when you hear that closest model to a realistic computer is a DFA. But you should think of an automaton more as a formalism how to write an algorithm. And from that perspective, the way you write software (algorithms) on you computer, is equivalent to writing Turing machine programs.

Maybe you are confused by the fact, that automata work on strings, and not on other problem instances. However, this is not a big deal, since we can encode an instance as a string.


Schedule X Classes In N Classrooms I would really appreciate any thought on this, or under which category does this problem fall (Interval scheduling, Interval partitioning,...)
I am really out of thoughts

I have X number of classes each with starting, and finishing time, and N number of free classrooms.
And I want to find the maximum number of non-conflicting classes that can be scheduled in those N classrooms.

What I've tries so far :

- First algorithm:

Sort Classes in ascending order according to the finishing time of each class.
Starting with the minimal finishing time, pick all the intervals that don't conflict with it and save it in a subset.
Repeat the first two steps on the very next interval that conflicts with the one we were working on before.

Why wrong?

Ex: we have 4 classes (1,4) (2,6) (6,7) (4,8) and we want to find the maximum number of non-conflicting ones that can be fit in 2 classes.

Starting the algorithm on (1,4) will give me subset {(1,4)(6,7)} that can be fit in the first classroom, and in the second classroom i need to put either (2,6) or (4,8) but not both since they conflict, so in total 3 of those classes can be fit in 2 classrooms using this approach.
However in real life you can put {(1,4),(4,8)} in a room and {(2,6),(6,7)} in the other, so all of the classes can be held in the 2 rooms.

- Second algorithm

Sort Classes in ascending order according to the starting time of each class.
Starting with the minimal starting time, pick all the intervals that don't conflict with it and save it in a subset.
Repeat the first two steps on the very next interval that conflicts with the one we were working on before.

Why wrong?

Ex: we have 4 classes (1,2) (2,1000) (6,7) (7,8) and we want to find the maximum number of non-conflicting ones that can be fit in 1 class.

Starting the algorithm on (1,2) will give me subset {(1,2)(2,1000)} that can be fit in the first classroom, and that's it, so in total 2 of those classes can be fit in a classroom using this approach.
However in real life you can put {(1,2),(6,7),(7,8)} in a room and, so 3 of the classes can be held in a room.

The minimal number of rooms needed can be computed by considering the classes in order of finish times, and if a class can't be fit into any one of the rooms in use, create a new room for it. See e.g. Erickson, "Algorithms", section 4.2.

This is the problem of asking if an interval graph can be colored with $N$ colors (the rooms). Perhaps digging into scheduling nets some algorithm(s). It isn't a problem for which I've seen a simple algorithm. Determining if a general graph is $N$ colorable is NP-complete (i.e., no much better solution expected than just trying all possibilities) if $N \ge 3$, perhaps being an interval graph is enough of a restriction to make it tractable...


Creating a Deterministic Push Down Automata I saw this old post on stack overflow of a PDA that accepts a language where there are exactly twice as many a's as there are b's. The image they used is below and so is the link to the post itself.

PDA for language that accepts twice as many a's as b's.

It was commented that the PDA was not deterministic. So I'm wondering what exactly makes a PDA deterministic, for example, would you remove the epsilon transitions here to make it deterministic or what?

If somebody could convert this into a deterministic PDA and explain the steps to do so, I would appreciate it, I'm pretty lost when it comes to push down automata.

Just like any automaton, a PDA is nondeterministic if (and only if) the transition relation is not a function, that is there are configurations that have multiple possible succeeding configurations. If this is the case for reachable configurations, this means that a non-deterministic automaton has inputs for which there are multiple computations.

Here, the transition $(\varepsilon, Z0/Z0)$ to state three may be taken even though the word has not been completely read, that is in configurations of the form

$\qquad (\alpha 1 \beta, Z0)$

you can either take transition $(\beta_1, Z0/\beta_1Z0)$ or $(\varepsilon, Z0/Z0)$ -- the automaton is non-deterministic. Of course, taking the latter always leads to rejecting the input unless $\beta = \varepsilon$, Since there is no other nondeterminism, this implies that the automaton is unambiguous.

Converting an NPDA to a DPDA is not always possible; NPDA define a properly larger language class than DPDA. Given an NPDA, checking if an equivalent DPDA exists is undecidable. And even if there is one (and you know that) there is no algorithm to find it. That is to say, there is no general, algorithmic technique for that part of your question.


Why does Karger's algorithm work "with high probability" I'm reading Karger 1993's "Global Min-cuts in RNC, and Other Ramifications of a Simple Min-Cut Algorithm" (link).

It states that a single round of contractions yields a min-cut with probability $\Omega(n^{-2})$ and concludes that $O(n^2 \log n)$ independent contractions are sufficient to find a min-cut with high probability.

It makes sense to me that $O(n^2)$ independent contractions yields a min-cut with a probability of approximately 1. Anything above this increases the probability, but why has $\log n$ being chosen?

Lets say that the algorithm succeeds if it produces a min cut. First, it is proved that a single run of the algorithm succeeds with probability $\Omega(n^{-2})$, i.e. with probability $\ge \frac{c}{n^2}$ for some $c>0$.

This is, of course, very bad. For large $n$ our success probability converges to zero. However, if we run it independently $k$ times, then our failure probability is now $\left(1-\frac{c}{n^2}\right)^k$ (we choose the minimal cut obtained from the $k$ runs, in order to fail finding the cut in this manner we must fail every time). Finally, we have:

$\Pr\left[\text{failure}\right]\le \left(1-\frac{c}{n^2}\right)^k\le
e^{-\frac{kc}{n^2}}$, taking $k=n^2\log n$ we get:

$\Pr\left[\text{failure}\right]\le e^{-c\log n} = \frac{1}{n^c}$, which converges to zero, as apposed to our failure probability after a single run of the algorithm.


Sorting in O(n) time in a finite domain I've been stuck with this problem for 2 weeks. Any idea of how to aproach it?.

  Let $L$ be a list of $n$ different integer numbers, assume that the elements of $L$ are in the range $[1,750]$. Design a linear ordering algorithm to order the elements of $L$.

I already tried with insertion sort. But I'm not sure if my approach is right:

Construct an array of bits. Initialize them to zero.
Read the input, for each value you see set the respective bit in the array to 1.
Scan the array, for each bit set, output the respective value.

Complexity: $O(2n) = O(n)$

I also wanted to use radix sort but I can't understand how to apply it, any idea?

Bitvector approach is correct solution.

Problem statement tells that you are given $n$ different integers so there is no need to count multiple occurrence of number in sequence. This also allows you to cut down needed storage to $\lceil{\frac{750}{8}}\rceil = 94$ bytes.

Now the algorithm:

Input: $A$ - array of unique integers, 1 based

Output: None - we update given array

B[750] = 0; bitvector of len 750 initially set to 0
for each i in A
    B[i] = 1
k = 1
for j = 1 to 750
    if B[j]
        A[k] = j
        k = k+1

This obviously runs in $O(n)$ and uses $O(1)$ memory.

This can run in linear time because it isn't compare based sorting. As you correctly pointed out every compare based sorting must take at least $O(n \log n)$ steps.

This approach is special case of bucket sorting but we used information about problem statement (namely: unique integers and range of those integers)


How to actually implement universal hashing? I sort of get what it is, but I don't understand how its actually supposed to be used in algorithms. Suppose the hash function is $h_{ab}(x) = ((ax+b) \mod p ) \mod m$ where $a$ not equal to 0. If I wanted to insert something into the table, would I calculate the bucket to place it in using the hash function and then place it in that bucket? How would I go about retrieving that data later on?

One example of universal hashing's application is perfect hashing. If you know all the keys beforehand, we can obtain $O(1)$ time for search, insert, delete (dynamic perfect hashing exists but is difficult to implement). More concretely we hash all of our values with an initial hash function into our table and keep track of where collisions occurred. For wherever $d>1$ collisions occurred, you build another hash table of size $d^2$. You obtain a hash function for this ($d^2$ size) table by applying universal hashing until you get no collisions.

Universal hashing guarantees that the probability of getting collisions with any two distinct keys is $\leq \frac{1}m$ where $m$ is our table size. Following your universal hash functions $h_{a,b}$ defined above (which is proved to be universal using number theory), we can try various $a,b$ in each $d^2$ size table until we get no collisions.

So to answer your question you just try a bunch of times (usually not too many as shown by probabilistic analysis and universal hashing) until you get a hash function that works for your problem setting and then save that hash function to use later for retrieval, insertion...

To be clear, the cost of utilizing this data structure is $O(1)$ because we only need to compute the first hash function and then the second hash function (we obtained via universal hashing).


How fast can all nth roots of an integer be computed? I mean that for every $i$ from 2 to $\lceil \log_2n\rceil$ I want to know $\lfloor \sqrt[i]{n}\rfloor$. Could this be done faster than computing the roots one by one?

Let's say n is very large, say around $2^{1000}$. In theory, you can calculate the k-th root of n by calculating $2^{(\log n) / k}$. Doing this for multiple k means you calculate $\log n$ only once, so you save some time here.

You will spend a large amount of time calculating say the first 50 roots because you need very high precision to calculate the root rounded down to the nearest integer. I can't see you saving any time by calculating multiple roots together.

The next roots are much easier to calculate. Then if k gets large, say 200, you will find that many roots rounded down are the same. Here you can make some savings by calculating for which range of integers k the k-th root of n will be between some integer r and r+1, and therefore the k-th root rounded down equals r. In this example there will be a few hundred k where the k-th root rounded down equals 2, for example.

But I think the first few roots (2nd, 3rd, 4th root) will take so much more time due to the high precision required, that the effort for the remaining roots will be much smaller. So I would say that you can save a little bit of time, but likely just a constant factor.

(Also, the effort may be bigger if the k-th root of n is very, very close to an integer, but that doesn't change the analysis. )


Amortized analysis of binary counter with increment and resetting operations I have a question about a specific amortized accounting algorithm and to be specific the variant with Reset operation.

First, 9th line of increment sets $\max[A]$ to -1 if $i \le \max[A]$  because for example going from 100 to 101 would set $\max[A]$ to $-1$ which does not make much sense.

Then, "if max[A] increases place 1 dollar as a credit on a new high-order 1." - when the high-order 1 has been set, 2 coins were given for this operation in increment - one for actually setting the bit to 1 and one for for the future, hence eventual reset to 0 would be covered by it. Why do we need to put yet another coin?

First, 9th line of increment sets $\max[A]$ to -1 if $i \le \max[A]$ does not make much sense.

It does not make sense because it is wrong. This part of code has been wrongly aligned. It should be

5. if i < length [A]
6.   then A[i] = 1
7.       if i > max[A]
8.         then max[A] = i
9.   else max[A] = -1 // the array A overflows; A is effectively reset to 0. So max[A] = -1.

  Why do we need to put yet another coin?

As explained in the article, the amortized costs of INC and RESET are $\$$4 and $\$$1, respectively.

$\$$4 for INC is composed of

pay $\$$1 to set 0 to 1;
place another $\$$1 on the same bit as credit. The credit on each 1 bit will pay to reset the bit during INC (not by RESET);
pay $\$$1 to update max[A]
place an additional $\$$1 of credit on the new high-order 1 (If max[A] does not increase we just waste that one dollar). The credit will pay to reset the bit during RESET.

$\$$1 for RESET is

pay $\$$1 to reset max[A]. Note that the resetting of bits From i = 0 to max[A] is paid for by the credit stored on the bits (each bit reset here has a credit on it due to the last $\$$1 for INC).

Added: For your specific question on "another $\$$1 on bit 1", note that the first $\$$1 credit on each bit 1 put by INC is consumed by the "resetting" part in INC itself (just as in the binary counter without the RESET operation). That is why you need another $\$$1 on each, to pay for the RESET operation (i.e., the code From i = 0 to max[A] A[i] = 0). The charged $\$$1 for RESET operation is only for the update of max[A].


Computing morphic word produced by uniform morphism Let $\Sigma = \{a,b,c\}$, and consider the function $f\colon \Sigma \to \Sigma^*$ given by $f(a) = abc$, $f(b) = bac$, and $f(c) = cba$. We can extend $f$ to $\Sigma^*$ in the obvious way. Since $f(a)$ starts with $a$, it can be shown inductively that $f^{(n-1)}(a)$ is a prefix of $f^{(n)}(a)$ for every $n$, where $f^{(n)}(a)$ is the result of applying $f$ on $a$ for $n$ times:
\begin{align}
&f^{(0)}(a) = a \\
&f^{(1)}(a) = abc \\
&f^{(2)}(a) = abcbaccba
\end{align}
and so on. Hence the sequence $f^{(n)}(a)$ converges to an infinite limit word $f^{(\infty)}(a)$.

How do I compute the $i$'th symbol of $f^{(\infty)}(a)$?

Denote $f^{(\infty)}(a)$ by $w$. Thus $f(w) = w$. Let $w_0,w_1,w_2,\ldots \in \{a,b,c\}$ be the individual symbols of $w$. The crucial observation is that if $n = 3m + r$ for $r \in \{0,1,2\}$ then
$$
w_n = f(w_m)_r.
$$
Indeed, since $w = f(w)$, we have
$$
w_0 w_1 w_2 w_3 w_4 w_5 w_6 w_7 w_8 \ldots = f(w_0 w_1 w_2 \ldots) = f(w_0) f(w_1) f(w_2) \ldots,
$$
from which this formula can be recovered.
This gives a very simple recursive formula for computing $w_n$:
$$
w_n = f(w_{\lfloor n/3 \rfloor})_{n \bmod 3},
$$
with base case $w_0 = a$.
A similar approach works for every morphic word produced by a uniform morphism (one in which $|f(\sigma)|$ is the same for all $\sigma \in \Sigma$).


What memory locations will the CPU fetch instructions from with instruction length of 16bits While reading Stallings OS Internals and Design, I run into problem. Here is example from the book.

  For example, consider a simplified computer in which each instruction occupies one 16-bit word of memory. Assume that the PC is set to the location 300. On succeeding instruction cycles, it will fetch instructions from locations 301, 302, ...

My question is: If the length of instructions is 16bits, and the smallest addressable unit of the memory is 1B, why on succeeding instruction cycles it will fetch instructions from locations 301 and 302, and not multiples of two, 302 and 304?

Is the memory then organised as a sequence of 16bit long memory words?

I too read the book. If Dr. Stallings has quoted this, the memory locations 301 and 302 must be referring to word-wise and not byte-wise locations.


Formulate the Marriage Problem into a Maximum-flow problem (Graph theory) Suppose I have $M=\{1,\ldots, n\}$ men and $W = \{1, \ldots, n\}$ women and $B =\{1, \ldots, m\}$ brokers, such that each broker knows a subset of $M \times W$ and for each pair in this subset a marriage can be set up among the corresponding man and women.

Each broker $i$ can set up a maximum of $b_i$ marriages and a person can only be married once. Also we assume all marriages are heterosexual.

I want to determine the maximum number of marriages possible and I want to show that the answer can be found be solving a maximum-flow problem.

What I've tried:

Make source and sink nodes with opposite demand. And then for each ordered pair $(i,j)$ where $i$ is a woman and $j$ is a man making a node. For each broker $j$ make a corresponding node and introduce an arc with capcity $b_j$. For each node $(i,j)$ make an arc from broker $k$ with capacity $1$ if broker $k$ can arrange a marriage otherwise $0$.

However, after this I stop. I need to keep track of state, that is no person gets married twice !

You shouldn't need to keep track of state. This can all be handled with capacity constraints over the nodes. The network can be structured as follows:

Start with the graph where one partition consists only of the "men" nodes and the other partition consists of the "women" nodes. Now, add a node for each broker $b$ and for each marriage pair $(m, w)$ on $b$'s list create two edges $(m, b)$ and $(b, w)$. Finally add a source node connected to all men and a sink node connected to all women (you can add another arc between those to simplify constraint cases if you want, but it's not necessary).

So now we have a graph, but to have a proper flow-network we need capacity constraints. For each man and women node we have a capacity constraint of 1, since they can each only marry at most one person. For the $i$th broker node, add a capacity constraint of $b_i$. This way the total number of flows (marriages) going through the broker is at most $b_i$.

Compute maximum flow over this graph and you should be good to go.


A variant of the vertex cover problem on trees Consider the following variation on the vertex cover problem: given a tree on $n$ vertices, we are asked to calculate minimum size of a multiset $S$ such for each edge $(u,v)$ in the tree at least one of the following holds:

$u\in S$,
$v\in S$,
there are at least two vertices in $S$, each of which is adjacent to $u$ or $v$.

Since $S$ is a multiset, a vertex may be in $S$ multiple times.

My hunch is the following. First of all, we take into consideration the following fact: in optimal solution each vertex is in $S$ at most twice. So we can traverse tree in post-order and calculate results for the three cases where a vertex is not in the optimal $S$, it's in once and it's in twice.

Unfortunately I can't link relations between subproblems and I'm not sure if this idea would be correct.

Hints or references are both welcome. Many thanks.

Define $f(v,r,s)$ to be the minimum size of a multiset $S$ that covers the entire tree rooted at $v$, such that $S$ contains exactly $r$ copies of $v$'s parent and exactly $s$ copies of $v$.

Then you can express $f(v,r,s)$ in terms of the values $f(w_i,s,t_i)$, where the $w_i$'s are the children of $v$.  If the tree is a binary tree, there are only $9=O(1)$ cases you need to consider and at most $2\times 3=O(1)$ terms in the recursive expression for $f(v,r,s)$.  The case analysis gets a bit ugly, but it's all $O(1)$.

Therefore, you get a $O(n)$ time algorithm for this problem, if the tree is guaranteed to be a binary tree.  I don't know what happens for general trees of unlimited degree.


Finding a winner in a "long list" This is from betting domain which has something that is called a long list: a list of a "home team win/draw/away team win"  markets for 13 games.
A punter can select any combination of the possible outcomes which are encoded in a following way:

1 - home team wins
2 - draw
4 - away team wins
3 - home team wins or draw
5 - home team wins or away team wins
6 - draw or away team wins
7 - home team wins or draw or away team wins

Meaning a [3, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7] represents a selection where punter put following bets:

"home team wins or draw" in a first game
"home team wins"  in games 2-12
"home team wins or draw or away team wins"  in 13th game

After games are finished there will be another 13 elements list representing winning outcomes, for example: [4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] means that in a first game away team won and in all other games home team won.

The question is if I'm missing any properties within those numbers that will make finding a winning bets easier than comparing each number one by one? Like in our case case checking if there are bets that has 4,5, 6 or 7 for the first game and 1, 3, 5 or 7 for rest of them.

The bitwise and of the bet and result is nonzero if and only if the bet is winning.
Further, the bitwise and has exactly one bit set if the bet wins.

To see this, note that the encoding of a bet has bit $1$ set iff it wins if the home team wins, bit $2$ set iff it wins if the game is a draw, and bit $4$ set iff it wins if the away team wins.

For example, if our bet is 6 - draw or away team wins, its binary encoding is 110. Then if the away team wins, the result is encoded as 100 and the bitwise and is 100. If the home team wins, the result is encoded as 001 and the bitwise and is 000.

In the word-ram model this can even help us calculate the result asymptotically faster: if the encodings of the bets and results are stored consecutively in binary with 3 bits per number, then counting the number of bits in the bitwise and of these two sequences gives the number of won bets in $\mathcal{O}(\frac{n}{w})$ with $w$ bits per word. Similarly all winning bets could be found in $\mathcal{O}(\frac{n}{w} + r)$ where $r$ is the number of winning bets. Of course this assumes the representation of the data is convenient for us, if it isn't, we need $\mathcal{O}(n)$ work to change its representation.

For example, the bets [3, 6, 1] and results [4, 2, 1] would be represented as 110011100 and 001010100 respectively, the bitwise and of which is 000010100. This indeed has two set bits corresponding to the two winning bets.


How are variables stored in and retrieved from the program stack? Apologies in advance for the naivety of this question. I am a 50 year old artist trying to properly understand computers really for the first time. So here goes.

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

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

Thanks for reading this far.

Storing local variables on a stack is an implementation detail – basically an optimization. You can think of it this way. When entering a function, space for all local variables is allocated somewhere. You can then access all variables, since you know their location somehow (this is part of the process of allocation). When leaving a function, the space is deallocated (freed).

The stack is one way of implementing this process – you can think of it as a kind of "fast heap" which has limited size and so is only appropriate for small variables. As an additional optimization, all local variables are stored in one block. Since each local variable has known size, you know the offset of each variable in the block, and that is how you access it. This is in contrast to variables allocated on the heap, whose addresses are themselves stored in other variables.

You can think of the stack as very similar to the classical stack data structure, with one crucial difference: you are allowed to access items below the top-of-stack. Indeed, you can access the $k$th item from the top. This is how you can access all your local variables with pushing and popping. The only pushing being done is upon entering the function, and the only popping upon leaving the function.

Finally, let me mention that in practice, some of the local variables are stored in registers. This is since access to registers is faster than access to the stack. This is another way of implementing a space for local variables. Once again, we know exactly where a variable is stored (this time not via offset, but via the name of a register), and this kind of storage is only appropriate for small data.


Is union of context-free and non-context-free languages non-context-free? It is known that union of two context-free languages is also context-free.

But how about union of context-free and non-context-free languages?

Not in general. Consider a language $L$ over some alphabet $\Sigma$ such that neither $L$ nor its complement $\overline{L}$ is a decidable language. It is obvious that neither of these languages can be context-free. But $L \cup \overline{L} = \Sigma^*$, which is a context-free language.

And consider $\emptyset$, which is trivially a context-free language. Clearly $L \cup \emptyset = L$ is not a context-free language.


Converting a Mixed SUBSET-SUM Problem To All-Positive Case Let's say we have a SUBSET-SUM problem with list {$x_1,x_2,x_3,...x_N$} and weight $W$, with some of $x_i<0$. Is there a known way, in polynomial time, to convert this problem into an equivalent problem, but with all $x_i \geq 0$? And if there aren't any, is it possible for there to be such an algorithm?

Both variants are NP-complete, so such a reduction surely exists: the definition of NP-completeness guarantees it.
If you want an explicit reduction, you can reduce one to the other (reduce to 3SAT using Cook's theorem, then reduce 3SAT to the other using its NP-completeness).  The resulting reduction will be ugly, though, so I suspect this might not be what you're looking for.
If you want a simple and natural reduction, I'm not sure how to achieve it.


Reliability of a service Assume that I need to determine the reliability of a service. The service includes component a (software reliability=0.95) and component b (software reliability=0.98). I have 2 computers: Computer A (hardware reliability=0.99) and Computer B (hardware reliability=0.99).
I have two following cases:

Case 1: Deploy both a and b on computer A. For this case, the service
reliability is around 0.923.
Case 2: Deploy a on computer A, and b on computer B. For this case, the service reliability is around 0.912

I really wonder why the service reliability in case 2 is lower than in case 1. The thing is A and B have the same hardware reliability. Can someone clarify that?

Ignore the software reliability for now, and only focus on the machines.

In case 1 there is only one machine that can fail, and it fails 1% of the time.

In case 2 there are two machines that can fail. However, even if just one fails the service goes down. The chance that at least one machine fails is $1 - 0.99^2 = 1.99\%$. So instead of spreading the risk we've just made our service more liable to fail.

There are two components to making a system reliable despite hardware failure:

Spreading out risk of failure across multiple machines.
Making the system robust to failure of some machines.

In the exercise we do have #1 but are missing #2.


finding best n players in minimum number of comparisons I am trying to find out if there is any generic way to find out first to nth best player in a tournament if n is less than the square root of input size i.e. 5 best players in the sample size of 25 players?
I thought of using below approach to find out 2 best players.
So for finding out the 3rd best player we can use the same approach i.e.
players lost again best best player + players lost against 2nd best player should be again played against each other to find out the 3rd best player.
Am I right if this would be the minimum number of comparisons to get 3rd best player?
Or should I divide the players in square root of input size and then play in groups as this?
Edit:
When two players play better player always wins. You can design your own tournament strategy to figure out the best n players.

You can't.  There isn't enough information in a single elimination tournament to know who the $n$ best players are.  All you can infer is who the best player is.  You can't even tell who is second best; the second-best player could be any of the people who lost to the best player.

If you're not limited to a single-elimination tournament, I recommend you use a selection algorithm to find the top $n$ players, then use a sorting algorithm to rank-order those $n$ players.  Asymptotically, this needs only $O(N + n \log n)$ matches if you start out with $N$ players and want to rank-order the top $n$ of them.  If you only want to find the top $n$ players without rank-ordering them, a selection algorithm suffices, and then you'll only need $O(N)$ matches.  You can study the literature on selection algorithms and sorting algorithms to figure out how to reduce the constant factor hidden in the big-O notation.

In practice if you want to hold some matches simultaneously, you might want parallelizable selection algorithms and sorting algorithms.  Figuring out how to parallelize selection algorithms might be worth a question of its own.


Why on board graphics is unfit for gaming/rendering? What is the difference between a dedicated GPU and an integrated one?

The difference between dedicated and integrated device is in resources and power. Dedicated have own resources integrated share them with various tasks. Integrated is less parallel but has (commonly) higher frequency. Integrated card uses CPU and RAM while dedicated has own RAM and own cores (far more than dedicated one).

This makes integrated cards unfit for real graphics, besides rendering part there are also tasks like controlling the game, running AI, keeping buffers of done tasks etc.


How can OS schedule disk requests efficiently without knowing the LBN to PBN mapping ? I learn from the OS schoolbook that the OS has the function that schedule the disk requests with the knowing algorithms such as SSTF, SCAN .. However, the date layout inner disk drives now is very complex that we may can't know. Disk zoning, disk skew, disk slipping and many other features of disk drives changes the distribution of data layout.  So how can the OS do this work ?
Thanks!

Modern disks interfaces provide an approximation of position called the logical base address.  This is just a linear integer indexing scheme where each block gets a unique integer assigned to it.

While you can't calculate an exact "distance" (in terms of arm movement latency and rotational latency) between two blocks it is approximately the case that if the difference between address $a$ and address $b$ is smaller than the distance between address $a$ and address $c$ then block $a$ will be closer to block $b$ than it is to block $c$.

Disk scheduling algorithms try to improve average latency or average throughput without being significantly unfair or causing starvation.  They also don't know about requests that are going to arrive in the future, so whatever they do needs to be an approximation based only on the requests they've already seen.

Since the algorithms are approximate anyway, the fact that we don't know the exact distance between two requests is not particularly a problem.


How to find max number with a single-tape turing machine? I'd appreciate hints for this problem

I'm trying to design a Turing Machine which calculates $\max \{x_1, x_2,..,x_k \}$.

Assuming $1 = 1^1; 2=1^2; n=1^n$ and all numbers/strings are separated by a blank character $B$.

There are many ways to tackle this. This is just one suggestion. I assume you need a single-tape machine, and that you actually need to write it down formally, so you need a very simple solution, not something like "just compare the numbers".

Start by finding $\max\{x_1,x_2\}$, and replacing $x_1,x_2$ with this new number. To do this, you can take to new symbols $X,Y$, and erase one letter from each number using one of $X,Y$. After one of the numbers is erased, you remain with the second number. You can then erase the smaller number, and restore the bigger one to $1$'s.

Then, simply repeat the process until you are left with a single number.
It requires several states, but it shouldn't be too huge.


Trouble finding average case of a find max algorithm I'm trying to find the average case number of times that max is assigned by the algorithm findMax included below.
findMax(list):
    maxNum = -oo  # negative infinity
    for k = 0 to len(list)-1:
        if list[k] > maxNum:
            maxNum= list[k]
    return maxNum

The distribution I have considered is uniformly random.

At the back of the textbook I am currently using, the solution is said to be $O(logn)$, however, using the approach that I have came up with (which I'm not quite sure why is incorrect), I got $O(n)$ instead.
In my approach: I have used the following formula $$E[t_n] = \sum^{n}_{t=1}t \cdot Pr(t_n=t)$$
And, I considered how many times maxNum was updated to calculate the expected value. First, I noticed that if the max would have been the first element, maxNum would have only been updated once. If the max was the second element, then it would have been updated twice, and so forth. Using this reasoning, I deduced that the probability of maxNum appearing in the nth position is $\frac{1}{n}$. Then, I got
$$E[t_n] = 1 \cdot Pr(t_n = 1) + 2 \cdot Pr(t_n = 2) + ... + n \cdot Pr(t_n = n)$$
$$=\frac{n+1}{2}$$
$$\Rightarrow O(n)$$.
I am a bit lost and am unsure where my mistake took place exactly.

Let me start with your main question "where my mistake took place exactly?" - in short, the whole point is in the wrong choice of the probability distribution  for $Pr(t_n=t)$. You are considering the number of changes in the maximum, i.e. how many times maxNum was updated, but you are using probabilities for the  location the maximum in the array.
Before starting analysis, let me say, that, for example, CLRS  Introduction to Algorithms, Third Edition, on page 120, calls formula you are using "cumbersome" for calculating and choose indicator function way. Donald Ervin Knuth in TAOCP Volume 1, Third Edition, 1997, pages 96-101 are using generating functions mechanism.
Now in more detail: for simplicity, let's consider the case when you have only 4 elements in the array and let us consider only such 4s in which all elements are different i.e. $(a, b, c, d)$, where all are different. I bring the pseudocode for this case from the book  Jeffrey J. McConnell, Analysis of Algorithms: an Active Learning Approach , 2001, page 3
maxNum = a
if b > maxNum then
    maxNum = b
end if
if c > maxNum then
    maxNum = c
end if
if d > maxNum then
    maxNum = d
end if
return maxNum

where your loop is simply decomposed into separate lines and in 1-st line is not used negative infinity. As we are considering function $T$ the number of maxNum updatings, i.e. number of assignements, then, obviously $T$ have values 1,2,3,4. Probability distribution for $T$ can be counted directly and is
$Pr(T=1)$: $\frac{1}{4}=\frac{4}{16}$
$Pr(T=2)$: $\frac{1}{4}+\frac{1}{4}\cdot \frac{1}{2}+\frac{1}{4}\cdot \frac{1}{2}\cdot \frac{1}{2}=\frac{7}{16}$
$Pr(T=3)$: $\frac{1}{4}\cdot \frac{1}{2}+\frac{1}{4}\cdot \frac{1}{2}\cdot \frac{1}{2}+\frac{1}{4}\cdot \frac{1}{2}\cdot \frac{1}{2}=\frac{4}{16}$
$Pr(T=4)$: $\frac{1}{4}\cdot \frac{1}{2}\cdot \frac{1}{2}=\frac{1}{16}$
Anticipating the question of how these calculations were obtained, let me say that it is enough to simply consider the possible options for finding the maximum in the all fours and count their fractions.
To calculate general case, where we have $n$ elements in array it's more easy to find reccurence relation for $T(n)$:
$$T(n) = n \cdot T(n-1) + (n-1)!$$
and from here obtain expected value
$$\frac{ T(n)}{n!} = \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + ... + \frac{1}{n-1} + \frac{1}{n} = \sum_{i=1}^{n}\frac{1}{i} - 1 =\\
= \ln n + \gamma + \varepsilon_{n} -1 = \ln n +O(1)$$
where $\gamma$ is Euler–Mascheroni constant and $\varepsilon_{n} \sim \frac{1}{2n}, n\rightarrow \infty$.
Addition.
Now more about calculating probabilities in case of 4s $(a, b, c, d)$  where all are different:
The proportion of such fours in which the maximum is in the first place, i.e. maximum is $a$, is equal to the proportion of such fours in which the maximum is in second place , i.e. maximum is $b$, and is $\frac{1}{4}$. Same for cases with $c$ and $d$.
Such fours where maximum is $a$ and only they gives $1$ assignement for maxNum, i.e. $T=1$,  and so we obtain $Pr(T=1)$: $\frac{1}{4}=\frac{4}{16}$.
Such fours where maximum is $b$ gives $2$ assignements, $T=2$, but we can obtain $2$ assignements also from cases where $c$ or $d$ is maximum, so we can say, that $Pr(T=2)$ includes $\frac{1}{4}$ plus some more numbers i.e. we obtain first summand for $Pr(T=2)$.
Now let's take fours where maximum is $c$. This case can produce values $2, 3$ for $T$: when $b \gt a$, then $T=3$ and when $b \lt a$, then $T=2$. As proportion for both is $\frac{1}{4}\cdot \frac{1}{2}$, then we obtain second summand for $Pr(T=2)$ and first summand for $Pr(T=3)$.
Last we consider 4s where maximum is $d$. Hope it's easy to understand, that here we have $4$ parts with equal proportion $\frac{1}{4}\cdot \frac{1}{2}\cdot \frac{1}{2}$: 1) $b \gt a, c \gt b$ which gives $T=4$, 2) $b \gt a, c \lt b$ and $b \lt a, c \gt a$ which gives $T=3$, 3)$b \lt a, c \lt a $ which gives $T=2$. Correspondingly we obtain all remained summands.
At end let me say, that it's easy to write code for some virtual experiment, for example on python from random import uniform, I can share if needed, and check, that practical frequences approximates theoretical probabilities.


minimum moves for Knight on a infinite chessboard You are given an infinite chessboard, a knight, a source and a destination.(Normal chess rules apply) we are required to get move knight from source to destination in minimum moves possible.

I can only think of a bfs solution. Is there a better solution possible?

The question is further extended by adding obstacles to the board. How to solve this question what will be the complexity.(I basically need a answer for this.)

Thank you.

With obstacles, you can use an algorithm as it is used for routing the shortest car distance. The idea is that you perform a search not breadth first, but with moves first that get you closer to the target. And you start from both ends and meet in the middle.

Define the "optimal distance" between points as the distance given by the algorithm for lowest number of moves without obstacles. At the starting point, find all neighbouring points, and for each calculate a lower bound for the number of moves to the target: One initial move, and the moves for the closest distance to the target. Then the same from the other end. Next you examine those points with the lowest lower bound. All moves are eventually evaluated, bot you tend to check those first that get you closer to the target.


Representation of -40 in 8bit computer using 2's complement What is the representation of -40 in a 8bit computer using 2's complement intiger?

First of all, 40 in binary is 101000.

The 8-bit representation is obtained by zero-padding: 00101000.

The one's complement of this is obtained by inverting the bits: 11010111.

To obtain the two's complement, we simply add 1: 11011000.


Examples of problems for each class in $L \subseteq NL \subseteq P \subseteq NP \subseteq PSPACE$ Given that $L \subseteq NL \subseteq P \subseteq NP \subseteq PSPACE$ and that it is commonly believed that all these inclusions are strict can you provide examples of problems that are believed to be in each class and not in the preceding ones?

To try to narrow the scope of the question, could you provide paradigmatic examples of problems that are believed to be in each class and why they are so?

You can take complete problems for each class. Think of a complete problem as one which represents the "hardness" of this class, then under the assumption that all of the inclusions are strict, such a problem can not reside in the weaker classes.

If $\mathsf{L\neq NL}$, any $\mathsf{NL}$ complete problem (under logspace reductions) cannot lie in $L$ . An example for such a problem is deciding whether there exists a path between two given vertices in a directed graph.

If $\mathsf{P\neq NL}$, no $P$ complete problem (under logspace reductions) can lie in $\mathsf{NL}$ . One example for such a problem is $CVAL$, given a circuit and input, does the circuit outputs $1$ on the given input. You can find other examples of $P$ complete problems here.

If $\mathsf{P\neq NP}$, then NP-complete problems (under polynomial time reductions) cannot lie in $\mathsf{P}$. You can find hundreds of examples here, traveling salesman, hamiltonian path, SAT, just pick your favorite.

You probably got the point by now, but i'll say it anyway. If $\mathsf{NP\neq PSPACE}$ then PSPACE complete problems (under polynomial time reductions) cannot lie in $\mathsf{NP}$. Famous complete problems here are TQBF (checking if a CNF formula with quantifiers is true), and games (do I have a winning strategy in a game from a given position, of course you need to be careful and precisely define the language). You can find more examples on Wiki.

These were the easy examples, there are problems who are not complete for their class, but still believed to be hard. For example, FACTORING (deciding whether an integer has a factor smaller than some given number), is believed to be NP-intermediate (not NP complete but still not in P). See this question from cstheory about NL-intermediate problems. PSPACE is very far away from NP, and examples are easier here. If the polynomial hierarchy does not collapse, then any complete problem for $\Sigma_i$ with $i\ge 2$ is in PSPACE but not in NP.


Minimal Spanning Tree With Double Weight Parameters Consider a graph $G(V,E)$. Each edge $e$ has two weights $A_e$ and $B_e$. Find a spanning tree that minimizes the product $\left(\sum_{e \in T}{A_e}\right)\left(\sum_{e \in T}{B_e}\right)$. The algorithm should run in polynomial time with respect to $|V|, |E|$.

I find it difficult to adapt any of the traditional algorithms on spanning trees(Kruskal, Prim, Edge-Deletion). How to solve it? Any hints?

I'm going to assume you are not given negative weighted edges, because this may not work if there are negative weights.

Algorithm

For each of your edges, label them $1$ to $n$

Let $a_i$ weight A of edge number $i$

Let $b_i$ weight B of edge number $i$

Draw up this table

   |a_1 a_2 a_3 a_4 .. a_n
---+-------------------------
b_1|.........................
b_2|.........................
 . |.........................
 . |.........................
b_n|...................a_n * b_n

With each of the table elements being the product of row and column.

For each edge, sum the relevant table row and column (and remember to remove the element in the intersection since it has been summed twice).

Find the edge that has the largest sum, delete this edge if it doesn't disconnect the graph. Mark the edge as essential otherwise. If an edge has been deleted, fill its rows and columns with 0.

Correctness

The result is obviously a tree.

The result is obviously spanning since no vertices are disconnected.

The result is minimal? If there is another edge whose deletion will create a smaller spanning tree at the end of the algorithm, then that edge would have been deleted and nulled first. (if somebody could help me make this a bit more rigorous/and/or counter example then that would be great)

Runtime

Obviously polynomial in $|V|$.

edit

$(2,11), (11,2), (4,6)$ is not a counter example.

$a_1 = 2, a_2 = 11, a_3 = 4$

$b_1 = 11, b_2 = 2, b_3 = 6$

Then

   | 2     11     4
---+--------------------
11 | 22    121    44
 2 | 4     22     8
 6 | 12    66     24

\begin{align*}
(4,6) &= 44 + 8 + 24 + 66 + 12 = 154 \\
(2,11) &= 22 + 4 + 12 + 121 + 44 = 203 \\
(11,2) &= 121 + 22 + 66 + 4 + 8 = 221
\end{align*}

$(11,2)$ gets removed.

End up with $(2,11), (4,6) = 6 * 17 = 102$

Other spanning trees are

$(11,2), (4,6) = 15 * 12 = 180$

$(2,11), (11,2) = 13 * 13 = 169$


Determine the number of elements that is divisible by a prime number in an array I have an array (|A|≤10^6) of numbers (not guaranteed to be distinct) and a set of prime numbers.
For each of the prime numbers, I want to know how many numbers in the first array are divisible by this prime number.
For example:

Array = {5 5 7 10 14 15}
Set = {2 3 5 7 11}
result:2:2; 3:1; 5:4; 7: 2; 11:0

Brute force by using nested loops works, but is there a faster way?

Yes if the number of integers and primes is large. Sort the primes in ascending order. Count the number of divisible numbers and remove prime factors until the numbers are all larger than the square of the smallest remaining primes. Now the remaining numbers are all primes. Sort them and check which ones are in the list of primes, in linear order.
This works as long as most primes are greater than the square root of the largest number.


Understanding decidability Sorry this is a basic question to understand decidability. It is the first time I see it in my undergrad course.

1)
I am reading why the language AFDA is decidable and why ATM (halting problem) is not. The explanation says that the emulated TM in ATM might loop forever. I agree, because a specific input string might make the TM going forever, always able to apply rules and never halting.

However, why is AFDA decidable? What if the automaton never reaches any of its final states and keeps looping? There might be a specific input that makes the FDA never reach such states. I understand that once the input string finishes, it will be either accepted or rejected, but what if it does not finish? I'm assuming the input string in the TM can be infinite.

2)
The same problem I have here:

A = { 0^k 1^k | k >= 0}

This language is decidable, and it will halt in strings like 10, 010101, etc but what if the input string is infinite 01010101...... it will never end.

What am I missing?

1) The automaton "halts" after it reads the input, whether or not it reaches a final state.  It accepts the input if, when it halts, it's in a final state.

2) Inputs are always finite strings.  There are generalizations of finite automata ($\omega$-automata of various kinds  [Buchi, Rabin, Muller]) that accept $\omega$-words (countably infinite strings) as inputs.


Job sites for applied/interdisciplinary mathematics related to computer science? I'm looking for job sites in applied/interdisciplinary mathematics, more specially, say postdocs or higher positions in mathematics and medical imaging, mathematics and computer vision. I'm aware of mostly all the popular job sites, mathjobs, euro math jobs, jobs.ac.uk, nordic math jobs etc etc, but most of the jobs there are of 'pure' nature, with very few for applied/interdisciplinary.

I'm trying to find postdoctoral position in mathematical imaging problems, which would use significant amount of conformal/quasiconformal mappings, Riemann surfaces, differential geometry etc. Looking into individual group's webpage is too much work. But if there's an webpage containing all the information, that'll be much better!

So, if you know any such website for the above (for Europe(preferable) and US), I'd appreciate if you could pass them onto me. Thanks!

There are 2 google lists:

Imageworld

visionlist

You can join these. They have a lot of information.


Haskell type of lambda expressions I'm new to Haskell and have some general questions.

Question 1:
The Haskell expression (\x -> \x -> x) is the same as the λ-term λx.λx.x
The type of this expression is p1 -> p2 -> p2. What does this mean?

Question 2:
λyx.x is shorthand for λy.λx.x. In Haskell (\y x -> x) is shorthand for (\y -> \x -> x). Do (\x x -> x) and (\x -> \x -> x) have the same type in Haskell and why?

Contrary to Church's lambda calculus, Haskell is typed.

Answer 1

When types are denoted with lower-case letters (such as p1 and p2) that indicates a type variable. When types are denoted with capital letters (e.g. Bool or Int) they're concrete types.

The type p1 -> p2 -> p2 indicates a function in curried form. You can think of it as a function that takes a p1 value as input and returns a new function of the type p2 -> p2, or you can think of it as a function that takes p1 and p2 as inputs, and returns p2 as output. The right-most type indicates the return type.

The types p1 and p2 are here unconstrained, which means that they can be literally any type - Bool, Int, or your own custom type(s). They can also be equal. For example, both p1 and p2 could be Bool.

The interpretation of p1 -> p2 -> p2 as a function that takes p1 as input and returns a function with the type p2 -> p2 makes most sense. What really happens is that in the expression \x -> \x -> x the second x shadows the first x. If you think of the expression as \x -> (\x -> x), you can see that the returned function is \x -> x, and that it doesn't matter what the 'leftmost' x was. Thus, the type of the leftmost x is irrelevant because the value is never used. It'd be more idiomatic to write the expression as \_ -> \x -> x. The underscore is Haskell's wildcard placeholder, indicating that there's a variable there, but we don't care about it.

In the expression \x -> x, however, the input value is being returned unmodified, so that the type must be p2 -> p2 - i.e. the output type must be the same as the input type.

The expression \x -> x is the identity function, and it's already built into Haskell as the function id. Likewise, a function that ignores its input and instead always returns the same result is called const. Thus, the expression \x -> \x -> x is equivalent to const id.

Answer 2

The expression \x x -> x is invalid in Haskell. It would indicate a (curried) function that takes two arguments, but returns a value. Which one of them? Keep in mind that they could be different.

In Haskell, variables are bound to input arguments, but the binding must be unambiguous. That's the way that the language works, but it's quite a standard design.

For an example of a language that behaves differently you might look to Erlang, where a function that receives two arguments with the same variable name indicates a pattern-match where the match only succeeds if the arguments are equal to each other. Erlang is the only language I'm aware of that does it that way, but I only know a handful of languages...


How to prove that in an AVL tree with height h, the depth of every leaf node is at least $\lceil h/2 \rceil$ I have an AVL tree with height h. I understand how to get h $\thickapprox$ 1.440 log N. However, I can't figure out how to calculate the minimum depth of a leaf node from root. I tried constructing a recursive formula where d = 1 + min(dL, dR) where dL and dR are the depths of the left and right subtree of the root. But can't get a solution of this. Can anyone help me out here?

Denote by $d(h)$ the minimum height of a leaf in an AVL tree of height $h$. One subtree of the root necessarily has height $h-1$, and the other one has height either $h-2$ or $h-1$ by the defining property of AVL trees. Therefore
$$
d(h) = \min(d(h-1),d(h-2)) + 1.
$$
Also, one checks that $d(0) = d(1) = 0$ (if one measures height as the maximum number of edges in a root-to-leaf path). The recurrence makes it clear that $d$ is monotone, and so $d(h) = d(h-2) + 1$. From here it's easy to calculate $d(h) = \lfloor h/2 \rfloor$.


Does $L_1L_2 = L_2L_1$ imply $L_1 = L_2$? Let $L_1, L_2 \subseteq \Sigma^*$ be two languages, where $\Sigma$ is some finite Alphabet.

Does $L_1L_2 = L_2L_1$ imply $L_1 = L_2$?

What if $L_1$ and $L_2$ are regular languages?

Can you give counterexamples?

No, just take as counter example $L_1=\epsilon$ and $L_2$ any other langage different from $L_1$.


NP-Hard on Complete Graphs I have a problem (A) on undirected graphs that I wish to show is NP-Hard. I can show that there is a reduction from a well known NP-Hard problem (B) to A by constructing an instance of A with a complete graph that solves B.

Since undirected graphs generalize complete graphs, am I safe in saying that A is NP-Hard for undirected graphs? Something about that doesn't seem right to me, since problem A on complete graphs is essentially the "non-graphical" version of the problem. Am I missing something?

Disclaimer: I am new to proving hardness results.

Usually, when reducing problem B to problem A, not all possible instances of problem A appear in the image of the reduction. This is absolutely not an issue.

In your case, you can say that problem A is NP-hard even if restricted only to complete graphs. This is a stronger result, which is a good thing, and definitely allowed.

As an example, 3-coloring is hard even for 4-colorable graphs, and even just for planar graphs. You show this (say) by reduction from SAT to 3-coloring, in which all the resulting graphs are planar. This is not a drawback – in fact it's a bonus.


How to express time complexity when the exponential "e" comes into play? I am new to all of this and I am trying to understand how to define Time Complexity. I have an algorithm which performs a set of operations on inputs of different size.

While timing the execution of such algorithm I have figured out that the time elapsed follows an exponential law:

Time(size)=0.15*exp(0.05*size)

My question: is it correct to define this complexity according to

T(n)=O(e^n)?

It depends on whether you're talking about $O$ or $\Theta$. The notation $O$ indicates that the complexity is "this much or smaller", and the notation $\Theta$ indicates that the complexity is "this much, no more or less".

The complexity of $0.15 e^{0.05 n}$ is $\Theta(e^{0.05 n})$. The complexity is not $\Theta(e^n)$, because $e^n$ grows faster than $e^{0.05 n}$ does (the ratio between the two increases without bound).

It is, in fact, true that $0.15 e^{0.05 n}$ is an $O(e^n)$ function, but this isn't a good description of the complexity, in much the same way that "more than a thousand people live in China" is not a good description of the population of China.

What this comes down to is that you should state the complexity as $\Theta(e^{0.05 n})$ or as $O(e^{0.05 n})$.


What is the use of First() and Follow() in compiler design? I am completely aware of how to calculate first and follow, my professor has taught me that well , but he had not explained what is the need of First() and Follow(), so any explanation why we need them will help me very much.

$FIRST$ and $FOLLOW$ sets are used by the algorithm which produces an $LL(k)$ parser from a grammar. They're also used in a number of other algorithms which analyze grammars, but most students will run into them when learning about top-down parsers.

Parsing is a tiny part of the work of producing a compiler, and in practice you can generate a parser using code-generation tools which avoid you having to know much about implementation details. So I'd say that th4e direct answer to your question is that $FIRST$ and $FOLLOW$ sets have very little to do with compiler design, but they are useful in the understanding of how particular parsing algorithms work.


Given directed connected weighted graph, check if d(v) = delta(s,v) I'm having some hard time with this problem.
Can someone give me some clue/guidance?

This is an homework question, so please don't just solve it.

  Given a weighted directed connected graph $G = (V,E)$  and given another
  function $d: V \to \mathbb{R}^+$ (including zero), find a linear time algorithm that checks if $d(v)=\text{delta}(s,v)$ for each $v$, for some fixed vertex $s$.

  $\text{delta}(s,v)$ is like in Dijkstra algorithm, meaning shortest path from $s$
  to $v$.

My thought is to make use of BST to check if these functions are equal, but I can't avoid running Dijkstra for it.

If $d$ indeed represents the length of the shortest path, we must have

$$
d(v)=
\begin{cases}
0, &\text{if $v=s$,}\\
\displaystyle\min_{u:(u,v)\in E}\{d(u)+w(u,v)\}, &\text{otherwise,}
\end{cases}
$$

where $w(u,v)$ is the weight of the edge $(u,v)$.

So you can check whether $d$ satisfies this property for all $v$. It takes only linear time. If $d$ does not satisfy this property, it cannot represent the length of the shortest path. However, if $d$ does satisfy this property, does it really represent the length of the shortest path? I'll let you figure out this part.

For a further hint:

   Note what you need to prove is that, for all $v$, $d(v)$ is length of the shortest path from $s$ to $v$. Suppose the shortest path from $s$ to $v$ contains $k$ edges, you may try a mathematical induction on $k$.


How does hashed inverted page table work? I understand hash function and inverted page table, but then the book I read describes something called hashed inverted page table (use hash to accelerate the finding because IPT is large), with TLB used. I don't understand why there is an arrow point to itself inside the hash table? Could anyone explain the mechanism?

From your picture, one definitely see a hash table collision solution. If one carefully examine it, will see that the table uses itself to solve the collision, that is Open Addressing.

In open addressing, the collision can be resolved by many methods;

Linear Probing
Quadratic Probing
Double hashing.

It might be Double Hashing or Quadratic Probing but the information is not enough to resolve.


How to show working for summing of Big O notation The equation below is intuitively correct, but how do you show that this is actually the case? What is the working out needed?
$$\sum_{i=1}^{n-1}O(lg n) = O(nlgn)$$

Summand inside sum is not depend on summation index, then pull it out and you have n−1 before log.


Performing semantic segmentation on images on word documents At the moment, I'm making a comparative analysis between two different neural networks for a class. The problem they are both trying to solve is detecting tables on documents. Below is an example of one:

One of the algorithms I am analyzing is a fully convolutional network. The way the algorithm works is that it goes pixel by pixel and assigns each pixel a label of which class it could be in (in my case, table or not a table).

However, my issue is how should you pre-process/label your data if you're training one of these networks? Because tables themselves have words on them, looking at such a fine resolution to detect tables is not optimal. It would be preferable if I could have the FCN look for structural elements that help us identify tables (big gaps, columns, header, etc).

I'm not sure how to train a network that goes pixel by pixel to search for the bigger structural elements. Any thoughts on this?

There are many papers on document structure analysis.  I suggest you read them, rather than trying to reinvent the wheel.  As they say, a week in the lab can save a day in the library.

I think there may be some misconceptions.  The way we evaluate neural networks is by trying them on a representative workload to see how well they perform.  There are effectively no useful methods for performing a "comparative analysis".  When you ask "how should you..", the answer with neural networks is typically "whatever works".  There are no rules.  Often helpful advice is to look for papers that have addressed this problem before and see what they do.

A plausible approach is to just feed in the entire image as input to the network, with no pre-processing (other than the standard pre-processing for images, i.e., to normalize pixels to mean 0 and variance 0).

Labels are more challenging, and that depends on what task exactly that you want to solve.  Presumably, you need to manually label the images and then use those as your labels.

How would you train such a network?  The same way you train any other network: you construct a training set, choose a loss function, and then use an optimizer to minimize the loss on that training set.


Minimum total waiting time for arrivals/durations I have come up with the following problem, and cannot seem to find an effective way of solving it:

  Consider $n$ clients arriving at a service point at time moments $\{a_i\}_{i=1}^n$ whose duration of service (by a single employee, let's say) is known
  to be $\{d_i\}_{i=1}^n$. Choose the turn of servicing them, such that
  the total sum of waiting times (i.e. if we consider $\{s_i\}_{i=1}^n$
  the start-of-service time for each client, then the total waiting time
  would be $\sum\limits_{i=1}^n\{s_i-a_i\}$) is minimized.

The only difference in this problem to the Interval Scheduling that has a greedy method of selecting the earliest finish time first, is that here all clients have to be serviced. (whereas in the Interval Scheduling, some intervals may not be selected)

Is there an efficient greedy algo for this problem? Or isn't there? Many obvious or less obvious approaches do not seem to work, example with this:

Client 1: arrival at 1, duration of 9
Client 2: arrival at 2, duration of 13
Client 3: arrival at 15, duration of $\epsilon$

The above example hints at choosing the smallest $a_i+d_i$ first, but I seem to be unable to prove this on an exchange argument... Is perhaps the problem NP-Complete?

Yes, this is NP-hard. Since neither the $a_i$ nor the $d_i$ depend on the solution, the problem is equivalent to the problem of minimizing the sum of the completion times of the requests, which is known in the scheduling literature as "$1|r_i|\sum C_i$" and is NP-hard. Reference:

J.K. Lenstra, A.H.G. Rinnooy Kan, and P. Brucker.
Complexity of machine scheduling problems.
Ann. of Discrete Math., 1:343-362, 1977.

Also, I disagree with the statement that "the only difference to Interval Scheduling is that here all clients have to be serviced". There is one more important difference: in Interval Scheduling, the algorithm can just accept or reject the clients, while in this problem, even after the algorithm accepts a client, it has to choose when to start it.


Finding a (minimal?) program that maps $M$ items to indices $[0,M)$ Let's say there are $M$ strings that we are trying to create a perfect hash for such that we get as output of the hash $[0,M)$ with no collisions, when hashing those $M$ items.

I know that there are algorithms that can help you achieve this by finding salt values to use with a given hash function that will cause this to happen (like this one http://blog.demofox.org/2015/12/14/o1-data-lookups-with-minimal-perfect-hashing/).

However, all of the algorithms I've seen are randomized/probabilistic: e.g., there is a probability $p$ for any particular salt value to yield a perfect hash, so keep trying until you find one.

Is there any deterministic algorithm for constructing a perfect hash?

Second, is there a deterministic algorithm to construct a perfect hash that is minimal in size (the smallest program that is a valid perfect hash on these $M$ items)?

Security isn't a concern, and while efficiency of the algorithm to find the mapping is nice, it isn't a requirement. Evaluating whatever mapping program was found should be as efficient as possible though.

There is a deterministic algorithm for constructing a perfect hash, if you don't care about efficiency.  For instance, you can enumerate all programs (in order of increasing size) and test each one to see which is the first that produces a valid perfect hash.  This is a valid deterministic algorithm that is guaranteed to always find a valid perfect hash (and even to find the minimal such program).  However, this will be extremely slow for all but the smallest values of $M$, so it's not likely to be useful in practice.

I expect that finding the smallest such program will be NP-hard, and probably $\Pi_2$-hard (loosely, "even harder than NP-hard").  I don't have a proof of this -- just a suspicion.  For example, the problem of circuit minimization is known to be $\Pi_2$-hard.  In other words, given a circuit $C$, it's $\Pi_2$-hard to find the smallest circuit $C'$ that computes the same function as $C$.  Your probably isn't quite the same, but it has a "similar feel", so I would expect your problem (finding the smallest deterministic program that yields a valid hash for the $M$ items) will also be hard.

If you are willing to make unproven assumptions, it is possible to come up with a deterministic algorithm that is also efficient: about as efficient as the randomized/probabilistic algorithms you know of it and want to avoid.  In particular, you can take a randomized algorithm and derandomize it as follows: fix a cryptographic-strength pseudorandom number generator (e.g., AES-CTR mode); fix a seed for it (e.g., the all-zeros AES key; or pick a random 128-bit value, and fix it as the AES key); feed this seed the prng algorithm and use it to generate an unending stream of pseudorandom numbers; now run the randomized algorithm, except that whenever it calls for a random number, give it the next pseudorandom number from the output of the crypto prng.  Note that this is a completely deterministic algorithm: the seed is hardcoded into the code of the algorithm and fixed for all time.  Here's what we know: if the pseudorandom number generation algorithm is cryptographically secure, and if the randomized algorithm outputs the correct answer, then (with high probability over the choice of seed) the deterministic algorithm also outputs the correct answer.

This means that if you know how to build a cryptographically-secure pseudorandom number generator, you can convert any randomized algorithm into a deterministic algorithm.  It may be surprising that cryptography has anything to do with this subject, since we don't require kind of security properties from the hash, but it turns out that this construction gives a generic way to derandomize any randomized algorithm.  Here's how to see the connection: the definition of what it means for a prng to be cryptographically-security is that no polynomial-time algorithm should be able to tell that it is receiving pseudorandomness rather than real randomness; thus, we can run the randomized algorithm, and swapping out the true-random bits for pseudorandom bits won't mess up the algorithm.

Thus, this will let you build a deterministic algorithm that is correct and efficient, if AES is secure (or one that works if factoring is hard, or based on any other cryptographic assumption).   It's widely believed that AES is secure (and factoring is hard, etc.), even though we have no proof, so this provides a reasonable practical solution to your problem, even though we have no proof that it works.


Partition problem with distinct integers The partition problem is a well-known NP-complete problem. In the definitions I have seen, the input is assumed to be a multiset of integers, and we want to decide the existence of a partition into two sets that have the same sum. My question is:

  Is the partition problem still NP-complete if all input integers are distinct (i.e., no integer is repeated)?

Here is an outline of a reduction from PARTITION to UNIQUE PARTITION. Suppose the original numbers are $x_1,\ldots,x_n$ and the target is $T$. I assume that all $x_i$ are positive integers. The new numbers are going to be $2^n x_i + i$, as well as $1,2,4,\ldots,2^{n/2}$, and the new target is $2^n T + 2^{n/2}$. (The numbers $2^n,2^{n/2}$ are quite arbitrary and could be made much smaller.)


How to purge a linked list in $\mathcal{O}(n\log n)$ time? I was wondering how to remove duplicate values from a linked list in $\mathcal{O}(n\lg n)$ time. I have an idea that by using merge sort when we want to compare elements for choosing the small one, if they are equal advance on pointer and just consider one element. Any alternatives?

You can do it in $O(n)$ as follows.

1) Build an hash table by traversing the linked list and adding its elements to the hash table. In each iteration, search the hash table for the current element being considered in the iteration. If the element is not found, add to the hash table the element value as the key, and 1 as the corresponding value. If you instead find the element (which has been inserted in a previous iteration), you simply add 1 to the corresponding value and update the hash table entry (correctly updating the element multiplicity). At the end, your hash table will contain at most $n$ entries (this corresponds to the case that the element in the linked list are distinct), or less than $n$ elements, with at least one of the entries showing a multiplicity greater than one. This takes $O(n)$ time since in each of the $n$ iterations the work done on the hash table is $O(1)$.

2) Now, traverse the hash table and build a new linked list by adding a node for each element found. this takes at most $O(n)$ since the hash table contains at most $n$ elements, the work done on each element of the hash table is $O(1)$ and adding a node to the new list takes $O(1)$.

Therefore, the total complexity is at most $O(n)$.


How does continuous computer vision works? First: I have programmed a few programs dealing with computer vision (not with libraries but from scratch):

Simple Character and Figure Recognition
Character and Figure Recognition with Neural networks
Facial recognition

so I am not asking for details on these.

The characteristic of all my programs is that once you focus your camera on something you want to analyze, you hit a command (it can be through several means- serial, voice orders, etc- it is not relevant how) and the system takes a photo and analyze it, then produce a result in some cases the camera is deactivated since it is resource intensive.

Following all that introduction,
my question is:

How do the programs that do continuous recognition work?

You have seem them, the camera is all the time on and it continually recognize or process things. Does it just do all the processing every frame? Or perhaps do the processing in a multithreaded way (for resource intensive processing)?

My apologies if the question is too beginner-like. I would really like to modify my work and increase my knowledge

It depends on what you're recognizing, but I'm familiar with two basic techniques:

Apply the recognition algorithm to each frame of the video.  Be fast enough that you can run on every frame of video.  This is probably the most common approach.
Recognize the object once, in one frame.  Then use motion tracking to keep track of the location of the object in subsequent frames.  In this way, you might be able to run the recognition algorithm (say) once every 10 frames and then use motion tracking to keep track of where it is in the remaining frames.  This has some tradeoffs (some latency to detect the object when it first occurs; fast motion or fast panning can cause loss of the object), but is another possible alternative.


How to partition the rows of a matrix in such a way that every column satisfies a given condition? The input is: Given a matrix $\mathbf{A}=\left[a_{ij}\right]$ of nonnegative integers for all $i\in\{1,\ldots, m\}$ and $j\in\{1,\ldots, n\}$ (where $n<m$). Nonnegative integers $V_j$ for all $j\in\{1,\ldots,n\}$.

The question is: Find $n$ disjoint sets $S_j$ of $\{1,\ldots,m\}$ such that
$$\bigcup\limits_{j=1}^{n} S_j=\{1,\ldots,m\},$$
$$\quad\quad\quad\;\,\sum_{i\in S_j}a_{ij}\geqslant V_j, \forall\,j\in\{1,\ldots,n\}.$$

So for example, given the matrix

$$
\begin{pmatrix}
7 & 4 & 3\\
3 & 2 & 7\\
2& 3 & 4\\
1 & 1& 5\\
6 & 10 & 8
\end{pmatrix},
$$
where $n=3$, $m=5$ and $V_1=12$, $V_2=10$ and $V_3=5$.

Then, a solution is $S_1=\{1,2,3\}$, $S_2=\{5\}$ and $S_3=\{4\}$.

I think the difficulty of solving this problem comes from the fact that we would like to partition the rows of a given matrix in such a way that every column satisfies a given condition.

Even though the problem seems related to the exact cover problem, I cannot find a good way to solve it.

Can you suggest a method/algorithm that finds solutions to such problem? If it is a known problem, do you know any reference?

As suggested by Yuval Filmus, reduce PARTITION to my problem.

Given an instance of PARTITION, that is a set of nonnegative integers $\{b_1, \ldots, b_k\}$, is there a subset $S\subset\{1,\ldots,k\}$, such that $\sum_{i\in S}b_i=\sum_{i\notin S}b_i=\frac{\sum_{i=1}^kb_i}{2}$?

Let $n=2$, $m=k$, $a_{ij}=b_i$ for all $(i,j)\in\{1,\ldots,k\}\times\{1,2\}$ and $V_1=V_2=\frac{\sum_{i=1}^kb_i}{2}$.

This is clearly created in polynomial-time.

PARTITION is solved if and only if my problem is solved.

If PARTITION is solved: there is a set $S\subset\{1,\ldots,k\}$, such that $\sum_{i\in S}b_i=\sum_{i\notin S}b_i=\frac{\sum_{i=1}^kb_i}{2}$. Take $S_1=S$ and $S_2=\{1,\ldots,k\}\backslash S$. Clearly, $S_1\cup S_2=\{1,\ldots,k\}$ and $S_1$ and $S_2$ are disjoint. Further, we have
$$\sum_{i\in S_1}a_{i1}=\sum_{i\in S_1}b_i=V_1\geqslant V_1,\\
\sum_{i\in S_2}a_{i2}=\sum_{i\in S_2}b_i=V_2\geqslant V_2,$$
and my problem is solved.
If my problem is solved: there are disjoint $S_1$ and $S_2$ such that
$$S_1\cup S_2=\{1,\ldots,k\},\\
\sum_{i\in S_1}a_{i1}=\sum_{i\in S_1}b_i\geqslant V_1,\\
\sum_{i\in S_2}a_{i2}=\sum_{i\in S_2}b_i\geqslant V_2.$$
Since $V_1=V_2=\frac{\sum_{i=1}^kb_i}{2}$ and $\sum_{i\in S_1}b_i+\sum_{i\in S_2}b_i=\sum_{i=1}^kb_i$, we must have
$$\sum_{i\in S_1}b_i=\sum_{i\notin S_2}b_i=\frac{\sum_{i=1}^kb_i}{2},$$
and PARTITION is solved.

Therefore, my problem is NP-hard.

To solve the problem, let us write it as integer programming problem as suggested by Yuval Filmus. To do so, introduce the binary variable $x_{ij}$ that is equal to $1$, if $i$ is in set $S_j$, and, $0$ otherwise.

\begin{align}
      & {\underset{\mathbf{ x }}{\text{maximize}}}
      & & 0\\[6pt]
      & \text{subject to}
      & & \sum_{i=1}^ma_{ij}x_{ij}\geqslant V_j,\forall\, j\in\{1,\ldots,n\},\tag{C1}\\[6pt]
      & & & \sum_{j=1}^nx_{ij}=1, \forall\, i\in\{1,\ldots,m\},\tag{C2}\\[6pt]
      & & & x_{ ij }\in\{0, 1\}, \forall (i,j)\in\{1,\ldots,k\}\times\{1,\ldots,n\}\tag{C3}.
    \end{align}

Even though this solves my problem, I need to develop a greedy algorithm for it, can I do that?


How do I prove that SPACE($n^{555}$) $\neq$ NP? I thought about finding a language with a polynomial verificator "larger" than $n^{555}$, but then I realized it would not imply the space needed for computation is the size of the verificator.

According to the space hierarchy theorem, there is a language in $\mathrm{SPACE}(n^{556})$ which is not in $\mathsf{SPACE}(n^{555})$. A padded version of this language will be in $\mathsf{SPACE}(n^{555})$. If the latter is equal to $\mathsf{NP}$, then the original language would also be in $\mathsf{NP} = \mathsf{SPACE}(n^{555})$, since we can implement padding while remaining inside $\mathsf{NP}$.

I'll let you flesh out this argument.


Integer Programming Complexity I would like to seek help on the complexity of the following problem.  Given positive integers $m$, $n$ and $D$, find all sequences $0 \lt a_1 \lt a_2 \lt  \dots \lt a_n$ are there such that:

each $a_i\in\{1, \dots, m\}$
$\sum_{i=1}^n a_i = D$

I want to know the complexity with respect to $m$, $n$, $D$. To what extend of $m$, $n$, $D$ that is computationally feasible?

Thanks very much.

This can be calculated using dynamic programming: for each $0 \leq T \leq D$ and $0 \leq \ell \leq n$, calculate $C(T,\ell)$, which is the number of solutions over $\{1,\ldots,m\}$ of $\sum_{i=1}^\ell a_i = T$. The base case is $C(0,0) = 1$ and $C(T,0) = 0$ if $T > \ell$. For $\ell > 0$, we have the formula $C(T,\ell) = \sum_{S=\max(T-m,0)}^{T-1} C(S,\ell-1)$. The answer is $C(D,n)$. This algorithm runs in time $O(mnD)$.

Equivalently, you are looking for the coefficient of $x^T$ in the generating function $(x+\cdots+x^m)^n = x^n\left(\frac{1-x^m}{1-x}\right)^n$. This expression can be massaged to give an explicit formula involving a double summation with alternating signs.


What's the correct term for this analog of cryptography? Suppose there is a communications channel between two parties. Suppose I want to send information through this channel, but I want to make it look like noise. Ie, I don't necessarily want to encrypt it, though I'm not prohibiting encryption - the point is I want to be able to transmit information to someone else such that what is sent across the channel cannot be distinguished from random noise by any potential eavesdropper.

Maybe something like the above is impossible to do "perfectly", but in any case the question I'm asking is - what is the correct term/keywords for problems in the spirit of what I described above?

Is there a mathematical theory of something of this type?

It's not an exact match to your question, but you're probably looking for something in the field of steganography.


Is no language with the non-primes property context-free? A language $L$ is said to have the "no primes" property if:

For every prime $p$ there are no words $w$ in $L$ s.t. $|w|=p$.
For every non-prime $m$ there is at least one word $w\in L$ of length $|w|=m$.

Given a language $L$ that has the no primes property, must $L$ be non-context-free?

Intuitively I believe yes, since the languages of all primes is not context free. But how can I prove this for every language that has this property?

I thiught proving using the sequence of lengths of words from any such language $L$, but this sequence is bounded by (at most) 3 (if 1 is consideres non prime, otherwise bounded by 2).

I also thiught proving by using the pumping lemma, but since I have no information on $L$ I am not sure if its possible.

Is there another method to prove so? Or a counter example that dissproves this?

You can use Parikh's theorem to prove this claim.

Indeed, if such a language was context-free, then its Parikh image would be regular. But the Parikh image would also satisfy the condition (as it only talks about length of words). It's very easy to prove that no regular language can satisfy this condition (e.g. by complementing it and using the pumping lemma).