title: Microsoft Singularity : why closed

text:
# Question
Title: Microsoft Singularity : why closed
I'm talking about this one research project:

but MS closed it in 2008. I've read many articles about it, about high perfomance (30+% faster against tradinional monolithic kernels), much more secure etc. So it should be really a revolution in OS designing. Why they did it? I would be really happy if they didn't... So only one question i have: why? Was "effective managers" who destroyed it or some else? I'm thinging about it for many strenuous months...

# Answer
First you need to understand the goals of Microsoft Research.

> Our labs are unique among corporate research facilities in that they balance an open academic model with an effective process for building research results into product development. This approach, unique among corporate research facilities, pays off for Microsoft as enhancements to virtually every product and service it offers and as entirely new lines of business for the company. At the same time, it produces significant technological and intellectual advances across the spectrum of computer science.

from: Inventing the Future of Computing

Second you need to see how these ideas are translated into current projects.

> Windows 7. The latest version of Microsoft’s flagship operating system incorporates a number of “under the hood” technologies from Microsoft Research that contribute to the product’s improved performance, reliability and usability. These include enhancements to handwriting recognition, graphics performance, networking and security. Additionally, the product development team made use of a number of Microsoft Research technologies to write and test code efficiently and more thoroughly identify potential security issues.

See: Bringing Innovations to Life and Making Computers More Capable and Useful

Lastly you need to understand that Singularity has been used as a springboard for other projects:

> Microsoft describes Singularity as a research project "which demonstrated that modern programming languages and software engineering techniques could fundamentally improve software architectures." Singularity ended up spawning and/or influencing a number of other operating system research projects at Microsoft, including Barrelfish, Helios, Midori (Wikipedia) and Drawbridge.

from The father of Microsoft's Singularity OS moves on
> 7 votes

# Answer
it is probably not so accurate to say the project is "closed". wikipedia says it is "completed" (2007) as basically a "proof of concept" type project. the code is nearly open source and still available for researchers to build on. the site is still available. one "deliverable" of the project can be seen as academic papers of which there are many available.

the goal of the project was re-architected design principles/design patterns (massively refactored/streamlined) for a future operating system, not nec. built by MS. such a system may still be possible. it seems likely that some of the ideas may already be circulating in new OSes eg Android and/or new versions of Apples OS & also some variants of Linux.

not all R&D projects in microsoft or other corporations are slated to be converted directly to products. especially from more pure research, the results may not be "productizable". from GCs article

> Microsoft officials often publicly downplayed (at least publicly) the significance of Singularity -- not wanting company watchers to consider a research project a threat to Windows, one of Microsoft's biggest commercial cash cows. But at least one member of the Singularity family, Midori, may still end up a commercial project at some point.

in other words the new design was so different than the old that it could not merely be incorporated as an enhancement. its a very ambitious near-revolutionary rework/ground-up redesign of the entire operating system. one can see eg with Vista that there were massive initial feature ideas (such a as a rework of the filesystem architecture) that turned out to be too ambitious to carry out and was scrapped.

in other words, somewhat counterintuitively Windows may now be considered to be a legacy system running on a PC. in earlier history there were no legacy systems running on PCs because they were so new, it was more a mainframe concept. but after nearly 2 decades of Windows on the PC, its in unequivocally in many ways approaching legacy system symptoms/status.

it is a very large amount of code, increasingly unwieldy to maintain/change, that cannot be changed in major ways without causing major breakage. another relatively new concept to describe this is technical debt.

a classic book describing the powerful/overwhelming inertia effect of attempting change in large codebases is Brooks Mythical Man Month.

other aspects to consider are Microsofts competitive position in the industry which has faded somewhat in recent years, making it less able to pull off/carry out very bold and game-changing new designs and making it necessary to prioritize (and yes cut) some projects. Microsoft routinely goes though massive internal reorganizations which it is involved in currently with the departure of the longtime ceo Ballmer.

a reality of applied CS principles in industry: complex internal politics not entirely grounded in technical merit/finesse or gamechanging potential plays a role in what projects live and die in Microsoft or \[quite similarly\] any large corporation. it does take on Darwinian aspects at times esp in the fast-moving/evolving IT industry where one leader, Grove of Intel, also espousing/emphasizing its Darwinian aspects, famously said "only the paranoid survive".
> 6 votes

---
Tags: operating-systems, os-kernel
---


# Question
Title: Can a tree be traversed without recursion, stack, or queue, and just a handful of pointers?
Half a decade ago I was sitting in a data structures class where the professor offered extra credit if anyone could traverse a tree without using recursion, a stack, queue, etc. (or any other similar data structures) and just a few pointers. I came up with what I thought was an obvious answer to that question which was ultimately accepted by the professor. I was sitting in a discrete math class with another professor in the same department--and he asserted that it was impossible to traverse a tree without recursion, a stack, queue, etc., and that my solution was invalid.

So, is it possible, or impossible? Why or why not?

Edit: To add some clarification, I implemented this on a binary tree which had three elements-- the data stored at each node and pointers to two children. My solution could be extended to n-ary trees with only a few changes.

My data structures teacher did not put any constraints against mutating the tree, and indeed I found out later that his own solution was to use the child pointers to point back up the tree on his way down. My discrete math professor said any mutation of a tree means that it is no longer a tree according to the mathematical definition of a tree, his definition would also preclude any pointers to parents--which would match the case where I solved it above.

# Answer
> 22 votes
A lot of research in this area has been done, motivated by method of "cheaply" traversing trees and general list structures in the context of garbage collection.

A threaded binary tree is an adapted representation of binary trees where some nil-pointers are used to link to successor nodes in the tree. This extra information can be used to traverse a tree without stack. However, an extra bit per node is necessary to distinguish threads from child-pointers. Wikipedia:Tree\_traversal

As far as I know binary trees implemented using pointers in the usual fashion (left and right pointer per node) can be traversed using the method of threads, in a method attributed to **Morris**. The NIL-pointers are temporarily re-used to thread a path back to the root. The clever part is that during traversal one can distinguish the original edges from the temporary thread-links, using the way they form cycles in the tree).

Good part: no extra data structure. Bad part: slightly cheating, the stack is *inside* the tree in a clever way. Very clever.

A proof of the hidden stack is shown in P. Mateti and R. Manghirmalani: Morris's Tree Traversal Algorithm Reconsidered DOI:10.1016/0167-6423(88)90063-9

J.M. Morris: Traversing binary trees simply and cheaply. IPL 9 (1979) 197-200 DOI:10.1016/0020-0190(79)90068-1

Then there also is **Lindstrom** scanning. This method "rotates" the three pointers involved in each node (parent and two children). If you want to perform any decent pre-order or post-order algorithms you need extra bits per node. If you just want to visit all the nodes (three times, but you never know which visit you perform) then it can be done without the bits.

G. Lindstrom: Scanning list structures without stacks or tag bits. IPL 2 (1973) 47-51. DOI:10.1016/0020-0190(73)90012-4

Perhaps the most straightforward way is a method by **Robson**. Here the stack needed for the classic algorithm is threaded through the leaves.

J.M. Robson: An improved algorithm for traversing binary trees without auxiliary stack IPL 1 (1973) 149-152. 10.1016/0020-0190(73)90018-5

IPL = Information Processing Letters

