title: Teaching Recursion

text:
# Question
Title: Teaching Recursion
I'm a teacher assistant in my university and my next topic is recursion. what way is the best to teach recursion so that the student can grasp the concept easily and can think recursively?
I was thinking about explaining the stack structure to teach recursion but I'm worried that they get stuck in tracing the process. any hint?

# Answer
My favorite way to teach recursion is by reference to the Recursion Fairy.

I'm sure we're all familiar with the idea that stories can be a very effective way to teach ideas; people seem built to hear and remember stories. The Recursion Fairy is an explanation suggested by Jeff Erickson, which lends well to this approach.

As Jeff E. writes:

> Recursion is a a particularly powerful kind of reduction, which can be described loosely as follows:
>
> * If the given instance of the problem is small or simple enough, just solve it.
> * Otherwise, reduce the problem to one or more simpler instances of the same problem.
>
> If the self-reference is confusing, it’s helpful to imagine that someone else is going to solve the simpler problems, just as you would assume for other types of reductions. I like to call that someone else the Recursion Fairy. Your only task is to simplify the original problem, or to solve it directly when simplification is either unnecessary or impossible; the Recursion Fairy will magically take care of all the simpler subproblems for you, using Methods That Are None Of Your Business So Butt Out1. Mathematically sophisticated readers might recognize the Recursion Fairy by its more formal name, the Induction Hypothesis.
>
> 1: When I was a student, I used to attribute recursion to “elves” instead of the Recursion Fairy, referring to the Brothers Grimm story about an old shoemaker who leaves his work unfinished when he goes to bed, only to discover upon waking that elves (“Wichtelmänner”) have finished everything overnight. Someone more entheogenically experienced than I might recognize them as Terence McKenna’s “self-transforming machine elves”.

I recommend reading his entire lecture notes on recursion. They are a thing of beauty and will give you many excellent ideas for how to teach recursion.

For instance, check out his explanation of the Towers of Hanoi, where he shows how to solve the problem by recursion. My favorite part:

> The trick to solving this puzzle is to think recursively. Instead of trying to solve the entire puzzle all at once, let's concentrate on moving just the largest disk. \[...\] And then after we move the $n$th disk, we have to move those $n-1$ disks back on top of it. So now all we have to figure out is how to...
>
> STOP!! That's it! We're done! We've successfully reduced the $n$-disk Tower of Hanoi problem to two instances of the ($n-1$)-disk Tower of Hanoi problem, which we can gleefully hand off to the Recursion Fairy (or, to carry the original story further, to the junior monks at the temple).

---

References to the Recursion Fairy: A Youtube video ("Recursion is when you need to solve something, you call on yourself instead of others!" "So when I have a problem, I ask myself to solve it?" "In order to understand recursion, one must understand recursion"). Divide-and-conquer is an Army of Recursion Fairies.
> 7 votes

# Answer
I find that the best way to explain non trivial recursion is to start with mathematical functions, which are more "comfortable" for some of the students. For example, Fibonacci numbers are an excellent example, since they use two recursive calls.

Another example (which can be given as a simple exercise) is to compute $n!$.

Then, some more "algorithmic" examples are in order, on more involved data structures. The most natural examples here are tree traversals (pre-order, in-order, post-order). I think that after these examples, the students get the hang of it. From there on, it's mainly practice.

I would save the stack structure for later, as it is more relevant to the way recursion is actually implemented in computers, which has less to do with the actual concept of recursion.
> 3 votes

# Answer
Shaull's suggestions are good. It's important to keep in mind, and continually remind the students that the underlying idea is:

> To solve a problem: (1) deal with the base case(s), where recursion doesn't apply, and (2) solve everything else by solving smaller problem(s) and suitably combining the smaller solutions into your solution for the original problem.

This works well for numeric problems, like computing $n!$ (where the smaller problem involves computing $(n-1)!$) or computing $x^n$ using repeated squaring (where the smaller problem is, basically, computing $x^{n/2}$).

Recursion and induction go hand in hand, especially when proving correctness of a recursive algorithm or when getting timing estimates for one.

Recursion is a natural technique for trees, of course, but don't forget about lists, as well, doing things like recursively summing a list of numbers or reversing a list. Of course mergesort is a natural candidate here and it's worth the effort to do it all recursively, including a recursive implementation of splitting a list into two nearly-equal parts and implementing the merge portion recursively.

I like to point out that besides being a powerful design tool, recursion is worth study since there are problems where the non-recursive solution can be exceedingly hard to come up with. A good example of this is the Towers of Hanoi: the recursive solution is simple and more or less transparent, while a non-recursive solution is really difficult to explain and, probably, even harder to invent in the first place.
> 3 votes

# Answer
When teaching recursion, you may want to start with **functions** or with **data-structures**.

As I recall from my teaching days, I used to start with a cooking structure: the onion. So I explained that a onion is either a lonely peal (or a kernel), or an oinion with a peal around it. Then I switched to other structures such as strings or trees.

Then I had to write programs for these structures. And they naturally called themselves recursively, following the definition of the structure. The base case concept also appears more natural, and the approach avoid having the concept of simpler instances of the problem, at least at first.

Applying it to other data such as numeric data is then more natural.
> 2 votes

---
Tags: recursion, education, didactics
---


# Question
Title: Largest N squares that fit in a rectangle
I was working on a project and I needed to display N squares inside a rectangle area and I want them to be as large as possible, no rotations. More formally:

Problem: Given N equal-sized squares and a rectangle with width W and height H, find out the maximum size of the squares L such that the squares fit inside the rectangle in such a way that their sides are orthogonal to the rectangle sides.

So far, I think we have a `O(sqrt(N))` solution, in which we assume `W>H`, start by trying to place all squares in a single row, then in two rows and so on, until we get to `O(sqrt(N))`. For formally, let `nRows` be a variable from 1 to `sqrt(N)`, `nCols = ceil(N/nRows)` and then do `L = min(H/nRows, W/nCols)`.

I'm not completely sure the idea above is optimal. I was also wondering if we can solve this problem in `O(1)`?

I've tried looking for orthogonal square packing, but the problem seems a bit different (or could we easily reduce on to another?)

# Answer
> 1 votes
Let

\begin{align} C&=\left\lfloor\frac WL\right\rfloor& R&=\left\lfloor\frac HL\right\rfloor \end{align}

be the maximum number of rows and columns respectively. It sounds as though you're looking for the maximum $L^\*$ such that, when $L=L^\*$, we have $CR\ge N$. Let

\begin{align} L\_0&=\sqrt{\frac{WH}N}\\ C\_0&=\left\lceil\frac W{L\_0}\right\rceil=\left\lceil\sqrt{\frac{WN}H}\right\rceil& R\_0&=\left\lceil\frac H{L\_0}\right\rceil=\left\lceil\sqrt{\frac{HN}W}\right\rceil. \end{align}

Observe that $L\le\min{\\{W/C\_0,H/R\_0\\}}$ is sufficient, and $L\le L\_0$ is necessary:

\begin{align} \frac{WH}{L^2}&\ge\left\lfloor\frac WL\right\rfloor\left\lfloor\frac HL\right\rfloor=CR\ge N\\ L&\le\sqrt{\frac{WH}N}=L\_0, \end{align}

with equality only if $W/L\_0$ and $H/L\_0$ both are integers. As a result, the optimal solution has dimension either $C\_0\times\lceil N/C\_0\rceil$ or $\lceil N/R\_0\rceil\times R\_0$.

# Answer
> 0 votes
Another possible approach is to look for good rational approximations to the ratio $W/H$, i.e., positive integers $r,s$ such that $r/s \approx W/H$.

Any good solution to your problem immediately yields such a good rational approximation (just let $r = $ the number of rows of squares and $s = $ the number of columns). Similarly, any good rational approximation to $W/H$ suggests a candidate solution to your problem (let $k=\lceil \sqrt{N/rs} \rfloor$, and then consider an arrangement with about $kr$ rows and $ks$ columns). So, a plausible approach might be to generate a bunch of good rational approximations to $W/H$, then test each corresponding candidate layout to see which is the best.

There are various algorithms for generating good rational approximations to a desired number $\alpha \in \mathbb{R}$. For instance, you can use continued fractions to generate a set of candidate approximations; there is a mathematical guarantee that each candidate will be a very good approximation, in some well-defined mathematical sense. The running time to generate and examine all such continued fractions will be poly-logarithmic in $N$. However, I don't know whether this will be better in practice than your simple $O(\sqrt{N})$ time algorithm.

---
Tags: optimization, computational-geometry, packing, square-grid
---


title: How is IO a monad?

text:
# Question
Title: How is IO a monad?
I am learning the Haskell programming language. From what I am reading, Input/Ouput (IO) raises challenges for Haskell's purity, since by definition we are interacting with the outside world. From Wikipedia:

> In a purely functional language, such as Haskell, functions cannot have any externally visible side effects as part of the function semantics. Although a function cannot directly cause a side effect, it can construct a value describing a desired side effect, that the caller should apply at a convenient time.
>
> In the Haskell notation, a value of type IO a represents an action that, when performed, produces a value of type a.

Soon, I learned that IO is an example of a Haskell monad. Although we don't get a lot of explanation of what monads are. From Functors, Applicatives, And Monads In Pictures

> How to learn about Monads:
>
> 1. Get a PhD in computer science.
> 2. Throw it away because you don’t need it for this section!

By now, I have read various definitions of - that they add context or create smaller programming languages inside a big one around a specific concept. Still trying to get a sense of what monads and how those ideas apply.

In Haskell, `monad` is another typeclass, with basically only one rule defining it. And `IO` is an instance of that.

```
class Monad m where
    (>>=) :: m a -> (a -> m b) -> m b

```

https://stackoverflow.com/questions/44965/what-is-a-monad

Is there something algebraic going on here? What is so algebraic about IO?

---

I apologize for being language specific. My hope is that most of this discussion applies to all functional programming languages. Any errors in my discussion represent my own limited understanding of this area.

There is another definition of monad I found in nLab that is not even specific to programming languages.

In a separate question, I would like to understand how the category theory notion of monad matches with the CS definition in the case of Haskell.

# Answer
> 9 votes
TLDR: Haskell types and functions form a category and from that we notice that things with `>>=` and `return` satisfy the rules for monads.

