# Question
Title: How to handle L-attributed SDDs with LR parsers
I've read *Chapter 5*, *Syntax Directed Translation*, of the *Dragon Book* but am still unable to understand the following related points:

1. How to handle L-attributed SDDs in an LR grammar when using a tool such as Bison? I believe, the book says that inherited attributes could be used with an LR parser (via Marker symbols?) provided the grammar is LL, or is (partly?) transformed into LL. Is this true? What if the grammar is LR and/or converting it to LL is not easy -- how do you then use inherited attributes?
2. If LR grammars are a proper superset of LL grammars and therefore more powerful, then how come LR grammars/parsers won't out-of-the-box allow L-attributed SDDs which, being a superset of S-attributed SDDs, are more powerful?
3. Avoiding the SDD style - Parsing style mismatch: Is it true that no matter the grammar (LL, LR, ...) or the parsing tool (Antlr, bison, yacc...), I can always first build the AST and then traverse it post-/pre-order any number of times to get whatever SDTs I want? (Ignore the time inefficiency here.)

Is there a text or online resource that covers topics 1 and 2 better or in more detail?

# Answer
Let's start with #3: Can you always walk the AST in any way you like after it is built? Yes, you can, and the Dragon book has an extensive discussion about how to do that for a given set of attributes; in particular, how to avoid (or detect) infinite regression.

Moreover, there is really no inefficiency in doing it this way. Or, to put it another way, trying to compute attributes on the fly during the parse does not speed things up much if at all, and can even slow things down. Even if it were slightly inefficient, it generally makes the parser much more complicated than it should be, partly because of the artificial hoops which need to be jumped through to perform the analysis online, and partly because it tends to interlace code which doesn't need to be codependent. Separation of concerns is almost always a good programming model.

With that out of the way, and briefly:

1. What the Dragon book says (iirc, because I still don't have either of my copies at my fingertips) is that adding markers can destroy the LR property of a grammar. This doesn't happen if the grammar happens to be LL. It's not actually necessary for the whole grammar to be LL, but it's a bit tricky to provide a formal description of what it means for a part of a grammar to be LL, although it's possible. Before LALR parser generators were available, there was quite a lot of research into left corner parsing (LCP), which you could look at if you're interested in the concepts. (I don't have references handy but the phrase should still be usable as a search term.)

If you want to introduce a marker into an LR grammar, you need to ensure that the reduction action for that marker does not conflict with any shift action. For that to be the case, each itemset which contains an item whose • is just before the marker must be free of items which would allow a shift of a symbol which could follow the marker. This is very similar to the LL(1) criterion, because it is effectively saying that the parser needs to be able to predict a single unique production at that point in the parse, something which is not normally required in an LR parser. (Strictly speaking, the parser only needs to be able to predict a single unique production for some lookahead symbols -- as I said, those which might follow the marker -- but that fact doesn't usually help much.)

A common way of creating this sort of conflict is when you have two similar productions with different markers before the same symbol. See the bison manual for some specific examples. (Bison automatically inserts markers for you when you put an action in the middle of the rule, which is why that section is called what it is called.)
2. LR grammars can recognise a strictly larger set of languages than LL grammars. But here, we're not talking about just *recognising* whether a sentence is in a language or not. The goal of parsing (outside of some formal language theory discussions) is almost always to recursively break the input into parts (which is the root of the verb "to parse") and understand the relationships between those parts.

All the same, LR parsers are, by and large, more capable at parsing as well. For example, the common language of arithmetic expressions can easily be recognised by an LL parser, and most textbooks insist that students work through the chore of ~~destroying~~ refactoring a simple operator grammar in order to make it possible to parse with a top-down parser. But the resulting LL grammar does not produce the same AST; it has completely lost any information about operator associativity. In order to use the parse, it is necessary to rewrite the AST to recover that information. The fact that an LL grammar cannot produce a parse tree for left-associative operators seems to me like it should count as a weakness.

In any event, if there is an LL grammar which correctly parses a language then you can indeed insert whatever attributes you like wherever you want to insert them. But that grammar will also be an LR grammar, and you will be able to insert markers freely into that grammar without losing the LR property. Unfortunately, it is possible that adding markers to the $LL(1)$ grammar will produce a grammar which is not $LALR(1)$ (since not all $LR(1)$ grammars are $LALR(1)$). But as far as I know this doesn't show up often in practical grammars.

If you want an academic reference, you can look at Beatty, J. C. (1982). "On the relationship between LL(1) and LR(1) grammars", Journal of the ACM, 29 (4 (Oct)): 1007–1022. (doi:10.1145/322344.322350. I got that from a reference in the Wikipedia entry on LL grammars; the reference link is not pay-walled, at least as of today.)
> 1 votes

---
Tags: compilers, parsers
---


# Question
Title: Isn't a small monolithic kernel a micro-kernel, and a big micro-kernal a monolithic kernel?
I don't understand the last para. I corrected its typos. Please explain like I'm 5. If micro-kernels can be big, and monolithic kernels can be small, doesn't this size gradation collapse the distinction between monolithic kernels and micro-kernels? Is this what a hybrid kernel means?

> So.. that's the ELI5 version. Things change, microkernels was going to be the cool logical way to do it, that argument between Tovalds and Tanenbaum really is worth a read. But Monolithic kernels appear (for now) to have won, as they want speed, instant access to resources (like kitchens or GFX cards) and rely on the OS managing processes a bit smarter to figure out who gets what type of access at what time. But just because a kernel is micro doesn't mean it won't take a lot of room up, as it'll then still need all the drivers to do things and be useful. So you can have a monolithic kernel that's small (compiled with only the drivers it needs into the kernel), and a microkernel that's big (compiled for a certain architecture/memory configuration with lots of modules available to handle all sorts of odd hardware to be plugged in). Google will provide more details and far more pros/cons that we can throw here. But again, read that linked Torvalds/Tannenbaum argument, it's the kind of thing that still goes on today.

# Answer
The distinction between monolithic kernels and microkernels has nothing to do with the size.

In a monolithic kernel, all services are provided by a *single piece of code* running in a single, flat, shared address space. There are monolithic kernels which support dynamically loadable modules now (actually most monolithic kernels do), but when these modules are loaded, they *still* become part of the single monolithic (hence the name!) blob of code running in the single address space. All communication between these different services is done by accessing shared memory, or another way of looking at it is that there *is no communication* because it's all just one singular monolithic blob of code.

In a microkernel, *only the most basic, fundamental services are provided by the kernel*. Everything else is provided by *separate programs*, which are separate pieces of code, running in separate address spaces. All communication between the services is done through a well-defined messaging protocol.

So, in a monolithic kernel, you have a *single piece of code* which manages memory, schedules tasks, accesses the disk, accesses the filesystem, accesses the network card, implements the TCP/IP stack, implements Ethernet, implements WiFi, access the graphics card, etc.

In a microkernel, the kernel *only implements* the very basics: memory management, task scheduling, and a simple messaging protocol that allows the programs to talk to each other and to the kernel. The disk driver is a separate program. The filesystem driver is a separate program. The network card driver is a separate program. The implementation of the IP protocol is a separate program, TCP is a separate program, UDP, IPv6, etc. are all separate programs. The Ethernet implementation is a separate program, actually probably a set of separate programs for the PHY layer, the LLC layer, the MAC layer, etc. Same for WiFi, that's going to be a whole set of separate programs. The graphics driver is a separate program. And so on, and so forth.

These "separate programs" are sometimes calls "services" or "deamons".

The relationship between a microkernel and its daemons is analogous to the relationship between an Operating System and the user programs: Your browser, your email program, your first-person shooter, your music software, your text editor, your chess program, your video editor, your drone controller, your video chat program, they are not part of the Operating System. They are all separate programs that run in separate processes in separate address spaces. One of them can crash without taking the entire system down.

But none of this has anything to do with size: the sum of a microkernel and many services that provide many features can be larger than a simple monolithic kernel that doesn't provide many features. If a system doesn't support networking, for example, then it doesn't need code for networking, regardless of whether that is a microkernel or a monolithic kernel. So, it is easily possible for a microkernel system that supports networking to be larger than a monolithic kernel system that does not support networking.
> 3 votes

---
Tags: os-kernel
---


title: Master theorem: $T(n)=10T(n/9)+n\lg(n)$

text:
# Question
Title: Master theorem: $T(n)=10T(n/9)+n\lg(n)$
I am told to solve the recurrence $$T(n)=10T(n/9)+n\lg(n)$$ using the Master theorem. I then try to use case 3. However, I am unable to show that for $f(n)=n\lg(n)$ then $10f(n/9) \leq cn\lg(n)$ for $c \< 1$ and all sufficiently large $n$. Is it wrong to use case 3? Or does the Master theorem even apply?

# Answer
> 2 votes
Case 3 does not apply. Indeed: $$ f(n) = n \log n \not\in \Omega(n^{\log\_9 10}) = \Omega(n^{\log\_b a}). $$

However case $1$ applies since, for $0\<c \le 0.01$ $$ f(n) = n \log n \in O(n^{1.04 - 0.01}) \subset O(n^{\log\_9 10 - 0.01} ) \subseteq O(n^{\log\_b a - c} ). $$

This shows that $T(n) \in \Theta(n^{\log\_9 10})$.

---
Tags: algorithm-analysis, asymptotics, recurrence-relation, master-theorem
---


title: Converting to CNF - Distribution

text:
# Question
Title: Converting to CNF - Distribution
I am still trying to get my head around what is valid CNF and how distribution works, I am not even sure if the examples I have tried to convert are correct for one, but I am also unsure of the rule for distribution and when I have looked at other posts here it seems so complicated and the actual rule does not seem to me to be obvious.

I think the correct process is:

* Elimate Bi-Directionals
* Eliminate Implications
* Apply De Morgans Law
* Apply Distributive Law

Clause One

```
A V B => C
-(A V B) V C -- Remove implication
(-A ^ -B) V C -- De Morgans Law
(-A V C) ^ (-B V C) -- Is this right? I am unsure of exactly how to distribute the or.

```

Clause Two

```
A ^ B => C
-(A ^ B) V C -- Eliminate Implication
(-A V -B) V C -- Is this now valid CNF or is there something more to do?

```

Clause Three

```
-A ^ -B => C
(A ^ B) V C -- Elimate Implication - Is this correct for a negated expression?
(A V C) ^ (B V C) -- Distribute OR - Is this correct?

```

I am not able to access the set of maths symbols for some reason so have used the notation in my course book.

I am currently taking a self taught course and have an exam in two weeks and I know there will conversion to CNF involved so I am trying to make sure I understand the steps now but I am still not entirely sure what is valid CNF.

The course material states it is a conjunction of disjunctions which I get, but then it seems to imply that: `A V B V C V ..n` is valid CNF?

# Answer
By definition - for example Herbert B. Enderton - A Mathematical Introduction to Logic-Academic Press (2001), page 53 - simply saying CNF is conjuction of disjuntions or product of sums.

1. So, as we agreed earlier, $$(I \lor M) \Rightarrow H = (\neg I \lor H) \land (\neg M \lor H )$$
2. For $(I \land M) \Rightarrow H$ we can get $\neg (I \land M) \lor H=\neg I \lor \neg M \lor H$ and this last is CNF
3. For third case for $(\neg I \land \neg M) \Rightarrow H$ answer is analogical $2$d case: $\neg(\neg I \land \neg M) \lor H = I \lor M \lor H$ and this also is valid CNF.

And answer for the last question is yes - $A\_1 \lor A\_2 \lor \cdots \lor A\_n$ is valid CNF if each $A\_i$ is either a sentence symbol or the negation of a sentence symbol - it's allowed to have just one conjuct.

Let me add, that one symbol is as CNF, so DNF.
> 0 votes

---
Tags: propositional-logic
---


title: Product Sum of Special Arrays

text:
# Question
Title: Product Sum of Special Arrays
**Can someone please explain why this is correct:**

```
function productSum(array,depth=1) {
    let sum=0;
    for(let i=0;i<array.length;i++){
        if(Array.isArray(array[i])){
            sum+= productSum(array[i],depth+1)
        }else{
            sum+= array[i];
        }
    }
    return (depth)*sum;
}

```

**But, following is wrong:**

```
function productSum(array,depth=1) {
    let sum=0;
    for(let i=0;i<array.length;i++){
        if(Array.isArray(array[i])){
            sum+=(depth)* productSum(array[i],depth+1)
        }else{
            sum+= array[i];
        }
    }
    return sum;
}

```

I haven't been able wrap my head around it. Why is does it give wrong answer if I multiply the sum with depth before the for loop on an array ends?

It is clear from the sample output that if there are multiple array items at a depth, we are supposed to multiply the sum with the depth as many times. Eg. depth 2 is multiplied by the sum twice in the example.

Could someone please break it down for me?

# Answer
> 0 votes
here, you are multiplying the depth of the "parent" array, instead of the nested array.

```
sum+=(depth)* productSum(array[i],depth+1)

```

try this

```
 sum+=(depth+1)* productSum(array[i],depth+1)

```

multiply it by depth+1

---
Tags: algorithms, data-structures, arrays
---


title: Finite loop on a NFA

text:
# Question
Title: Finite loop on a NFA
I understand that in a non-deterministic automaton, an input can lead to one, more than one, or no transition for a given state.

Given this information, I would assume that if the input lead to a loop, this loop would be infinite until a determined input happened (being one || more || ε).

However I would like to know if there's a way to represent a "finite" loop with an NFA. For example, an ATM where a person only has a determined amount of chances to get the password right. If not, the operation is cancelled.

The input is always the same (0-9 digits), so how can the outcome be different after 3 tries?

Thank you for any hints on this!

# Answer
> 2 votes
Let's assume the user needs to enter a password and then press OK. Let's assume the password is 42:

But let's say the user makes a mistake, how can we allow three tries? By adding failure states, waiting for OK, and if we're in a failure state when OK gets pressed we get another try. Let $\*$ notate 'anything else' - any character that wasn't handled by another arrow.

# Answer
> 0 votes
Some of this depends on what you mean by "tries." But here is a reasonable first whack.

Suppose that the password is `ab` and you want to give a person two tries. Take q0 to be the initial state, take q2 to be the only accepting state, take q3 to mean "first try failed, initalize second try" (and it might light a light, warning the inputter that their first try failed). Also take q5 to be the (non-accepting) state meaning two-try failure.

Coming from q0 are two arrows, one to q1 labeled `a` and one to q3 labelled `b`. From q1 are two arrows, one to q2 labeled `b` and one to q3 labeled `a`. From q2 is a loop, labeled `any`.

You get the idea. From q3 are two arrows, one to q4 labeled `a` and one to q5 labeled `b`. From q4 come two arrows, one to q2 labeled `b` and one to q5 labeled `a`. From q5 is a loop, labeled `any`.

This is of course hopelessly naive from a security standpoint. But it gets across the basic idea.

---
Tags: finite-automata
---


# Question
Title: Determine saving moves for a checked king
In my chess code I explore the whole tree of possible movements to find saving moves for a checked king. That is, for every one of the checked king's side pieces I search their whole tree of moves and keep those that remove the king from check in a list.

Not like it's particularly expensive computationally-wise with a board of 8x8, but just for the sake of knowledge - is there a more efficient algorithm to calculate the saving moves?

# Answer
> 2 votes
Well, you could try to directly use the geometry the attacking piece and possible defenders to see if an intersection is available. This would be faster. But there is a lot of cases to be taken into consideration : multiple checks, pinned defenders, half-pinned defenders, *en passant* rules... It's much easier to code that wrong, so be careful, and prepare lots of test cases to compare to the "simple" version, to check that you're not mixing things up.

Computing "long" lists of legal moves isn't hard for a computer, there's less than 200 anyway. What's hard in chess computer programs is the exponential search tree and deciding when to stop recursing and evaluate.

---
Tags: algorithms, search-algorithms
---


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

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

I found this description of how it was achieved:

http://people.cs.clemson.edu/~mark/330/kidder/no\_mode\_bit.txt

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

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

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

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

# Answer
> 10 votes
The answer is that Ed deCastro, President of Data General Management, had established a team of engineers in North Carolina specifically to design the next generation CPU. He assigned the task of support and incremental enhancements to us, the Massachusetts team. Three times we proposed a major new architecture, each time with a very sensible mode bit, and described it as a modest incremental enhancement. Each time, Ed saw through our disguise and rejected the proposal, expecting the North Carolina team to succeed. Ed believed that regardless of how we attempted to disguise our proposals, he would know it was a new generation architecture if it had a mode bit. So we had to propose a new generation architecture with no mode bit, even if that made it less efficient. That's how we got it past Ed deCastro. See The Soul of a New Machine, by Tracy Kidder.

# Answer
> 8 votes
In theory "no mode bit" would allow you to use the old, 16-bit, operating system with absolutely no modifications, and that OS would be able to launch 32-bit apps, although the new 32-bit apps would be stuck with 16-bits of virtual address, so would be able to use the 32-bit registers and new instructions, but would misbehave if they accessed virtual addresses larger than $2^{16}$.

With a mode bit the old 16-bit OS would have had to have been modified to figure out whether the program was 16-bit or 32-bit and then set the mode bit appropriately before launching the program.

In practice, it seems the MV/8000 actually had a mode bit. Elsewhere on Mark Smotherman's web page at Clemson he has posted the Data General, *ECLIPSE MV/8000 Principles of Operation*, 1980. If you look in Appendix E (starting on page 369) you will see that the MV/8000 had two completely different page table mechanisms. The specific machine the MV/8000 was backwards compatible with was the C/350, and the C/350 had a specific 16-bit Memory Allocation and Protection Unit, with specific ways of controlling that unit. For 32-bit logical to physical operation you would instead turn on the Address Translation Unit (described in Chapter 3, starting at page 31.

In practice what that means is that when you execute a 16-bit instruction in 32-bit mode it is specified that the high 16-bits of the logical address get set to 0. There also must be some specification about what happens to the high 16-bits of an address when you execute a 32-bit instruction in 16-bit mode, but I wasn't able to find it during my brief perusing of the manual.

So it's less a question of whether or not a mode bit is a good or a bad thing. It's more that there was no particularly good reason to use a mode-bit to differentiate between 16-bit and 32-bit instructions. The 16-bit instructions use 16-bits of logical address (with the high 16 bits set to 0) and 16-bit registers, and the 32-bit instructions use 32-bits of logical address and 32-bit registers. The old OS "just works" on the new machine, but you can also try out the new instructions by running a new program under the old OS.

# Answer
> 1 votes
I think part of the reason was that the DEC VAX 780. Dec DG's main competitor had beaten DG to the creation of a 32 bit minicomputer. However Dec handled backwards compatibility with an inelegant kludge. In the early Vax there was an embedded PDP-11 (the Vax's 16 bit ancestor), switching between PDP-11 mode and Vax 32 bit mode was literally switching between 2 machines. The MV-8000 like the Intel x86 CPUs, POWER and Sparc allow 32 and 64 bit programs to co-exist concurrently on the same OS.

---
Tags: computer-architecture
---


title: Example for Database architecture

text:
# Question
Title: Example for Database architecture
PHPMyadmin is stated as a 3 tier database architecture.How is this possible,Isn't it a 2 tier architecture.What are the real world examples of 1-tier and 2-tier architecture.

# Answer
*The short answer:*

You're right, it is a 2-tier architecture. A 1-tier architecture doesn't allow the database to be run on a separate host. *phpMyAdmin* does, so it is 2-tier; but not 3-tier.

*The long answer:*

I've Googled for examples of this claim and ended up at this webpage, which says:

> In the 2-tier architecture, we have an application layer which can be accessed programatically to perform various operations on the DBMS. The application generally understands the Database Access Language and processes end users requests to the DBMS.
>
> In 3-tier architecture, an additional Presentation or GUI Layer is added, which provides a graphical user interface for the End user to interact with the DBMS.
>
> For the end user, the GUI layer is the Database System, and the end user has no idea about the application layer and the DBMS system.
>
> If you have used MySQL, then you must have seen PHPMyAdmin, it is the best example of a 3-tier DBMS architecture.

While this distinction is certainly useful, this is not what is usually meant by a 3-tier architecture. To quote Wikipedia:

> N-tier application architecture provides a model by which developers can create flexible and reusable applications. By segregating an application into tiers, developers acquire the option of modifying or adding a specific layer, instead of reworking the entire application. A three-tier architecture is typically composed of a presentation tier, a domain logic tier, and a data storage tier.
>
> While the concepts of layer and tier are often used interchangeably, one fairly common point of view is that there is indeed a difference. This view holds that a layer is a logical structuring mechanism for the elements that make up the software solution, while a tier is a physical structuring mechanism for the system infrastructure. For example, a three-layer solution could easily be deployed on a single tier, such as a personal workstation.

... and further down:

> Generally, the term "tiers" is used to describe physical distribution of components of a system on separate servers, computers, or networks (processing nodes).

So in order to be 3-tier, it is not enough for *phpMyAdmin* to have a GUI that allows the user to manipulate databases without typing SQL. It must separate its GUI from its application logic (the code that actually implements its functionality) into two different *layers*, such that the application logic really is a separate layer: it can be tested separately, a completely different user interface can be written on top of it as an alternative to the GUI, etcetera.

The phpMyAdmin code base doesn't do this. You can see this by looking at libraries/classes/DatabaseInterface.php, which contains utility functions that the rest of the phpMyAdmin code bases uses to communicate with the database. This is what is used to perform an SQL query:

```
/**
 * runs a query
 *
 * @param string $query               SQL query to execute
 * @param mixed  $link                optional database link to use
 * @param int    $options             optional query options
 * @param bool   $cache_affected_rows whether to cache affected rows
 *
 * @return mixed
 */
public function query(
    string $query,
    $link = self::CONNECT_USER,
    int $options = 0,
    bool $cache_affected_rows = true
) {
    $result = $this->tryQuery($query, $link, $options, $cache_affected_rows);

    if (! $result) {
        Generator::mysqlDie($this->getError($link), $query);

        return false;
    }

    return $result;
}

```

Note how it calls `Generator::mysqlDie` \- which is a function that generates HTML. So executing SQL queries and generating HTML (which is presentation) are mixed together in the same function. It is impossible to put a command-line interface on top of this code, it would need to be rewritten first.

So the *phpMyAdmin* code can't be separated into 2 layers. Even if it could, 2 layers aren't 2 tiers: 2 tiers can be *physically* separated: they can be run on different machines with the presentation tier connecting over the network to the application tier.

Some general lessons to take away from this:

1. IT people tend to be incredibly sloppy with jargon. When 10 authors use a term, they probably mean at least 5 different things with it. Be especially wary when it comes to jargon used to sell expensive IT to managers; *3-tier architecture* is a prime example. Never trust anything written on IT at face value. Always wonder - as you're doing with this question - whether what you're reading uses terms in a more or less standard way. Or whether there *is* a standard way in the first place. Apply this caution to *anything*: articles on websites by random people on the internet, books published by popular IT publishers, lecture notes from famous universities. All authors bend terms to fit their own needs and preconceptions.
2. Wikipedia articles on IT are just as bad as the rest, on average, or worse; but sometimes, they are pretty good. This one is pretty good - today (who knows what it will look like one year from now).
> 1 votes

# Answer
"3 tier database architecture" is a bit of misnomer, as database by itself doesn't have extra tiers. So what are the 3 tiers? From outter-most to inner most, they are:

1. presentation,
2. application processing,
3. data management.

https://example.net is literally 1-tier since it doesn't have application processing and data management, it just presents a text permitting you to use that domain name in documentations.

FTP would be a 2-tier protocol since it doesn't have application processing.
> 0 votes

---
Tags: databases
---


# Question
Title: Proving that $ \{u\#v\#w \mid u,v,w \in {a,b,c}*, |u|_a = |v|_b = |w|_c\}$ isn't context-free
I have a question about the pumping lemma for context-free languages. I understand the conditions of the pumping lemma.

Assume $L$ is context-free. Let $n\>0$ be the pumping length given by the lemma. $z=uvwxy$ with conditions:

1. $|vwx|\leq n$
2. $|vx|\geq 1$
3. $\forall i \>0, \exists z= uv^iwx^iy \in L$

But i need to know what are the possible cases for the $vx$, alternatively $vwx$, so when pumped we can argue it does not belong to the language, and if the # symbol affects the assumption?

$$L = \\{u\\#v\\#w \mid u,v,w \in \\{a,b,c\\}^\* , |u|\_a = |v|\_b = |w|\_c\\}$$

From what I understand, I can assume that $v$ or $y$ are only in first part $u$ or second $v$ or $w$, but also $vxy$ can be in between $a$'s and $b$'s, including the $\\#$ between them.

# Answer
Condition 3 as in the question, "$\forall i \>0, \exists z= uv^iwx^iy \in L$" does not make sense. It should be "$uv^iwx^iy \in L\text{ for all } i\ge0$", i.e., $uv^0wx^0y=uwy$, $uv^1wx^1y=uvwxy$, $uv^2wx^2y$, $uv^3wx^3y$, $uv^4wx^4y$, and so on are in $L$. Please note the first word, $uwy$, where $v$ and $x$ do not appear, i.e, we "pump down" $uvwxy$ to $uwy$.

The difficulty of applying pumping lemma comes from, indeed, recognizing "the possible cases for the $vx$" correctly and organizing them in a way that is easy to pump the word up or down to be not in the language.

Since the condition on the words in $L$ is about the number of $a$s, $b$s or $c$s in them, we will classify $v$ and $x$ also in the number of $a$s, $b$s or $c$s in them. For pumping length ${n}$, we will let $z$ be $a^n\\#b^n\\#c^n$, the simplest word in $L$ with length at least $n$.

1. If either $v$ or $x$ contains $\\#$, $uwy$ will have less than 2 $\\#$s, hence not a word in $L$.
2. Otherwise, all symbols in $v$ must be the same, and all symbols in $x$ must be the same.

Since we have 3 symbols, $a,b,c$ in $z$, (at least) one of $a,b,c$ will be missing in $vx$.

The number of $a$s, the number of $b$s and the number $c$s in $uvwxy$ are the same. Since $uv^2wx^2y$ is $vx$ "more than" $uvwxy$, the number of that missing symbol in $uv^2wx^2y$, will be less than both the number of $s\_v$ in it if $s\_v$ is the symbol in $v$, and the number of $s\_x$ in it if $s\_x$ is the symbol in $x$. Since $|vx|\ge1$, either $s\_v$ or $s\_x$ exists. This means $uv^2wx^2y$ is not in $L$.

Since we can always pump $z$ outside of $L$, $L$ does not satisfy the pumping lemma. So, $L$ cannot be context-free.

---

> I can assume that v or y are only in first part $u$ or second $v$ or $w$ but also $vxy$ can be in between $a's$ and $b's$ including the $\\#$ between them.

I don't quite understand your statement literally.

However, apparently, you wanted to say that given $z$, there are various possibilities for $u$, $v$, $w$, $x$ and $y$, which is totally true. Only the usage of some abstraction or general property (which might be simple or complicated) will enable us to cover all of them. That is where the fun or wisdom are.
> 3 votes

---
Tags: formal-languages, context-free, pumping-lemma
---


# Question
Title: Can anyone give me an instance of 3SAT with exactly one solution?
I need an instance of 3SAT with exactly one solution but I cannot think of or find one anywhere. Can anyone please give me an example?

# Answer
> 16 votes
Try this: $$ (A \lor B \lor C) \land (A \lor B \lor \lnot C) \land (A \lor \lnot B \lor C) \land (A \lor \lnot B \lor \lnot C) \land (\lnot A \lor B \lor C) \land (\lnot A \lor B \lor \lnot C) \land (\lnot A \lor \lnot B \lor C) $$

# Answer
> 25 votes
The empty 3SAT instance (over no variables) has one solution.

# Answer
> 17 votes
If you are seeking a formula with 3 variables $x$, $y$, $z$, then you can consider clauses $(\ell\_x \vee \ell\_y \vee \ell\_z)$ where $\ell\_x$ is either $x$ or $\neg x$ (and same thing for $\ell\_y$ and $\ell\_z$). There is a total of 8 such clauses. If you consider a conjunction of all 8 clauses and remove exactly one of them, you get a 3-CNF formula with exactly one solution.

For exemple, if you remove the clause $(\neg x \vee y\vee z)$, then the solution to the formula is given by $x = \top$, $y = \bot$ and $z = \bot$.

# Answer
> 11 votes
One variable: $(A \lor A \lor A)$

# Answer
> 3 votes
Just about every puzzle game can be formulated as a 3SAT with a unique solution. Sudoku is perhaps the canonical example.

# Answer
> 3 votes
Semiprime factoring.

Define an unsigned integer multiplication circuit such that X * Y = P.

Define P as a constant equal to an arbitrary semiprime number (there are an infinity of such numbers).

Define X and Y as free variables such that they have one less bit than P (to ban the solution 1 * P and P * 1).

Add the constraint that X \<= Y (to ban the solution Y * X).

Convert the multiplication circuit to a 3SAT formula (clauses for each OR,AND,XOR gate, each gate of the circuit should have 3 variables, then the clauses ban the incorrect combinations). The bits of P are unit clauses.

The only way to satisfy this formula is to put X and Y in the right order as the input. Just like in the circuit, the rest of the formula is defined by the input. By the mathematical definition of a semiprime number, there no other way to obtain P through multiplication except by multiplying X and Y, or 1 and itself.

Depending on your goals, this is a convenient approach because you can generate an infinity of random formulas with unique solution.

*(However, the formula's unique solution should be exponentially hard to solve in the size of P, because multiplication is considered a one-way function.)*

---
Tags: satisfiability, 3-sat
---


# Question
Title: Is Huffman encoding for the entire language or the body of text?
I am using language as a placeholder although I think it can be used in music too. I am unclear if the frequencies are given based on the text or the entire language. The latter would prove to be difficult because if we are to say that 'e' is the most common letter in English, wouldn't this shift over time with some new words being created and some being dropped due to fashion etc?

Say we are trying to encode the first book of Harry Potter, is the encoding basing the frequency of letters of the book only or of the English language at the time? Extending it to music, would the entire domain be all possible sounds the human ear can hear or only of the track being listened to.

# Answer
> 2 votes
The statistics used to derive the Huffman codes from can come from any source that you want. For a practical example, the popular DEFLATE format allows both "dynamic Huffman codes" (in this usage it is *not* a form of adaptive Huffman coding, it means the codebook is specified in the data stream) and "fixed Huffman codes" (a codebook that is specified in the DEFLATE specification).

A codebook based on the statistics of the actual data being compressed generally results in a smaller compressed size. The trade-off is that a codebook that is not pre-defined must be supplied along with the data (the decoder still needs it), adding to the overall size. Canonical Huffman codes can mitigate the impact (requiring only the code lengths to be transmitted, the codes themselves can be inferred in a simple way), but transmitting the codebook is going to cost *some* extra data, and may not be worth the size overhead for short texts (especially when the statistics of the given text happen to approximately line up with the statistics on which the pre-defined codebook was based).

Other practical considerations may favour using slightly inaccurate statistics, for example statistics based on some prefix of the data to be able to start encoding without having to wait until the input is fully known. The more accurate you want the statistics to be, the longer the latency is between the "first input" and the "first output" of the encoder. Even if the input is entirely known at the start, depending on the application, gathering fully accurate statistics may not be worth the time investment.

# Answer
> 1 votes
If you wanted to compress 20 bytes of text, knowing the language would be useful. If you want to compress the first book of Harry Potter, no matter what language you pick, you would most likely not use Huffman encoding in the first place because it is just based on letter frequencies, but something like LZW encoding, which also handles correlations between letters (in other words, it handles the fact that some sequences of letters are more likely for others).

You would likely base the compression on the text, not on the language. For example, "Harry" will happen many times in this particular book, and it will be compressed a lot better than with compression based on the language. On the other hand, I doubt you'll find "Harry" in "War and Peace" at all.

---
Tags: huffman-coding
---


title: Matching with specific cardinality

text:
# Question
Title: Matching with specific cardinality
In a weighted graph $G(\mathcal{V},\mathcal{E})$ where $w(i,j)$ is the weight of the edge $(i,j) \in \mathcal{E}$. How can I find a maximum weighted matching with a specific size (i.e specific cardinality).

# Answer
Let me start by answering a slightly different question: Given a weighted graph $G=(V,E)$ on $n=|V|$ vertices, we want to find a maximum-weight matching of cardinality **at most** $k$.

Let $L$ be the largest edge weight in $G$, and define $L' = 2nL$. Transform the graph $G$ by adding $\ell =n-2k$ new vertices $v\_1, \dots, v\_\ell$, and all edges in $\\{v\_1, \dots, v\_\ell\\} \times V$. Each new edge has weight $2nL$. Let $G'$ be the new graph. Compute a maximum matching $M$ of $G'$ and return the matching $M \cap E$.

**If there is a matching $M$ of weight $\ell L' + x$ in $G'$ then there is a matching of weight $x$ and size at most $k$ in $G$.**

There are exactly $\ell$ edges in $M' = M \cap (\\{v\_1, \dots, v\_\ell\\} \times V)$ since at most $\ell$ edges in $\\{v\_1, \dots, v\_\ell\\} \times V$ can belong to any single matching and, if $|M| \< \ell$, the weight of $M$ would be at most $(\ell-1)L' + \frac{n+\ell}{2}L \< (\ell-1)L' + nL \< \ell L'$. Then, there are at most $k$ edges in $M'' = M \setminus M' = M \cap E$ as otherwise we would have $|M| = |M'| + |M''| \> \ell + k = \frac{\ell}{2} + \frac{\ell}{2} + k = \frac{\ell}{2} + \frac{n}{2} - k + k = \frac{\ell + n}{2}$, which is a contradiction. Since the weight of $M'$ is exactly $\ell L'$, the weight of $M'' \subseteq E$ must be $x$.

**If there is a matching $M''$ of weight $x$ and size at most $k$ in $G$ then there is a matching $M$ of weight $\ell L' + x$ in $G'$.**

Since $|M''| \le k$, there are at least $n-2k= \ell$ distinct unmatched vertices $u\_1, \dots, u\_\ell$ in $V$ (w.r.t. $M''$). Choose $M = M'' \cup \\{ (v\_i, u\_i) \mid i=1, \dots, \ell\\}$. The weight of $M$ is $\ell L' + x$.

---

We can now look for a maximum-weight matching of cardinality **exactly** $k$ in $G$. We can reduce this problem to the one of finding a maximum-weight matching of cardinality **at most** $k$.

Given $G=(V,E)$ let $L$ be its largest edge weight. Modify $G$ by changing the weight $w(u,v)$ of each edge $(u,v)$ to $w'(u,v) = w(u,v) + kL$. Call $G'$ the resulting graph. Find a maximum-weight matching $M$ of cardinality at most $k$ in $G'$. If $|M| \< k$, the instance has no feasible solution, otherwise return $M$.

Clearly a matching $M$ of size $k$ in $G'$ weighs $kL + x$ if and only if $M$ weighs $x$ in $G$. We only need to show that: 1) if a matching of size $k$ exists in $G$, $M$ contains exactly $k$ edges, and 2) if no feasible matching exists in $G$, $M$ contains less than $k$ edges.

The second claim is immediate since any matching in $G'$ is also a matching in $G$. We then focus on the first claim:

**If $G$ admits a matching of size $k$, $M$ contains exactly $k$ edges**

By construction $|M| \le k$. We now show that $|M| \ge k$. Suppose towards a contradiction that $M \< k$. Then the weight of $M$ is at most $\sum\_{(u,v) \in M} w'(u,v) \le (k+1) |M| L \le (k+1)(k-1)L = (k^2 - 1)L \< k^2 L$. Since a weight of at least $k^2 L$ is attainable by selecting the edges in any matching of size $k$ in $G'$ (such a matching exists in $G$ and hence in $G'$), this contradicts the fact that $M$ is a maximum-weight matching.

.
> 0 votes

---
Tags: combinatorics, matching, string-matching
---


# Question
Title: Is the language of all words of the form $wxw^Rx^R$ context-free?
Is the language $\\{wxw^Rx^R \mid w,x \in \\{0,1\\}^\* \\}$ context-free

My thoughts, Let $x = \epsilon$ and we get $ww^R$, which is context-free. Hence the given language must be context-free.

Am I right?

# Answer
Denote your language by $L$, and consider $$ L' = L \cap 10^\*1110^\*10^\*10^+11. $$ Any word in $L'$ is of the form $$ 10^a1110^b10^c10^d11, $$ where $d \> 0$. Also, it is of the form $wxw^Rx^R$. Since both $wx$ and $w^Rx^R$ contain the same number of $1$'s, necessarily \begin{align} wx &= 10^a1110^{b\_1} \\ w^Rx^R &= 0^{b\_2}10^c10^d11 \end{align} where $b\_1 + b\_2 = b$. We see that $x^R$ ends with $110$ (since $d\>0$), and so $x$ starts with $110$. Hence $w = 10^a1$ and $x=110^{b\_1}$, implying that $w^Rx^R = 10^a10^{b\_1}11$. This shows that $b\_2 = 0$ hence $b\_1 = b$, and furthermore $c = a$ and $d = b$. That is, the word is of the form $$ 10^a1110^b10^a10^b11, $$ where $b \> 0$. Conversely, every word of this form is in $L'$ (take $w = 10^a1$ and $x = 110^b$).

Let $h\colon \\{1,2,3,4,5\\} \to \\{0,1\\}$ be the homomorphism given by $h(1) = 1$ and $h(2) = h(3) = h(4) = h(5) = 0$, and let $d\colon \\{1,2,3,4,5\\} \to \\{2,3,4,5\\}$ be the homomorphism that deletes $1$. Then $$ d(h^{-1}(L') \cap 12^\*1113^\*14^\*15^\*11) \cup \\{2^n4^n : n \geq 0\\} = \\{2^n3^m4^n5^m : n,m \geq 0\\}. $$ The latter language is well-known not to be context-free. Since all our operations preserve being context-free, we conclude that $L$ is also not context-free.
> 0 votes

---
Tags: context-free
---


# Question
Title: Justifying a claim in the proof of the master theorem
I am trying to understand the proof of the master theorem and I came up with my own proof for why (4.23) is true.

My argument is as follows:

**Claim:** $g(n)=O\left(\sum\_{i=0}^{\log\_{b}(n)-1}a^i(n/b^i)^{\log\_b{a}-\epsilon}\right)$.

$$g(n)=\sum\_{i=0}^{\log\_{b}(n)-1}a^if(n/b^i)$$

Now by the definition of big O, we have that $\exists c\in\mathbb{R}, N'\in \mathbb{R }$ such that $\forall n/b^j\>N'$, we have that $$f(n/b^j)\<c(n/b^j)^{\log\_b{a}-\epsilon}$$

This implies that $\forall n\>N'b^{\log\_bn-1}$

$$g(n)= \sum\_{i=0}^{\log\_{b}(n)-1}a^if(n/b^i) \leq \sum\_{i=0}^{\log\_{b}(n)-1}a^ic(n/b^i)^{\log\_b{a}-\epsilon} \leq c\sum\_{i=0}^{\log\_{b}(n)-1}a^i(n/b^i)^{\log\_b{a}-\epsilon} $$

Which implies that $g(n)=O\left(\sum\_{i=0}^{\log\_{b}(n)-1}a^i(n/b^i)^{\log\_b{a}-\epsilon}\right)$ with $M=c$ and $N=N'b^{\log\_bn-1}$.

Have I found the correct $c$ and $N$ to prove this claim for the upper bound of $g(n)$ and is this proof valid? Thanks!

# Answer
> 4 votes
Suppose that $f(n) = O(n^{\log\_b a - \epsilon})$. According to the definition, there exist constants $N,C\>0$ such that $f(n) \leq Cn^{\log\_b a - \epsilon}$ for all $n \geq N$. Let $M$ be the maximum value of $f(n)/n^{\log\_b a - \epsilon}$ over all positive integers $n \< N$. The maximum exists since there are only finitely many such $n$. Then $f(n) \leq \max(M,C) n^{\log\_b a - \epsilon}$ holds for all integer $n \geq 1$. Therefore $$ g(n) = \sum\_{j=0}^{\log\_b n-1} a^j f(n/b^j) \leq \max(M,C) \sum\_{j=0}^{\log\_b n-1} a^j (n/b^j)^{\log\_b a - \epsilon} = O\left( \sum\_{j=0}^{\log\_b n-1} a^j (n/b^j)^{\log\_b a - \epsilon} \right). $$

---
Tags: algorithms, data-structures, recurrence-relation, master-theorem, divide-and-conquer
---


title: Show $\{0^1^|≠\}$ is not regular

text:
# Question
Title: Show $\{0^1^|≠\}$ is not regular
So I have the question: show "Show $\\{0^1^|≠\\}$ is not regular". I've already seen various proofs for this question, but they all have one step I don't get.

They all take: $\bar{L}∩(0^∗1^∗)$ ($\bar{L}$ is the complement of $L$) and show that it's not regular. I don't get why we can't just take $\bar{L}$. Because isn't $\bar{L} = \\{0^1^|m=n\\}$ which is the same as $\\{0^n1^n|n ≥ 0\\}$ which we know is not regular? What am I missing?

# Answer
Try to express in natural language what $\overline{L}$ contains; that is, what words $L$ *doesn't* contain. Most obviously, it's "words of the form $0^m0^n$, with $m = n$." However, it also contains "words that are not of the form $0^m1^n$", such as "$101010$". That's why the intersection with $0^\*1^\*$ is employed, to not bother with these words.

The demonstration is then possible because intersection and complementation are closed properties on the regular language. So if $\overline{L} \cap L(0^\*1^\*)$ is not regular, we know that $\overline{L}$ must not be regular, so its complement, $L$, must not be regular.
> 4 votes

# Answer
Assume m ≠ m'. After processing $0^m$ and $0^{m'}$ you cant be in the same state, because in one state adding $1^m$ is not accepted and in the other state adding $1^m$ is accepted. Since is the case for all m ≠ m', the number of states is not finite.
> 0 votes

---
Tags: formal-languages, regular-languages, check-my-answer
---


# Question
Title: Are the frequencies of the Huffman encoding of 3 characters unique?
I have to figure out the frequencies of 3 letters for Huffman encoding of {0, 10, 11}. One suggestion is in the order {$\frac{2}{3}$, $\frac{1}{6}$, $\frac{1}{6}$} as given in part (a) the 2nd slide of page 3 here. My question is whether the last 2 character frequencies need to be evenly split. Could we not have had {$\frac{2}{3}$, $\frac{2}{18}$, $\frac{1}{18}$}? Or could the 3 character frequencies be entirely different say {$\frac{1}{2}$, $\frac{1}{4}$, $\frac{1}{4}$}?

# Answer
> 2 votes
You want frequencies $f\_1,f\_2,f\_3$ for three characters, so that their Huffman encodings are $(0,10,11)$.

The Huffman algorithm repeatedly "merges" the two least frequencies. So any choice that assigns the two least frequencies to the last two characters will work. That means $f\_2,f\_3 \le f\_1$. Since these are frequencies you probably also want the values to add to $1$, but that is of no consequence for the algorithm.

In general the Huffman algorithm does not specify which branches go left and which go right (unless we add that to the implementation) so it is hard to guarantee codes $(0,10,11)$ instead of $(1,00,01)$ for instance.

# Answer
> 0 votes
At a higher level: For sets of n symbols, n fixed, the set of possible Huffman codes is finite (since the length of a Huffman code is at most n-1 bits). The set of possible frequencies is infinite.

---
Tags: huffman-coding
---


# Question
Title: Create a turing machine for log base 2 of n
How would someone create a Turing machine that computes ⌈log2(n)⌉?

I know that:

n = 1, 2, 3, 4, 5, 6, 7, 8, ...

f(n) = 0, 1, 2, 2, 3, 3, 3, 3, ...

And that I want the input tape to have n 1's in it to represent the number i.e. 8 would be

###11111111###

How would the the turing machine for this be created?

# Answer
> 1 votes
The value of $\lceil\log\_2(n)\rceil$ is more or less equal to the number of bits in the binary representation of $n$ (except if $n$ is a power of 2).

You can then imagine a Turing Machine with an input tape (on which is written the number), a work tape and an output tape. First, you need to convert your unary number on the input tape, into binary on the work tape. This can be done with a simple incrementation Turing Machine (you can decide on the side of the least significant bit, but imho left is easier). Then, you need to count the number of bits in the binary number, and write a $1$ for each bit counted. You can use an additionnal state, to detect is the number is a power of 2 (a $1$ followed only by $0$).

This machine can be reduced to two tapes by replacing bits by $1$ on the work tape (except maybe for the last one which needs to become $\\#$ if $n$ is a power of $2$). It can be further reduced to one tape by using the read part of the tape to write the binary number (and another symbol than $\\#$ to replace the $1$ which are read).

Let's be more formal:

I consider a Turing Machine $(Q, \Sigma, \Gamma, \delta, q\_0, q\_f, \\#)$ where $Q$ is the set of states of the TM; $\Sigma = \\{1\\}$ is the input alphabet; $\Gamma = \\{0, 1, \\\\$, \\#\\}$ is the work alphabet ($\\\\$$ is a symbol to separate the input and the output), $\delta$ is the transition function, $q\_0\in Q$ is the initial state, $q\_f \in Q$ is the final state and $\\#$ is the blank symbol. The Turing Machine I imagined is composed of 13 states, it may be possible to do better. Here is the detail on each state (to understand how the TM works) :

* $q\_0$: initial state
* $q\_1$: I have read only one $1$ in the input
* $q\_2$: I have read only two $1$'s in the input
* $q\_3$: I am reading another $1$ in the input ($q\_1$ and $q\_2$ make it easier to separate the input and the output)
* $q\_4$: I am returning to the most left to increment the binary representation
* $q\_5$: I am incrementing, and there is still a carry
* $q\_6$: I have finished incrementing, I return to the input to read $1$'s
* $q\_7$: I have finished reading completely the input, I am returning to the most left to transform the binary representation of $n$ into unary representation of $\lceil\log\_2 n\rceil$
* $q\_8$: I am replacing $0$'s by $1$'s without having seen a single $1$
* $q\_9$: I am replacing $0$'s by $1$'s having seen a single $1$
* $q\_{10}$: I am replacing $0$'s by $1$'s having seen at least two $1$'s (therefore $n$ is not a power of $2$)
* $q\_{11}$: I have concluded that $n$ is a power of $2$, so the last $1$ must be replaced by $\\#$
* $q\_f$: final state

Here is the detail of the transition function, state by state. The first column is the current state of the Turing Machine, the last 4 correspond to the read tape symbol. Each box is given as a triple $(\alpha, q, d)$ where $\alpha$ is the symbol written on the tape, $q$ is the next state and $d$ is the direction of the head shift.

| State | $0$ | $1$ | $\\\\$$ | $\\#$ |
| --- | --- | --- | --- | --- |
| $q\_0$ | - | $1, q\_1, \rightarrow$ | - | $\\#, q\_f, \rightarrow$ |
| $q\_1$ | - | $1, q\_2, \rightarrow$ | - | $\\#, q\_{11}, \leftarrow$ |
| $q\_2$ | - | $\\\\$, q\_3, \rightarrow$ | - | $\\#, q\_{11}, \leftarrow$ |
| $q\_3$ | - | $\\\\$, q\_4, \leftarrow$ | $\\\\$, q\_3, \rightarrow$ | $\\#, q\_{7}, \leftarrow$ |
| $q\_4$ | $0, q\_4, \leftarrow$ | $1, q\_4, \leftarrow$ | $\\\\$, q\_4, \leftarrow$ | $\\#, q\_{5}, \rightarrow$ |
| $q\_5$ | $1, q\_6, \rightarrow$ | $0, q\_5, \rightarrow$ | $1, q\_6, \rightarrow$ | - |
| $q\_6$ | $0, q\_6, \rightarrow$ | $1, q\_6, \rightarrow$ | $\\\\$, q\_3, \rightarrow$ | - |
| $q\_7$ | $0, q\_7, \leftarrow$ | $1, q\_7, \leftarrow$ | $\\#, q\_7, \leftarrow$ | $\\#, q\_8, \rightarrow$ |
| $q\_8$ | $1, q\_8, \rightarrow$ | $1, q\_9, \rightarrow$ | - | - |
| $q\_9$ | $1, q\_9, \rightarrow$ | $1, q\_{10}, \rightarrow$ | - | $\\#,q\_{11},\leftarrow$ |
| $q\_{10}$ | $1, q\_{10}, \rightarrow$ | $1, q\_{10}, \rightarrow$ | - | $\\#,q\_f,\leftarrow$ |
| $q\_{11}$ | - | $\\#, q\_f, \rightarrow$ | - | - |

Here is a simulation of this TM : http://turingmachinesimulator.com/shared/eikrrbjoiz

---
Tags: complexity-theory, turing-machines, automata
---


title: Sorting an interval

text:
# Question
Title: Sorting an interval
Given that array has $k$ elements (all distributed uniformly).
Its length is exactly $3$ somewhere in $\[0, k)$.

For example, if $k=100$ then, we have $100$ numbers and they can be in $\[10,13)$, but they can also be at $\[89,92)$

I need to offer a sorting algorithm, which is efficient.

Now, my idea was Bucket Sort, but why would I care the length of the interval is $3$ or $1000$ ? if the numbers are distributed uniformly, then it does not even matter because we could do just a "regular" bucket sort!

But there is a solution that instead of linked lists in each bucket, we use AVL trees. Why would that matter?! the elements still distributed so it is $O(1)$ in each AVL-Tree AND $O(1)$ in each linkedlist... I really don't get it!

Thanks for helping!

# Answer
You can use a counting sort: if the first element of the array is $n$, then the values of the array are between $n-2$ and $n+2$. If you count the number of elements equal to each of these 5 values and reorder them, your data are sorted.

This can be done because numbers are in an interval of length 3, so you only have 5 different values to consider given the first one.
> 1 votes

# Answer
You don't need any fancy data structures at all, using counting sort.

Initialize three-element array $C$ to all $0$s and $x$ to infinity. Then loop over every element in $A\[i\]$ and:

1. Increment $C\[A\[i\] \bmod 3\]$.
2. If $A\[i\] \< x$ set $x = A\[i\]$.

Finally, output an array consisting of $x$ repeated $C\[x \bmod 3\]$ times, followed by $x + 1$ repeated $C\[(x+1)\bmod 3\]$ times and finally $x + 2$ repeated $C\[(x+2)\bmod 3\]$ times.
> 0 votes

---
Tags: algorithms, sorting
---


# Question
Title: Why is $\forall x \in \mathbb{N}\ \Phi(x,x)$ unary but $\Phi$ is binary?
May anyone explain me why $\forall x \in \mathbb{N}\ \Phi(x,x)$ is unary but $\Phi$ is binary?

In my latest exam I wrote that the universal function $\Phi^n(x\_1, x\_2, ..., x\_n,y) = \psi^n\_y(x\_1,x\_2,...,x\_n)$ is unary because its $n+1$ parameter is a constant referring to the number of the S-program ($y$), but my teacher corrected me writing: "Pay attention: $\Phi$ is binary (and its second parameter is not a constant), but $\Phi(x,x)$ is."

# Answer
A lot of confusion arises because the sloppy notation and imprecise terminology involving free and bound variables. Let me try to clear some of it up.

The title of your question wrongly claims that $\forall x \in \mathbb{N} \\,.\\, \Phi(x,x)$ is a function, which it is not. It is a truth value. Let us see why this is the case.

Suppose someone defined $f$ by writing down $$f(x,y) = x^2 + 3 y,$$ where $x$ and $y$ range over $\mathbb{N}$. First of all, it would be more precise to define $f$ like this: $$f = ((x, y) \mapsto x^2 + 3 y).$$ The right-hand side is read as "the *function* which maps $(x,y)$ to $x^2 + 3 y$". The variables $x$ and $y$ are *bound*, i.e., we get *the same function* if we rename them, for example $(u, v) \mapsto u^2 + 3 v$ is equal to $f$. The function $f$ is *binary* because it takes two arguments.

With $f$ defined as above:

1. The expression $f(x, y)$ is *not a function*! It is a number. Indeed, you would have no trouble claiming that $f(x,y) \in \mathbb{N}$, would you? However, this number is *parameterized* by two *free variables* $x$ and $y$. Thus, *which* number it is *depends* on $x$ and $y$.
2. The previous remark maybe becomes clearer if we contemplate the fact that $f(3, 4)$ is not a function but a number, and so is $f(u,u)$ where $u \in \mathbb{N}$ is a free variable.
3. We can fix just one of the arguments to get a unary function, for example $x \mapsto f(x, 7)$ is unary because it is a map $\mathbb{N} \to \mathbb{N}$.
4. The expression $f(x, 7)$ is not a function! It is a number, parameterized by the free variable $x$.

Next, consider the definition $$g = (x \mapsto x^2 + 3 y).$$ The function $g$ is *unary* because it takes one argument. However, $g$ *depends* on the free variable $y$. (Some people may call this $y$ a "constant", or call $x$ an "argument" and $y$ a "parameter", but let us not do that. We will stick strictly to the terminology "$x$ is a bound variable" and "$y$ is a free variable".) We may rename the bound variable but not the free one:

* $(u \mapsto u^2 + 3 y)$ is equal to $g$
* $(u \mapsto u^2 + 3 v)$ is *not* equal to $g$ because $y$ and $v$ are different free variables
* $(y \mapsto y^2 + 3 y)$ is not equal to $g$ because the free variable $y$ does *not* appear in it.

Some people might define $g$ above like this: $$g\_y = (x \mapsto x^2 + 3 y).$$ They want to indicate that $y$ is a free variable in the definition of $g$. In our notation, this would correspond to $$g = (y \mapsto (x \mapsto x^2 + 3 y))$$ so that now $g$ is a *unary* function *without* free variables. When we apply $g$ to $y$ by writing $g\_y$, we again get a unary function, this time wit one free variable $y$. By the way, writing $g\_y$ instead of $g(y)$ is just cosmetics.

Consider $$\Phi = ((u, v) \mapsto u \< 7 \lor (v + u^2 \> 6).$$ Then $\Phi$ is a *binary function* because it maps from $\mathbb{N} \times \mathbb{N}$ to $\\{\bot, \top\\}$. It should be clear that:

* $\Phi(x,x)$ is *not a function*. It is a truth value parametrized by the free variable $x$.
* $x \mapsto \Phi(x,x)$ is a *unary function* mapping from $\mathbb{N}$ to truth values $\\{\bot, \top\\}$.
* $\forall x \in \mathbb{N} \\,.\\, \Phi(x,x)$ is *not* a function. It is a truth value. Indeed, we can plug in $\Phi$ and get $\forall x \in \mathbb{N} \\,.\\, x \< 7 \lor (x + x^2 \> 6)$, which is false (a truth value, not a function).

What I think you really wanted to ask was this: why is $\Phi$ binary but $x \mapsto \Phi(x,x)$ is unary? Is the answer not obvious, once we use correct notation that does not mess up free and bound variables?

Regarding the discussion with your teacher, there you need to correctly indicate which things are supposed to be free variables and which ones arguments of functions. You wrote: $$\Phi^n(x\_1, \ldots, x\_n, y) = \Psi\_y^n(x\_1, \ldots, x\_n).$$ I am sure you can see such thigs in textbooks, but they are a bit sloppy. To be very precise, we need information on which things in $\Psi$ are supposed to be free variables and which ones are arguments. I would guess that what is meant is that $$\Psi\_y^n : \underbrace{\mathbb{N} \times \cdots \mathbb{N}}\_n \to \mathbb{N},$$ which means that $$\Psi : \mathbb{N} \to (\mathbb{N} \to \underbrace{\mathbb{N} \times \cdots \mathbb{N}}\_n \to \mathbb{N})).$$ We see that $\Psi$ is a unary function, $\Psi\_n$ is a unary function, and $\Psi^y\_n$ is an $n$-ary function with free variables $n$ and $y$. If we read your definition as $$\Phi = (n \mapsto ((x\_1, \ldots, x\_n, y) \mapsto \Psi\_y^n(x\_1, \ldots, x\_n)))$$ then $\Phi$ is an unary function and $\Phi\_n$ is an $(n+1)$-ary function with free variable $n$.
> 4 votes

---
Tags: computability
---


# Question
Title: Is $n \log n$ in $O(n^{1.46-\varepsilon})$?
I am trying to figure out the solution of the recurrence relation $$T(n) = 5T(n/3) + n \log n$$ using the Master Method.

I am guessing that $f(n) = O(n^{1.46 - \varepsilon})$, but I am confused in the part that $\frac{n \log n}{n^{1.46}}$ must be polynomially smaller. If something is polynomially smaller does it mean it can not be bounded either from below or from above (or both)?

# Answer
> 2 votes
When $f(n)$ is said to be polynomially smaller than $g(n)$ it just means that there is some constant $\varepsilon \> 0$ such that $f(n) \in O(g(n) n^{-\varepsilon})$. This is not about being able to bound $f(n)$ from above and/or below but about the growth rate of $f(n)$ when compared to $g(n)$. In other words you want $\frac{g(n)}{f(n)}$ to grow at least as fast as some polynomial/root of $n$.

In your particular case, $n \log n$ is indeed polynomially smaller than $n^{1.46}$, and this follow from the fact that $n \log n \in O(n^\alpha)$ for any $\alpha \>1$.

A a concrete choice of $\varepsilon$, you can pick $\varepsilon=0.1$ yielding $n \log n \in O(n^{1.46-0.1}) = O(n^{1.36})$.

To see this you can consider the limit: $$ \lim\_{n \to \infty} \frac{n \log n}{n^{1.36}} = \lim\_{n \to \infty} \frac{\log n}{n^{0.36}} = \lim\_{n \to \infty} \frac{1}{0.36 \cdot n^{0.36}} = 0, $$ where we used L'Hôpital's rule.

In the above, the choice $\varepsilon = 0.1$ was just a convenient value that works, but any choice of $\varepsilon \in (0, 0.46)$ suffices.

# Answer
> 0 votes
It is well known, that for any fixed number $a\>0$ we have $\log(n)=O(n^a)$.

Then, for a small enough epsilon, that is for $\epsilon\<0.46$ we can define $a=0.46-\epsilon\>0$. Therefore, $log(n)=O(n^{0.46-\epsilon})$. Multiply by $n$ both sides and you get the solution.

---

In fact, $\log(n)=o(n^a)$, and therefore not only $n\log(n)=O(n^{1.46-\epsilon})$, but also $n\log(n)=o(n^{1.46-\epsilon})$ which means that $n\log(n)$ grows substantually slower than $n^{1.46-\epsilon}$.

Therefore, $n\log(n)$ cannot be bounded from below by $n^{1.46-\epsilon}$ but can be bounded from above.

# Answer
> -1 votes
Answering title: $n\lg n = O(n^{1,46 - \varepsilon})$, when $\varepsilon \lt 0.46$.

---
Tags: algorithms, big-o-notation, master-theorem
---


title: Matrix covering by squares

text:
# Question
Title: Matrix covering by squares
I wonder about the following decision problem :

Instance: We consider a $n\times p$ matrix $M$ of zeros and ones, and two integers $N$ and $k$.

Question: is it possible to cover all the ones of the matrix with $N$ squares of side length $k$?

It is possible that the squares cover some of the zeros in the matrix, and they can overlap with each other.

I get the impression that it is $\textsf{NP}$-complete (it is clearly $\textsf{NP}$), I find some similarities with Grid covering by rectangles but can't find a good reduction.

Might I get some insight on the problem?

Thanks.

EDIT: After days of reflexion, these are the ideas I've got:

I try to create a reduction from a Satisfiability problem with the following approach.

Given $\varphi = \bigwedge\limits\_{i=1}^m C\_i$ where $\forall i \in \[\\!\[1,m\]\\!\]$, $C\_i = (\ell\_{i1}\vee \ell\_{i2}\vee\ell\_{i3})$ and $\ell\_{ij}$ is either $x$ or $\neg x$ where $x\in\mathcal{V} = \\{x\_1,…,x\_n\\}$. I create the matrix $A$ with dimensions $(2m+2)\times (6n-1)$ defined by:

* $\forall j \in \[\\!\[1,n\]\\!\], a\_{1,6(j-1)+3} = a\_{2m+2,6(j-1)+3} = 1$;
* $\forall i,j\in \[\\!\[1,m\]\\!\]\times \[\\!\[1,n\]\\!\]$, for $k = 2i - 1$ and $k = 2i$ and for $p = 6(j-1) +2$, $p = 6(j-1) + 3$ and $p = 6(j-1) + 4$, $a\_{kp} = 1$;
* all other coefficients are set to 0.

Here's a visual representation of the matrix:

With this matrix, if, for a variable $j$, we allow the use of $2m-1$ squares of size $2\times 2$, we can either cover all of (except extremities) the column $6(j-1)+1$ or the column $6(j-1) + 5$, but not both and not a mix between them. This can simulate a boolean variable!

The idea I got then was to put ones in the column $6(j-1)+1$ save if $x\_j$ appears in the clause $C\_i$ in which case, $a\_{2i-1, 6(j-1)+1}$ and $a\_{2i,6(j-1)+1}$ stay to zero (and do the same thing similarly in the column $6(j-1)+5$ with the $\neg x$ litteral).

If we then allow the use of $2n-1$ squares for each clause $C\_i$, we need one of the variables to be set correctly in the clause to cover all ones in lines $2i-1$ and $2i$. The problem with this reduction is that you can "gain" some squares in a clause with multiples variables set correctly to change the disposition of a variable elsewhere.

My second idea was to create a reduction from $\texttt{ONE-IN-THREE-SAT}$, in which we ask if there is an assignation to $\varphi$ which satisfies exactly one litteral per clause, or even its restriction where we can suppose that $\varphi$ contains no negations, but I couldn't find something satisfying, so I'd like some help again!

# Answer
This was proved NP-complete in "Optimal Packing and Covering in the Plane are NP-complete" (Fowler, Paterson and Tanimoto, *Information Processing Letters* 1981). I found a freely available version of the paper here. They give a neat reduction from 3SAT -- I'll summarise this below, but the paper is short and easy-to-read with several diagrams, and I recommend reading it!

For each variable they construct a "loop of wire" having an even number of points (1-cells in your formulation), and such that a single square can cover two adjacent points in the loop but no more. This means that there are two ways to cover all points in the loop using a minimal number of squares: Either use a square to cover points 1 and 2, another square to cover points 3 and 4, and so on, or use a square to cover points 2 and 3, another square to a cover points 4 and 5, and so on. Which minimal cover is used corresponds to whether the variable is assigned a value of true or false.

For each clause, they add a single extra point out to the right, and "extrude" the wire loops for the three relevant literals near this point. If any of them is in the right state, the extra point for this clause can be covered "for free" by a square in that loop. Negated literals are achieved simply by slightly compressing a few links in the loop, so that at a position to the right of the compression zone the "parity" of the wire is reversed.

In order to thread the loops through each clause they participate in, wires need to be able to cross over with their signals remaining independent. Interestingly, this "just works" without any additional gadgets.
> 3 votes

---
Tags: complexity-theory, np-complete, np, matrices
---


# Question
Title: Showing that a bijection preserves homomorphism
I have the vocabulary $\tau = \\{+, 0 \\}$ and the structure $R = (\mathbb{R}, +^R, 0^R)$ where $+^R$ is a binary function symbol representing the normal addition of numbers and $0^R$ is the constant $0$ in $\mathbb{R}$. I 'm trying to prove that the bijection $$\sigma : \mathbb{R} \rightarrow \mathbb{R} \text{ with } \sigma(x) = -x$$

is an automorphism of $R$.

What I (think I) only need to show: the homomorphism property for each function symbol, in this case $$+^R : \sigma (x +^R y) = \sigma(x) +^R \sigma(y) \ \forall x, y \in \mathbb{R}$$ holds. We don't need to worry about $0$, since it's covered by our bijection's definition.

So, the homomorphism property seems to work for every $x$ and $y$ I pick, for example:

$$\sigma(1+^R1) = \sigma(2) = \sigma(1) +^R \sigma(1) = -1 +^R -1 = -2$$

$$\sigma(2+^R1) = \sigma(3) = \sigma(2) +^R \sigma(1) = -2 +^R -1 = -3$$

etc.

We can't prove by induction because we're not working in $\mathbb{N}$. Can anyone show me or give me a hint how I can formally prove this for all numbers in $\mathbb{R}$?

# Answer
> 0 votes
The symbol $0^{\mathbb R}$ is a 0-ary function symbol, and you need to handle it as well. Since $-0 = 0$, this is not a problem.

As for $+^{\mathbb R}$, high school arithmetic shows that $$ -(x+y) = (-x) + (-y). $$

More generally, $-$ is an automorphism of any Abelian group. An Abelian group is a set together with a binary operator $+$, a unary operator $-$, and a constant $0$ such that:

1. $x+y = y+x$.
2. $(x+y)+z = x+(y+z)$.
3. $x+0 = x$.
4. $x+(-x) = 0$.

The mapping $x \mapsto -x$ is an automorphism. Notice that

* For all $x$, $(-x)+x=x+(-x)=0$.
* For all $x$, $(-x)+(-(-x))=0$.
* Hence $x = x+0 = x+((-x)+(-(-x))) = (x+(-x))+(-(-x)) = 0+(-(-x)) = (-(-x))+0 = -(-x)$.

Therefore $-$ is an involution. In particular, if $-x=-y$ then $x=-(-x)=-(-y)=y$, so that $-$ is one-to-one. Since $-(-x)=x$, it is also onto.

Since $0 = 0 + (-0) = (-0) + 0 = -0$, we see that $-$ maps $0$ to itself.

Since $-(-x) = -(-x)$, we see that $-$ maps $-$ to itself.

Finally, $$ (x+y)+((-x)+(-y)) = (y+x)+((-x)+(-y)) = ((y+x)+(-x))+(-y) = (y+(x+(-x)))+(-y) = (y+0)+(-y) = y+(-y) = 0. $$ Therefore $$ -(x+y) = (-(x+y)) + 0 = (-(x+y)) + ((x+y)+((-x)+(-y))) = ((-(x+y))+(x+y)) + ((-x)+(-y)) = ((x+y)+(-(x+y))) + ((-x)+(-y)) = 0 + ((-x)+(-y)) = ((-x)+(-y)) + 0 = (-x)+(-y). $$ This shows that $-$ maps $+$ to itself.

---
Tags: logic
---


# Question
Title: Is there a non-deterministic polynomial by time Turing machine such that: $L(M)\in NPC$ and $L(\overline{M})\in P$
When $\overline{M}$ is a non-deterministic polynomial by time Turing machine that final states switched: accept to reject and vice versa. I'm thinking that this equal to $P=NP$, but I saw a solution (an example) that I disagree with: $M$ is a non-deterministic polynomial by time Turing machine that decide $SAT$, if all that paths are rejected then $L(\overline{M})=\Sigma^\*\in P$

Is it a valid solution, or as I'm thinking $L(M)\in NPC$ and $L(\overline{M})\in P \Leftrightarrow P=NP$

# Answer
Let's imagine a Non Deterministic Turing Machine $M$ that decide $SAT$. If we tune this machine a bit, and add a transition on the initial state, for every letter read, that reject the entry. Let $M'$ be the new NTM. Then, $L(M') = L(M)$, since $u\in L(M) \Leftrightarrow \exists$ at least one computational path in $M$ to an accepting state (and the same thing for $M'$).

Now consider $\overline{M'}$. Since we added a rejecting transition which is possible for every entry in $M'$, that means that there is an accepting transition for every entry in $\overline{M'}$, so it means that $L(\overline{M'}) = \Sigma^\* \in P$.

That does not necessarily imply that $P = NP$, the reason being that $L(\overline{M'}) \neq \overline{L(M')}$.

Generaly speaking, $L \in NPC \Leftrightarrow \overline{L} \in \text{co-}NPC$, but that is not the case if you consider a Turing Machine and its switched version.
> 1 votes

---
Tags: complexity-theory, formal-languages, turing-machines, computability
---


# Question
Title: Given a sorted array with n integers, how to find the element that has no duplicates?
I am given a sorted array with n integers. All of the elements repeat exactly twice, while there is one element without duplicate. I need to solve it as efficient as it is possible by divide-and-conquer algorithm. I have noticed that n needs to be odd to satisfy my condition. I thought about doing this: divide my array in two parts from the mid, if from \[0, mid\] or \[mid, end\] I have odd number of elements then my elements is in that half. So, recursively divide also that subarray and so on.

1. How to decide which part of the array to look at first?
2. Does this solution take O(logn)?
3. Is there other effective approach?

# Answer
Assume elements start at index 0. N is odd.

Let mid be an even number close to the middle of the array. Compare a\[mid-1\] and a\[mid\]. There is an odd number of elements before mid-1 and an even number after mid.

If both numbers are equal then the unique one is in the left half \< mid-1. If they are not equal then the unique one is in the right half starting at mid.
> 0 votes

# Answer
This is a classical problem when the array isn't sorted, which has a surprising, almost magical linear solution.

But here, with a sorted array, your idea is great.

The unique element will have an index $u$, and every element $a\[i\]$ will be exactly the same as either $a\[i-1\]$ or $a\[i+1\]$ (which are different). Assuming that arrays start at $0$, the shape of the (sorted) array is first a list of elements where $a\[2i\] = a\[2i+1\]$, then $a\[u\]$, then a list of elements where $a\[2i-1\] = a\[2i\]$.

So to decide where $u$ is, you can take a random position in the array, and just have to ask whether you're in the first part (where doubles start on even indexes) or the second part (where doubles start on odd indexes). This takes a constant number of operation by question, and each question reduces the size of the search array by $2$ (if you sample in the middle, of course).

So, to synthesize :

1. By looking in the middle, you ensure that the next part you have to look at will be as small as possible
2. This yields a $\log(n)$ algorithm
3. This approach is probably optimal, but the proof that there isn't something better to do must be quite hard, so I leave it to someone else ^^
> 1 votes

---
Tags: algorithms, arrays, pseudocode
---


# Question
Title: How can you represent a Huffman-tree in Hex?
I was trying to store a Huffman tree in a binary file recently. I thought it wouldn't be a big problem since you actually have the binary codes already in front of you.

Well, the difference is that the file (in the hex editor) is logically coded in hex. So I tried to convert the "characters" from binary to hex. Without any success.

**Let's take this tree as an example:**

My first attempt was to simply convert Binary to Hex. So for example `01` became `0x01`. But there is a problem now: There are duplicates. So `01` as well as just `1` both became `0x01`.

So I couldn't use that. I also tried to just represent the zeros and ones in hex, for example: `10 1...` (The equivalent of 1 01) but that wouldn't be really efficient anymore.

---

So how could I now make a Huffman tree in Hex? Would I maybe even have to use a different encoding?

I hope I could describe my problem well enough.

# Answer
This practical problem comes up in JPEG, where you can define your own Huffman tables. The codewords are limited to 16 bits, and the table is stored as follows:

* For $\ell=1,\ldots,16$, the number of codewords of length $\ell$ bits.
* For each $\ell$, a list of the values encoded by the codewords of length $\ell$.

The codewords themselves need not be stored, since a Huffman code can be extracted from this description. See Imran Nazar's notes.
> 2 votes

---
Tags: binary, huffman-coding
---


# Question
Title: If $A$ reduces to $B$ and $B$ is NP-hard, is $A$ NP-hard?
Suppose there is a polynomial time reduction from problem $A$ to $B$.

Why is the following false?

> If $B$ is NP-hard then $A$ is NP-hard.

Can some explain this intuitively?

# Answer
***B*** being *NP-hard* does not say anything about ***A***. The problem says that there is a way to reduce *A* to *B* in *polynomial time*.

But on the other hand, it is also not given that *A* getting reduced to *B* is the only pathway for solving *A*. So, there can be other ways of solving A in polynomial time.

Hence, the implication that *A is NP-hard* is false.
> 2 votes

# Answer
Let $B$ be a $\mathsf{NP}$-hard problem and $A=\emptyset$. Then $A \le\_p B$ (the reduction just maps any instance of $A$ to some fixed "no" instance of $B$). However $A$ cannot be $\mathsf{NP}$-hard since there is no Karp reduction from $\Sigma^\* \in \mathsf{NP}$ to $A$.
> 1 votes

# Answer
Suppose that all problems in the world could be ranked in terms of difficulty, where higher numbers correspond to more difficult problems.

If $B$ is NP-hard then its ranking is large, $r(B) \geq M$.

If $A$ reduces to $B$ then $A$ is not harder than $B$, that is, $r(A) \leq r(B)$.

Given $r(B) \geq M$ and $r(A) \leq r(B)$, can you conclude any lower bound on $r(A)$?

---

Concretely, if $r(A) = 0$ then $r(A) \leq r(B)$ yet $r(A) \not\geq r(B)$. This can be realized in the real world by choosing $A$ to be some trivial problem, such as the empty language (all instances are No instances) or the complete language (all instances are Yes instances). Trivial languages are trivially reducible to any language, but they are so trivial that we can be sure that they are not NP-hard (for technical reasons).

If we disallow trivial languages, then we can still take $A$ to be any language in P. Since P is a subset of NP, we know that $A$ reduces to $B$ (this can also be seen directly – a reduction can simply solve $A$ and output one of two fixed instances of $B$), but assuming that P≠NP, $A$ is not NP-hard.

Is the assumption P≠NP really necessary? If P=NP and $A$ is non-trivial then $A$ is trivially NP-hard, since all language in P trivially reduces to any non-trivial language.
> 1 votes

# Answer
Problem: Is a = b? Reduction to bin packing: Assume you have bins of size (a+b)/2. Can one item of size a and one item of size b be packed into 2 bins?

We just reduced a very, very simple problem to an NP-complete problem.
> 0 votes

---
Tags: algorithms, complexity-theory, turing-machines, computability, np-complete
---


title: Average case running time of quick sort

text:
# Question
Title: Average case running time of quick sort
How to show that the quick-sort algorithm runs in $O(n^2)$ time on average ?

Because on average, the expected running time is in $O(n\log n)$. The algorithm should not be in exponential time.

# Answer
It suffices to show that Quicksort runs in time $f(n) = O(n^2)$ *in the worst case*, since this immediately implies that it also runs in at most $f(n)$ time on average.

The recurrence equation that describes the worst-case running time for Quicksort is $$ T(n) = T(n-1) + \Theta(n), $$ which has solution $T(n) = \Theta(n^2)$.
> 1 votes

# Answer
It’s a trick question...

O(f(n)) doesn’t only contain functions that grow about as fast as f(n), it also contains all the functions that grow a lot slower than f(n).

So the average time for quicksort is O(n log n), but it is also O(n^2), O(n^5), O(n!) and many other functions.
> 1 votes

---
Tags: algorithms, asymptotics, runtime-analysis, quicksort
---


# Question
Title: Constructing a NFA that accept complement of language L of another NFA
if given a language $L$ recognized by NFA $N\_0$ over an alphabet $\Sigma$. Is it possible to find a general way of constructing an NFA $N\_1$ that accept $L^C$ such that $L^C= \\{w \in \Sigma^{\*} |\mid w \notin L \\}$?

# Answer
Is there a general way to do it? The answer is yes: one way to do it is to find a DFA that accepts $L$ (for example with the powerset construction), make it complete (by adding a sink state), and swap final states and non-final states. The automaton is deterministic, but it is a special case of non deterministic.

Is there a polynomial time way to do it? I don't know, since the construction above can be exponential time in the number of states (because of the powerset construction).
> 1 votes

---
Tags: regular-languages, finite-automata, nondeterminism
---


# Question
Title: Is there a Zero-Knowledge proof for SAT?
I know that SAT can be reduced to (3 vertex) Graph colouring, and there is a Zero-knowlegde protocol (ZKP) for graph colouring. However, I am interested in a ZKP that can be performed directly on a SAT instance, without graph colouring.

Is there a known ZKP for SAT, and if not how would you suggest coming up with one?

# Answer
As usual with zero-knowledge proofs, this is an interactive proof. A prover is trying to prove that he has a satisfying assignment to some 3-SAT formula without giving away the assignment. A verifier is trying to build up enough statistical evidence to believe the prover. The proof proceeds as a series of rounds and continues until the verifier is convinced the prover has the assignment or convinced that he doesn't. 3-SAT is used so that clauses have uniform length, which along with other measures prevent the verifier from being able to identify any particular clause between the rounds. Since general SAT formulas can be easily converted into 3-SAT formulas, this works as a zero-knowledge proof for SAT as well.

For each round the prover should:

* Permute the variable labels randomly.
* Permute the clause order in the formula randomly.
* Permute the variable order in each clause randomly.
* Invert the parity of each variable's literals randomly with probability one-half.
* Commit to this new formula, but in a way that is hidden from the verifier.
* Commit to a satisfying assignment of this new formula, but in a way that is hidden from the verifier.

After this is done, the verifier can ask the prover for either:

1. The new formula and the permutation mappings so that he can verify that the new formula is the same as the original formula, or
2. One clause of the new formula and the variable assignments for the variables in that clause, taken from the satisfying assignment previously committed to.

If the verifier asks for (1), he can verify that the new formula is the same as the original formula by reversing the permutations and literal inversions. If the prover is cheating by altering the formula to something he can satisfy, this check should eventually catch him.

If the verifier asks for (2), he can check whether part of the committed satisfying assignment will satisfy a randomly selected clause. If the prover is cheating by not satisfying all the clauses, running enough rounds will eventually catch him leaving some clause unsatisfied. The permutations and inversions prevent the verifier from gathering meaningful information about variable assignments from these checks.
> 2 votes

# Answer
Here is a zero-knowledge protocol for E3SAT, the variant of SAT in which each clause contains exactly three literals.

Consider an instance of E3SAT, consisting of variables $x\_1,\ldots,x\_n$ and clauses $C\_1,\ldots,C\_m$.

Prover chooses a color in $\\{1,2,3,4\\}$ for each of the following:

* Variable literals $V(x\_i), V(\lnot x\_i)$ ($2n$ colors in total).
* Literals appearing in clauses ($3m$ colors in total): for each clause $C\_j$ and literal $\ell$ appearing in it, $C\_j(\ell)$.
* Three additional values $a,b,c$.

Verifier makes one of the following checks:

* The colors assigned to $a,b,c$ are all different.
* For a variable $x\_i$, the colors assigned to $V(x\_i),V(\lnot x\_i),b,c$ are all different.
* For a clause $C\_j$ consisting of literals $\ell\_1,\ell\_2,\ell\_3$, the colors assigned to $C\_j(\ell\_1),C\_j(\ell\_2),C\_j(\ell\_3),a$ are all different.
* For a clause $C\_j$ and a literal $\ell$ appearing in it, the colors assigned to $V(\ell),C\_j(\ell)$ are different.

If the formula is satisfiable, the prover acts as follows:

* It chooses random colors for $a,b,c$. We call these colors $a,b,c$, and the remaining color $d$.
* If $x\_i$ is assigned true then we color $V(x\_i)$ by $a$ and $V(\lnot x\_i)$ by $d$, otherwise we color $V(x\_i)$ by $d$ and $V(\lnot x\_i)$ by $a$.
* For a clause $C\_j$, choose a satisfied literal $\ell$, assign $C\_j(\ell)$ the color $d$, and assign the other two $C\_j(\ell'),C\_j(\ell'')$ associated with the clause the colors $b,c$.

It is not hard to check that this satisfies all constraints checked by the verifier. Moreover, since we chose $a,b,c,d$ at random, verifier can simulate the answers on her own, and so this is a zero knowledge protocol.

Finally, suppose that all potential checks of the verifier pass. Let $a,b,c$ be the colors assigned to $a,b,c$, and let $d$ be the remaining color. For each variable $x\_i$, the variable literals $V(x\_i),V(\lnot x\_i)$ are assigned the colors $a,d$. We extract a truth assignment as follows: if $V(x\_i)$ is colored $a$ then we let $x\_i$ be true, otherwise it is false. Each clause $C\_j$ is colored using $b,c,d$, and so some clause literal $C\_j(\ell)$ is colored $d$. The corresponding variable literal $V(\ell)$ must be colored $a$, and so it satisfies the clause.
> 2 votes

---
Tags: complexity-theory, satisfiability, interactive-proof-systems, zero-knowledge-proofs
---


# Question
Title: Number of substrings with exactly k distinct characters
Given a string s and an int k, return an int representing the number of substrings (not unique) of s with exactly k distinct characters. If the given string doesn't have k distinct characters, return 0.

```
Input: s = "pqpqs", k = 2
Output: 7
Explanation: ["pq", "pqp", "pqpq", "qp", "qpq", "pq", "qs"]

```

I have this solution for it:

```
   def subarraysWithKDistinct(self, A, K):
        return self.atMostK(A, K) - self.atMostK(A, K - 1)

    def atMostK(self, A, K):
        count = collections.Counter()
        res = i = 0
        for j in range(len(A)):
            if count[A[j]] == 0: K -= 1
            count[A[j]] += 1
            while K < 0:
                count[A[i]] -= 1
                if count[A[i]] == 0: K += 1
                i += 1
            res += j - i + 1
        return res

```

What I don't understand is how does atMost(k) - atMost(k-1) gives the total number of substrings that have exactly k distinct characters? I tried different examples and it works. I understand how the code works but not how the final answer is computed after two-passes.

Can someone give me generic mathematical proof or intuition behind it?

# Answer
`atMost(A, K)` computes the number of substrings with at most K distinct characters.

A substring with at most K distinct characters has either exactly K, or at most K-1, distinct characters. So, `atMost(A, K) - atMost(A, K-1)` is the number of substrings with exactly K distinct characters.
> 0 votes

---
Tags: algorithms, logic, combinatorics, mathematical-programming, mathematical-analysis
---


# Question
Title: Why doesn't the Floyd-Warshall algorithm work if I put k in the innermost loop
The Floyd-Warshall algorithm is defined as follows:

```
   for k from 1 to |V|
      for i from 1 to |V|
         for j from 1 to |V|
            if dist[i][k] + dist[k][j] < dist[i][j] then
               dist[i][j] ← dist[i][k] + dist[k][j]

```

Why doesn't it work if I simply use

```
for i from 1 to |V|
  for j from 1 to |V|
     for k from 1 to |V|
        if dist[i][k] + dist[k][j] < dist[i][j] then
           dist[i][j] ← dist[i][k] + dist[k][j]

```

In this case, the intermediate node k is iterated in the innermost loop. I expect it will make the same comparisons, but maybe different order. Why is the result different and incorrect?

# Answer
> 6 votes
Take $i - 1$ and $j = 2$. The algorithm is trying to find the shortest path between $1$ and $2$, by considering intermediate vertices. But at this point, most of the array dist is infinity, so we don't even find that $2$ is reachable from $1$ unless the distance is $1$ or $2$.

# Answer
> 4 votes
The approach of the algorithm is dynamic programming. This means that during computation only partial solutions are determined. Here $k$ is an important parameter in the algorithm. When dealing with $k$, shortest paths are computed that are only allowed to pass vertices $1$ upto $k$, the other vertices can only be initial or final. That means that $k$ has a different position than that of $i,j$. We cannot change that order. For a fixed $k$ however, the values $i,j$ within the inner two loops can be evaluated in ant order.

# Answer
> 1 votes
Here is an example when `for k` being the inner most loop doesn't work:

0 -- 2 -- 3 -- 1

Say each edge weight is 1. The corresponding adjacency matrix is:

| Node | 0 | 1 | 2 | 3 |
| --- | --- | --- | --- | --- |
| 0 | 0 | inf | 1 | inf |
| 1 | inf | 0 | inf | 1 |
| 2 | 1 | inf | 0 | 1 |
| 3 | inf | 1 | 1 | 0 |

The final distance for 0 and 1 is inf, which is incorrect:

```
dist[0][1] = min(inf, dist[0][1]+dist[1][1], dist[0][2]+dist[2][1], dist[0][3]+dist[3][1])
           = min(inf, inf, inf, inf)
           = inf

```

# Answer
> 0 votes
Initially

```
dist[i][j] = AdjacentMatrix[i][j] //all directly reachable nodes are the base case.

```

How more can we improve on the base case?

Two possible algorithms which can work.

1. Find `dist[i][j] = For all k { dist[i][k] + dist[k][j] }`

This doesn't work because `dist[i][k]` can still be `INF` and is not finalized.
2. Fix one intermediate node `k1` & find all `dist[i][j]` passing through intermediate node.

On the second intermediate node `k2`, Find `dist[i][j] = min { dist[i][k1] + dist[k1][j] , dist[i][k2] + dist[k2][j] }`

In this algorithm, although `dist[i][k]` is not finalized, it is OK. Because value of `dist[i][j]` is finalized only when `dist[i][kn]` is compared.

---
Tags: algorithms, graphs, shortest-path
---


# Question
Title: Computational indistinguishability for any distribution using a Chernoff bound
I had a question about a general statement regarding finding a computationally indistinguishable distribution given any distribution, observed (in the third paragraph of Section 11, page 31) here. This is the statement:

For any distribution $D$ over $\\{0,1\\}^{n}$, there exists a distribution $D'$ such that $D$ and $D'$ are $\epsilon$ indistinguishable with respect to any classical distinguisher of size $n^{k}$.

Let me restate the proof.

> Let $D$ be any distribution over $\\{0,1\\}^{n}$. Then choose $w$ elements independently with replacement from $D$, and let $D′$ be the uniform distribution over the resulting multiset (so in particular, $H(D′) \leq \log\_{2} n$). Certainly $D′$ can be sampled by a circuit of size $\mathcal{O}(nw)$: just hardwire the elements. Now, by a Chernoff bound, for any fixed circuit $C$, clearly $D$ and $D′$ are $\epsilon$-indistinguishable with respect to $C$, with probability at least $1 − e^{-\epsilon^{2} w}$ over the choice of $D′$. But there are “only” $n^{\mathcal{O}(n^{k})}$ Boolean circuits of size at most $n^k$. So by the union bound, by simply choosing $w = \Omega\left(\frac{n^{k} \log n}{\epsilon^2}\right)$, we can ensure that $D$ and $D′$ are $ε$-indistinguishable with respect to all circuits of size at most $n^{k}$, with high probability over $D′$.

I do not understand how the Chernoff bound is applied. How do we know the action of the circuit $C$? I also don't understand why $w = \Omega\left(\frac{n^{k} \log n}{\epsilon^2}\right)$ in the union bound. Since we need to "protect against" $n^{\mathcal{O}(n^{k})}$ Boolean circuits, shouldn't $w$ be something like $w = \Omega\left(\frac{n^{\mathcal{O}(n^k)} \log n}{\epsilon^2}\right)$?

# Answer
> 1 votes
**How the Chernoff bound is applied**

What does it mean for $D$ and $D'$ to be indistignuishable by a circuit $C$? It means that $$ |\Pr\_{x \in D}\[C(x) = 1\] - \Pr\_{x \in D'}\[C(x) = 1\]| \leq \epsilon. $$ Let $x\_1,\ldots,x\_w$ be the sampled elements. Then $$ \Pr\_{x \in D'}\[C(x) = 1\] = \frac{X\_1 + \cdots + X\_w}{w}, $$ where $X\_i$ is the indicator of $C(x\_i) = 1$. If we sample $x\_1,\ldots,x\_w$ at random, then $X\_1,\ldots,X\_w$ are independent Bernoulli random variables whose expectation is $\Pr\_{x \in D}\[C(x) = 1\]$. Chernoff's bound shows that their average is concentrated around their expectation.

**Applying the union bound**

The probability that a choice of $x\_1,\ldots,x\_w$ is bad for a specific circuit $C$ is $e^{-\epsilon^2 w}$. The probability that a choice of $x\_1,\ldots,x\_w$ is bad for one of $N$ different circuits is at most $Ne^{-\epsilon^2 w}$. Hence if $Ne^{-\epsilon^2 w} \< 1$, the probability that a choice of $x\_1,\ldots,x\_w$ is good to all $N$ circuits is positive, hence there exists such a choice which is good to all $N$ circuits.

Since $w$ is in the exponent, the minimal $w$ needed to satisfy $Ne^{-\epsilon^2 w} \< 1$ scales only logarithmically in $N$.

---
Tags: asymptotics, probability-theory, randomness, pseudo-random-generators, chernoff-bounds
---


# Question
Title: For every Non Deterministic polynomial Turing Machine $M$ exists $L(\overline{M})\in P \Leftrightarrow P=NP$
The $\Leftarrow$ direction is straightforward.
On the other hand for $\Rightarrow$ direction I have an idea of the prove but I don't sure about it.
For NTM, Non Deterministic Turing Machine, $M$, for example TN that decide $SAT$, $L(M)=L(\overline{\overline{M}})\in NP$. It's clear that exists NTM $M'=\overline{M}$ such that $L(\overline{M})\in NP\Rightarrow L(\overline{\overline{M}})\in P$ so $P=NP$. Is this the proof correct?

$\overline M$ is a TM that accept and reject final states swaped

# Answer
> 1 votes
Im assuming the OP meant the question is $(\forall M. M \text{ is nondeterministic polynomial TM }, L(\overline{M})\in P) \iff P=NP$. Look at Steven's answer for the solution regarding the other interpretation of this question.

---

This proof assumes $\overline M$ is a TM that accepts $(w, x)$ where $w$ is a witness for $x $, iff $M$ rejected $(w,x)$. This **does not** imply that $L(\overline {M})=\overline{L(M)}$. Thanks for Nathanuek for correcting me in this one.

In this case, the OP's solution looks correct to me. I will write it here again, a bit more organized.

Lets assume the left side of the question, and we will prove P=NP.

Let $M$ a non-deterministic polynomial turing machine for $SAT$. Then, we can define $M'=\overline M$. From our assumption, we know that $L(\overline{M'})\in P$. But notice that $M=\overline{\overline{M}}=\overline{M'}$, and therefore $SAT=L(M)=L(\overline{M'})\in P$. Since $SAT\in NP-complete$, and we showed that $SAT\in P$ then $P=NP$.

---

This is an "old" proof assuming $\overline{M}$ is a TM for the complement language of $M$.

Lets assume the left side of the question, and we will prove $P=NP$.

Let $M$ be a non-deterministic polynomial turing machine for $SAT$. Then, by assumption we know that $L(\overline M)\in P$ and thus $\overline{SAT} = \overline{L(M)}\in P$.

Therefore there is some **deterministic** polynomial TM $M'$ that solves $\overline{SAT}$. We know that $P$ is closed under negation and thus $co-P=P$ (we usually dont even write $co-P$ since this always holds). In other words, we know that there is $\overline{M'}$ which is also **deterministic and polynomial**. Therefore $SAT = L(\overline{M'})\in co-P=P$

Since $SAT\in NP-complete$ then $P=NP$

---
Tags: complexity-theory, formal-languages, turing-machines, computability
---


# Question
Title: Big Oh and Big Omega when $n$ and $\log n$ terms are in $f(n)$
having problems with big oh and big omega functions when there is a $\log n$ added or subtracted. For example how do I deal with $n+\log n$ or $n-\log n$ when I have to determine whether the function is in $\Omega(n)$ or in $\Omega(n^2)$? For example, is $n-\log n$ in $\Omega(n)$ or in $\Omega(n^2)$?

I cannot ignore the log function and am not sure how to deal with it. Polynomials and logs when multiplied I find OK. But I have a mental block over this one so help would be appreciated

# Answer
You are right that you cannot *a priori* ignore additional terms, although morally you can as the "smaller" terms do not contribute to the asymptotic growth.

As an example $f(n) :=n+\log n$ is in $\Theta(n)$. Why? Going back to the definition, we want to show that $f(n)$ is in $O(n)$ and in $\Omega(n)$. Showing $f(n)\in \Omega(n)$ is immediate, as $f(n) \geq n$ for all $n\>0$.

To show that $f(n)$ is in $O(n)$, simply notice that for large enough $n$ (say $n\>N$ for some constant $N$) we have $\log n \leq n$ and thus $f(n)\leq 2n$ for all $n\>N$. By definition $f(n)\in O(n)$.
> 2 votes

# Answer
Actually, you CAN ignore the log function in a sum or substraction, because the log is always asymptotically negligible in front of $n^x$, for every $x \> 0$.

If you consider the function $f(n) = n^x + \alpha\log n$ (where $x \> 0$ and $\alpha \in \mathbb{R}$), then there exists $A, B \in \mathbb{R}\_+^\*$ such that $An^x \leq f(n) \leq Bn^x$. That means that $f\in \Omega(n^x)$ and $f\in \mathcal{O}(n^x)$.
> 0 votes

# Answer
In your example, $n-\log(n)=\theta(n)$, that is $n-\log(n) = \Omega(n)$ and also $n-\log(n)=O(n)$.

You can see this like that:

* $n-\log(n)\le n = O(n)$
* $n-\log(n) \ge n - 0.5n = \Omega(n)$
> 0 votes

---
Tags: asymptotics
---


# Question
Title: What algorithm do SVMs use to minimize their objective function?
Support Vector Machines turn machine learning linear classification tasks into a linear optimization problems.

$$ \text{minimize } J(\theta,\theta\_0) = \frac1n \sum\_1^n \text{HingeLoss}(\theta,\theta\_0) + \frac{\lambda}{2} ||\theta||^2 $$

My question is, what linear programming runs on the background for the minimization of the objective function $J$. Is it Simplex?

# Answer
The SVM problem (and other related problems) can be described as a minimization \ maximization of a quadratic function.

This can be easily solved with the gradient descent algorithm, however I recommend using the SMO algorithm since it is a direct solution (to the dual of the SVM problem), and can be also used for kernelized SVMs
> 6 votes

---
Tags: machine-learning, svm, simplex
---