# Answer
> 6 votes
I suppose that each node has a pointer to its parent (unless it's the root), as well as to its first child (if any), and its child has a pointer to its next sibling (if any). You can now simulate your favorite traversal order. You just need to come up with a rule of selecting the next node. For example, suppose you want to simulate postorder. Your first node is the "leftmost descendant", which can be obtained by starting at the root, and repeatedly moving to the first child. Now suppose that you're at some node $v$. If you have a next sibling, then you output the leftmost descendant of that sibling. If you don't have a next sibling, then you output the parent. If you don't have a parent, you're done.

# Answer
> 0 votes
My solution was a bredth-first traversal using nested for-loops to brute force the tree. This isn't efficient by any means, and indeed a recursive data-structure like a tree is begging for a recursive traversal, but the question wasn't whether a tree could be traversed efficiently, is was whether it was even possible.

```
Pseudocode:
root = pointer root
depth = integer 0
finished = bool false
//If we n-ary tree also track how many children have been found
//on the node with the most children for the purposes of this psuedocode
//we'll assume a binary tree and insert a magic number of 2 so that we
//can use bitwise operators instead of integer division
while(!finished)
    ++depth
    treePosition = pointer root
    finished = true;
    for i := 0..2**depth
        for j := 0..depth
            if (i & j) //bitwise operator explained below
                // if right child doesn't exist break the loop
                treePosition = treePosition.rightChild
            else
                // if left child doesn't exist break the loop
                treePosition = treePosition.leftChild
        if j has any children
            finished = false
            do anything else you want when visiting the node

```

For the first few levels it would look like this, as you can see, the bitwise operator in the pseudocode simply decides a left or right turn on a binary tree:

```
2**1       0               1
2**2   00      01      10      11
2**3 000 001 010 011 100 101 110 111

```

For n-ary, you would take i%(maxChildren\**j)/j to determine which path to take between 0 and maxChildren.

At each node on n-ary you would also need to check to see if the number of the children is greater than maxChildren and update it appropriately.

---
Tags: algorithms, trees, recursion
---


# Question
Title: What should I do with a bunch of 16-17 year olds to get them interested in computer science?
I'm going to be involved with a sort of 'open day' at my university in a few weeks. As part of this time, I (along with a coworker) am being given a whole bunch of high-school level students for two hours, as well as a computer lab big enough to contain them all, and I have to do some kind of activity or set of activities with them to encourage them to do computer science (at my university, ideally, but in general also). I am at an absolute loss as to what to do here, and welcome any and all suggestions.

# Answer
* You can have them draw pictures using context-free grammar. context free art This also works for people who never programmed before and scales to experienced programmers. The basic language is easy enough to explain in maybe half an hour.
* Learning something about geometry using Turtle graphics should be nice too. Logo was designed for children, so highschool students should have no problem. There are nice videos about children using Logo on youtube
* If you can get your hands on some MindStorms robots, programming them is lots of fun.
* There are a variety of programming games in which you program robots to fight each other, or assembly programs that try to overwrite each other in a virtual machine. Wikipedia on the topic, related stackoverflow question
* You can also think about some kind of hardware project. Making a microcontroller blink a LED depending on the number of unread e-mails in your inbox for example.
* Have them implement different maze generation algorithms, try to come up with criteria that make mazes "difficult for humans". If time permits extend the algorithms to include not only corridors but also rooms.
* Buy a couple of Arduinos and LEDs. Let them program the blinkenlights.
> 21 votes

# Answer
Check out Computer Science Unplugged. From their site:

> CS Unplugged is a collection of free learning activities that teach Computer Science through engaging games and puzzles that use cards, string, crayons and lots of running around.
>
> The activities introduce students to underlying concepts such as *binary numbers*, *algorithms* and *data compression*, separated from the distractions and technical details we usually see with computers.
>
> CS Unplugged is suitable for people of *all ages*, from elementary school to *seniors*, and from many countries and backgrounds. Unplugged has been used around the world for over fifteen years, in classrooms, science centers, homes, and even for holiday events in a park!
> 13 votes

# Answer
Most Computer Science undergraduates that I know consider learning to program to be the most painful and demoralizing part of their education. I would therefore stay away from *anything* that has to do with programming itself. As scphantm pointed out already, you probably also won't have time for this.

What your looking for is a two-hour exercise that satisfies two goals:

* It's exciting enough to keep high-school graduates interested enough for two hours,
* It will give them a glimpse of what Computer Science is, and hopefully get them interested in it.

The first goal is fairly independent of what you're actually going to show and has a lot more to do with being a good teacher/presenter. Good didactic practice, i.e. keeping your audience on their toes, letting them try small things in groups, giving them a breather every 15 minutes, and so on.

The second goal is a bit of a tricky bit, and what I think works best here is to take a problem which can be explained with their current knowledge, show how you can describe the solution algorithmically, and then show how that solution can be analysed and improved.

A good example is the shortest path problem in graphs, otherwise known as a GPS navigation system. No explanation needed. You can give them a small map with edge weights/length drawn in and a bunch of crayons to actually execute the algorithm as you describe it.

You can then start a discussion on how you would find a shortest path, and so on, let them try to formulate it as an algorithm, etc... Then you describe Dijkstra's algorithm, letting them colour the nodes as *visited*, *tentative* , and *unvisited* sets. Bam. You've got an algorithm!

If you still have time, you can go on to explain some details, i.e. stuff that we take for granted like finding the minimum in the set of tentative nodes. If you get this far, you can show the difference between linear search and a heap, and as a bonus you get to introduce $\mathcal O$-notation.

Having said all that, this is about as far as I would go. Stay away from the whole $P$ vs. $NP$ discussion with a ten foot pole. Although most Computer Scientists find this fascinating, most high-school students won't. I know this from experience. The key, in my opinion, is to start with a problem that they can understand, or relate to, and take it from there without the need for much introduction.
> 11 votes

# Answer
If you only have 2 hours, you aren't going to get much coding done. Just learning syntax will be hard in that time, but there are plenty of things that can be done instead.

As a suggestion, try teaching them control flow and the importance of being specific:

1. Divide the class into 2, "robots" and the others "programmers".
2. Come up with a suitable challenge that requires some simple logic, looping etc. - there is an example below.
3. Have the "programmers" write out a list instructions that are given to the "robots"
4. Have the "robots" perform the instructions, but let the "robots" know that if the instructions are confusing they are allowed to stop, error or otherwise act up until the "programmer" stops and debugs them. Guaranteed, if given a chance to play up, a high schooler will.

As an example task, set up some tubs of different coloured balls, with corresponding coloured strips of paper elsewhere and enough small buckets for each robot/programmer pair. The task is to make the robot fill the bucket with balls, however to do so they can only take balls that match a specific strip of paper. If there are no more balls of that colour in a tub, then the robot must return their strip of paper and collect a new one.

**This task requires conditional branching, looping, error handling, and thinking proceedurally. All things that a programmer needs to be good at, regardless of the language or activity.**

Run something like this twice so the "robots" and "programmers" can swap. In between, give a small lesson on the above patterns of thinking, and they will perform much better in the second, close out with a small talk on the big events in programming - defeating the Nazis, going to the moon, the internet, and you'll have a room of potential and engaged programmers!
> 9 votes

# Answer
I've trained many programmers. If all you have is 2 hours, don't bother with teaching them how to code. Computer lab is unnecessary too. To go from zero to hello world, you will loose half the class and spend and hour 45 of your 2 hours dealing with glitches and get nothing done.

You may have more luck showing them what its like to think like a programmer. Give each of them a pad of paper and a pen and tell them to write a program in their own language on how to pick up their cell phone off the desk and make a phone call. Walk thru their answers. If your a code jocky of any salt you can step thru their programs and tell them how to make them better and how to accomidate the detail you need to have. Then ask them to write a program in their own words to do something else mundane. put your pants on, brush your teeth, open a door, whatever. Do the same with that program.

Give them a taste of what its like to THINK like a programmer. They will certainly get more out of that than you trying to teach them Python in 2 hours.
> 7 votes

# Answer
You might try Alice. It's an IDE and API for 3D animation. It has all sorts of built in objects (rabbits, aliens, trees, buildings, ...) that you can place in an initial scene, with very high-level methods: like `walk(north)` (which animates the arms and legs while the character moves) and `say("my name is Winky")` which might cause a cartoon bubble to come out of the characters mouth.

It allows you to hook keyboard and mouse events so you can do things that are interactive.

The underlying programming language is Java, but the IDE gives you a graphical variant where you drag and drop parts of expressions into an editor window. (It won't let you create a syntax error.)

I think you could get it all preset up with a scene so that someone with no programming experience could do something interesting in just a couple of hours.
> 6 votes

# Answer
Coding, even in a toy or graphical language, seems far-fetched in the course of an hour. Hell, I'm not sure I could pick up Alice again and do anything worthwhile in 2 hours. Maybe a weekend, but not 2 hours.

I'd suggest boiling CS down to the bare essentials: problem solving and analysis. Break the group into teams. Take 10 minutes to describe a few high-level computational problems. These should be easy problems that can be easily explained to people with little mathematical or CS background. Examples include:

1. Sorting lists
2. Finding minimal spanning trees
3. Computing (approximate) roots of integers
4. etc.

Take another 10 minutes for further discussion, and to explain the task. Each group is assigned one problem, for which they are to brainstorm solutions. The team will have a half hour to collaboratively figure out a solution or solution(s) to their assigned problem. Then, take an hour to go over the solutions in the entire group, and let the kids figure out whether they work or not, whether there's a faster/better way to solve the problem, etc.

If the kids don't land on a correct/optimal solution, that's OK. Don't just give the answers away, though - this is absolutely critical. The reason why kids don't do STEM anymore is because educators give kids the impression that everything's already figured out. It will take very mature counselors to allow the kids to try to solve these problems, and to succeed or fail, on their own. Getting the right answer's not the point. The point is giving the kids interesting problems and showing the kids what computer science is about: solving problems, and evaluating solutions for correctness and efficiency. Letting the kids come up with their own answers will give them a sense of ownership and help them feel engaged.

Of course, if the kids ask whether they got a correct/good/the best known answer, tell them the truth. But don't just give away the answers, unless they come up organically as a result of discussing the students' solutions. To summarize:

1. Give kids easy to understand but rich problems to explore.
2. Let the kids come up with their own solutions, providing only enough help to make sure the kids understand the problem at hand.
3. Discuss correctness/efficiency in a group setting, giving the groups a chance to explain their solutions. As counselors, you're free to take the discussion of correctness/efficiency as far as you think it can profitably go.
4. Under no circumstances should you present your own, or any well-known, solutions to the problem, unless they are basically identical to those provided by students. Do not make it seem like CS is a field where people have already figured out all the answers.
5. If possible, leave the kids feeling like they've learned something, but so that they still have questions: did they find the best answers? Are their other questions they can solve in a similar way? You might even provide them some undecidable problem in an easy-to-digest format to give them something to work on afterwards.
> 6 votes

# Answer
Im 17 now and I started programming around the time I turned 16. Im going to tell my story and than make some suggestions: My interest in programming started when I was watching a computer tech guy I called mess around with my registries and command prompt(even though he wanted 500$ to fix my BSODs and I didn't pay, I fixed them on my own) So I googled "command prompt language" and found out that there was something called "source code" and it allowed you to program. At the time I had no idea what c++ was, I don't even think I'd ever heard of it. So I went on cpp.com(very bad tutorials, you will learn bad and outdated practices) and started learning the basics. My mind went crazy and I actually learned that the virus I was infected with causing my problems was written in c++, which further interested me. I later started reading, learning assembly and other high level languages. I started first wanting to learn about malware and Graphics programming and I did.

1. This may sound bad but a lot of people my age are actually interested in the destructive side of programming. The first question I get from my friends when I tell them im pretty good with c++ is "Can you make viruses, change grades or hack games" Im not quite at that level...ive been studying dll injection recently though, so im getting there. Perhaps you could come up with something along the lines of malware that isn't dangerous or illegal but still interesting. (Maybe get the login information of a student from the school server) You could talk to them about how viruses and malicious software work too.
2. Develop a small game along the lines of pokemon and describe to them how games and game engines work. A lot of people would probably be surprised to know that in a lot of 2d games like this the character is not actually moving, the background is and the character is just using an animation, talk about random numbers ect. Come up with some 3D demonstrations too.
3. Try to stay away from explaining what the **code** does, try to tell them what the **program** itself does without talking about the code too much. In my experience that's an easy way to lose peoples attention especially if they don't understand the basics of the language. In fact, I would try not to really put the source code all out there because it could be fairly discouraging for someone to look at 500 lines of code and not understand any of it. Also if you have someone that youre demonstrating to that is like me they'll probably ask a chain of questions because they have a curious mind. i.e: Youre talking about random numbers, they ask what random numbers are for and where they come from...than you have to explain to them about electronic noise and how its random and everything, than youll probably find yourself in a situation where youre just like "I don't know". Questioning from teenagers can be pretty recursive...
4. **Lego Mindstorms is a great Idea. If you don't wanna take the long route and use a major language it comes with a block style programming language that you can use. I figured out the language in about 30-40 minutes, everything lines up when you think about it**
5. You could quickly develop an app and show it off, talk to them about the $$ that can come from app developing.
> 6 votes

# Answer
some of my favorites

* generating fractals. they have a strong link to deep mathematics and computer graphics, and also they're naturally suited for parallelism. it illustrates complexity and emergent behavior, esp when you zoom to arbitrary scales, and has strong tieins to science and natural phenomena. it is not hard to write some parallel fractal code that runs on multiple machines. one experiment is to have each machine display the random lines that it processed (eg "slave" machines that process lines from a queue) and then a central machine display the combined results.
* lego robotics (or other robotics kits eg stamp). mindstorms is a toy, but it can be a very advanced one serving as a tangible demonstration of abstract concepts. the software that can be run on them can be very complex, and they can have complicated sense-think-act loops/algorithms. there are many good books of constructions. also impressive are the Rubiks cube solvers, recently breaking the world record.
* raspberry pi is a new inexpensive platform that is seeing a lot of interest and use. it can be used to demonstrate linux programming, robotics etc, and has HD output, etc. see eg Southhampton raspberry pi supercomputer with a Lego rack.
* Logo as mentioned in the other answer is an old classic. another newer angle is game programming eg with a new emerging popular language called Scratch (invented at MIT). it can teach many natural/advanced CS topics.
> 4 votes

# Answer
heres another angle. there are so many interesting open problems or emerging technologies in computer science at the frontiers of scientific understanding that can spark curiosity/wonder, ie exploration of nearby *terra incognita*. if you raise the problems and then have the class participate in a discussion about the ramifications of solutions, that can spark significant interest/inspiration. \[since you mention the availability of the computer lab, it would also be possible to creatively come up with some hands-on computer exercises related to these areas.\]

this can take on a sci-fi feeling but in CS like no other field, it turns what was once scifi into reality in a short amount of time. they also can be controversial and timely, connecting with today's headlines, and students can begin to grasp how ubiquitous CS is in our world/society, and how significant it is, when broadly interpreted. here are a few big ones:

* DNA to protein folding problem. is there an algorithm to calculate it accurately?
* artificial intelligence in general. is it possible? are there ethics involved?
* robotics has various key emerging areas. eg autonomous autos/driving. its on the nearterm horizon. how will this affect society? the video of the DARPA contest from not too long ago is impressive. Kurzweil's writing has a lot of stuff to get into. drones are a complicated topic rarely openly discussed and will be increasingly used domestically. the mars rovers are extraordinary technology and there are amazing stories behind it, such as how the systems had to be debugged *remotely—interplanetarily* when they failed.
* IT-based surveillance systems to detect crime/terrorism are heavily in the news lately.
* P vs NP problem. it sounds abstract but it can be presented in a very tangible way such as talking about how video games are NP complete, and the problem can be visualized as the size of circuits required to solve NP complete problems, and the wild implications of P=NP, and how cryptography & secure transactions depend on the P$\neq$NP assumption. oh yeah and dont forget to mention the hanging $1M prize as close to what is called in \[theory\] teaching, "motivation"!
* the Higgs boson could not have been discovered and the supercollider cannot function at all without large CS-based systems for analyzing the "big data".
* Moore's law. how far will it continue? how much has it already affected society/humanity?
* Quantum computers. are they possible? will they be faster? will they be lowcost or always unweildy? Dwave is a colorful case study, there is a great SciAm article by Aaronson, etc
* Google pagerank algorithm is one of the multibilliondollar wonders of modern computer science. will it be extended? how does spam filtering work? the company seems to be moving toward analyzing images, etc.
* algorithmic/high frequency trading now moves massive amounts of trading volume/value. is it good/bad? is it increasing/decreasing? will it be regulated in the future? what kind of computational arms race is involved?
* supercomputers are massive, solving amazing problems, and getting bigger. are there limits? what do they compute and what will they compute in the future? somewhat related, Big Data and datamining.
* social networking sites have had huge implications in less than a decade of growth. they are involved in fueling popular uprisings eg Arab spring and Occupy wall st. what is their future?
> 2 votes

# Answer
I have a proposition that

* focuses on computer *science* (not programming or auxiliary),
* starts with a premise most kids know and
* has actually been tried and works.

We have been holding small workshops with high school students about **Minesweeper**. The workshop would roughly go like this:

1. Let's play the game a bit (most know it).
2. What have we just done? What is the problem we try to solve? Can we formulate general rules?

This will usually take a while. Kids are not used to formulate problems in terms of input and output lest general rules for solving them. Those who have programed before will appreciate the effort; referencing "spaghetti code" can help. Nevertheless, the rules will be simple most of the time, considering only one cell at a time.
3. Exhibit problems with the rules.

At this point, you want to introduce a Minesweeper simulator. The one by Bayer, Snyder and Chouiery is not perfect but allows you to exhibit carefully designed scenarios.
4. Improve the ruleset to cover more scenarios.

This will typically lead the students to investigate more and more cells together. You can also nudge them towards "solve all" approaches like expressing the information at hand as a linear equation system -- this comes up if you try to express the available information in mathematical terms. Students already know how to solve such systems!
5. Note limitations.

First, there are scenarios that have no (deterministic) solution. Furthermore, we can contrast brute-force with our developed strategies. Can we trade-off speed versus power? If the equation-system approach turns up, note that we can only solve this efficiently over the reals, but we need binary answers. It's not too hard to build scenarios which lead to huge runtimes (we used computer algebra to illustrate).

Depending on the group, this approach allows to cover multiple principles of computer science in a natural way: defining problems, describing general algorithms, iterative problem-solving as well as issues of computability and complexity can all be touched upon.

Feedback by students has been overall positive; they feel engaged and express interest in the concepts. It is important let them do most of the work, only carefully nudging them in the desired direction by asking pointed questions.
> 2 votes

# Answer
you have a lot of things to do ... but one thing that would seem so exiting "money" , so present the "P≠NP" question and the seven millennium prize , when I was in middle school I read about it although I didn't knew the notations the only thing that I understand : there is big prize and question ! other things would be presenting the connection of mathematics and computer science like : solving equations , checking solutions using computers .

other things I would suggest is presenting Alan turing "the father of computer science" and tell his story. the last thing that I suggest is zero knowledge proofs and the game "where is waldo?" and playing without cheating and cryptography and cyber attacks .
> 1 votes

# Answer
Do anything with facebook, they love it. Maybe this is to difficult for beginners, but u clould let them draw connextions graphs, that show how their profiles are connected to each other. I would recommend Javascript as programming language.
> -2 votes

---
Tags: education
---


# Question
Title: computer science in the movies as an educational angle
recently there have been a few questions on teaching CS in both cs.se & tcs.se and there are many high-rated related questions on the two sites on the topic. thinking over the latest one made me realize that a lot of students get exposed to some aspects of STEM through the media (sometimes inaccurately), and one of the most powerful media outlets is movies.

it seems that maybe instead of rolling ones eyes or recoiling from their unrealism, these have some potential and can be used as a teaching tool (aka "teachable moment") by taking them as a student experience to build on, as case studies for students to learn about certain concepts and how the concepts actually work vs the screenwritten, "hollywood" version, ie address (possible widespread?) misconceptions about the field and its essential aspects.

> what are key or compelling movies introducing CS-type concepts and what is accurate/inaccurate about the portrayal? \[or is it roughly correct?\]

# Answer
> 3 votes
I haven't seen it yet, but Travelling Salesman could be pretty interesting.

---
Tags: education
---


# Question
Title: Recursive language with non-recursive subsets
I have a professor who is really poor at explaining the material, which is what makes answering his questions very hard. Here is the question:

> Recursive language with non-recursive subsets. Does one exist?

I'm sure it is a very simple and easy answer but I can't figure it out. Don't give me the answer just point me in the right direction and I'm sure I'll figure it out.

# Answer
> 3 votes
Hint. Take a very big recursive language over any alphabet you like. Verrrry big. Something so big it has all kinds of subsets.

---
Tags: formal-languages, computability, undecidability
---


title: How to I get a TM with lowest index?

text:
# Question
Title: How to I get a TM with lowest index?
I'm struggling to understand this question:

> Give an encoding of the Turing machine with lowest index that accepts anything but the empty set.

I know what an encoding of a Turing Machine is. But my professor didn't explain what the index of a Turing machine is and how I know that it is lower or higher? Can someone explain what lowest index is and how would I go about this problem?

# Answer
> 3 votes
If I understand your question correctly, then it simply asks for the TM with the encoding who is ordered first in the lexicographic ordering.

As you surely know, many TMs perform the same task. Look at all the TMs that accept anything but empty set. Look at the encodings of all of those. Each encoding is simply a string. If you write all those string ordered using the lexicographical ordering (like in the dictionary), which string comes first? That should be your answer.

---
Tags: terminology, turing-machines
---


# Question
Title: If the language of a TM is TMs which cannot self recognize, can the original TM?
I've been thinking about this one for a while:

> Consider the language of TMs which do not recognize themselves: $L\_{s}=\\{ \langle M\rangle ~|~ M \text{ does not accept } \langle M\rangle \\}$. If $N$ is a TM where $L(N) \subseteq L\_s$, then is $\langle N\rangle \in L\_s$?

Intuitively, I'm pretty sure it is true. I pictured $N$ as a compiler, and imagined some machine $P$ that $N$ compiled. It seemed that if $P$ was not able to bootstrap, then $N$ wouldn't be able to either. But I'm having trouble thinking about this problem more formally.

Am I on the right track? A hint would be really helpful.

# Answer
> 1 votes
You have to argue formally. Intuition can be helpful in pointing the way, but you need a formal argument in the end.

Hint: Suppose that $\langle N \rangle \notin L\_s$. Then $N$ accepts $\langle N \rangle$, and so $\langle N \rangle \in L(N) \subseteq L\_s$, a contradiction.

---
Tags: formal-languages, turing-machines
---


# Question
Title: Why does Patience sorting find the longest increasing subsequence?
According to Wikipedia (link), patience sort finds the longest increasing subsequence of a given sequence. Lets say the longest increasing subsequence of seq has length `correct(seq)`

Patience sort works like this:

```
Parameters: A sequence of integers called seq
Output: A number between 0 and the length of seq. Lets call it patienceSort(seq)
Algorithm (in Python):

def patienceSort(seq):
    piles = []
    for el in seq:
        for i in range(len(piles)):
            # If there is a pile with a strictly greater element on top,
            # place current element on that pile
            if piles[i][-1] > el:
                piles[i].append(el)
                break
        # if there is no such pile, create a new one
        else:
            piles.append([el])
    return len(piles)

```

## What I've understood:

(I) We can guarantee that at every time the top of piles (`piles[i][-1]`) is ordered in increasing order.

(II) For numbers in the same pile: Numbers are ordered...

(II.1) ... by time (first one in the pile came first)

(II.2) ... by value (first one in the pile has highest value)

(III) The numbers on top of the piles are not necessarily an increasing sequence within seq

(IV) The right pile is always the latest one that was created

Example for (III):

```
      37
20    38
30    39
40    40
50    70
pile1 pile2
seq = [50,40,70,30,40, 39,38,37,20]
[20,37] is not an increasing sequence in seq

```

For each card (which is not on the first pile), you can store a pointer to the top of the pile before when you add it to the pile. This way, you can get an increasing sequence by following the pointers and inverting the list. So:

```
patienceSort(seq) <= correct(seq)

```

## Question

Why is `patienceSort(seq) >= correct(seq)`

# Answer
> 6 votes
With the two insights from `(II)` it is obvious that no increasing sequence can use two cards (or more) from one pile.

This means: No increasing sequence can use more cards then the number of piles. But patience sort returns the number of piles.

So: `patienceSort(seq) >= correct(seq)`

See also: Slides from Princeton with pictures.

Thank you very much Yuval Filmus :-)

---
Tags: algorithms
---


# Question
Title: On the language of Turing machines not accepting their own encoding
Let $\text{NOT-SELF} = \\{\langle M \rangle : M \text{ is a TM that does not accept } \langle M \rangle \\}$. How do you prove the following claim?

> If $Q$ is a TM so that $L(Q) \subseteq \text{NOT-SELF}$, prove that $\langle Q \rangle \in \text{NOT-SELF}$.

# Answer
> 1 votes
Hint: If $\langle Q \rangle \notin \text{NOT-SELF}$ then $\langle Q \rangle \notin L(Q)$, and so $\langle Q \rangle \in \text{NOT-SELF}$.

# Answer
> 1 votes
In general, this problem is undecidable: that is, there is no general algorithmic solution.

Yuval gives a good answer for the specific question. Here are some general tips for showing the subset relation, that is, that $L\_1 \subseteq L\_2$:

1. Induction on word length. Show that the smallest string in $L\_1$ is in $L\_2$ and that having one string. This is most effective when there's some sort of inductive structure to the languages you are looking at.
2. Paths to accepting states. Look at how a word is actually accepted by your first machine, the states it travels through and what your tape looks like. For each step, show that you can do an equivalent step in the second machine which won't fail. The hard part is doing this abstractly enough so that it works for all words. This will usually break into a massive proof-by-cases.
3. Forget about Turing Machines. Look at the machines, find out what languages they accept as sets, and perform pure logic on those sets. This isn't very useful if you are given a random TM, but is handy if you know what one TM figures out. For example, if you realize that $L\_1$ is the set of all primes larger than 10, and $L\_2$ is the set of all odd positive integers, then it's pretty easy to show that $L\_1 \subseteq L\_2$

---
Tags: turing-machines
---


title: Show that a language is RE or recursive

text:
# Question
Title: Show that a language is RE or recursive
Consider these 2 languages:

* > $L\_{\ge5} = \left \\{ \left\< M \right\> : M \text{ accepts at least 5 strings} \right\\} $
* > $L\_{\<5} = \left \\{ \left\< M \right\> : M \text{ accepts fewer than 5 strings} \right\\}$

Are these recursive, R.E., or not R.E. sets (languages)?

I would say that they are not recursive, based on applications of Rice's Theorem.

* For the first case $L\_{e}= \left \\{ \left\< M \right\> :L(M)= \emptyset \right \\} \notin L\_{\ge5} $ and $L\_{\ge5}$ are not empty. For example, I define $L= \left \\{ \left\< M \right\> : M \text{ accepts all palindromes} \right \\}$, which is not finite set and accepts an infinite number of strings.
* For the second case I would do the same thing. I have $L\_{e}=\left\\{ \left\< M \right\>: L(M)= \emptyset \right\\} \in L\_{\<5}$ and $L=\left\\{ \left\< M \right\>:M \text{ accepts all palindromes} \right\\} \notin L\_{\<5} $

So I would say that both are not recursive. Is my reasoning correct?

Now about the R.E. of the languages I don't have an idea of how I can prove it, this should be the beginning (if L is not RE it can't be recursive), how can I check if they are RE or not?

From the definition: "$L$ is RE $\iff$ there exists a TM $M$ that accepts $L$", so I just have to define a TM that accepts each language?

# Answer
> 5 votes
$L\_{\geq5}$ is RE. Basically, given a machine $M$, you iterate through all strings, starting with all of length 0, then length 1, etc. You simulate $M$ and test if the current string $s$ is accepted by $M$. If it is, then you increment some counter. If the counter ever hits 5, you accept. There's no guarantee that this will terminate, which is why it's RE and not recursive. There is a guarantee, however, that it will terminate for any input machine $M$ that does accept 5 or more strings.

We know from Rice's theorem that $L\_{\geq5}$ is not recursive, and since it is RE, then we know its compliment is not RE. So $L\_{\<5}$ is neither RE or recursive.

Intuitively, you could iterate through all strings, but there would never be a point where you could say "Based on the strings I've seen so far, I know that this machine accepts less than 5 strings." Even if you accept less than 5 so far, there's no way of knowing that there aren't larger strings which would be accepted.

---
Tags: computability, undecidability, semi-decidability
---


# Question
Title: How can I solve for T(n) recurrence equations?
Solve the following recurrence equations

a. T(n) = T(n/2) + 18

b. T(n) = 2T(n/2) + 5n

c. T(n) = 3T(n/2) + 5n

d. T(n) = T(n/2) + 5n

This is only a sample of what I was given but I am not sure what the question is asking me or how to solve it? Can someone please explain this to me?

The only thing I really know about them is that it has something having to do with Big O and such. I was a bit sick when they gave this lecture so I couldn't really grasp the concept. Could someone please help me understand this?

# Answer
Solving a recurrence essentially means getting rid of the recursion and giving a way to calculate the answer such a recursive function would give you, without doing the recursion. Additionally, when you solve it in terms of asymptotic complexity, then it becomes a bit easier, since you don't care about the slower-growing terms and can get rid of a lot of terms on the way.

So, choosing an example, if we have, $T(n) = T\left(\frac{n}{2}\right) + 18$ then $T(n) = \Theta\left(\log n\right)$. See, I got rid of the recursion; there is no longer any recursion on the right-hand-side. How did I do this? Well, there are two ways.

## General way

We recurse a few steps, and generalize it to step $k$: $$ \begin{eqnarray} T(n)&=&T\left(\frac{n}{2}\right) + 18\\ T\left(\frac{n}{2}\right)&=&T\left(\frac{n}{4}\right) + 18\\ T\left(\frac{n}{4}\right)&=&T\left(\frac{n}{8}\right) + 18\\ &...&\\ T\left(\frac{n}{2^k}\right)&=&T\left(\frac{n}{2^{k+1}}\right) + 18\\ T\left(1\right)&=&\Theta(1)&\genfrac{}{}{0}{}{\text{We choose a (constant) base}}{\text{ case, unless given one}}\\ \end{eqnarray} $$

Then we see how large $k$ must be in order to get down to $T(1)=T\left(\frac n n\right)$:

$$ \begin{eqnarray} 2^{\max k}&=&n\\ {\max k} &=& \Theta \left(\log n\right)\\ \end{eqnarray} $$

Now we know it will recurse $\max k$ times, so we replace each $T(x)$ on the right-hand-side with its recursed value (calculated above), then generalize it to $\max k$.

$$ \begin{eqnarray} T(n)&=&T\left(\frac{n}{2}\right) + 18\\ &=&\left(T\left(\frac{n}{4}\right) + 18\right) + 18 & \text{Replace }T\left(\frac{n}{2}\right)\text{ in terms of }T\left(\frac{n}{4}\right)\\ &=&\left(\left(T\left(\frac{n}{8}\right) + 18\right) + 18\right) + 18& ...\\ &...&\\ &=&T\left(\frac{n}{2^{\max k}}\right) + 18\cdot {\max k}\\ &=&T\left(1\right) + 18\cdot \Theta \left(\log n \right)\\ &=&\Theta \left(\log n \right)\\ \end{eqnarray} $$

## Master theorem

An easier way for special cases of asymptotic recurrence relations is called the master theorem, and allows you to "cheat" if $T(n)$ follows 3 specific forms, and you want the asymptotic solution. See the master theorem page for the different forms, but I will demonstrate for the example I chose:

General form:

$T(n) = a \\; T\\!\left(\frac{n}{b}\right) + f(n) \\;\\;\\;\\; \mbox{where} \\;\\; a \geq 1 \mbox{, } b \> 1$

So for us, $a=1,b=2,f(n)=18$. Therefore, $\log\_b a = 0$ This fits **Case 2** as follows:

### Case 2:

If:

$f(n) = \Theta\left( n^{c} \log^{k} n \right)$, where $c = \log\_b a$, and some $k \ge 0$.

Then:

$T(n) = \Theta\left( n^{c} \log^{k+1} n \right)$

We have $c=\log\_b a=0$ and choose $k=0$. This gives us:

$$\begin{eqnarray} f(n) &\stackrel{?}{=}& \Theta\left( n^{c} \log^{k} n \right)\\ &\stackrel{?}{=}& \Theta\left( n^{0} \log^{0} n \right)\\ &\stackrel{?}{=}& \Theta\left( 1 \right)&\checkmark\\ \end{eqnarray}$$

Which is true, so we match the case. Therefore:

$$\begin{eqnarray} T(n) &=& \Theta\left( n^{c} \log^{k+1} n \right)\\ &=& \Theta\left( n^{0} \log^{0+1} n \right)\\ &=& \Theta\left( \log n \right)\\ \end{eqnarray}$$
> 1 votes

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


# Question
Title: Can the String, $0^p 0^p 0^p$, be Used with the Pumping Lemma to Show that $w^r w w^r$ is Not Context Free?
I'm trying to show that $L=\left\\{w^rww^r:w \in \\{0,1\\}^\*\right\\}$ is not context free using the pumping lemma.

I thought picking the string, $0^p0^p0^p$, would be a good candidate for this, but someone told me I might want to consider another string. Why is this? Any way in which I divide the string and then pump the string results in the balances between the $w^r$on either side of the string being thrown off, no?

# Answer
> 2 votes
For $p\>0$, you can always split $0^{3p}$ into $uvxyz$ such that $u=x=\varepsilon$, $v=0$, $y=0^2$, and $z=0^{3p-3}$. Such a split clearly satisfies $|vxy|\leq p$, $|vy|\geq1$. Finally, for all $n\geq0$, $uv^nxy^nz=0^{3(p-1+n)}$, which is in $L$, since $0^{3m}\in L$ for all $m$.

Since you want to show, that for an arbitrary split satisfying the length conditions, there is some $n$ for which $uv^nxy^nz\notin L$, the choice of $0^{3p}$ is unfortunate.

# Answer
> 1 votes
The string $0^{3p}$ can always be pumped so that it stays in $L$. Recall what the pumping lemma says: there exists a $p \in \mathbb{N}$ such that any $w \in L$ of size at least $p$ can be written as $w=uvxyz$ such that $|vxy| \leq p$, $|vy| \geq 1$ and $uv^ixy^iz \in L$ for all $i \in \mathbb{N}$. In your case, we can choose $u = x = y = \epsilon$ and $v=0^3$, and then $uv^ixy^iz = 0^{3(p-1+i)} \in L$, and so no contradiction can be obtained using the word $0^{3p}$.

In order to prove using the pumping lemma that $L$ is not regular, you need to come up with a word $w$ so that for *every* possible decomposition $w = uvxyz$ such that $|vxy| \leq p$ and $|vy| \geq 1$, there exists some $i \in \mathbb{N}$ such that $uv^ixy^i z \notin L$. For your word $w$ this is not the case, since the decomposition indicated above is "bad". While you are free to choose $w$, you are not free to choose the decomposition $w = uvxyz$; your argument should work for *all* possible decompositions.

In fact, the word $w = 0^{3p}$ doesn't even help in showing that $L$ is not *regular*; we can choose the decomposition $w = xyz$ with $x = \epsilon$ and $y = 0^3$, and then $xy^i z = 0^{3(p-1+i)} \in L$.

The root cause of all these problems is that $L \cap 0^\* = \\{0^n : 3|n\\}$, which is regular. So you have to look at a word which contains both $0$s and $1$s.

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


# Question
Title: Proving that the language of TMs with finite left head moves is undecidable
I'm trying to prove that the following language is undecidable:$$ \\{ \langle M, w \rangle ~|~ M \text{ is a TM where its head moves left a finite number of times on } w \\} $$

But I'm having a bit of trouble. I know I have to do some type of reduction, but I'm not really sure what. Can a Turing Machine be simulated by one which only moves left? if so, then I think I could show $A\_{TM}$ reduces to it. Any hints would be appreciated.

# Answer
Hint: Reduce from the halting problem. Given a Turing machine $M$ and an input $w$, you want to come up with a new pair $\langle M',w \rangle$ such that $M$ halts on $w$ iff $M'$ makes a finite number of left moves on $w'$. Now if $M$ halts on $w$ then in particular it makes a finite number of left moves, but the other direction is not true. Think of a way of ensuring that if $M$ makes an infinite number of moves in any direction, then $M'$ makes an infinite number of left moves. (You might want to add some spurious moves.)
> 2 votes

---
Tags: formal-languages, turing-machines
---


# Question
Title: Solving a graph problem by Gaussian elimination
I have been given a graph with n nodes. Now, I have to color every node of this graph by k colors, number from 0 to k-1. Now, there is a rule.

For a node $x$ with adjacent nodes $y\_1 , y\_2, y\_3, y\_4,... y\_m$, $color(x)=(color(y\_1)+color(y\_2)+color(y\_3)+...+color(y\_m)) \pmod k $

where $color(a)$ indicates a color number from 0 to k-1. I have to find number of ways I can color the whole graph.

My approach to the problem was simple. I was constructing a $n\*n$ matrix for n nodes in graph with equations like $col(x)-col(y\_1)-col(y\_2)-col(y\_3)...-col(y\_m)$. And trying to find number of all zero rows, which will provide us number of free variable. Is my approach correct?

# Answer
> 0 votes
As, no good solutions were given and my research else where proved to be helpful, I am answering my own question. The main idea of the solution is correct.

The number of independent variables controls the total possible way of coloring but the matrix construction is little different.

The matrix will look like this for the following graph.

A graph with 4 nodes $\\{1,2,3,4\\}$ and 4 edges $\\{(1,2),(2,3),(3,4),(4,1)\\}$ provides us the equations,

$col\_1 \equiv (col\_2+col\_4)\mod k$

$col\_2 \equiv (col\_1+col\_3)\mod k$

$col\_3 \equiv (col\_2+col\_4)\mod k$

$col\_4 \equiv (col\_1+col\_3)\mod k$

Providing us equations like,

$(col\_1 -col\_2-col\_4)\mod k \equiv 0$

$(col\_2 -col\_1-col\_3)\mod k \equiv 0$

$(col\_3 -col\_2-col\_4)\mod k \equiv 0$

$(col\_4 -col\_1-col\_3)\mod k \equiv 0$

We form matrix like this for these equations:

$$ \begin{bmatrix} 1 & k-1 & 0 & k-1\\ k-1 &1 & k-1 & 0\\ 0 &k-1 & 1 & k-1\\ k-1 &0 & k-1 & 1\\ \end{bmatrix} $$

Not to mention for every step of Gaussian elimination we have to use mod operation, if any number is negative take the equivalent positive mod.

Then, for every independent variable we can assign a value from 0 to (k-1) and get solution for every of these equations. If number of independent variables is $x$ then the answer will be $k^x$

---
Tags: graphs, linear-algebra, mathematical-programming
---


# Question
Title: Emulating boolean circuits using addition and multiplication (mod 5)
I'm trying to use gates that do addition and multiplication modulo 5 to emulate logic gates.

Assuming false and true are mapped to 0 and 1 respectively (with 2, 3, and 4 being invalid), I figured out I can map the operations like this:

```
a and b -> a*b (mod 5)
a or b -> 2*(a+b)*(a+b+2) (mod 5)

```

I was wondering if there was a simpler approach.

For the application I have in mind, a toy example of secure multi party computation using secret sharing, I haven't shown/discovered/figured-out yet if it's safe to re-use private values. If I have to recompute a, b, and a+b two times in order to do an `or`, costs would be exponential in the length of the circuit. (I'm only using tiny circuits so that's not a big deal, but it would be interesting to know if it was just a non-issue via a clever transformation.)

# Answer
There are many other solutions. For example, even keeping your True and False, you can have $a\lor b = 1 - (1-a)(1-b) = a+b-ab = a + (1-a)b$ and so on.
> 4 votes

---
Tags: circuits, modular-arithmetic
---


# Question
Title: How can I tell who is a truth teller and who is a liar?
This is a problem that I was given for my data structures and algorithms class. I am not sure how to tackle this problem. Can I get some assistance?

> At Hogwarts a new shipment of $n$ goblins has arrived. To be of any use, a goblin must be completely truthful (never lies). Unfortunately, not all of the $n$ goblins in the shipment are truth tellers. Only some are truth-tellers, and some are deceivers. It is your task to design an algorithm to separate the truth-teller goblins from the deceiver goblins. To do this, you have one tool available: You may combine any two goblins and have them state whether the other goblin is a truth-teller or a deceiver. A truth-teller will always say correctly what the other goblin is, but a deceiver may lie (but also may sometimes tell the truth to REALLY confuse you). For any two goblins that you test, the following can be concluded from the goblin responses:
>
> $$ \begin{array}{ccc} \text{Goblin A says} & \text{Goblin B says} & \text{Conclusion} \\\hline \text{B is a truth-teller} & \text{A is a truth-teller} & \text{both are truth-tellers or both are deceivers} \\ \text{B is a truth-teller} & \text{A is a deceiver} & \text{at least one is a deceiver} \\ \text{B is a deceiver} & \text{A is a truth-teller} & \text{at least one is a deceiver} \\ \text{B is a deceiver} & \text{A is a deceiver} & \text{at least one is a deceiver} \end{array} $$
>
> * Show that if more than $n/2$ goblins are deceivers, it is impossible to determine which goblins are the truth-tellers using only the pairwise testing strategy.
> * Consider the problem of identifying $1$ truth-teller goblin. Show that if we assume that more than $n/2$ of the goblins are truth-tellers, then the problem of finding a single truth-teller from $n$ goblins can be reduced to a problem of about half the size using $n/2$ goblin comparisons.
> * Use a recurrence equation to show that if more than half of the goblins are truth-tellers, then the truth-tellers can all be identified within $O(n)$ goblin comparisons.

# Answer
> 3 votes
Here are some hints to get you started. Admittedly, this question isn't that easy.

Part (a): Suppose that there are exactly $n/2$ truth-tellers and $n/2$ deceivers. Show that the deceivers have a strategy in which what a goblin A says about a goblin B depends only on whether they both have the same nature. Draw the conclusions.

Part (b): Pair the goblins up. Show that for some pairwise responses, it is safe to get rid of both goblins. Explain why it is useful to have a majority of truth-tellers.

Part (c): This part should be clear enough.

---
Tags: algorithms
---


title: Regular expression over a monoid

text:
# Question
Title: Regular expression over a monoid
I'm looking for the name of the following concept.

Given a monoid $(M,\oplus)$, and a finite set of generators $x\_1,\ldots,x\_n$. The generators are the alphabets.

We define the regular expression on the words formed by the generators. We treat those words just like strings.

For words $x$ and $y$, we write $x\equiv y$ if $x$ and $y$ represent the same element in $M$.

If $R$ is a regular expression, we define $L(R)$ to be the set of strings matched by $R$ and $L\_M(R)$ as

$$L\_M(R) = \\{w'|w'\equiv w,w\in L(R)\\}$$.

I'm interested to know if there exist known literature on $L\_M(R)$.

Many problems related to $L\_M(R)$ are undecidable, because the word problem on $M$ might be undecidable. I wonder if $M$ has a decidable word problem, does it imply we can decide if $L\_M(R)=L\_M(R')$ for 2 regular expressions $R$ and $R'$.

# Answer
The sets that can be defined this way are called *rational*. As an example, the pairs of input-output strings $(u,v) \in \Sigma^\*\times\Delta^\*$ of accepted computations in finite state automata on two tapes define rational subsets in $\Sigma^\*\times\Delta^\*$ (with pair-wise concatenation as monoid operation). The word problem in $\Sigma^\*\times\Delta^\*$ is trivially decidable, but equality for their rational languages (of pairs of words) is not.

A special collection of monoids that were extensively studied for their rational language decision problems are the so-called trace monoids (or free partially commutative monoids). A special case of these monoids is $\Sigma^\*\times\Delta^\*$.

An overview of the literature in that area is given by Sakarovich, in his paper "The "last" decision problem for rational trace languages".
> 2 votes

---
Tags: formal-languages, reference-request
---


title: 2SUM with a weight

text:
# Question
Title: 2SUM with a weight
Suppose we have a $n\times n$ symmetric matrix $\mathbf A$.

I want to know if there exists two elements of a vector $\mathbf x$, let's call them $x\_i,x\_j,i\ne j$, such that $x\_i +x\_j+\[A\]\_{i,j}\ge y$ for some vector $\mathbf x$ of size $n$. So:

$$ f\left(\mathbf x \in \mathbb N^n,y\right)= \begin{cases} 1&\text{if }\exists\_{i,j,i\ne j}x\_i+x\_j+\[A\]\_{i,j}\ge y\\ 0&\text{otherwise}\\ \end{cases} $$

We can alternatively formulate it simpler, by subtractiong $\frac y 2$ from all $x\_i \in \mathbf x$, and flip the sign of the elements $\mathbf A$ and formulate it like this:

$$ g\left(\mathbf x \in \mathbb N^n\right)= \begin{cases} 1&\text{if }\exists\_{i,j,i\ne j}x\_i+x\_j\ge \[A\]\_{i,j}\\ 0&\text{otherwise}\\ \end{cases} $$ $\mathbf A$ does not have to be stored as a matrix, and I am hoping some other form of storage can help here - some sort of precomputation.

### Is there an efficient algorithm for this (subquadtratic in $n$)?

I am sort of struggling to name this, so:

### Is this a known problem, or reducible to a known problem?

# Answer
Here is one approach that might offer some improvements for some matrices $A$. However, I don't expect it will lead to an algorithm whose worst-case running time is subquadratic, so your question remains open.

---

Let's characterize the set of $\mathbf{x}$ for which $g(\mathbf{x})=0$. This happens exactly if $x\_i+x\_j \< A\_{i,j}$ holds for all $i,j$. Notice that this gives us a set of $n(n-1)/2$ linear inequalities (one for each $i,j$) in $n$ unknowns (the $x\_1,\dots,x\_n$). They define a convex polytope $\mathcal{P}$ in $n$ dimensions.

Your problem then reduces to the following: given $\mathbf{x}$, test whether $\mathbf{x} \in \mathcal{P}$. I don't know whether there are any algorithms for testing membership in a convex polytope (defined as the intersection of halfspaces) more efficiently than separately testing whether the point is contained in each halfspace, but that's something you could investigate.

As a simple optimization, it is easy to identify a minimal subset of those linear inequalities that generate the same polytope. For each linear inequality, you can test whether it is redundant (implied by the other linear inequalities) using linear programming. If it is, delete that redundant linear inequality and continue trying to minimize the set. If you're able to reduce the set of linear inequalities to $m$ inequalities, then you can classify any given vector $\mathbf{x}$ in $O(m)$ time. However, I don't see any reason to expect that in general you will be able to remove enough inequalities to make this run in subquadratic time (I don't see any reason to necessarily expect that more than a constant fraction of the linear inequalities will be redundant).

---

Incidentally, here's a variant of your problem which might be easier to think about. Suppose we have a symmetric matrix $D$, and given a vector $\mathbf{x}$, we want to test whether $x\_i - x\_j \< D\_{i,j}$ for all $i,j$. Let $h(\mathbf{x})=1$ if there exists $i\<j$ such that $x\_i - x\_j \ge D\_{i,j}$ and $h(\mathbf{x})=0$ otherwise. This problem looks much like your original problem, except with subtraction instead of addition.

This problem might be a little easier to think about, because this system of difference equations can be expressed as a difference graph. Build a directed graph whose vertices are the indices, and where the edge $i \to j$ is labelled with $D\_{i,j}$. Each edge in the graph corresponds to a linear inequality; e.g., the edge $i \stackrel{d}{\to} j$ corresponds to the inequality $x\_i - x\_j \< d$. Consequently, each path also corresponds to a linear inequality: e.g., $i \stackrel{d}{\to} j \stackrel{d'}{\to} k$ corresponds to $x\_i - x\_k \< d+d'$, so given a difference graph, you can construct its transitive closure (for each pair of edges $i \stackrel{d}{\to} j \stackrel{d'}{\to} k$, replace the edge $i \stackrel{d''}{\to} k$ by $i \stackrel{d^\*}{\to} k$ where $d^\* = \min(d+d',d'')$).

Now if you take the transitive reduction of the difference graph corresponding to $D$, you get a minimal set of non-redundant linear equations that characterize the set of vectors $\mathbf{x}$ such that $h(\mathbf{x})=0$. If the transitive reduction of this graph has $m$ edges, then you can test whether $h(\mathbf{x})=0$ in $O(m)$ time. However, I don't see any reason to expect that every graph will have a transitive reduction that is subquadratic in size, so this is probably another dead end.
> 2 votes

---
Tags: algorithms, data-structures, number-theory
---


# Question
Title: Do we know how to make a "voice print" and use it for computer generated voice?
Well everything is in the title.

After all Siri voice was made from someone, so can I use software to make a computer generated voice sound like my voice or anybody else?

# Answer
> 3 votes
See the **Voice transformation** project from the **The Center for Speech Technology Research** at the University of Edinburgh.

Thesis: **Transforming Voice Quality and Intonation** by Ben Gillet.

It doesn't do exactly what you are asking, but something similar; it tries to change the voice of a recording to another voice.

Abstract:

> Voice transformation is the process of transforming the characteristics of speech uttered by a source speaker, such that a listener would believe the speech was uttered by a target speaker. In this thesis two aspects of the transformation problem are addressed: voice quality and intonation
>
> The voice quality transformation component of our system has two main parts corresponding to the two components of the source-filter model. The first component transforms the spectral envelope as represented by a linear prediction model. The transformation is achieved using a Gaussian mixture model, which is trained on aligned speech from source and target speakers. The second part of the system predicts the spectral detail from the transformed LPC parameters. A novel approach is proposed, which is based on a classifier and residual codebooks. The system has some similarities with earlier work by Kain, however the work reported here is not restricted to speech spoken in a monotone and with mimicked prosody. Also, on the basis of a number of performance metrics it outperforms existing systems.
>
> We also present a new method for the transformation of pitch contours from one speaker to another based on a small linguistically motivated parameter set. The system performs a piecewise-linear mapping using these parameters. A perceptual experiment, clearly demonstrates that the presented system is at least as good as the existing technique for all speaker pairs, and that in many cases it is much better and almost as good as using the target pitch contour.

---
Tags: software-engineering
---


title: Prove this language is decidable?

text:
# Question
Title: Prove this language is decidable?
$L$ is defined over the alphabet $\\{a,b\\}$ and it's decidable. The language is $\mathrm{perm}(L)$ which is the set of all permutations of all words in $L$.

So far my proof is the following:

Construct a TM $M$ that decides the language $\mathrm{perm}(L)$. $M$ has input $w$. Let $\pi(w)$ be a random permutation of w. Then feed it to $M$: $M$ accepts if $\pi(w) \in L$ or rejects if $\pi(w) \notin L$.

I.e. if we let $\pi(w)$ be a permutation of $w$ s.t. $\pi(w) \in L$, $M$ should halt and accept. If we let $\pi(w)$ be a permutation of $w$ s.t. $\pi(w) \notin L$, $M$ should halt and reject.

Is this correct and enough?

# Answer
> 1 votes
To show it's decidable, you just need to give some effective procedure to decide the language. While giving a TM is a pretty straightforward way to do this, it's not the only way. A much easier way to show this language is decidable is to give plain-old pseudocode for an algorithm to decide the language. Consider this:

```
AcceptsPermutation(
    word : string,
    Accepts : string -> Boolean)
1. permutations = GenerateAllPermutations(word)
2. result = false
3. for each permutation in permutations do
4.     if Accepts(permutation) then result = true
5. return result

```

In the above pseudocode, `Accepts` is a function that accepts the target language. Since the target language is decidable, this function is guaranteed to exist; in fact, you have a TM that computes it (or at least, you have something close).

If you can produce pseudocode to generate all permutations of a word, then you're already done. Consider the following:

```
GenerateAllPermutations(word : string)
1. if length(word) <= 1 then return {word}
2. else then
3.     result = {}
4.     for n = 1 to length(word) do
5.         first = word[n]
6.         rest = GenerateAllPermutations(word[1...n-1] + word[n+1...length(word)])
7.         for each permutation in rest do
8.             result.add(first + permutation)
9.     return result

```

Apologies if that isn't quite right... with luck, it's enough to convey the idea.

Suppose you really, really want to stick to Turing Machines. We can still make this problem a lot easier by relaxing the restrictions. Consider a multi-tape, multi-TM scenario: one TM reads the input tape, and begins writing permutations to an auxiliary tape. Once a permutation is written, the TM stops, activates a second TM on the new tape, and waits for the answer. If the TM accepts, so do we; otherwise, write the next permutation to the tape. If we run out of permutations to write, reject.

The TM on the second tape is the TM we assume exists since the language $L$ is decidable. All you need now is a $TM$ that can write permutations to a second tape. We might imagine a single-tape TM that works like the above algorithm... it might make the tape look something like this:

```
Someword_Omeword_Meword_Eword_Word_Ord_Rd_D_
Someword_Omeword_Meword_Eword_Word_Ord_rD_R_
...
someworD_somewoR_somewO_someW_somE_soM_So_O
someworD_somewoR_somewO_someW_somE_soM_sO_S_

```

Very roughly, the way to get the tapes to look like this is to:

1. Write out the initial one by capitalizing the first letter, scanning to the end, adding a blank, copy all the lower-case letters between the last two blanks, and repeat until nothing is copied.
2. Scan to the front; then, scan right, copying each upper-case letter to the second tape as a lower-case letter, until you see two blanks in a row.
3. Run the second TM on the second tape, to see if that's an accepted permutation.
4. Clear the second tape.
5. From the end of the first tape, scan backwards until you see a lower-case letter preceding a blank, erasing anything you see. When you do see a lower-case letter right before a blank, scan left until you see an upper-case letter; change it to lower-case, move right, and change that letter to upper case. Move to the second blank space to the right. Then, proceed to recreate the permutation string as in (1).
6. Continue in this way until, while scanning left, you see two blanks in a row. This means you've erased the entire tape without finding a matching permutation; since this procedure tries all permutations, you're done.

To make sure you've got it, try to work out the 3rd and 4th permutation strings generated by the above method, as well as the 3rd and 4th from last strings. They should be those given below:

```
...
Someword_Omeword_Meword_Eword_Word_oRd_Od_D
Someword_Omeword_Meword_Eword_Word_oRd_oD_O
...
someworD_somewoR_somewO_someW_somE_sOm_Sm_M
someworD_somewoR_somewO_someW_somE_sOm_sM_S
...

```

# Answer
> 0 votes
Your solution isn't described very well, but I'm assuming it's the following: given a word $w$, compute a random permutation $\pi(w)$ of $w$, check whether $\pi(w) \in L$, and answer accordingly.

---

There are at least two problems with your solution:

1. It gives a probabilistic Turing machine.
2. Even as a probabilistic Turing machine, it could fail to accept a word in $\mathrm{perm}(L)$ with high probability.

Consider for example the language $L = a^\*b^\*$. Then $\mathrm{perm}(L) = (a+b)^\*$, but your machine accepts the word $ab^{n-1}$ only with probability $1/n$, and the word $a^{n/2} b^{n/2}$ only with probability $1/\binom{n}{n/2} = \Theta(\sqrt{n}/2^n)$.

Your idea does work as a non-deterministic Turing machine, which you could then convert to a deterministic Turing machine if you wanted to. I'll leave you the details.

---
Tags: computability, permutations
---


# Question
Title: Efficiently sampling shortest $s$-$t$ paths uniformly and independently at random
Let $G$ be a graph, and let $s$ and $t$ be two vertices of $G$. Can we efficiently sample a shortest $s$-$t$ path uniformly and independently at random from the set of all shortest paths between $s$ and $t$? For simplicity, we can assume $G$ is simple, undirected and unweighted.

Even in many restricted graphs, the number of shortest paths between $s$ and $t$ can be exponential in the size of $G$. Therefore, we would naturally like avoid actually computing all the shortest $s$-$t$ paths. I don't know about the general case, but it seems to me that we can achieve this for some special graph classes.

This feels like something someone must have considered before. Is there any existing research into this, or is this in fact simple to do even for general graphs?

# Answer
I am not 100% sure this answer is correct, but here goes:

I think you can reduce this to uniformly random any-paths, from $s-t$, in a DAG with a single source and a single sink.

Given a graph $G$

1. Make a new empty digraph, $H$.
2. First: run the BFS part of Dijkstra's shortest-path, starting from $s$, mark all the nodes with their shortest-distance-from-$s$.
3. Let $d(s,v)$ be the minimum distance from $s-v$; which we know from the BFS step of Dijkstra's shortest-path algorithm.
4. Then do the next step of Dijkstra's shortest-path algorithm, obtain the shortest-path, store it in $\mathbf p$ (by going backwards from $t$ to $s$).
5. Now start the following loop; expanation in comments, and below:
    * $q\_0=\\{t\\}$
    * While $q\_0 \ne \emptyset$
        + $q\_1= \emptyset$
        + For $u \in q\_0$
            - So we want to find all possible next nodes for this shortest-subpath from $t-u$
            - For all $\text{edge}(u,v) \in G$ such that $d(s,v) \< d(s,u)$
                * $v$ is a neighboring node, with less $d(s,\cdot)$ (it will be $1$ less)
                * Therefore, $t-u-v$ is possible subpath in a shortest path.
                * Put $v \rightarrow H, \text{di-edge}(u,v)\rightarrow H$
                * Now we need to check $v$'s lesser-neighbors next turn.
                * Put $v \rightarrow q\_1$
        + Set $q\_0$ to $q\_1$:
            - $q\_0 \leftarrow q\_1$

Essentially, I am collecting all possible nodes that can be used in the shortest-path, and placing them in $H$.

More on how this works:

> Dijkstra's shortest-path algorithm works by first running a BFS, and marking all the nodes $v\in G$ with their-shortest paths from $s-v$. The next step is to go back from $t-s$, and follow the least-neighboring nodes back.
>
> The thing is, here you can choose *any* of the least neighboring nodes. What I do here is collect *all* the least-neighboring nodes each step, which means I account for *all* the shortest-paths.
>
> Now you quickly think, but hey, why is *enumerating them* exponential, but my way is not?
>
> The answer is, because I use a set to avoid adding the same nodes twice, I avoid recalculating this for each possible path.

Now we have a DAG that we can traverse in any way from $t-s$, and obtain a shortest-reversed-path from $s-t$. The graph should have $t$ as the only source, and $s$ as the only sink.

---

If the above is correct, then I think we can take this a step further and solve the problem as follows.

Give each node in the DAG a node-weight; the node-weight will be the number of paths from from that node to $s$. Let us call this $w(v)$.

You can compute these quickly, see Algorithm that finds the number of simple paths from s to t in G.

Once we have the node-weight, we can uniformly pick a path by:

* ~~Layout the DAG as a level-structure (for visualization)~~
* ~~At each level, choose an arbitrary ordering between the nodes ie. a notion of "left to right".~~
* Traversing down the DAG: at each step $i$, $i \in \left\[1,\left|\mathbf p\right|\right\]$ (where $|\cdot|$ means size-of, in this case, the length of the shortest-path):
    + Let $u\_i$ be the current node (starting at $t$)
    + Add up all the weights of the children of $u\_i$, and using an RNG, choose one child node, $v\_i$, uniformly between the weighted children.
    + Set $u\_{i+1} = v\_i$, and go to the next step
> 6 votes

# Answer
Here is a solution based upon the ideas in Realz Slaw's answer. It is basically a re-exposition of his ideas that might be clearer or easier to follow. The plan is that we will proceed in two steps:

1. First, we will build a graph $S$ with the following property: any path from $s$ to $t$ in $S$ is a shortest path from $s$ to $t$ in $G$, and every shortest path from $s$ to $t$ in $G$ is also present in $S$. Thus, $S$ contains exactly the shortest paths in $G$: all the shortest paths, and nothing more. As it happens, $S$ will be a DAG.
2. Next, we will sample uniformly at random from all paths from $s$ to $t$ in $S$.

This approaches generalizes to an arbitrary directed graph $G$, as long as all edges have positive weight, so I'll explain my algorithm in those terms. Let $w(u,v)$ denote the weight on the edge $u \to v$. (This generalizes the problem statement you gave. If you have an unweighted graph, just assume every edge has weight 1. If you have an undirected graph, treat each undirected edge $(u,v)$ as the two directed edges $u\to v$ and $v\to u$.)

---

**Step 1: extract $S$.** Run a single-source shortest-paths algorithm (e.g., Dijkstra's algorithm) on $G$, starting from source $s$. For each vertex $v$ in $G$, let $d(s,v)$ denote the distance from $s$ to $v$.

Now define the graph $S$ as follows. It consists of every edge $u \to v$ such that (1) $u \to v$ is an edge in $G$, and (2) $d(s,v) = d(s,u) + w(u,v)$.

The graph $S$ has some convenient properties:

* Every shortest path from $s$ to $t$ in $G$ exists as a path in $S$: a shortest path $s=v\_0,v\_1,v\_2,\dots,v\_k=t$ in $G$ has the property that $d(s,v\_{i+1})=d(s,v\_i)+w(v\_i,v\_{i+1})$, so the edge $v\_i \to v\_{i+1}$ is present in $S$.
* Every path in $S$ from $s$ to $t$ is a shortest path in $G$. In particular, consider any path in $S$ from $s$ to $t$, say $s=v\_0,v\_1,v\_2,\dots,v\_k=t$. Its length is given by the sum of the weights of its edges, namely $\sum\_{i=1}^k w(v\_{i-1},v\_i)$, but by the definition of $S$, this sum is $\sum\_{i=1}^k (d(s,v\_i)-d(s,v\_{i-1})$, which telescopes to $d(s,t)-d(s,s)=d(s,t)$. Therefore, this path is a shortest path from $s$ to $t$ in $G$.
* Finally, the absence of zero-weight edges in $G$ implies that $S$ is a dag.

**Step 2: sample a random path.** Now we can throw away the weights on the edges in $S$, and sample a random path from $s$ to $t$ in $S$.

To help with this, we will do a precomputation to compute $n(v)$ for each vertex $v$ in $S$, where $n(v)$ counts the number of distinct paths from $v$ to $t$. This precomputation can be done in linear time by scanning the vertices of $S$ in topologically sorted order, using the following recurrence relation:

$$n(v) = \sum\_{w \in \text{succ}(v)} n(w)$$

where $\text{succ}(v)$ denotes the successors of $v$, i.e., $\text{succ}(v) = \\{w : v \to w \text{ is an edge in $S$}\\}$, and where we have the base case $n(t)=1$.

Next, we use the $n(\cdot)$ annotation to sample a random path. We first visit node $s$. Then, we randomly choose one of the successors of $s$, with successor $w$ weighted by $n(w)$. In other words:

```
choosesuccessor(v):
    n = 0
    for each w in succ(w):
        n = n + n(w)
    r = a random integer between 0 and n-1
    n = 0
    for each w in succ(w):
        n = n + n(w)
        if r < n:
            return w

```

To choose a random path, we repeatedly iterate this process: i.e., $v\_0=s$, and $v\_{i+1} =$ `choosesuccessor`$(v\_i)$. The resulting path is the desired path, and it will be sampled uniformly at random from all shortest paths from $s$ to $t$.

Hopefully this helps you understand Realz Slaw's solution more easily. All credit to Realz Slaw for the beautiful and clean solution to this problem!

---

The one case this doesn't handle is the case where some edges have weight 0 or negative weight. However, the problem is potentially not well-defined in that case, as you can have infinitely many shortest paths.
> 5 votes

---
Tags: graphs, reference-request, shortest-path, sampling
---


# Question
Title: Regular expression for the language where every a is surrounded by b's
I had a question on an assignment where we were supposed to write a regular expression for a language where every $a$ in $w$ is immediately preceded and followed by a $b$. My answer was $\epsilon + (b + bab)^\*$. The teacher pointed out that my answer makes an $a$ surrounded by at least two $b$s, which isn't correct. I can't for the life of me figure out how to fix it to make it correct. Can anyone help?

# Answer
> 1 votes
Here is a regular expression for your language: $(b(ab)^\*)^\*$. It's not hard to check that every $a$ is bordered by $b$s in both directions. The other direction is more complicated and left to you.

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


title: Skip lists with limited height

text:
# Question
Title: Skip lists with limited height
This is homework, so please only hints. I didn't want to put this on StackOverflow since this is mostly about theory, and SO gets inundated with too many questions.

I am asked to find a method of arranging items in a skiplist, with height limited to 3 and unlimited number of elements, in such a way such that searching takes *worst-case* $\Theta (n^{1/3})$. No restriction on how expensive the arranging part is; just describe what subset of the keys go into which level.

I am somewhat confused. How can a skiplist with a limited number of items have search complexity anything other than $\Theta(n)$? Clearly, with any clever algorithm, I can just fill the skiplist with a horrendous amount of elements, and as the number of elements goes up, surely the handicapped skiplist can't do any better than a linked list asymptotically? I think I can prove this for the simple set of rearranging algorithms that put a random proportion $q$ of the items into the second layer, and another random proportion $p$ of items within these items to the top layer.

Am I missing anything obvious? Is the question faulty?

# Answer
> 1 votes
Hint: If the height is $k$, then the search complexity should be $O(kn^{1/k})$ (so the best choice is $k = \log n$, giving logarithmic time). Each level should contain every $n^{1/k}$th element of the lower level. Do the obvious thing - find the two elements bracketing your element in the first level, then the two elements bracketing it in the second level, and so on.

---
Tags: data-structures, lists
---


# Question
Title: Subtracting binaries using two's complement
I am trying to subtract these two binary numbers:

$ 1110 \- 1011$

First I convert 1011 to two's complement by doing 1011 to 0100 and then adding 1 to get 0101. Then I add the first number to the converted two's complement number:

$1110$

$+$ $0101$

$-----$

$0011$

0 + 1 = 1

1 + 0 = 1

1 + 1 = 0 carry 1

carry 1 + 1 + 0 = 0

For a final answer of $0011$ which is 3 in decimal, however, the answer in my book says it should be 2 or 0010...?

# Answer
Your book is wrong and what you are doing is correct.

1110 is 14 in decimal and 1011 is 11 in decimal. Hence the answer should be 3 i.e. 0011
> 1 votes

---
Tags: computer-architecture, binary-arithmetic
---


# Question
Title: Is the language of DFAs which do not accept themselves recognizable?
I understand how a the language of turing machines which do not accept themselves is not recognizable but I'm not sure if the same proof could be used to describe a DFA... i.e a proof by contradiction in which a recognizer M recognizes a TM which does not accept itself on input ...creates a contradiction in which if M accepts then M does not accept itself.

# Answer
DFAs always terminate, so if you want to check whether a given DFA accepts or rejects a given word (say its representation), just run it on the word. You can even do this in polynomial time.
> 3 votes

# Answer
interesting idea! havent seen this in the literature but maybe its somewhere. what youve asked is a great simpler conceptual stepping stone into more advanced areas of TCS such as undecidability.

in a word: yes! there are multiple ways to do this. for example: choose any enumeration of all the words in the regular language $L$ where $w\_i$ is the $i$th word $w\_i$ in the language. then change the $i$th single symbol in each word to another symbol in the same alphabet to create $L'$. by diagonalization, $L'$ cannot be regular. this works for all languages that have at least two symbols. also note that in a sense, all regular languages with an arbitrary number of symbols can be "emulated" by an equivalent language of binary strings only.
> 0 votes

---
Tags: computability, turing-machines, undecidability
---


title: processes response time confusion

text:
# Question
Title: processes response time confusion
An OS contains 10 identical processes that were initiated at the same time.Each process contains 15 identical requests. Each request consume 20 msec of CPU time.A request is followed by an I/O operation which consumes 10 msec.The CPU scheduling overhead is 2 msec. The system uses Round Robin scheduling with the time quantum of 10 msec.

Q1) What is the response time of 1st request of last process ? A) 210 msec B) 140 msec c) 230 msec D) 240 msec

Q2) The subsequent request of the processes receives a response times of A) 110 msec B) 220 msec C) 230 msec D) 240 msec