In order to consider what it means for some type to be part of a monad triplet we must first consider what a category means in the Haskell sense.

We let our category `Hask` be defined with objects as Haskell types and arrows to be functions. Each identity arrow is an instance of `id` and composition is the normal `.`. It's trivial to see that these satisfy the normal coherence conditions.

We can now look at endofunctors in Hask. The contain two parts, a map from types to types, and a map from functions to functions so that

* `map g . map f` = `map (g . f)`
* `map id` = `id`

Functors are therefore type constructors (which map types to types) paired with a function `map` which lifts arrows `a -> b` to arrows `F a -> F b`. We can also define natural transformations between them as something which "slides" a member of `F a` to a member of `G a` satisfying the normal coherence conditions

* `nat . fmap f` = `fmap f . nat`

So we can conclude that a natural transformation is something with the type

```
nat :: forall a. F a -> G a

```

Finally we take note that the identity type constructor

```
type Id a = a

```

is a functor with its map given by identity.

We're now prepared to discuss monads! A monad is a triplet of 3 things,

* A functor, `F`
* A natural transformation `return` between `Id` and `F`
* A natural transformation `join` between `F x F` and `F`

With the coherence conditions that `join . fmap join = join . join` and `join . fmap return = join . return = id`.

where the `x` means the product of two functors which is just defined by composition of type constructors.

The `IO` monad has a `return :: a -> IO a` $\equiv$ `Id a -> IO a`. That's our first natural transformation. Our second isn't quite as easy, but we can define `join` as

```
join :: IO (IO a) -> IO a
join = (>>= id)

```

We can view `join` as a sequencing operation. It takes all the actions stored in the structure of the outer `IO` and sticks them in front of all the actions in the inner `IO`, returning a bigger but flat `IO a`.

So in essence, we have this abstract notion of monads in category theory and since Haskell types can be viewed as a category, we can apply normal category theoretic notions like monads and get common patterns out of them. That's it. There's no secret category theory juice lending higher meaning to monads beyond those coherence conditions.

This is actually quite a common pattern. Whenever we view something with categories, be it logic, semantics, or type systems, we can blindly apply the last 100 years of research to our new category and discover "new" abstractions.

---
Tags: programming-languages, functional-programming
---


# Question
Title: Obtaining an Algorithm for a heavier coin
You have n coins — they all look identical, and all have the same weight except one, which is heavier than all the rest. You also have a balance scale, on which you can place one set of coins on one side, and another set of coins on the other, and the scale will tell you whether the two sets have the same weight, and if not, which is the heavier set. (a) Assuming that n = 3^k , devise a strategy that will identify the heavy coin using at most k weighings in the worst case. (b) Without any assumption on n, devise a strategy that will identify the heavy coin using log3 n+O(1) weighings.

My thought so far is to divide the number of coins into a set of 3 piles and weigh 2 piles at a time. Then take the heavier pile and weigh it with the other pile. This is probably incorrect, but its all I've got.

# Answer
> 0 votes
Split the pile into 3 groups. Then weigh any 2 against each other. If one is heavier, then keep it and discard the other 2 immediately. If they weight the same, then discard them both and keep the other one. Continue this until there is one left.

You will eliminate $2(n/3)$ with every iteration i.e. if we started with $n=3^k$ and we divide the size of the pile by three with every weighing then after the first weighing, $i=1$ we have $3^{k-1}$ coins remaining. When $k-i=0$ then there is one coin left. Cleanly the number of weighings is $log3(n).$

---
Tags: algorithms
---


title: Which fixpoint is Haskell list type?

text:
# Question
Title: Which fixpoint is Haskell list type?
Let's say that lists are defined as

```
List a = Nil | Cons a (List a)

```

Then, in Haskell is `List x` the greatest or least fixpoint? I'm asking because the lfp should exclude infinite lists (but you can build them in Haskell), whereas the gfp should exclude finite ones.

# Answer
> 5 votes
The proper thing is to setup

```
data ListF a x = Nil | Cons a x

```

Now you can write

```
newtype Mu f= Mu (forall a.(f a->a)->a)
data Nu f   = forall a. Nu a (a->f a)

```

In Haskell we can observe that `Mu ListF` and `Nu ListF` coincide. So, it can be either (!). (one source on this claim: http://www.cs.ox.ac.uk/jeremy.gibbons/publications/adt.pdf)

Additionally, we can prove things by induction on all lists and get proofs that work as long as we limit ourselves to caring about finite ones, as described here: http://www.cs.ox.ac.uk/jeremy.gibbons/publications/fast+loose.pdf

Two other references on this are:

# Answer
> 10 votes
It's the greatest fixed point, or the final coalgebra, depending on how you set things up. In Haskell it is impossible to define the datatype of finite lists because Haskell does not have inductive types, only the coinductive ones. Many people are in denial about this particular issue.

---
Tags: programming-languages, type-theory, functional-programming, semantics, category-theory
---


title: Implementation of datatypes in Haskell?

text:
# Question
Title: Implementation of datatypes in Haskell?
In Haskell, are datatypes converted to the "Church encoding" i.e. folding the data type. For example, given

```
data N = Z | S N

```

in Haskell, it can be converted to its church encoding by

```
foldN Z z s = z
foldN (S n) z s = s (foldN z s n)

```

Where if we do foldN m, we get the church encoding:

```
\z s . s (  .... s n ... )

```

In Proofs and Types, Girard shows how this works for any inductive datatype. There are two questions I have: (1) is this actually how Haskell treats datatypes and (2) what is the equivalent construction for coinductive datatypes.

# Answer
> 1 votes
To answer the question: No implementation of Haskell to my knowledge has ever represented datatypes as church encodings.

I believe that church-style encodings (or variants such as Scott encodings) work equally well for coinductive types.

---
Tags: data-structures, term-rewriting, interactive-proof-systems
---


# Question
Title: How much math background do you need to understand how category theory is applied to Haskell?
Basically, how much math background do you need to understand how category theory is applied to Haskell? If you already have mathematical maturity, can you jump right into it, or should you be familiar with certain subjects in algebra?

# Answer
The first step is to learn category theory without regards to Haskell (and if you don't have it, Haskell without regards to category theory). A book such as Lawvere's *Conceptual Mathematics* is a good start. Awodey is also recommended, and Leinster's recent *Basic Category Theory*.
> 0 votes

---
Tags: category-theory
---


# Question
Title: Is dependency analysis required in order to type a program?
I have seen stated in various places that in order to allow an "increase in polymorphism," functional dependency analysis should be performed, and type inference should be used for every declaration group in topological order. It seems like a well-known fact... except that nobody provides any reference or example.

In fact I don't understand what is really meant by this statement. Does it mean that without doing dependency analysis I wouldn't be able to type some programs (i.e. some valid programs would fail type-checking) or only that I would type them with a type that is more specific than what really is?

I'm particularly interested in consequences in a Haskell-like language/type system. In particular during *kind inference*, is dependency analysis actually necessary to avoid rejecting valid programs? Can you provide an example that wouldn't be well-kinded if typed without performing dependency analysis?

Since kinds are monomorphic I struggle to understand why dependency analysis should matter in this particular case.

# Answer
> 2 votes
Any use of a type anywhere may place constraints on that type. So, in the absence of explicit type signatures (i.e. when doing type *inference*) it is necessary to perform inference in a way that doesn't allow *specific* usages of a type in a particular form to "infect" the most general type it may have. This involves a dependency analysis. Consider

```
id = \x -> x
foo = id 1

```

Now if we type foo first, we would unify the first argument of `id` with `Int` and thus conclude `id` had type `Int -> Int`. So therefore we must first type `id` and then *generalize* its signature to the polymorphic type `forall a. a -> a`, and *then* instantiate that at type `Int` when we apply it and attempt to unify the argument type with `Int`.

Hence, dependencies and topological sort!

---
Tags: functional-programming, typing, type-inference
---


# Question
Title: What is the Relationship Between Programming Languages, Regular Expressions and Formal Languages
I've looked around the net for an answer to this question and it seems as if everybody implicitly knows the answer except me. Presumably this is because the only people who care are those who have had tertiary education on the subject. I, on the other hand, have been thrown in the deep end for a high school assignment.

My question is, how exactly are programming languages related to formal languages? Everywhere I read, something along the lines of "formal languages are used for defining the grammar of programming languages" is said.

Now from what I've been able to gather, a formal language is a series of production rules that apply to a specific set of symbols (the language's alphabet). These production rules define a set of transformations, such as:

`b -> a`

`aaa->c`

This can be applied such that:

`abab->aaaa` `aaaa-> ca`

Just as a side note, if we define that our formal language's alphabet as {a,b,c}, then a and b are non terminals and c is terminal as it can not be transformed (please correct me if I'm wrong about that).

So given all that, how on earth does this apply to programming languages? Often it is also stated that regex is used to parse a language in it's text form to ensure the grammar is correct. This makes sense. Then it is stated that regex are defined by formal languages. Regex return true or false (in my experience at least) depending on if the finite state automata that represents the regex reaches the goal point. As far as I can see, that has nothing to do with transformations\*.

For the compiling of the program itself, I suppose a formal language would be able to transform code into consecutively lower level code, eventually reaching assembly via a complex set of rules, which the hardware could then understand.

So that's things from my confused point of view. There's probably a lot of things fundamentally wrong with what I have said, and that is why I'm asking for help.

---

\*Unless you consider something like `(a|b)*b*c->true` to be a production rule, in which case the rule requires a finite state automata (ie: regex). This makes no sense as we just said that

# Answer
Whoever told you that regular expressions are used to parse code was spreading disinformation. Classically (I don't know to what extent this is true in modern compilers), the parsing of code – conversion of code from text to a syntax tree – is composed of two stages:

1. Lexical analysis: Processes the raw text into *chunks* such as *keywords*, *numerical constants*, *strings*, *identifiers* and so on. This is classically implemented using some sort of finite state machine, similar in spirit to a deterministic finite automaton (DFA).
2. Parser: Run after lexical analysis, and converts the raw text into an annotated syntax tree. The grammar of programming languages is (to first approximation) context-free (actually, one needs an even stricter subset), and this allows certain efficient algorithms to parse the lexified code into a syntax tree. This is *similar* to the problem of recognizing whether a given string belongs to some context-free grammar, the difference being that we also want the *proof* in the form of a syntax tree.

Grammars for programming languages are written as context-free grammars, and this representation is used by *parser generators* to construct fast parsers for them. A simple example would have some non-terminal STATEMENT and then rules of the form STATEMENT$\to$IF-STATEMENT, where IF-STATEMENT$\to$if CONDITION then BLOCK endif, or the like (where BLOCK$\to$STATEMENT|BLOCK;STATEMENT, for example). Usually these grammars are specified in Backus-Naur form (BNF).

The actual specifications of programming languages are not context-free. For example, a variable cannot appear if it hadn't been declared in many languages, and languages with strict typing might not allow you to assign an integer to a string variable. The parser's job is only to convert the raw code into a form which is easier to process.

I should mention that there are other approaches such as *recursive descent parsing* which doesn't actually generate a parse tree, but processes your code as it parses it. Although it doesn't bother to generate the tree, in all other respects it operates at the same level as described above.
> 24 votes

# Answer
This is some heavy stuff for a high school assignment.

Yuval Filmus's answer is really good, so this is more of a supplementary answer to clarify some of the points he made.

A formal language is a mathematical construction. Their use for programming languages is just one of many possible uses; in fact, linguist Noam Chomsky made significant contributions to the early theory of formal languages. He invented the Chomsky Hierarchy, which classifies formal languages into regular, context-free, etc. Formal languages are also applied in linguistics to describe the syntax of natural languages like English. Think of it like the real numbers: we can use the real numbers to describe both concrete things like the distance from Los Angeles to New York, and abstract things like the ratio of a circle's circumference to its diameter. Even though both of those things exist independently of the real numbers, the real numbers are a helpful system for describing them. Formal languages are a helpful system for describing both English and Python, because both have a similar structured format.

Formal languages are just manipulations of symbols; they don't say anything about what the symbols mean. Think of an algebra problem like $a + b + c = d$. That equation has no inherent meaning, but we can still manipulate the symbols according to the rules of algebra; for example, we can rewrite it as $a + b = d - c$, even though we have no idea what the symbols mean. A way of giving meaning to the symbols within a system is called the semantics (in both natural and programming languages). So we could interpret $a$, $b$, and $c$ as dollar amounts, for example, and then the equation has meaning.

Classically, a programming language will have two grammars: a lexical grammar and a syntactic grammar. The lexical grammar deals with characters such as letters, semicolons, braces, and parentheses. It's usually a regular grammar, so it can be expressed with regular expressions or a DFA or NFA. (There are proofs in formal language theory showing the three are equivalent in power—meaning they accept the same set of languages.) The lexing phase of the compiler or interpreter is sort of a mini interpreter for the regular language grammar. It reads the rules of the grammar, and following those rules, it lumps up individual characters into tokens. For example, if the language has an `if` statement that looks more or less like C's, the lexer might lump the characters `i` and `f` into the single token `IF`, then look for an opening parenthesis and output a token `OPEN_PAREN`, then handle whatever's between the parentheses, and then find the closing parenthesis and output a `CLOSE_PAREN`. When the lexer's done making tokens, it hands them over the parser, which determines if the tokens actually form valid statements of the programming language. So if you write `ip a == b` in Python, the lexer just does its best to guess what kind of token `ip` is (probably it would be taken for an identifier by most lexers), and passes it to the parser, which complains because you can't have an identifier in that position.

The parser implements the syntactic grammar, which is usually context-free, although as Yuval's answer mentions, most programming languages nowadays actually don't use the full abilities of context-free grammars to make parsing simpler and more efficient. Here's Python's syntactic grammar, written in a variant of Backus-Naur form, which is a slight variant of the $a \rightarrow b$ format in the OP. The Java language specification also has examples of Java's lexical and syntactic grammars.

Let's look at the grammar rules for Python's `if` statement. This is the rule:

`if_stmt: 'if' test ':' suite ('elif' test ':' suite)* ['else' ':' suite]`

That rule tells us how the parser will figure out if a string of tokens sent from the lexer is an `if`-statement. Any word in single quotes needs to appear, just like that, in the source code, so the parser will look for the plain word `if`. The parser will then try to match some tokens to the rule for `test`:

`test: or_test ['if' or_test 'else' test] | lambdef`

`test` is defined in terms of other rules in the grammar. Notice how `test` also includes itself in its definition; that's called a recursive definition. It's the big power of context-free languages that regular languages don't have, and it allows things like nested loops to be defined for programming language syntax.

If the parser manages to match some tokens to `test`, it will try to match a colon. If that succeeds, it will try to match some more tokens using the rule for `suite`. The section `('elif' test ':' suite)*` means that we can have any number of repetitions of the literal text `elif`, followed by something that matches `test`, followed by a colon, followed by something that matches `suite`. We can also have zero repetitions; the asterisk at the end means "zero or as many as we want".

At the very end is `['else' ':' suite]`. That part's enclosed in square brackets; that means we can have zero or one, but no more. To match this, the parser needs to match the literal text `else`, a colon, and then a `suite`. Here's the rule for a `suite`:

`suite: simple_stmt | NEWLINE INDENT stmt+ DEDENT`

It's basically a block in C-like languages. Since Python uses newlines and indentation to mean things, the lexer outputs `NEWLINE`, `INDENT`, and `DEDENT` tokens to tell the parser where a new line started, where the code started to be indented, and where it was returned to the outer level of indentation.

If any of these match attempts fail, the parser flags an error and stops. If the parsing of the whole program succeeds, the parser will usually have built a parse tree as Yuval covered in his answer, and possibly a symbol table and other data structures that store semantic information. If the language is statically typed, the compiler will walk the parse tree and look for type errors. It also walks the parse tree to generate low-level code (assembly language, Java bytecode, .Net Intermediate Language, or something similar) which is what actually runs.

As an exercise, I'd recommend taking the grammar of some programming language you're familiar with (again, Python, Java, and here's C#, Javascript, ) and try to hand-parse something simple, like maybe `x = a + b;` or `if (True): print("Yay!")`. If you're looking for something simpler, there's also a nice grammar for JSON, which basically covers just the syntax for object literals in Javascript (like `{'a': 1, 'b': 2}`). Good luck, this is brain-bending stuff but it turns out to be really interesting when you're not on some crazy deadline.
> 12 votes

# Answer
## In a nutshell

Programming languages are composed of a syntax that represent the program as strings of characters, and a semantics that is the intended meaning of the program.

Formal languages are syntax without meaning. It is meant to study the structure of sets of strings defined formally, without usually attaching meaning to those strings.

Regular expression and other formalisms (such as Context-Free Grammars) are used to define formal languages, used as syntactic component of programming and natural languages, i.e. to represent sentences in a structured way. Other mechanisms are used to relate that structure with the semantics of the programming languages.

Much here is considerably simplified, particularly regarding natural language.

## With a lot more details

To answer your question we should start from the beginning. A language in the usual sense is, informally, a means to convey information or ideas. In a language, one usually distinguishes between syntax and semantics. Semantics is what you want to talk/write about. the information you want to convey. Syntax is the means you use to convey it, i.e. a conventional representation that can be exchanged between people, and now also between people and devices, or between devices (computers).

Typically, you will use the word `dog` to convey the idea of a dog. The word `dog` is made of three letters, or some equivalent sound, and is intended to be the representation of some kind of animal. The key idea is that communication is done through representation of what is to be communicated. Representation structures are usually called syntax, while what is represented is called semantics. This goes more or less for natural language as well as for programming languages.

Words are syntactic entities to represent more or less elementary semantic concepts. But these elementary concepts have to be put together in a variety of ways to give more complex meaning. We write `the dog` to convey that we mean a specific dog, and `the dog bites the cat` to convey a more complex idea. But the way the words are organized has to be fixed by rules, so that we can tell which of the dog and the cat is actually biting the other.

So we have rules such as `sentence -> subject verb complement` that are supposed to match sentences and tell us how the ideas associated with each part are articulated. These rules are syntactic rules, since they tell us how the representation of our message is to be organized. The `subject` can itself be defined by a rule `subject -> article noun`, and so on.

The same is true in mathematics. You have mathematical expression written with a very formal syntax. and the meaning of the expression can be obtained by analyzing the syntactic structure. For example $2x+1=23$, depending on context, may be read as an equation, stating that if you take the double of $x$ and add $1$, it should be the same as $23$. Some of the rules are:

```
equation -> expression "=" expression
expression -> expression "+" expression
expression -> number

```

The structure of programming languages is the same. Programming languages are semantically specialized in expressing computations to be performed, rather than expressing problems to be solved, proof of theorems or friendly relations between animal. But that is the main difference.

Representations used in syntax are usually strings of characters, or of sounds for spoken languages. Semantics usually belong to abstract domain, or possibly to reality, but still abstracted in our thought processes, or to the behavioral domain of devices. Communication entails encoding the information/idea into syntax, which is transmitted and decoded by the receiver. The result in then interpreted in whatever way by the receiver.

So what we see of the language is mostly syntax and its structure. The example above are only one of the most common way to define syntactic strings and their structural organization. There are others. For a given language, some strings can be assigned a structure, and are said to belong to the language, while others do not.

The same is true for words. Some sequences of letters (or sound) are legitimate words, while other are not.

*Formal languages are just syntax without semantics. They define with a set of rule what sequences can be constructed, using the basic elements of an alphabet. What the rules are can be very variable, sometimes complex. But formal languages are used for many mathematical purposes beyond linguistic communication, whether for natural of for programming languages. The set of rules that define the strings in a language is called a grammar. But there are many other way to define languages.*

In practice, a language is structured in two levels. The lexical level defines words constructed from an alphabet of characters. The syntactic level defines sentences, or programs constructed from an alphabet of words (or more precisely of word families, so that it remain a finite alphabet). This is necessarily somewhat simplified.

The structure of words is fairly simple in most language (programming or natural) so that they are usually defined with what is usually considered the simplest kind of formal language: the regular languages. They can be defined with regular expressions (regexp), and are fairly easily identified with programmed devices called finite state automata. In the cases of programming languages, examples of a word are an identifier, an integer, string, a real number, a reserved word such as `if` or `repeat`, a punctuation symbol or an open parenthesis. Examples of word families are identifier, string, integer.

The syntactic level is usually defined by a slightly more complex type of formal language: the context-free languages, using the words as alphabet. The rules we have seen above are context-free rules for natural language. In the case of programming languages rules can be:

```
statement -> assignment
statement -> loop
loop ->  "while" expression "do" statement
assignment -> "identifier" "=" expression
expression -> "identifier"
expression -> "integer"
expression -> expression "operator" expression

```

With such rules you can write:

`while aaa /= bbb do aaa = aaa + bbb / 6` which is a statement.

And the way it was produced can be represented by a tree structure called a parse tree or syntax tree (not complete here):

```
                          statement
                              |
            _______________  loop _______________
           /      /                 \            \
      "while" expression           "do"       statement
       __________|_________                       |
      /          |         \                  assignment
 expression "operator" expression          _______|_______
     |           |          |             /       |       \
"identifier"   "/="   "identifier" "identifier"  "="   expression
     |                      |            |                 |
    aaa                    bbb          aaa             ... ...

```

The names appearing on the left of a rule are called non-terminals, while the words are called also terminals, as they are in the alphabet for the language (above the lexical level). Non-terminal represent the different syntactic structures, that can be used to compose a program.

Such rules are called context-free, because a non-terminal can be replaced arbitrarily using any of the corresponding rules, independently of the context in which it appears. The set of rules defining the language is called a context-free grammar.

Actually there are restrictions on that, when identifiers have to be first declared, or when an expression must satisfy type restrictions. But such restriction may be considered as semantical, rather than syntactical. Actually some professionals place them in what they call *static semantics*.

Given any sentence, any program, the meaning of that sentence is extracted by analyzing the structure given by the parse tree for this sentence. Hence it is very important to develop algorithms, called parsers, that can recover the tree structure corresponding to a program, when given the program.

The parser is preceded by the lexical analyzer that recognize words, and determine the family they belong to. Then the sequence of words, or lexical elements, is given to the parser that retrieves the underlying tree structure. From this structure the compiler can then determine how to generate code, which his the semantic part of the program processing on the compiler side.

The parser of a compiler can actually build a data structure corresponding to the parse-tree and pass it to the later stages of the compiling process, but it does not have to. Running the parsing algorithm amount to developing a computational strategy to explore the syntax-tree that is implicit in the program text. This syntax/parse tree may or may not be explicited in the process, depending on compilation strategy (number of stages). What is necessary though is that there is ultimately at least one bottom-up exploration of the parse-tree, whether explicited or left implicit in the computation structure.

The reason for that, intuitively, is that a standard formal way to define semantics associated to a syntactic tree structure is by means of what is called a homomorphism. Do not fear the big word. The idea is just to consider the the meaning of the whole is constructed from the meaning of the parts, on the basis of the operator that connects them

For example, the sentence `the dog bites the cat` can be analyzed with the rule `sentence -> subject verb complement`. Knowing the meaning of the 3 subtrees `subject`, `verb`, and `complement`, the rule that composes them tells us that the subject is doing the action, and that the cat is the one who is bitten.

This is only an intuitive explanation, but it can be formalized. Semantics is constructed upward from the constituents. But this hides a lot of complexity.

The internal working of a compiler can be decomposed into several stages. The actual compiler may works stage by stages, using intermediate representations. It may also merge some stages. This depend on the technology used and on the complexity of the compiling the language at hand.
> 10 votes

# Answer
There are significant differences. Chief among them, I would say, is that parsing real programming languages is all about handling syntax errors. With a formal language you'd just say "well it's not in the language", but a compiler that says that is not very useful - it should tell you what's wrong, and if it was a small error, ideally keep parsing so it can report more errors. A lot of research (and implementation effort) goes into that. So really you don't even care that much about the true/false result, you just want to analyse the structure of the input. Formal languages are used as a tool there, and there's a lot of overlap, but you're really solving a different problem.

Also, in most languages it has been chosen to not enforce certain things in the *grammar*, for example the example you mentioned, "a variable cannot appear if it hadn't been declared". That's typically a thing that would be completely ignored by the parser, and then caught in a separate analysis (semantic analysis) that looks at that sort of thing and isn't affected by considerations such as context-freeness. But not always - for example to parse C, the lexer hack is often used, and C++ is a famous example of a language that can not be parsed without simultaneously doing some serious semantic analysis (actually parsing C++ is undecidable, because templates are Turing complete). In simpler languages it tends to be split though, it's easier that way.
> 2 votes

# Answer
A formal language is a set of words - where a word is a string of symbols from some alphabet.

This means that your coupling of the production rules and the formal language is too strong. It's not correct that the formal language is the production rules. Rather the production rules define the formal language. The formal language is the words that can be produced by the production rule. (This requires that the formal language is of the sort that can be defined by production rules, e.g. regular languages can be defined by a context free grammar)

So the regular language corresponding to the expression `(a|b)*c*d` is defined by the production rules;

```
S->ACd
A->
A->aA
A->bA
C->
C->cC

```

The words that these production rules generate from the starting symbol S is precisily those strings that the regular expression accepts.
> 1 votes

# Answer
There is another relationship between regular expressions and programming languages which is to do with semantics. The basic control constructs of an imperative language are sequential composition (do A and then B), choice (do A or B), and repetition (do A again and again).

The same three ways of combining behaviours are found in regular expressions. Throw in subroutine calls and you have an analogy to EBNF.

So there is a lot of similarity between the algebra of regular expressions and the algebra of commands. This is explored in detail by Dijkstra in "The Unification of Three Calculi". It is also the basis of Milner's CCS, which provides an answer to the question: what if we add parallelism?
> 0 votes

---
Tags: formal-languages, programming-languages, regular-expressions
---


# Question
Title: What is the runtime of Mergesort if we switch to Insertion Sort at logarithmic depth?
> Consider the Mergesort algorithm on inputs of size $n = 2^k$. Normally, this algorithm would have a recursion depth of $k$. Suppose that we modify the algorithm so that after $k/2$ levels of recursion, it switches over to insertion sort. What is the running time of this modified algorithm?

I know that MergeSort has worst-case runtime of $O(n \log n)$ and Insertion Sort has worst-case runtime of $O(n^2)$, but I'm not sure how these bounds will be affected within the problem above.

# Answer
> 3 votes
You know that MergeSort has a complexity of $O(n\log n)$. Why? We can write a recurrence for the running time of MergeSort: $$ T(n) = 2T(n/2) + Cn, \quad T(1) = D. $$ (Assume for simplicity that $n$ is a power of 2.) The solution is $T(n) = O(n\log n)$. Why? Since we can write $$ T(n) = 2T(n/2) + Cn = 4T(n/4) + Cn + Cn = 8T(n/8) + Cn + Cn + Cn = \cdots = (\log n)Cn + Dn. $$ That is, at each internal level the total complexity is $Cn$, there are $\log n$ levels, and at the bottom the complexity is $Dn$. It is instructive to rewrite it in terms of $n = 2^k$: $$ T(2^k) = 2^1T(2^{k-1}) + C2^k = 2^2T(2^{k-2}) + C2^k + C2^k = \cdots. $$ In your case, you want to stop the recursion at depth $k/2$, and instead of expanding $2^{k/2}T(2^{k/2})$ using the recursion, apply the $En^2$ insertion sort algorithm. What would you get? (that's a question for you)

---
Tags: algorithms, algorithm-analysis, runtime-analysis, sorting
---


# Question
Title: Finding bridge edges more efficiently than Tarjan's algorithm
I have to find a bridge edge in a graph but have to find it efficient time complexity.

Is there an algorithm that is better than Tarjan's Bridge-finding algorithm?

# Answer
Schmidt \[1\] gives another algorithm based on chain decompositions (see the Introduction of \[1\] for even more algorithms). The algorithm runs in linear time, just like Tarjan's algorithm. Asymptotically, there is no faster algorithm for the problem, since reading the input already takes linear time. If you are interested in finding bridges *in practice*, it is best you experiment with both Tarjan's algorithm and the one in \[1\] with your specific data.

If you want a sublinear algorithm (i.e. faster than Tarjan's or the one in \[1\]), you must not read the whole input.

---

\[1\] Schmidt, Jens M. "A simple test on 2-vertex-and 2-edge-connectivity." Information Processing Letters 113.7 (2013): 241-244.
> 2 votes

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


# Question
Title: How do we analyze Algorithms with parallelism features
As I am comparing between two algorithms, I was wondering which is the best approach to use to compare between the both. Big-O seems not the perfect metric for me, as the it's based on the worst-case, while most of cases in the area that I am working on is optimized. The second though is, I am using "Python-Maps" (and other parallelism features, but let's take just "map no python as an example" to simplify the question) to implement the first algorithm, while I don't use parallelism features in the second algorithm.

What is the approach to compare, abstractly, the both algorithms ?. Can you please give any hint ?

# Answer
> 2 votes
The conceptual/abstract model I use when developing a parallel algorithm is (loosely) Leslie Valiant's Bulk Synchronous Parallel model.

You have $P$ processors (where $P$ is typically some small number like 4, 8, 16, maybe 128, but certainly $P \ll N$). You are trying to design an algorithm where you spend most of your time computing in parallel, then you use a barrier to synchronize the processors, then do some communication between processors, synchronize again, and then go on to the next parallel computation step. It is called *bulk synchronous* because you can think of the algorithm as a series of steps where the work inside each step is completely asynchronous, but the steps happen one at a time and in order.

There are a handful of different things you need to worry about that all interact and have inescapable tradeoffs.

1. **Algorithm efficiency**. You should have a *best sequential algorithm* you are using as a baseline. Often the best sequential algorithm won't parallelize well (because of all the rest of this list) so your parallel algorithm may require substantially more work. For example: There are often clever sequential algorithms that are $O(N \log N)$ where the only realistic parallel algorithms are $O(N^2)$. Alpha-Beta pruning tree search algorithms are another case where you may need to do (significantly) more work to avoid synchronization/communication overheads.
2. **Work independence**. You need to choose an algorithm where, in each bulk step, there are approximately $O(N)$ (or more) *independent* pieces of work to do.
3. **Load imbalance**. During each step of the algorithm you want to break the work into $P$ nearly-equal chunks. If the chunks are unequal then each bulk synchronous step will take the amount of time for the largest chunk and many of your processors will spend a significant portion of their time idle. Examples of load imbalance problems happen with:
    * divide and conquer algorithms (the first step has to happen on one processor, then you get two (perhaps unequal chunks) so the second step happens on two processors. It takes $O(\log P)$ steps to get all $P$ processors working, and the amount of work they are doing may not be similar, let alone the same.)
    * hashing algorithms (it depends on whether your hash function is distributing the data evenly among hash buckets or whether there is some bias. The bias ends up as load imbalance.)
    * sparse graphs and sparse matrices. (Similar to the hashing problem. It may be easy to divide up the number of nodes in your graph evenly, but the number of edges per node determines the amount of work so two chunks with similar numbers of nodes may have very different amounts of work involved.)
4. **Synchronization overhead**. Synchronization is "pure overhead". It is added cost for parallelization that simply isn't required in the sequential algorithm.
5. **Data communication overhead**. This one is quite tricky because it interacts with a problem (cache locality) that is quite difficult in the sequential case as well.
6. **Reductions**. Often some of your work looks unavoidably sequential, but involves *associative* operators that can be mostly parallelized (with some cleverness, and assuming that your hardware supports it.) Similarly you sometimes have operators that are (a) associative, (b) commutative and (c) applied sparsely, in which case it may be possible to parallelize a chunk of code using fine-grained mutual-exclusion (locks).
7. **SIMD hardware limitations**. The Bulk Synchronous Parallel model is single-*program*-multiple-data (SPMD). In each chunk of work between barrier synchronizations each processor has something like $O(N/P)$ work to do, and that work may require a substantial amount of data-dependent branching. But most modern parallel hardware exposes a substantial fraction of its parallelism only with single-*instruction*-multiple-data (SIMD) short-vector units. This means that you have to go beyond the *work* independence in step (2) above. You have to find work to do that is not just *independent* but where there are few (hopefully *none*) data-dependent branches for each chunk of work.
8. **Accelerator data marshalling**. This is starting to get better, but for the moment many parallel accelerators (GPGPUs) require you to move data back and forth between the accelerator and the processor at each barrier synchronization point. This means that you need to find more work independence to make the cost of using the accelerator break even.

That's a lot to keep in mind, but you can often think about it a little more simply.

1. Rewrite the sequential code using the *least* clever algorithm you can think of.
2. Look for the *loop nest* where you are spending most of your time (use a profiler.)
3. Choose the outer-most loop where the iterations are independent of one another.
4. Turn *that loop* into a parallel-for (using whatever method your programming language and/or libraries provide.)
5. Hope that everything else works out.

---
Tags: algorithms, algorithm-analysis, parallel-computing
---


# Question
Title: Understanding A* Search on Tropical Island
I am working on an online course on AI and I am now working to understand A\* better.

Basically, right now I am working on a problem where: we live on a tropical island and we're trying to navigate between areas, starting from `d` and heading towards `q`.

I am trying to find:

* the cost used between `d` and `q` using `A*` search
* how many 'nodes' that were opened during the search
* Whether this route is actually optimal
* How many cycles where detected
* If the person was good at swimming, and what could we change the value of `q-r` (that's the river path) from 240 to what, to lead to the optimal path.

(see far below for my ideas to these problems)

Below is the costs (when travelling to nodes)

Below is the distance to the target

**Attempt at Solving**

1. The optimal path from `d` to `q` is d-\>e-\>f-\>g-\>l-\>n-\>q with which would give me a cost of 50+70+20+60+45+20 = 265. This looks like it is the optimal path to get from d to q as well.
2. Also, we should be expanding 1+2+2+3+1+1=10 nodes to find this path with A\*.
3. I tried a bunch of other different paths and it looks like this one gives us the least cost. So YES! this is true.
4. Err, this one I don't actually know how to do. Is there a cycle detector in A\*?
5. If the cost of q-r was 0, then that would be the best route indeed. (This seems pretty obvious).

---

Can any of you AI gurus/graph theorists help me confirm whether I am understanding this properly?

*Thanks a ton in advance!*

# Answer
> 1 votes
I can respond to your question as follows:

* the cost used between d and q using A\* search

This can be done by applying the algorithm on paper.

* how many 'nodes' that were opened during the search

This also needs to be done on paper to see

* Whether this route is actually optimal

If you really want to know if a route is optimal without having guarantee correctness of the algorithm or your application, then you will need to check every possible route and compared with what you have

* How many cycles where detected

Apply the algorithm on paper

* If the person was good at swimming, and what could we change the value of q-r (that's the river path) from 240 to what, to lead to the optimal path.

There are other edges that cross the river. You have to look at that as well.

In your particular map, the use of distance might help you. I don't know I haven't exhaustively searched all the paths and I don't think anybody want to do brute force search on it. In general, the distance (Euclidean) I suppose will not help you when the cost is not proportional to it.

In general, without having a heuristic cost function that makes use of distance while still guarantees that the real cost is more than the heuristic cost, you will not have the optimal route.

However, it is possible that if you have a limit on the cost which is if you have a notion of a good enough path, then A\* will still help you, the heuristic also adds in value. You check this 'good enough value' after you reached the destination node. Because some heuristic is better than no heuristic, the better the heuristic, the better path you will find.

In this map of yours, since you have river crossing costs that are not intuitively proportional to distance, I am not sure you should apply A\* unless you construct a good heuristic cost function that I don't know. So it seems that there is little help using D if you want to expand that map.

---
Tags: graphs, artificial-intelligence, search-algorithms
---


# Question
Title: Terminologies of "Process calculus" and "Process algebra"
In the literature, the terms of "process calculus" and "process algebra" are often interchangeable. Meanwhile, it confused me.

**My questions are:**

> 1. Are there formal, standard, and widely-accepted definitions of "calculus" and "algebra"?
> 2. What are the significant distinctions (maybe informally) between "calculus" and "algebra"?
> 3. What are the features that make a theory kind of "calculus" or "algebra"?

# Answer
> 5 votes
To my knowledge the two terms do not have a formal established definition and are often used interchangeably.

There are different characteristics associated to each however, as @Dave already pointed out. I'll try to elaborate a bit further.

In both cases you start by introducing the syntax of a language for expressing (concurrent) systems. This introduces what the basic "combinators" (constructs) for assembling systems together are. The real distinction comes when you start to specify their semantics.

The *process calculi* approach is calculational in the sense that you focus on the reduction semantics, i.e. what are the steps a system can perform when executing it. This operational view helps a lot when using these languages for simulation for example. The chief notion in this case is the concept of "observation": what can you observe about the evolution of a system? Using this idea one can determine when two systems are equivalent. The technical word for this concept is *bisimilarity*. Then, in some situations, you find that processes which are bisimilar can be interchanged in any context without altering the behaviour of the system overall. This is the approach Milner and his collaborators took in defining many calculi such as CCS and π-calculus.

The *algebraic* view instead avoids specifying a model for the semantics directly and opts for a more axiomatic view: a series of laws (equations between expressions of the language) establish which processes have the same behaviours. The focus is in proving equivalences and enriching the calculus with different combinators. Even the "execution" of a system is expressed as an equivalence between a system and a (simpler expression used as a) specification (see the step laws for CSP for instance). The equivalence between two systems is established by using the laws instead of referring to a particular model for their behaviour. The chief concept in this context is the one of *refinement*. This approach is the basis of the work of Hoare and his collaborators in defining CSP and its variants.

That said, most of the languages mentioned have being studied with a mixture of these approaches so the distinction is more about the specific method used in a specific construction rather than about a language as a whole.

# Answer
> 4 votes
The distinction is not so clear. Nevertheless, here is an attempt to provide an alternative answer to your question.

A calculus involves calculation. Thus a process calculus will involve a notion of reduction. Examples include the $\pi$-calculus and CCS (and others from the Milner School).

Algebra involves equations. A a process algebra will be phrased in terms of equations. Examples include process calculus ACP (and others from the Amsterdam School).

---
Tags: terminology, process-algebras, mathematical-foundations
---


# Question
Title: If both the concatenation of two languages and the second "half" are regular, is the first too?
> Given that $L\_2$ is regular and infinite and $L\_1 \cdot L\_2$ is regular, then $L\_1$ is also regular.

I need some help on getting started on proving this is the case.

My intuition is that if $L\_1 \cdot L\_2$ is regular there exists a DFA for it, in which case you can just remove the states that correspond to the $L\_2$ part of the DFA and you are left with a DFA that recognizes $L\_1$.

# Answer
> 11 votes
Suppose that $L\_2 = \Sigma^\*$ and $L\_1$ includes the empty string. Then $L\_1 \cdot L\_2 = \Sigma^\*$, yet $L\_1$ doesn't even have to be computable.

# Answer
> 7 votes
Let $L\_1 = a^p$ such that $p$ is prime, let $L\_2 = a^\*$ then $L\_2$ and $L\_1 \cdot L\_2$ are both regular, but $L\_1$ is not

---
Tags: formal-languages, regular-languages, closure-properties
---


# Question
Title: How to order objects to minimize non-adjacency cost
I have an array of $N$ objects, each appearing exactly once. I also have a list of $M$ pairs of the objects. Each pair has a "non-adjacency cost" that must be paid if the two objects are not adjacent in the array. Is there an algorithm that orders the object array to minimize the total cost?

The costs will change from time to time, so I'd like to be able to apply the algorithm iteratively. It doesn't have to produce an optimal solution, but should converge to one if the costs remain constant over enough iterations. Practically, I will have somewhere around 1,000,000 objects, and each object will be a member of about 5 pairs.

Here is what I have tried:

1. Combine pairs that refer to the same two objects by summing their cost.
2. Each iteration, find a random pair whose cost changed. If no costs changed, take a random pair.
3. For each of the two objects from the pair as `obj1`:
    1. Set `obj2` equal to the other object.
    2. For each of the two objects touching `obj1` as `obj3`:
        1. Calculate the cost difference of swapping `obj2` and `obj3`.
        2. If it is less than zero, apply the swap and return.

I like my algorithm but it's pretty simple and I feel like it would fall on its face in select circumstances. Is there a better algorithm or some terminology I can google for?

# Answer
Your problem is just the problem of finding a maximum-weight Hamiltonian path in a weighted graph.

A candidate way of ordering objects in your array corresponds to a Hamiltonian path. The total weight of that Hamiltonian path (the sum of the weights on the edges in the path) is exactly the sum of the "non-adjacency costs" you *don't* pay. Minimizing the sum of the "non-adjacency costs" you *do* pay is equivalent to maximizing the sum of the "non-adjacency costs" you *don't* pay.

Unfortunately, this problem is NP-hard, so you should start looking for approximation algorithms or heuristics or special cases. For instance, there may be some special kinds of graphs (say, bounded treewidth or bounded clique-width) for which this problem might be solvable in polynomial time.

See also https://en.wikipedia.org/wiki/Hamiltonian\_path\_problem and https://en.wikipedia.org/wiki/Longest\_path\_problem.

You might also try looking at simulated annealing, which is often a good candidate approach to explore for these kinds of problems, and is in some ways a generalization of the sort of algorithm that you mention in your question.
> 1 votes

---
Tags: algorithms, optimization, sorting
---


# Question
Title: Finding out if languages involving counting and modulo operations are regular
I am having trouble with the regularity of the two following languages:

i) $\\{0^{n}1^{m}|n,m\>0,n-m=0\\,mod\\,3\\}$

ii) $\\{0^{n}1^{m}|n,m\>0,n+m=0\\,mod\\,3\\}$

To clarify this is stating that the (#(0's) - #(1's)) mod 3 = 0.

I know how to prove that the first language is regular *without* the n,m \> 0 restriction but with it I am inclined to think that the language **is not** regular because we'd need to make sure there is at least one 1 and 0 b and in doing so would also have to "remember" the previous numbers of 0's and/or 1's. Which is not possible with a DFA.

My logic is similar with the second statement.

Is my logic right?

# Answer
> 3 votes
This is essentially @Yuval's hint, expressed in a slightly different way. You've said that you can prove $$ L\_u = \\{0^n1^m\mid n, m \ge 0, n - m \equiv 0\pmod{3}\\} $$ is regular. If so, then its intersection with the regular language denoted by $00^\*11^\*$ will be regular. Show that this intersection is equal to $$ L\_r = \\{0^n1^m\mid n, m \> 0, n - m \equiv 0\pmod{3}\\} $$ and you're done. Notice that a similar construction shows that $$ \\{0^n1^m\mid n \> k, m \> j, n - m \equiv 0\pmod{3}\\} $$ is also regular for any $k, j \> 0$.

The same idea can be used on your second question.

# Answer
> 1 votes
Hint: $$\\{0^n1^m | n,m\>0,n\equiv m\pmod{3}\\} = \\{0^n1^m | n\equiv m\pmod{3}\\} \setminus (0^\* + 1^\*).$$

Alternatively, notice that remembering whether we have seen 0 or 1 can be done using a finite amount of memory.

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


title: Count points in 2-d range

text:
# Question
Title: Count points in 2-d range
You are given an array $A$ of size N $(N\leq 1\\,000\\,000)$ containing all integers $1..N$ exactly once. You are required to answer query in $O(\log^2 N )$ and to preprocess in $O(N\log^2N)$:

> How many elements are there between indexes S and E, that are less than X? $( |L| : \forall l \in L \leftrightarrow A\[l\] \< X \bigwedge S\leq l \leq E )$

$X, S, E$ will vary from query to query, and there will be at most $1\\,000\\,000$ queries.

I found a lot of algorithms based on kd-trees, but they have complexity linear in the size of the output. Are there any other options, maybe using the property that X and Y coordinates are unique?

# Answer
> 4 votes
First, notice that it is enough to compute how many elements in $a\_1,\ldots,a\_E$ are less than $X$. (Why?)

Second, assume for simplicity that $N$ is a power of 2. We partition $\\{1,\ldots,N\\}$ into intervals in $\log N$ ways: as a single interval of length $N$, two intervals of length $N/2$, four intervals of length $N/4$, and so on. We sort each of these. This takes time $O(N\log^2 N)$. (Why?)

Third, given $E$ and $X$, write $a\_1,\ldots,a\_E$ as a sum of $O(\log N)$ intervals of the kind we sorted above (use the binary expansion of $E-1$). Find the correct count for each of them in time $O(\log N)$ by searching for $X$ in the sorted interval, and compute the sum.

# Answer
> 1 votes
As mentioned by Yuval, you just need to count how many elements in $a\_1,\ldots,a\_E$ are less than $X$.

I would recommend you to use persistent binary search trees, some lecture notes here and here. Briefly, you could build a binary search tree of $a\_1,\ldots,a\_N$ by inserting them to a empty tree one by one. By remember some information when you build the tree, you would be able to access the binary search tree of $a\_1,\ldots,a\_k$ for any $k$. This can be done in $O(N\log N)$ time.

Later when you find the root of the binary search tree of $a\_1,\ldots,a\_E$, which is stored in an array so accessing costs $O(1)$ time. Then you count how many nodes in the tree are less than $X$, which cost $O(\log N)$ time.

So you get $O(\log N)$ time per query and $O(N \log N)$ preprocess time! And it's also easy to implement.

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


# Question
Title: Elements in a less than a value in a subarray
Let A be an fixed array of size n. Q(i,j,k) is number of elements from A\[i\] to A\[j\] which are less than k.

Currently I am using segment tree with each node containing sorted array of leaf elements. This answers the query in O((log n)^2) with O(n\*log n) space and per-processing.

Is there a way to answer this in O(log n) while keeping the per-processing and space complexity same.

# Answer
> 1 votes
This is essentially the 2D orthogonal range counting problem from computational geometry, which has attracted a lot of attention over the years. Fractional cascading definitely could be applied to reduce the query time to logarithmic while preserving the other big-O bounds. In a nutshell, the idea is to make auxiliary data structures that relate the positions of elements in each parent array to positions in the child array, so that, given the results of a search in the parent, searching the child for the same key is constant-time.

# Answer
> 0 votes
I would recommend you to use persistent binary search trees, some lecture notes here and here. Briefly, you could build a binary search tree of $a\_1,\ldots,a\_N$ by inserting them to a empty tree one by one. By remember some information when you build the tree, you would be able to access the binary search tree of $a\_1,\ldots,a\_k$ for any $k$. This can be done in $O(N\log N)$ time.

Later when you find the root of the binary search tree of $a\_1,\ldots,a\_E$, which is stored in an array so accessing costs $O(1)$ time. Then you count how many nodes in the tree are less than $X$, which cost $O(\log N)$ time.

So you get $O(\log N)$ time per query and $O(N \log N)$ preprocess time! And it's also easy to implement.

---
Tags: algorithms, data-structures, binary-trees, search-trees
---


title: Dynamic Programming Approach

text:
# Question
Title: Dynamic Programming Approach
when we are trying to solve a problem with dynamic programming. we have to follow some general steps

1. characterize the solution structure
2. Recursively define optimal solution
3. compute the value from bottom up fashion

Can anyone briefly explain the steps for this problem scenario. we need a 444 meter rope. but we have only small pieces of ropes. then we have to find out the minimum number of pieces of rope needs to construct that large rope.

**Length**----\>**Quantity**

* 50m---\>10
* 45m---\>12
* 30m---\>3
* 8m----\>12
* 3m----\>2
* 2m----\>2

# Answer
The Wikipedia page to the Knapsack Problem has a nice explanation of a dynamic programming algorithm for it:

http://en.wikipedia.org/wiki/Knapsack\_problem

The knapsack problem is *very* similar to your problem - just define length of rope to be equal to their "weight" and use a uniform cost for all of them.
> 1 votes

---
Tags: algorithms, optimization, dynamic-programming
---


# Question
Title: Machine epsilon vs least positive number
What is the difference between machine epsilon and least positive number in floating point representation?

If I try to show the floating point number on a number line .Is the gap between exact 0 and the first positive (number which floating point can represent) ,and the gap between two successive numbers, different?

which one is generally smaller? and on which factor these two values depends(mantisa or exponent)?

# Answer
> 3 votes
*Machine epsilon* is the *relative* error (the error independent of what exponent you are currently using.)

It tells you the maximum error in the *mantissa* after a given operation. For example take `sqrt(2.0)` and `sqrt(2048.0) = sqrt(2.0)*32.0`. In IEEE 754 double precision (53-bit mantissa) the maximum error in the mantissa for this result will be $2^{-53} \approx 1.11\times10^{-16}$.

Put another way, to quote Wikipedia, the machine epsilon is

> the maximum spacing between a normalised floating point number, $x$, and an adjacent normalised number is $2 \epsilon \times |x|$.

The *least positive number* in a floating point system *includes the exponent*. In double precision IEEE 754 the smallest *normalized* number is $2^{-1022} \approx 2.225 \times 10^{-308}$. The smallest *denormalized* number is $2^{-52}\times 2^{-1022}=2^{-1074}\approx 4.941\times 10^{-324}$.

---
Tags: floating-point
---


# Question
Title: ANN architectures that perform faster/efficient prediction over time?
ANN when compared to biological neural systems have this common concept of reducing error in prediction over time (training) and becoming more good at predicting correctly. But there is one behavior of biological neural system where the prediction do become good over time but it also becomes fast and uses less energy, it seems like the system is able to do the prediction based on few input rather than requiring all the inputs. For example when you start to learn to read, you have to look at each character and then then brain predicts what the word is but over a period of time you don't even look at the whole word and the prediction becomes more fast and efficient by using just a small portion of the input.

Are there any ANN architectures with their corresponding learning methods that have this aspect of becoming more efficient in prediction along with more correct prediction?.

# Answer
> 2 votes
The machine learning term for this is *dimensionality reduction* (see here for a survey), which is used in a more general context than just neural networks.

Dimensionality reduction can be both supervised and unsupervised. An example for unsupervised dim. reduction is PCA, in which a projection onto a lower-dimension space is found, in a way that preserves distances / structure as much as possible. In the case of supervised dimensionality reduction, the labels of the training set are also used in order to reduce the dimension. This is, however, a more advanced research area. This paper and references therein would be a good starting point.

Hope this helps.

---
Tags: artificial-intelligence, neural-networks
---


title: Data structure for range-value-sum

text:
# Question
Title: Data structure for range-value-sum
I have to be able to perform insert, delete, range-value-sum, and range-2-max-values with a data structure.

Range-value-sum(xl,xr): with a range \[xl,xr\] (for a range query), it reports the sum of values of all elements whose keys are in the range of \[xl,xr\], where xl and xr are real numbers and xl ≤ xr

Range-2-max values reports the largest value and the second largest.

**Approach**: This is my take on it so far, to use a single balanced binary search tree that is sorted by its keys. The augmented fields would be the value (of the key-value pair), subtree min and max keys, sum of the subtree, and the 1st and 2nd maximum of its subtree. The sum and 1st and 2nd max are of the values, not keys since the values don't have to be ordered in this case. For range-value-sum the recursion is to pretty much keep track of the 1st and 2nd max values that are within the range. Finally, you return the top 2 in each recursive step, excluding unnecessary values.

Thoughts? Ways to make more specific? For the time analysis, I'm relying O(logn) due to it being a binary search tree and its height.

# Answer
use Binary Index tree, segment tree for the range-value-sum it is the easiest way to do so and for range-2-max use a linear search to keep track of two maximums.For range-2-max you can also use min-heap(this can help you to find range-N-max).

BinaryIndexTree(fenwick tree) has many online tutorials read them and see this visualizer for understanding it. http://visualgo.net/bit.html

Hope this clears or solve your problem.
> 0 votes

---
Tags: data-structures, runtime-analysis, search-trees, dictionaries
---


# Question
Title: How can I translate this quantified logical expression into english
I was reading chapter-1 The Foundations: Logic and Proofs from this book.

The chapter gives example of translating English sentence : "There is a woman who has taken a flight on every airline in the world." as follows:

* Introducing variables : w for women, f for flight, a for airline
* Let P(w,f) : “w has taken f”
* Let Q(f,a) : “f is a flight on a.”
* Translation : ∃w∀a∃f (P(w,f ) ∧ Q(f,a))

I did understood above. Next it gives example of translating negation of above sentence : "There does not exist a woman who has taken a flight on every airline in the world.", which it solved as follows:

```
¬∃w∀a∃f (P(w,f ) ∧ Q(f,a)) ≡ ∀w¬∀a∃f (P(w, f ) ∧ Q(f, a))

                            ≡ ∀w∃a¬∃f (P(w, f ) ∧ Q(f, a))

                            ≡ ∀w∃a∀f¬(P (w, f ) ∧ Q(f, a))

                            ≡ ∀w∃a∀f (¬P(w, f )∨¬Q(f, a))

```

I thought their can be straight approach for this translation instead of going through negation. Anyways though my problem is I am unable to interpret the final translation ∀w∃a∀f (¬P(w, f )∨¬Q(f, a)) in plain English.

"Every woman has either not taken all flights or out of all the flight she has taken are not there on some airline." Is this correct? But if yess, it still does not make me much sense. Anyone?

# Answer
The negation is that every woman has an airline that she has never flown with. This is equivalent to saying that, for every woman there's an airline with the following property:

* for every flight in the whole world, either the woman was not on that flight (regardless of what airline operated it) or the flight was not operated by that airline (regardless of whether the woman was on it or not).

That is, there was no flight by the airline in question that the woman was on.

This is not quite the same as what you have.
> 1 votes

---
Tags: logic
---


title: Recipe book for SAT encodings?

text:
# Question
Title: Recipe book for SAT encodings?
SAT solvers are getting more and more efficient in solving large instances and are being used as back-ends in various contexts. Every time one wants to use them to solve a problem in a specific domain, he/she has to come up with an ad-hoc encoding that not only has the right set of solutions but also puts the constraints (even redundant) in a form that helps the heuristics of solvers in finding a solution faster.

Many such encodings seem to me would be very common, for example: asserting that a finite set of nodes is linked as a tree, or as a DAG, or a list is sorted...

Is there a repository/recipe book of common encodings for common problems with optimised solutions?

# Answer
I read a survey paper a few years ago that seems relevant, "Successful SAT Encoding Techniques" by Magnus Björk.

Abstract:

> This article identifies good practices for SAT encodings by analysing interviews with a number of well known SAT experts. The purpose is both to determine the confidence in different encoding strategies by analysing whether there is consensus among the experts or not, as well as bringing out hidden knowledge to SAT users.
>
> There is consensus that encoding techniques usually have a dramatic impact on the efficiency of the SAT solver, that it often takes much work to find a good encoding, and that the size of an enconding is only very loosely related to the hardness of finding a solution. Topics where the interviewees disagree include the feasibility of including arithmetics in SAT problems and whether to formulate problems as clauses or circuits.
>
> The article describes a number of strategies that are good in different situations, such as different ways to represent numbers and how to use incrementality.
> 10 votes

# Answer
not exactly a direct answer but another increasingly closely related angle: some of this is covered by a relatively new area of research known as SMT, Satisfiability Modulo Theories. the basic idea is to combine problem encodings (eg say integer arithmetic, graphs, etc) into the SAT solver but also use/ leverage the extra knowledge that comes from this coupling to build more advanced solution algorithms. heres a survey. as pointed out they can be much more efficient than combining an ad-hoc encoding mechanism with standard SAT solvers.

* Satisfiability Modulo Theories: An Appetizer / Leonardo de Moura and Nikolaj Bjørner

> Satisfiability Modulo Theories (SMT) is about checking the satisfiability of logical formulas over one or more theories. The problem draws on a combination of some of the most fundamental areas in computer science. It combines the problem of Boolean satisfiability with domains, such as, those studied in convex optimization and term manipulating symbolic systems. It also draws on the most prolific problems in the past century of symbolic logic: the decision problem, completeness and incompleteness of logical theories, and finally complexity theory. The problem of modularly combining special purpose algorithms for each domain is as deep and intriguing as finding new algorithms that work particularly well in the context of a combination. SMT also enjoys a very useful role in software engineering. Modern software, hardware analysis and model-based tools are increasingly complex and multi-faceted software systems. However, at their core is invariably a component using symbolic logic for describing states and transformations between them. A well tuned SMT solver that takes into account the state-of-the-art breakthroughs usually scales orders of magnitude beyond custom ad-hoc solvers.
> 5 votes

# Answer
It is always a good idea to first check out the Handbook of Satisfiability \[1\] (I guess it's not freely available, sorry). Here, Chapter 2 is titled "CNF Encodings". At the very least, the book provides literature references on the state of the art on the time of the writing, and you can expand your search through them.

In addition, here and here are two recent slides on SAT preprocessing. The slides give a concise overview of preprocessing techniques, and also further references. The idea is that instead of trying to "manually" model the problem in an efficient way, you just model it in the easiest way, press go, and a software gives you an efficient encoding.

---

\[1\] Biere, Armin, Marijn Heule, and Hans van Maaren, eds. Handbook of satisfiability. Vol. 185. IOS Press, 2009.
> 5 votes

---
Tags: reference-request, satisfiability, sat-solvers
---


title: Order of a pseudo code

text:
# Question
Title: Order of a pseudo code
I am trying to find order of an bellow algorithm but I have no idea about, the problem like below

we have an array of $n$ element name $T\[1...N\]$ and we have that $0\leq T\[i\] \leq i$ and $T\[i\] \in \mathbb{Z}$ then if we have that $\sum\_{i=1}^{n}T\[i\] = s$ what will be the order of following pseudo code

```
K := 1
for i = 1 to n do
    for j = 1 to T[i] do
        K := K + T[i]

```

I should prove it, but I just don't know what should I prove. is it $O(s)$ or $O(n+s)$ or $O(n)$ ? between these three one I need best guess. I just need some suggest to solve this. thanks

First I was thinking that it's $O(s)$ but if $T\[i\] = 0$ for $1 \leq i \leq n$ then then it should be $O(n)$. after that one of my friend said in fact $s = \frac{n (n + 1)}{2}$ so when we say that it's $O(s)$ in fact it's $O(n^2)$ so that the better answer is $O(s)$ because for some examples $O(n)$ is wrong, for example when $T\[i\] = i$ for all $i$. I think $O(s)$ should be right answer.

# Answer
> 2 votes
First note that $s \le \frac{n(n-1)}2$, equality need not necessarily hold.

Your observations are all correct:

* The addition (and the head of the inner loop) is executed $O(s)$ times.
* The head of the outer loop is executed $O(n)$ times.
* Neither $s\in O(n)$ nor $n \in O(s)$ holds for all possible inputs.

In this situation, there are multiple ways to give a bound that holds for all inputs:

* You can use the fact that $s \in O(n^2)$ and give $O(n^2)$ as a bound for the algorithm,
* you can say that the runtime is in $O(\max\\{n,s\\})$, or
* you can say that the runtime is in $O(n+s)$.

Note that the latter two statements are acually equivalent (i.e. $O(\max\\{n,s\\})$ and $O(n+s)$ describe the same set of functions).

---
Tags: algorithms, algorithm-analysis, time-complexity
---


title: Triangles incident on a vertex (Graphs)

text:
# Question
Title: Triangles incident on a vertex (Graphs)
I have a project that I am doing. The specification requires specific methods on a graph class. Two of the methods requires this:

> * `numberOfTrianglesIncidentToVertex()`, calculates and returns the number of triangles incident to vertex v. The algorithm below calculates the number of triangles incident for all graph vertices (V is the set of vertices, E is the set of edges):

```
foreach v in V
  foreach pair of vertices (p, q) in AdjacencyList(v)
    if (p, q) is in E then
      add 1 to triangles[v]

```

> * `listOfTrianglesIncidentToVertex()` calculates and returns the list of triangles incident to vertex v. A triangle should be specified by its vertices.

I have no idea what a *triangle* is in regards to the vertex and graphs. Can someone give me a clear explanation?

# Answer
> 1 votes
A *triangle* is a set of three vertices `p`, `q`, `r`, from the graph where there is a graph edge between `p` and `q` (that is `q` is in `AdjacencyList(p)`), and there is a graph edge between `q` and `r` and there is a graph edge between `p` and `r`.

---
Tags: terminology, graphs
---


# Question
Title: Possible to develop a game using assembly language?
I am wondering what it takes to develop a game in assembly language. For example, what are the limitations or advantages from using assembly language in game development? Also, are there any programs/softwares to aid the development of games in assembly language?

# Answer
> 2 votes
Yes, most definitely!

Would you want to these days? No, probably not, unless you were doing it for educational purposes.

The first games on computers were coded in Assembly language, because when computers first came out there wasn't anything else to program in. The most recent example of a popular game that I know of which was written in Assembly is RollerCoaster Tycoon: http://en.wikipedia.org/wiki/RollerCoaster\_Tycoon

The are a lot of limitations of writing a game in Assembler code.For example, in assembler you are writing individual instructions to the CPU. This takes a lot of thought and a lot of time. Chances are you won't be doing it as efficiently as you could be too! A modern programming language, like C++ for example, would be far easier to code a game in these days. It allows you to think about how you want to program things in at more complex level without having to think about the very basics of how it will actually run on your computer.

Plus, different computers will have their own versions of Assembler code, so writing your game on one computer may mean it won't run on a whole other line of computers! But when you write a game in something like C++, there's a special program you run that will turn it into assembler code, specifically for what ever machine type you run it on!

To sum this up, I'd say there really is no point writing a game in assembler, unless you are doing it to learn assembler. You will get much faster and better results when making a game if you do it in a higher level language. If you want to get up and running quickly I'd say you should go for something like Java, specifically using a special IDE & library called 'Processing', take a look at it and see how easy it is to get up and going, pretty good if this is your first time programming something and want to get a hang of it:

http://www.processing.org/

# Answer
> 1 votes
I am by no means an expert on assembly language. What I do know makes me think that there would be no reason to develop a game in assembly language, especially with all of the high level languages/ software out to help. Assembly language is a very low level, almost 1s and 0s language, so you would not be making any great 3d games like that I think. Using assembly language to make a game would be extremely difficult in my opinion, and it would not be worth the effort. Have you seen how assembly language looks? It would be very hard to fit that language into the game development context.

---
Tags: programming-languages
---


# Question
Title: parameter and variable in programming languages
From Bash Reference Manual, a parameter:

> **A parameter** is an entity that stores values.
>
> It can be **a name**, a number, or one of the special characters listed below.

A variable:

> **A variable** is **a parameter** denoted by **a name**.

1. Is a variable is a parameter A, denoted by a parameter B which is also a name? How do you understand the concept of a variable?
2. since a parameter stores values, does that mean a parameter is a block in memory?
3. I never heard of the concept of "parameter" in other languages such as C, C++, Python. Do the distinct concepts of parameter and of variable exist in programming languages besides bash? What are their definitions in programming languages?

Thanks.

# Answer
> 1 votes
Bash is a shell language for interacting with the computer on the command lines. These languages often have weird features dictated by expediency, sometimes disputable. I used the multics language long ago, and it was incredibly weird to program with. I actually do not know whether there has been serious scientific study of what would constitute a proper shell language.

In the case of bash, you can write shell scripts that you store in files, and can then call from the command line. When you call them, you can pass arguments to them, and the values thus passed are stored in order in the variables \\$1 \\$2 ... and can thus be accessed from wthin the script.

So \\$1, \\$2, etc. are just variable that you can use as you see fit. But they may also be used as standard locations to store the results of some standard commands, and they are location where the arguments passed to scripts are stored. hence the name *parameter*.

But ... What's in a name?

Regarding your other questions, you should find some answers in wikipedia, or learn some.programming language. They all have a variety of mechanisms to pass information to sub-program (whatever that may be). Hence it is not possible to answer simply your questions. There are parameters and variables, but they may come in different flavors, that depend on languages. Read a bit, before asking.

---
Tags: programming-languages
---


# Question
Title: Given a pile of cards, how to program to get card combinations whose sum is closest to 21?
This is an interview question:

**Given a pile of cards, how to program to get card combinations whose sum is closest to 21?**

Example:

input:

**Array : 2, 3, 4, 5, J, K**

output:

**2, 4, 5, J**

**2, 4, 5, K**

---

I have a naive solution:

check if two cards' sum is 21;

check if three cards' sum is 21;

check if four cards' sum is 21;

check if five cards' sum is 21;(Max number of cards in blackjack)

However, this is brute force solution.

Can anyone give me a hint to get a better solution? Thanks!

# Answer
> 2 votes
You have at least two options.

If the number of cards is very small, as in your example, then you can go over all possible subsets of cards and compute their sum, taking note of the one closest to 21. Then go over all of them again and output the ones achieving the best sum. With a realistic number of cards this will be very fast.

What they might have expected you to answer is to use dynamic programming. For each sum from 2 to 21, go over all cards and see if it is achievable from an earlier sum (including 0), and if so, annotate this with all possible cards. Now find the best sum and follow the edges back to 0.

---
Tags: algorithms, combinatorics
---


# Question
Title: how to improve solution generated by greedy method for 0-1 knapsack?
I am working on 0-1 knapsack using greedy method, I have some problem in it. It's already proved that solution generated by greedy method for 0-1 knapsack is may or may not be optimal. If solution generated by greedy method is not optimal then Please tell me how i can improve solution so that solution generated is optimal.

# Answer
0/1 Knapsack is an NP-hard problem which has pseudopolynomial time algorithms. This means that if the weights are allowed to be large, then there is no hope of always finding the optimal solution, while if they are small, then there is an algorithm, in this case a dynamic programming algorithm.

From a practical point of view, real-world instances may not represent the worst case, and so there is some hope that heuristics will work in most cases, though I'm not sure there is a simple criterion for when you have achieved the optimal solution; so even if these heuristics are very good, you wouldn't be able to tell.
> 2 votes

---
Tags: optimization, np-hard
---


title: Finding recursion for runtime of code

text:
# Question
Title: Finding recursion for runtime of code
This is the first time we have to do recursive/closed form expressions WITH code in class and I really have no idea how to approach this. My course notes that the prof put up don't really help as he put up a basic example, but this one has lots of recursive calls in it.

I know that the first part len(lst)$ \leq 1$ will be linear time because of it will just return whatever in the conditional. How do I tackle the rest, and ultimately come up with the recursive $T(n)$? The question is below:

# Answer
Base cases: $T(0) = T(1) = a, T(2) = b$. How did we get these base cases? Well, from the code:

```
if len(lst) <= 1:
    return

```

This tells us that for `n < 2`, `T` doesn't depend on the input list size; hence, the function takes some constant amount of time for these input sizes.

```
if lst[0] > lst[-1]:
    ...

if len(lst) >= 3:
    ...

```

This part tells us that for input sizes between `1` and `3`, exclusive (i.e., for `2`) we do some more work than in the `n <= 1` case but not as much as in the `n >= 3` case. THe amount of work done still doesn't depend on the input size, so it's constant, but it might be difference from that of the `n <= 1` case.

Now we consider the `n >= 3` case.

Recursive part: $T(n) = 3T(\frac{2}{3}n) + c$. Notice that the three recursive calls each use a list two thirds the size of the input list. To see this, let's consider the code:

```
if len(list) >= 3:
    split = len(lst) // 3
    do_something(lst[0..len(lst) - split - 1])
    do_something(lst[split..len(lst) - 1]
    do_something(lst[0..len(lst) - split - 1])

```

First off, we see that `split` will be equal to one third the length of the input list, rounded down (we assume `//` means integer division). We then have three recursive function invocations. To get the input size for these recursive calls, we have to see how big the lists we're passing are. All three are slices of the original input list; we can determine the size of the lists being passed to recursive calls by computing the indices used to determine slices. Observations:

* The first and third slices use the same indices.
* `0 .. len(lst) - 1` is the entire list, size `n`.
* `split` is one third the list size, equal to `n/3`.
* The second slice uses `split .. len(lst) - 1`; to get the size of this slice, we can use simple subtraction of the size of the smaller interval (`0..split`) from the bigger interval (`0..len(lst) - 1`): `n - n/3 = 2/3 n`.
* The first and third slices work similarly: if we take a slice of size `n` and stop it `n/3` indices earlier, we get `n - n/3 = 2/3 n`.

Now that you have a recurrence relation, you can resolve it using any of a several of techniques.
> 3 votes

# Answer
Hint: As you mention, there are two cases to consider, the list has length at most 2, and the list has length at least 3. In the first case, only some constant-time statements are executed. In the second case, there are additionally three recursive calls.

Now denote the time it takes to run the algorithm on a list of length $n$ by $T(n)$. (More accurately, $T(n)$ is going to be an upper bound on the running time, since we are not going to consider the cases $n=1$ and $n=2$ separately even though the running times are slightly different; this is OK since we don't care about constants.) The form of the recurrence is $$ T(n) = \begin{cases} ? & \text{if }n \leq 2, \\ T(?) + T(?) + T(?) + ? & \text{if }n \geq 3. \end{cases} $$ Make sure that you understand why this is the form of the recurrence, and then fill in the blanks.
> 1 votes

---
Tags: asymptotics, runtime-analysis, recurrence-relation
---


# Question
Title: Is there a class of formal grammars that generate Recursive Languages only?
Is there a class of formal grammars that generate Recursive Languages only? (ie with which it is not possible to generate non recursive languages.)

If so what kind of production rules/restrictions do they have?

And why are they not a part of Chomsky Hierarchy?

# Answer
> 2 votes
I cannot answer the question as asked, but here is what partial result I found, which may interest you.

I will first address the following problem.

## Is there a formal family of automata recognizing all and only recursive languages?

**The answer to that question is no**. This can be proved by diagonalization.

Suppose such a family F of automata, They can be enumerated as integers like TM, and there is a F-universal Turing Machine U that can simulate them given their integer representation. So given such an automaton M and an input X, U(M,X) can tell wether X in in the recursive language recognized by M, and always halt. Now, we modify U into a machine U' that lies when X=M. Then consider the language string X recognized by executing U'(X,X). By construction, the TM U' will always halt with an answer (yes or no), thus recognizing a recursive set. But it gives for any X an answer different from the one given by automaton X. So the language recognized is different from any of the languages recognized by the automata in the family F. So the family F cannot recognize all recursive languages. This establishes the result by contradiction.

However, this is not the question asked. The question is :

## Is there a formal family of grammars generating all and only recursive languages?

This question is about a generative device rather than a recognizer. Simulating a generative device will always halt and give me an answer if a string is in the language. But it will tell me nothing when a string is not in the language. Simulating generation will just give a non-halting computation if used for recognition.

To do better, I would have to pair each grammar with the grammar for the complement language, in which case I would have a recognizer, by simulating both in parallel, being sure that one will find the input string. But we have seen that such a recognizer cannot exist. So pairing such grammars for complementarity is not possible.

Given such a grammar, we would know there is another one that is its complement, but it would be undecidable whether any given one is the one generating the complement language.

But I do not know at this point whether such a grammatical formalism can exist.

---
Tags: formal-languages, computability, formal-grammars, halting-problem, semi-decidability
---