Ans: Q1) D

```
 Q2) C

```

What I thought :

For 1 process, there are 15 request so 15 * ( 20 + 10) = 450 msec But all answers are so small than this approach. So no need to think about further i.e. CPU overhead then 2nd...3rd...processes.

Here my problem is I didn't get the concept behind this question properly. CPU overhead ( i.e context switching ) will take place between 10 processes or each process's 15 request. So please tell how this scenario will work.

I didn't get the meaning of 2nd question.

# Answer
Hint : Try to understand more about context switching. Context switching takes place between 10 processes. (And you can forget about those 15 requests, instead consider each process needs 15 * 20 msec of CPU time)
> 3 votes

---
Tags: operating-systems, memory-management, process-scheduling, threads
---


title: Infinite union of recursive languages

text:
# Question
Title: Infinite union of recursive languages
I'm trying to figure out how to prove or disprove the following statement:

> Infinite union of recursive languages is recursively enumerable.

I know how to prove that infinite union of regular languages is not recursive, but I can't figure out how to prove the statement above. Intuition is telling me that the statement is true, but I'm not sure. Does anybody know how would I go about it?

Any help is greatly appreciated.

# Answer
Choose an arbitrary language $L$ that is not RE. Denote $L\_w=\\{w\\}$ the language containing a single word $w$. Clearly, $L=\bigcup\_{w\in L} L\_w$ is a union of infinitely many regular and recursive languages.
> 5 votes

---
Tags: computability, undecidability
---


# Question
Title: Converting a recursive algorithm to a runtime function
```
void Sort(int A[], int left, int right)
{
    int p;

    if (left < right)
    {
        p = (right + left + 2)/3;

        Sort(A, left, left+p-1);
        Sort(A, left+p, left+2*p-1);

        MergeSort(A, left+2*p, right);

        Merge3(A, left, left+p, left+2*p, right);
    }
}

```

I need to convert this function into a mathematical expression in order to solve it's run-time complexity.

I know that `MergeSort()`'s complexity is of $\Theta(n \log n)$ and that `Merge3()`'s complexity is of $\Theta(n)$.

I can't figure how to transform this into a recursive mathematical expression.

# Answer
The key is to use `right - left` as $n$ for the parameter of the runtime recursion. What is the size of the subparts?

Closer hint:

> Note that the algorithm separates the input part of the array in three approximately equal-sized parts; the first two are sorted recursively, the third with Mergesort. This should be reflected in your recurrence.

Almost finished:

> Assuming `Merge3` runs in time $\Theta(n)$ und `MergeSort` in time $\Theta(n \log n)$, you get a recurrence of the form
> $\qquad\displaystyle T(n) \approx 2T(n/3) + \Theta(n) + \Theta(n/3 \log(n/3))$
> since all parts have size $\approx p \approx n/3$. Solve this with the Master theorem and flesh out the details.
> 1 votes

# Answer
Hint: Usual merge sort takes a list of size $n$, divides it into two halves, sorts the two halves recursively, then merges them in $O(n)$. Your routine take a list of size $n$, divides it into *three thirds*, sorts the first two recursively and the last one using mergesort (this detail is a bit strange; you'd expect all three parts to be sorted recursively), then merges them in $O(n)$.
> 0 votes

---
Tags: algorithm-analysis, runtime-analysis, recursion
---


title: Show 1-in-3 SAT

text:
# Question
Title: Show 1-in-3 SAT
1-in-3 SAT is the set of 3CNF formulas with no negated variables such that there is a satisfying assignment that makes exactly one variable in each clause true. Show 1-in-3 SAT is NP-complete

Plan on doing a reduction from 3SAT.

My confusion arises from the "no negated variables". You need some way of representing negated variables. How do you do that? I can do the reduction from 3SAT to 1-in-3 SAT without the restraint that there are no negated variables. I'm just not sure how to do it with this constraint.

# Answer
*My confusion arises from the "no negated variables".* This is the point of the question. You need to figure out a way to simulate negated variables.

Hint: One way is using a "gadget" that forces $b = \lnot a$ for some variables $a,b$. You can start by coming up with a way of forcing certain auxiliary variables to be True or False.
> 4 votes

---
Tags: np-complete
---


title: Courcelle's Theorem: Looking for papers

text:
# Question
Title: Courcelle's Theorem: Looking for papers
I am looking for an easy and introductory paper on the proof of Courcelle's Theorem. I am also interested in its connection to parameterized complexity regarding the treewidth.

I am only a beginner in this field.

Any suggestions?

# Answer
> 4 votes
There's a soft introduction in Rolf Niedermeier's book Invitation to Fixed Parameter Algorithms. Daniel Marx also has quite a few slides available on his homepage that contain short examples of modeling a problem in MSOL. One set of relevant slides is here. For more links, see a related question on CSTheory.

# Answer
> 4 votes
Courcelle's Theorem is one of the things that is better explained (compared with Niedermeier's book) in the book of Flum and Grohe (see the treewidth chapter), since model checking problems etc. are covered in detail there. By the same authors and Frick there is also a generalization of Courcelle's Theorem: Query evaluation via tree-decompositions. You might also look at similar meta theorems for clique-width and shrub-depth.

Also look here for a short overview of some of Courcelle's earlier papers.

---
Tags: complexity-theory, graphs, reference-request, discrete-mathematics, parameterized-complexity
---


# Question
Title: Turing Machine Encoding and Complement of the Diagonal Language
In trying to understand how Turing Machine encoding works, there is a question that I have come across that goes something like this:

Given that the diagonal language, $L\_d = \\{ w\_i \mid w\_i \space is \space not \space accepted \space by \space M\_i \\}$, what is the first string of the encoding of the complement of $L\_d$ which is $\bar{L\_d}$?

I am assuming also that this is operating with the alphabet of $\Sigma = \\{0, 1\\}$. Is there any way that it is even possible? I am confused also since $L\_d$ is an undecidable language how this is possible?

Also by encoding I think that the question is referring to binary encoding with a tape alphabet $\\{0, 1, B\\}$ with Turing machine $M$ defined as:

$M = \< Q, \\{0, 1\\}, \\{0, 1, B\\},\delta,q\_1,B,\\{q\_2\\} \>$

with moves defined by:

$\delta(q\_i,X\_j) = (q\_k,X\_n,D\_m) \rightarrow 0^i10^j10^k10^n10^m $

where $X\_1 = 0, X\_2 = 1, X\_3 = B$ and Direction is given by: $D\_1 = L, D\_2 = R$,

and the Binary encoding of $M$ as $\<M\>$: $111 \space move\_1 \space 11 \space move\_2 \space 11 \space ... \space 11 \space move\_{last} \space 111$

**Update:** If my understanding is correct, the correct encoding should represent a Turing machine which accepts every string since originally we do not accept any string? How would one go about formulating an encoding for such a Turing machine? Does it have to be a unique encoding, or does it just imply that any Turing machine that accepts every string is valid?

# Answer
> 1 votes
The following hint repeats my comments and assumes that the question asks for the first encoding of a Turing machine which is in $\overline{L\_d}$.

Hint: Make a list of the first few encodings of Turing machines, in lexicographic order. For each one, check whether it's in $\overline{L\_d}$. The first one which is in $\overline{L\_d}$ is the answer.

By the way, how does your encoding handle termination? Does it mark accepting/rejecting states in some way, or does it use another convention?

---
Tags: computability, turing-machines
---


title: Time Complexity of Regular Languages

text:
# Question
Title: Time Complexity of Regular Languages
I wonder how I can go about proving that if a language L is decidable in o(nlog(n)) then L must be regular.

I should probably mention that by "decidable" I mean "being decidable by single-tape deterministic turing machine".

Thanks and regards Guillermo

# Answer
This is a classical result of Kobayashi, On the structure of one-tape nondeterministic Turing machine time hierarchy, Theorem 3.3 on page 188. The idea is to use crossing sequences: you show an upper bound $O(1)$ on the size of any crossing sequence, and then use an argument of Hennie, One-tape off-line Turing machine computations, Theorem 2 on page 561, to conclude that the language accepted by the machine is regular.
> 8 votes

---
Tags: regular-languages, time-complexity
---


title: Bipartite Graph Game

text:
# Question
Title: Bipartite Graph Game
So say we have a bipartite graph G=(X,Y,E). Let's make a game out of it.

I go first. I pick a node in X. You go next. You pick a node in Y that is connected by an edge to the node I picked. Next it's my turn. I pick another node in X (must be a new one that hasn't been used before) that is also connected to the node in Y you just picked. We continue playing in this manner, until someone cannot pick a node (i.e. all edges out of the current node have already been used). When that happens, the person who cannot pick a next node loses.

I'm supposed to find a polynomial time algorithm to decide which of the two players (you or me) can force a "win" for a given bipartite graph.

I'm stumped. I've approached this in many different ways, including the following two:

1) 1) each node in the xy "path" played will use two edges, except for the first and last nodes which will only use one edge. Idea: add one new node on each side of the bipartite graph, and connect to all opposite nodes. Then check for a perfect (or maximal) matching twice, removing the edges used in the first perfect (maximal) matching when finding the second one. I don't think this really helps us with the problem, though, as there are many different nodes you could visit next given a current node.

2) A second idea was to work with alternating/augmenting paths (as we "zig-zag" between the two sides). I again got stuck since at any given node there are many possible nodes to visit next.

Does anyone have any suggestions for this problem? I'm thinking it has to do with matching, but I could be wrong.

Thanks in advance!

# Answer
> 1 votes
I've found the solution here: solution courtesy of Dartmouth

Essentially, the second player wins if and only if there's a perfect matching.

# Answer
> 2 votes
Let me spell out the solution.

We first show that Player 2 wins if there is a perfect matching $\pi$. Player 2's strategy is very simple: if the current path ends at a vertex $v$, she choose $\pi(v)$. Induction shows that $\pi(v)$ is never taken, since the edges chosen by Player 1 never belong to the perfect matching. Player 2 never gets stuck, and so wins.

The more complicated case is when there is no perfect matching. Let $\pi$ be a maximal matching, and let $x \in X$ be a vertex not in $\pi$. Since $x \notin \pi$, the edge $(x,y)$ chosen by Player 2 is not in $\pi$. If he can, Player 1 now choose $\pi(x)$, and induction again shows that Player 2 never chooses edges in $\pi$, and so Player 1 can choose an edge in $\pi$ as long as there is one adjacent to the vertex that Player 2 chose. If Player 1 gets stuck then the edges chosen by the players trace out an alternating path with Player 2 having one extra edge, showing that $\pi$ wasn't a maximal matching.

---
Tags: graphs, combinatorics, computer-networks, bipartite-matching
---