# Question
Title: Why do we need full-fledged workstations running massive OSes with massive software?
I've grown up with computers. While watching old computer TV programmes and documentaries and reading the news about constant issues with these modern systems -- everything from the sheer amount of change/bloat/costs to all the security and privacy issues -- one thing that really stikes me hard is:

Why do normal people need computers that are so powerful and complicated?

In decades past, we used simpler, less powerful computers to perform all kinds of tasks, without the issues we face today.

I'm not suggested we swap out current computers for thin clients. I'm simply saying that current computers seem more powerful than necessary for vast majority of tasks that any person employed by an average company would logically need.

Even in the early 1990s, computers had advanced to the point where "all basic input/output tasks" were "solved". If I were running a company, I would create a minimal computer terminal which runs a minimal OS, and which just boots up and displays a "browser-like" interface that talks over HTTPS to my "mainframe". I'd use a simple username/password system, with no password resets or two-factor auth, and once logged in, the employee would see only the sections that are relevant for them, coded by me. For example, a secretary would see a basic form where she can input appointments, list current ones, etc. A different kind of employee, whose job is just to deal with customer support, would only see a minimal list of current support tickets and only have the ability to respond to these in a manner which cannot be misunderstood or abused. I'd log every action so that I can later look up exactly who messed up or went rogue.

I notice that modern systems don't seem to work that way. Instead, we have full-fledged PCs with expensive, bloated, and insecure Microsoft or Linux software. We spend enormous amounts of time, effort, and money to educate employees on how to use it, maintain it, and deal with all the problems that inevitably arise from exposing the general public to such complicated systems.

Why is this? Why is the only choice between a complex Windows system, a fragile Linux, or some kind of ChromeOS thin client that exposes my data to Google? Why don't we have a privacy-respecting, minimal thin client OS that can't do anything but display basic HTML, basic CSS and connect over HTTPS, has no system storage or ability to change it, and is just something you hook up to a standard display and network cable and mouse and keyboard.

I realize one still needs to administer the server/mainframe, but presumably this could be done by skilled professionals, rather than the general public.

Can you help me understand why computing works this way today?

# Answer
> 60 votes
You are conflating a number of issues here.

# Why does my software have all these features to begin with?

Because other computers' software has those features, and network effects punish any software developer who doesn't follow the herd.

Let's take an example from your question: *Why does my web browser need to do anything other than basic HTML and CSS?* Well, have you ever tried browsing the modern internet with all JavaScript disabled? It's functionally unusable. The problem is that, once JavaScript existed in a widely used browser (Netscape), people started using it in their webpages. That meant that other browsers had to add support for it to prevent their users from complaining that webpages are broken. And once more users had support for it in their browsers, more webpage authors started assuming that users had it. Round and round the positive feedback loop goes.

Software developers have strong incentives for adding features to software, and strong disincentives for removing them or even changing them.

It's taking 25 years to kill Flash Player, despite it being an incredibly complicated, bug-ridden, security nightmare black box that Adobe themselves no longer wants anything to do with. You know that all hell is going to break loose on December 31, 2020 when the plug finally gets pulled and people can no longer play their beloved Flash games from 2001.

# Why do employees of a company need to have full PCs rather than dumb terminals that can only view intranet pages?

Because intranet pages work great until an employee needs to do anything other than the specific tasks that the programmer has predetermined are that person's job.

What happens when someone else (either inside or outside the company—let's call her "Alice") wants to send you a presentation to review and edit? Every person at every job role at my company has had to do that at some point—managers, engineers, administration, facilities, you name it.

You can receive Alice's presentation file on your internal webmail, but you need some way to edit it. And that means your computer needs to be able to edit PowerPoint files, because *that's what everyone uses*. And PowerPoint files are *ludicrously* flexible in what sort of content can be contained in them. So we're back to the network effects problem. If Alice sends me a PowerPoint file and I can't edit on my computer because it uses features that my software doesn't support, that's *my* problem as far as Alice is concerned.

It's functionally impossible to forsee all the things that someone might need to do for most modern jobs, for the simple reason that if it were possible, that job would probably already be fully automated. And that's not even accounting for the fact that many companies allow their employees to use company computers for all sorts of things that are not strictly part of their job description, such as streaming music.

There's also a more general principle here. As you correctly point out, most PCs are "fundamentally overpowered and overcomplicated for the **vast majority of tasks** that any person employed by a normal, non-highly specialized IT company, or government entity, would logically need." The problem is that a computer that does all the tasks you need 95% of the time but is useless the remaining 5% of the time when you need to do something weird and specialized—is useless as a computer.

I've heard it said that in software design, 10% of the features cover 90% of what any user needs, but that the remaining 10% of what any user needs is *different for each user*. If you take the set of features used by each user and intersect all of these sets, the result is not sufficient for *any* user.

# "This interface would have a simple username/password system, with no demands to reset passwords or 'two-factor auth' or any of that nonsense"

This gets its own subheading, because this is a totally separate class of issues from everything else you mention. Go over to Security.SE and read about why these things exist. There are very specific reasons for these security practices, that are totally orthogonal to any discussion about complexity of software.

# Answer
> 13 votes
Since the other answers go pretty well into why companies just buy general purpose computers, I wanted to give an answer about security. In a lot of ways, it's easier to secure a system you know is insecure, than to secure a system you are pretty sure is secure but don't know in what ways it might be insecure. Windows 10 may have security vulnerabilities, but Microsoft has a passable track record of fixing them soon after they become well-known, and in many instances ahead of any actual use of the vulnerability in the wild. Windows 10 is also used by a huge share of the market and has security specialists analyzing it all the time, so vulnerabilities are more likely to be caught by the "good guys" and sent to Microsoft for patching. If on the other hand your company uses an OS that only does one thing but only a few companies use, you cannot be all that sure that the one thing it does is secure. Windows makes a reasonable guarantee that if someone is running as an unprivileged user, they won't be able to make privileged changes to the system, so the security team can be reasonably sure about what a malicious program or user can and can't do, and the fact that it's maintained by a reputable company and tested by lots of people unaffiliated with that company makes it easy for a security team to palate using.

There's also a question of training. Most people use Windows at home, and Windows and Mac are similar enough that people can use them interchangeably for basic use. So, your security training can focus on the important stuff - "Use a strong password, use different passwords for different sites" (or give them a Password Manager and show them how to use that, there may not be one available on your off-brand OS), "How to spot phishing emails," etc, as well as training for your particular company's processes, and you don't need to spend any time training your employees on how to do basic actions like opening files. Plus, by using the same OS as the company they are coming from, you get the benefit that they likely already have training from their previous company on the same standard policies and advice.

This does not just apply to regular employees, but your security team and sysadmins too. The fact is, if everyone trains on the same few OS's, then there is a much bigger pool of experienced candidates who can staff your IT department. On the other hand, everyone has to take remedial training to understand your special OS if you use one, increasing cost to the company.

Finally, I wanted to touch on a basic idea of security you have that is wrong. It seems like you believe the best way to secure a system is to lock it down as tight as possible and make it difficult to use. There is a common security approach that revolves around "three pillars" - Confidentiality, Integrity and Availability. The third one is important here, the purpose of security isn't just to prevent unauthorized users from modifying or viewing data, but to keep the systems a company needs to function available for users. Sure, you could have systems that are in their own LAN with no Internet access, but what happens when someone needs to communicate with another company? You cannot open up the network since you designed it to have no Internet communication and therefore "This interface \[has\] a simple username/password system, with no demands to reset passwords or 'two-factor auth' or any of that nonsense". So, either your company is the only company in your sector that doesn't have email (or a website), or you have to find another solution. If you take the first option, your company won't exist in 3 months, so you'll have to go with the second option. Well, perhaps your security team won't come up with the solution, your users will. That solution will be doing everything over personal email (or we set up a company domain with our department's budget and use a cloud email service with it). It might be to contract with an external cloud service to set up a website. I've been the user that doesn't want to deal with the security team and creates this kind of "shadow IT", and I've been the guy who has to deal with the fallout of "shadow IT" that gets created in companies with insufficient Availability, so I know some of what users can do without the security team's consent. I'll leave you with a very relevant quote, AviD's Rule of Usability:

> Security at the expense of usability comes at the expense of security.

Actually, one last thing. You say

> Yes, there's still the nightmare of dealing with the actual "mainframe"/server (I honestly don't understand why even a massive company would require more than one in this day and age, given their immense power)

No sane company has only one data center - either they have at least two so that they have redundancy if there is a natural disaster, or they contract with a cloud provider who does that for them. If your employees at least have laptops that can do most basic functions, even if there is a problem with your network they can still work on things on their local computer, but if they have to be connected to the network than any network issue grinds your whole company to a halt.

# Answer
> 5 votes
"If I were running a company ... the employee would see only the "sections" that are relevant for them, coded by me."

You are not prescient. You cannot predict the future requirements of all your employees with sufficient accuracy to know the minimum set of "section" that are relevant or suitable for any given employee.

The work required to refine this impossible prediction is far outweighed by negative consequences of your self belief that you know how best to do everyone else's job.

# Answer
> 5 votes
> I'd use a simple username/password system, with no password resets or two-factor auth

Password resets are required somewhere because people forget passwords. 2FA is required *sometimes* because they leak, as it turns out that building software free of security bugs is incredibly difficult.

> and once logged in, the employee would see only the sections that are relevant for them, coded by me. For example, a secretary would see a basic form where she can input appointments, list current ones, etc. A different kind of employee, whose job is just to deal with customer support, would only see a minimal list of current support tickets and only have the ability to respond to these in a manner which cannot be misunderstood or abused. I'd log every action so that I can later look up exactly who messed up or went rogue.

This is indeed the standard IBM 3270 kind of workflow. Modern versions are available through things like SAP. Note that in order to do this, you have to have your own fully or mostly custom system with its staff of developers. And you have to have a process for making changes to the system, and then approving those changes.

Not to mention that the software required by specific jobs tends to be both complex and demanding - everything from "desktop publishing" to video editing to circuit design. There are a lot of these niches. It's much easier for there to be a few possibilities that everyone in the trade uses rather than each company having their own .. which requires a general purpose software platform.

It turns out that "enumerate all the possible required actions in advance" tends to both produce a huge list, and be incomplete. Requirements management is hard. That pushes up the cost of the solution. And the delay between a department requiring changes and them being implemented. Entire multi-billion-dollar software projects have failed due to poor requirements planning.

The two big revolutions against central mainframe style working, the "personal computer" and the "cloud", both came about as means of escaping the inefficiency and delay caused by central control of IT. You could place a fully *general purpose* system on your desk, and do anything without needing approval! The efficiency gains of this were enough to overturn entire industries. Cloud was even more revolutionary because you didn't even have to set up and maintain the system. All it requires is a manager with enough authority to approve invoices.

# Answer
> 4 votes
I would argue that the premise of the question makes a wrong assumption:

There is an enormous amount of people that use computers set up to perform a single task. Behind the scenes, they're generic systems running a full OS and having all capability, but the machine has been specialized for some tasks.

For example:

* Cashiers use machines which are commonly running Windows. They do not have access to the computer's OS: the machine boots up in the only interface they'll use during the day and they do not need all the complexity.
* In supermarkets, devices scanning for prices and even electronic scales are sometimes running a full OS, but the user doesn't see it.
* Your TV set-top box might be running Linux and could be doing a lot of things, but it is abstracted from you and you just see the interface designed for you.
* In many offices, people have access to a single piece of software, to perform their tasks, and never see the OS.

In the professional world, you have a lot of situation where the complexities of the system are hidden from the user because they are locked in a single software (cashiers are the most obvious example).

When the work is less repetitive, people will have access to the computer OS because they will need a variety of software to perform their tasks; in this case, they'll need some basic computer skills.

For economical reasons, it's better to get standard PCs with one of the common OS and then specialize as much as you need from there. This is easier to setup, maintain, update, etc than a custom solution that might be locked in by a vendor.

Some companies, like http://www.citrix.com for example, are providing solution that turns a full flexible PC (read cheap and common computer) into a specialized device that will run specialized apps so that employees have all technical problems abstracted from them.

As I was saying at the beginning: I believe the premise of the question is flawed in the sense that there are millions of flexible computers set up to let employees just use the features they need and nothing else. In that context, all complexity is abstracted and usability is directly linked to the designed of the apps they'll be using.

When it comes to personal computing, it's a different story since every user has his/her own use cases.

# Answer
> 3 votes
*TL;DR: Modern computers are general purpose tools. They have a huge diversity of capabilities which will never be used simultaneously. All of these capabilities integrate with each other which creates huge complexity. More specialised systems are not created because generally it is more expensive to make and sell a reduced feature system than an existing general purpose system. Plus, you might need some features that you did not expect, and in that case it is nice to have bought the general purpose system anyway. **But check out KolibriOS**.*

Your question touches on 2 issues so my answer has two parts.

Modern computer systems (ie. hardware + software) are general purpose tools. You can create a text document in your preferred editor and open a web browser (at the same time). You can then copy some Thai text out of the web browser and paste it into your text document. It will display how it will actually look on a printed page. You can then save your text document to your preferred form of media, for example flash drive. If you make a mistake and put the wrong drive in, you can take it out and put another one in, it will not crash the computer. You can then open the text document on a different computer with a different operating system with a different working language in a different editor, and your Thai text will be displayed correctly. If the Thai text is copied from the high scores table of a 3d game in your browser, you can do that. This kind of workflow was not possible in previous eras of computing. Each of these capabilities is complicated to implement. To implement them so they simultaneously integrate is even more complicated. The more complicated the system the less efficiently we will typically implement it, so it becomes more complicated still. This explains where the complexity comes from.

Your question also touches on why we have complicated systems when we do not need them. Why can computers play 3d games that will only be used in the office? Why can computers do encryption if they are only going to be used by one person offline? There are several aspects to this. The main one is that it is more expensive to make more specialised systems than to use a more general one that you have already. As to your example, if you already have a "full featured" authentication module, which is fully tested and widely used, very resilient against attacks and errors, it is easier to use that than to make a new one. Even if there are already configuration options available on the module to disable some features that are not needed, sometimes it is quicker just to leave them enabled! Also there is a convenience factor. If you plug in a wifi adaptor, you do not want to have to download and install drivers somehow before it will work. So the operating system providers just bundle up the drivers in the system.

But, while new capabilities are being added all the time, continuous simplifying of existing features and designs is being done also. It is a long task but I think it is progressing!

You talk about a thin client OS. But similar things already exist. For example KolibriOS. It may not be as minimal as you propose but it is closer. It is only 1.44 MB after all. Why not give that a try? I think you will soon come back to Linux or Windows or whatever you use. But maybe not! And if not that will be great!

# Answer
> 2 votes
Real-world software is not designed to run on a single computer, but on an ecosystem, meaning that it interfaces with other software components, based on standards that have all kinds of different governance structures behind them. Complex ecosystems like this evolve on their own terms, and solutions do not scale elegantly, but given enough time they may form intricate and elegant architectures. Given enough time. Can we speed these things up? That's the trillion dollar question.

Hardware also forms an ecosystem, but one on which the number and complexity of the interfaces is much simpler, mostly because we decided to externalize complexity to software, as much as possible. It could have been different, and it may be different in the future. In rigorous scientific terms, the distinction between software and hardware is not as simple and clear as it may seem at a first glance.

# Answer
> 2 votes
# Why not?

Many would dispute the weight of your criticisms.

> we have full-fledged PCs with expensive, bloated, and insecure Microsoft or Linux software

**Expensive?** GNU/Linux is free of charge; Windows comes bundled with most PCs often contributing less than 10% to the price (sort of.) Web browsers are free. Some applications aren't free, but if you don't install them you aren't affected by their bloat.

Yes, workplaces install big office suites instead of using a simple plain-text mail client for staff to send information between each other. You have to weigh this up against the added features. And the amount of training (per workflow) needed for using *simple* software isn't much less than for complicated software.

**Bloated?** That's a subjective term. Are you talking about poor performance? Or a user experience which is overwhelming for users? OSes certainly do a lot of things they didn't use to, and it slows them down, but boot times have improved over the decades (with the help of faster hardware) and generally OSes don't chew up much CPU.

Application software is the real culprit of getting slower and more bloated, partly due to the transition to "slower" languages (I'm looking at you, Python). This is a simple business case of "spend less on development, plus get less buggy software." (Very roughly speaking.) In the Free Software world, your pool of volunteers is limited so there's pressure to use languages where you can get more done, faster.

**Insecure?** Well, yeah. (But do remember that the number 1 security problem with a computer software is the human.)

> We spend enormous amounts of time, effort, and money to educate employees on how to use it, maintain it

**Training?** As I said, the amount of training *per workflow* is not that different. But software that has more functionality allows more workflows.

> deal with all the problems that inevitably arise

**Yes. More can go wrong.** There are so many more "broken" configurations. This is definitely expensive. Security problems are rife. This is something you really have to weight against the benefits.

To be clear, I'm unhappy with the sprawling resource usage of modern software, but I appreciate that due to practical concerns it's quite hard to fight it.

## Some less obvious benefits to "massive software"

* Aesthetic user experience (this has substantial psychological effects)
* Interfaces that are more "real world" (e.g. touch and pinch)
* Economies of scale of software development (software developed for thousands of clients is *so* much cheaper than one client developing in-house, even though you get features you don't need)
* Tools that are thoroughly tested at scale, instead of home-grown software to meet the same needs which is flaky
* Keeping pace with the growing complexity and competitiveness of the business world (to stay afloat businesses have to watch several social networks, review sites, who is viewing their website and why, lead-conversion funnels; this is all growing)

And IMO,

* actualising the tremendous potential of technology.

# Answer
> 2 votes
> the employee would see only the sections that are relevant for them, coded by me.

This is a very dangerous mindset for any programmer. A company is comprised of lots of people with various evolving and changing roles. You often cannot standardize their jobs to a degree to decide what is relevant for them all the time. There are some jobs where we try to, e.g. call centers but these are often hated by all because often the problems presented cannot be solved by the thought up answers.

To give another example: My wife is a biologist who analyses the genome for birth defects. For this, she needs Word, Excel and some special biologic tools .But she also does some marketing (writing info sheets for doctors), interfaces with an external company developing a CRM tool and covers different analysis which all need different tools, data and access. You can give her a general purpose PC and the ability to configure her PC like she needs or you can spend all of your IT Buget trying to keep her from doing it itself. Her company chooses the latter and loses people and money to this.

# Answer
> 1 votes
What you were asking for in the "If I were a manager" part is in fact a thin client, and they were made quite for the reasons you named. Beside the huge mainframes and TTY terminals of the stone ages, in relatively recent past there was a very solid platform called Sun Ray as a terminal able to display X11 sessions from a Linux or Solaris server (and related to it, originally Tarantella's Sun Global Desktop for the browser-based remote desktop/app access, and later Sun VDI for dynamic per-employee VMs). The benefit here was that the "Desktop Terminal Unit" had no mechanical parts and no brains, it was on your desk for 10-15 years and as servers and technological abilities (X11, browser, vdi, ...) behind it were upgraded your desktop unit never had to change. And if some condensor did die, you just picked another DTU from the closet and plugged it in, and the user with their smartcard had their same session continued instantly. With about 400Kb(!) of firmware making it a remote video/keyboard/usb connection it virtually had no attack surface (marketing boasted just 4 issues found over almost 20 years on the market, 2 of which were found internally and never reached the open market), and had a good seating in companies, banks, military... until literally one day an Oracle exec said they disband the project, ciao to the team.

A modern equivalent is a small terminal computer with minimized Linux or similar distro, though not in Sun Rays' range of lack of attack surface, but also offloading (much of) computation and data to the secure central servers. Being a computer, they are more capable than Sun Rays for the modern office needs, from the useless video effects of transparent menus and window shadows, to the more useful video, VoIP etc. support and/or acceleration where supported by respective remote-desktop protocols.

I did not watch this area lately, so can't recommend what is good today. However, at the time of Sun Rays' untimely demise, many community members discussed migration to ThinLinc as their top choice; I'd assume this influx of geeks and ideas and battle-proven expectations could improve that ecosystem.

# Answer
> 0 votes
I just paid for a New Year's ball I will be attending with my wife. My iPad remembers my address. To enter my credit card, it suggests to scan the card which I did, just had to hold my card so that the camera can see it. The information is sent in a way that no hacker can get at it.

What kind of OS do you think is needed for that? For example, scanning that credit card and getting the number and expiration date from it, that requires quite a bit of software. And that's just a tiny example.

# Answer
> 0 votes
The comparative change has a much simpler drivers: commercialism and non-rigid work life. Nobody does the same task over and over as a job, because if they did it would be automated. And commercial software only works if whoever builds it finds a way to make money off of it, including data sale, product sale, network effect amplification and training.

What you describe is possible, but not realistic in the work environment of today, not even in a legacy top-down organisation where the workforce has no control.

# Answer
> 0 votes
There are already a lot of excellent answers that address the cs specific "science". I would like to answer a bit differently, by invoking a more general evolutionary analogy. It has been said\* that computers and their operating systems today are an innovation similar in impact to the impact electric motors had on society at the turn of the last century.

> My particular line of argument will be better served, however, by directing notice to the parallel between the modern computer and another general purpose engine, one that figured prominently in what sometimes is called the "second Industrial Revolution"-namely, the electric dynamo. (But, see also Herbert Simon, 1986.)

Back then, electric motors were big, expensive, stand-alone devices with lots of attachments one could use to power multiple other machines. Need to run a load of laundry? roll the motor over to the washing machine and hook up the belt. Need to cut some lumber? roll the motor over to the table saw and hook up the belt. Need to vacuum your floors? or knead bread? hook up the belt and connect the motor to the appropriate device. Over time however, electric motors got smaller, more efficient, more powerful, and much cheaper to produce. The trend continued. Today, we hardly think about all the "electric motors" surrounding us. We only think about the vacuums, refrigerators, and table saws; the tools we use that happen to be powered by internal electric motors.

A very similar trend is occurring with "computers". The "(computing) power" is disappearing inside the tools. (You already carry more computing power in your phone than (insert your favorite comparison here) and you can already buy a refrigerator that can send you emails). The days of the "general purpose OS" computer being a ubiquitous "stand alone" attachment (or host) for running "any" software are numbered.

When pressed, I imagine a future where people who "have a computer" actually have what would today be called a laptop or tablet "dock". Where the "dock" is their personal hardware/human interface to any software they might want to run. At a minimum the future "human interface dock" would just have audio and a touch screen interface; but the interface could also include keyboard, mouse, pen, touch, multi-screen, printer, network, scanner, etc... Then, similar to old-school video games, all "software" would actually be more-or-less self-contained "computers" that users plug into a "docking slot" (such that all "software" has a dedicated, known, tested hardware "engine" (inside the cartridge) that the "software runs on", and all interaction between the user and the software traverses standard, ubiquitous, I/O interfaces \[the only "software" in the "dock" is the various standard "drivers" for keyboard, mouse, monitor, whatever interface devices happen to be connected). Want to do "word processing"? plug-in the "Word" cartridge. Want to do "photo editing"? plug in the "Photoshop" cartridge. (Are you just editing "phone pictures" for Facebook? buy the 4GB cartridge. Are you editing professional images for print publication? buy the 64 GB cartidge) Want to do "Ultrasound"? plug in the "Sonogram" cartridge and the dedicated Wand. Etc. (Want to do both "word processing" and "spreadsheet-ing" at the same time, buy two or more "app docking slots")

The only reason NOT to build an electric motor into every washing machine and refrigerator is if those electric motors are bulky and expensive (so marketers want to externalize that cost). Once the price and efficiency fall into line, it's actually much cheaper and easier to build a washing machine and/or refrigerator with a dedicated internal motor "customized" to specifically power that specific washing machine or refrigerator model than to build one meant to run "universally" (meant to always run safely and correctly while hooked up to any third party's motor and/or belt assembly). The same logic already applies to "computers". The price, performance, and efficiency trends will continue along similar slopes.

The general situation you seek will become the norm. It's only a matter of time.

---
Tags: optimization, operating-systems, security, user-interface
---


# Question
Title: Matrix chain multiplication: Greedy approach
some suggested a thread in which the algorithm multiplies the 2 matrices with lowest values first. Mine is different: it divides by parenthesis the 2 matrices. And continues to the next section.

The problem is: finding the most efficient way to multiply a series of matrices together, using an algorithm of some sort, and comparing these algorithms to find the most efficient one.

The dynamic algorithm approach works at a time complexity of theta of N^3.

My question is, what is the runtime of this algorithm:

A= 5x2 B= 2x7 C= 7x3

1) First, find the matrix with the lowest dimension ( a matrix which has the lower number from the rows or columns of all the matrices).

\*If the lowest number is in the last dimension, it is the same like putting the entire sequence in parentheses.

\*There is no guidance as to what to do if the lowest number appears twice in the sequence, so I suggest the algorithm just takes 1 randomly.

2) Then divide the sequence to 2: (A)(B•C). The parentheses will close on the matrix from the right and open on the next matrix. This way they will divide the series to 2 parts.

Then repeat the process for the 2 parts. Stop when you have 1 (or 2) matrices in the sequence.

Is this algorithm optimal? It has to be better than N^3 (the usual algorithm)

# Answer
> 4 votes
Consider the product $ABC$, where

* $A$ is $5\times 2$
* $B$ is $2\times 3$
* $C$ is $3\times 100$

Your algorithm first computes $BC$ (600 products) and then $A(BC)$ (1000 products), for a total of 1600 products.

The optimal solution first computes $AB$ (30 products) and then $(AB)C$ (1500 products), for a total of only 1530 products.

---

Suppose that $A$ is $a\times b$, that $B$ is $b \times c$, and that $C$ is $c\times d$. There are two possibilities:

* Compute $AB$ and then $(AB)C$: cost is $abc + acd = ac(b+d)$.
* Compute $BC$ and then $A(BC)$: cost is $bcd + abd = bd(a+c)$.

The first option is preferable if $$ \frac{b+d}{bd} \< \frac{a+c}{ac} $$ or equivalently $$ \frac{1}{b} + \frac{1}{d} \< \frac{1}{a} + \frac{1}{c}. $$ For example, above we have $a = 5$, $b = 2$, $c = 3$, $d = 100$. Since $$ \frac{1}{2} + \frac{1}{100} \< \frac{1}{5} + \frac{1}{3}, $$ the order $(AB)C$ is preferable.

Your decision procedure would prefer this order if $c \< b$, that is, if $$ \frac{1}{b} \< \frac{1}{c}. $$ Your condition misses the contribution of $a,d$.

---
Tags: multiplication, matrix
---


# Question
Title: Inorder tree tranversal on binary search tree doesn't give the elements in order?
I have been told that inorder tree tranversal of binary search trees returns the tree elements in order. I came up with this binary search tree:

```
      20
    /
 10
    \
     26

```

However the inorder tree tranversal of this seems to be 10, 26, 20?! What is wrong here?

# Answer
This is not a valid binary search tree, since 26 is greater than 20 and is in its left subtree.
> 3 votes

# Answer
That is not correct BST as Narek mentioned. BST should be -

```
 20
/   \
10  26

```

For inorder traversal, start visiting tree from Top to bottom and left to right manner and print a node only when it is referenced 2nd time.

So, inorder traversal here would be 10,20,26.
> 1 votes

---
Tags: binary-trees, binary-search-trees
---


title: Gaussian noise: Image Processing

text:
# Question
Title: Gaussian noise: Image Processing
As we all know, Gaussian Noise follows Gaussian or Normal distribution, and that distribution follows a $BELL$ $CURVE$.

As we can see that most of the values are centered around the mean.

Now consider this image

When I add Gaussian noise to this image I get something like this

As we can see that the noise appears to be $UNIFORMLY$ $DISTRIBUTED$ throughout the image. There is no region where we can say that the **noises concentrated around the mean value**

So how can these be called Gaussian Noise?

The Code that I have used in octave is given below

```
 pkg load image;

I=imread('C:\Users\Hirak\Desktop\apple.jpg');
I=rgb2gray(I);

J = imnoise(I,'gaussian',0.02);
K = medfilt2(J);
imshow(J);

```

# Answer
The noise is Gaussian noise because the *values* you add to your existing images follow a Gaussian distribution, not the *locations* of where you add the noise - that is uniform (and not random at all - each pixel gets Gaussian noise added to it).
> 2 votes

---
Tags: image-processing, gaussian-noise
---


# Question
Title: You prove that vertex cover reduces to some problem A, does that mean that A is NP-Complete?
My question is essentially the title. Let's say you have some random problem A. You prove that Vertex Cover (which is NP-Complete) reduces to A. You know nothing else about A besides that Vertex Cover reduces to it. Does that mean that A is NP-Complete? Or because we don't know if P = NP, we technically don't know if A is in NP or P?

# Answer
> 4 votes
Let's start with the relevant definitions:

> A problem $A$ is NP-complete if:
>
> * $A$ is in NP, and
> * $A$ is NP-hard.
>
> A problem $A$ is NP-hard if for every problem $B$ in NP, there is a polytime reduction from $B$ to $A$.

Using these definitions, you can prove the following result:

> If a problem $B$ is NP-hard and there is a reduction from $B$ to $A$, then problem $A$ is also NP-hard.

Applying this to your problem, if there is a reduction from vertex cover to $A$, then $A$ is NP-hard. If $A$ is also in NP, then it is furthermore NP-complete. Whether P=NP or not has absolutely no bearing on this.

Note that there are NP-hard problems which are provably not in NP. For example, the halting problem is NP-hard, but is known not to be in NP.

# Answer
> 1 votes
If you show a *deterministic polynomial-time many-one* reduction from Vertex Cover to problem A, *and problem A is in NP*, then A is NP-complete. By definition, if A is NP-complete, that means that A is in NP and every problem in NP has a deterministic polynomial-time many-one reduction to A.

If P = NP, then every problem in NP can be solved in deterministic polynomial time. This means that every problem A in NP that has at least one accepting instance and at least one rejecting instance is NP-complete, because every problem B in NP can be polynomial-time many-one reduced to A by just solving B in polynomial time and choosing the appropriate A instance to return.

# Answer
> 0 votes
Yuval Filmus's answer is absolutely correct, but let me answer your questions a bit more directly.

> Let's say you have some random problem A. You prove that Vertex Cover (which is NP-Complete) reduces to A. You know nothing else about A besides that Vertex Cover reduces to it. Does that mean that A is NP-Complete?

No -- it means that A is *NP-Hard,* but not necessarily *NP-complete.* In particular, A might not be in NP. A could be much "harder", for example, exponential time or undecidable.

> Or because we don't know if P = NP, we technically don't know if A is in NP or P?

Whether P = NP doesn't matter here; what's important is that you only showed A is NP-hard, not that it is NP-complete. Remember, NP-complete means two requirements: first, A is in NP, and second, A is NP-hard.

---

By the way, even if P = NP, that doesn't mean that problems can't be NP-hard or NP-complete. Vertex Cover, for example, would still be NP-complete; it would just also be in P, so the notion of NP-completeness would not be as interesting or useful.

---
Tags: np-complete, np
---


title: Difference between task and process

text:
# Question
Title: Difference between task and process
I'd like to know which is the difference between a task and a process in computer science. I'm studying a course on real-time systems and there are some definitions that I don't know.

Thank you in advance.

# Answer
> 2 votes
The difference appears to be that "process" is a well-defined term with a specific meaning that is universally understood, whereas "task" is ambiguous and means different things to different people.

The following Stack Overflow questions on the same topic support this:

Microsoft Windows certainly conflates the two terms—the *Task Manager* is used to administer processes.

---
Tags: terminology, definitions
---


title: Is PREFETCH an asynchronous operation?

text:
# Question
Title: Is PREFETCH an asynchronous operation?
I often hear Prefetching as a technique for speeding up, for example, sequential memory access pattern. The prefetch should occur sufficiently far ahead in time to mitigate the latency of memory access, for example in a loop traversing memory linearly.

According to the famous "What Every Programmer Should Know About Memory" paper by Ulrich Drepper, it is written:

> This prefetching would remove some of the costs of accessing main memory since it happens **asynchronously** with respect to the execution of the program

*(emphasis mine)*

I could not find references on Google or Wikipedia corroborating or proving this. Does anyone know where I can find if this is true?

The only reasoning I can think of is rhetorical: it must be asynchronous b/c otherwise prefetching offers no benefit to sequential access... unless the execution time of prefetching a cache line is less than bypassing prefetch and placing the same cache line from RAM directly into cache.

# Answer
If it is implemented in hardware, prefetching is typically done asynchronously.

It's also possible for a compiler to insert extra prefetch instructions into the code. Thus, the initiation of the fetch is done synchronously, but then the memory access continues asynchronously.

See https://en.wikipedia.org/wiki/Cache\_prefetching.
> 3 votes

---
Tags: computer-architecture, cpu-cache, memory-access
---


# Question
Title: "higher intensity" and "high signal intensity" in images
I'm newbie in Computer Vision and image processing.

I'm reading the article "Automated White Matter Hyperintensity Detection in Multiple Sclerosis Using 3D T2 FLAIR" and it said:

> 2.2.4. WMH Segmentation with High Spatial Frequency Suppression
>
> White matter lesions have higher intensity and generally clear boundaries relative to the surrounding WM. Unfortunately, in the 3D T2 FLAIR images, the GM can also present with high signal intensity, especially in elderly people.

What does it means "higher intensity" and "high signal intensity"?

I think it means that white matter lesions are very white but I'm not sure because I don't understand why the use the words "intensity" and "signal" when they are talking about images.

# Answer
The intensity of a pixel is its value (e.g., from 0 to 255). For instance, in a black-and-white/grayscale image, pixel intensity 0 means the pixel is black, and pixel intensity 255 means the pixel is white; intensities in between the two are shades of grey.

"White matter lesions have higher intensity" means that the pixels in the area of a white matter lesion have higher intensity values.

In this context "signal intensity" is presumably a synonym for "intensity".
> 1 votes

---
Tags: computer-vision, image-processing
---


# Question
Title: Finidng edges of convexhull from rectangles
1. Green Boxes = rectangles
2. red dots = edge points
3. red lines = to be generated from convex hull algorithm

I have a problem with creating the convex hull algorithm. I want to select or collect all the edges from these rectangles and draw convex hull around through these edges (See red dots from the Image). To make my algorithm more efficient, I don't know how to deselect or eliminate the points (X black points) inside all rectangles.

Could someone give me a solution for this?

Thanks in advance

# Answer
> 1 votes
If you have $n$ rectangles, take the convex hull of the $4n$ points given by the corners of those rectangles. This gives you exactly what you want, and you can use any standard algorithm for computing the convex hull. There is no need to explicitly deselect individual corners -- let the algorithm for computing a convex hull take care of that.

---
Tags: convex-hull
---


# Question
Title: Does $P/O(1)$ equal to $P$ if solver needs to consider smaller inputs?
Suppose that $F$ is a problem such that for every $n$, there is a program of length $O(1)$, running in polynomial time to $n$, that solves $F$ correctly on all instances of size less than $n$. Can $F$ be solved in polynomial time? That is, does there exist a *single* polynomial time algorithm that solves $F$ on *all* instances?

# Answer
> 0 votes
Let $\\{P\_i\\}$ be the limits of programs, or to say, programs that appear for infinte times, then all of them solve $F$, and for each $size(x)$ at least one solve in $P$.

Now run all of them and use the eariest result, and we get a solution in $P$.

# Answer
> 4 votes
Suppose that $F$ is a problem such that for every $n$, there is a program of length at most $C$, running in polynomial time, that solves $F$ correctly on all instances of size less than $n$.

Let $P\_n$ be a program of length at most $C$, running in polynomial time, that solves $F$ correctly on all instances of size less than $n$. Since there are only finitely many programs of length at most $C$, there must be a single program $P$ that occurs infinitely often as $P\_n$. This program solves $F$ in polynomial time for *all* instances.

---

If we change $O(1)$ to *any* bound $f(n) = \omega(1)$ computable in $\mathit{poly}(n)$ time, then we can easily construct undecidable problems which are computable in this model. We can assume that $f$ is monotone and has no jumps (otherwise take $g(n) = \min(\max(f(0),\ldots,f(n)),g(n-1)+1)$). For an undecidable $S \subseteq \mathbb{N}$, consider the following language: $$ L = \\{ x \in \\{0,1\\}^\* : f(|x|) \in S \\}. $$ Since $f$ is monotone, if $|x| \leq n$ then $f(|x|) \leq f(n)$. Hence there is a program of length $f(n) + O(1)$ that solves $L$ correctly on inputs of length at most $n$. Conversely, since $f$ has no jumps, for each $m$ we can find a value $n$ such that $f(n) = m$, and this gives a computable reduction from $S$ to $L$, showing that $L$ is uncomputable.

---
Tags: complexity-theory, time-complexity, complexity-classes
---


# Question
Title: Is it feasible to solve this subset cover problem with SAT solver?
The problem is to find $\mathcal{S}$, a minimal collect of subsets of $\\{1,\dots, 17\\}$ such that the two conditions are satisfied:

1. if $S \subseteq \mathcal{S}$ then $|S|=6$;
2. for any $A \subseteq \\{1,\dots,17\\}$ with $|A|=3$, there exists a $S \in \mathcal{S}$ with $A \subset S$.

See here for a related combinatorial problem..

I think this can be formulated as a Min SAT problem.

For each $S \subseteq \\{1,\dots,17\\}$ with $|S|=6$, we introduce a variable $X\_S$. And for each $A \subseteq \\{1,\dots,17\\}$ with $|A|=3$, we introduce a clause $$ \vee\_{S: A \subseteq S, |S|=6} X\_{S} $$ Then in principal we can use a SAT solver to find the minimal number of $X\_S$ that needs to be true to satisfy all the clauses.

This needs $\binom{17}{6}=12376$ variables, $\binom{17}{3}=680$ clauses of length $\binom{17-3}{3}=364$.

I have very little experience in actually using SAT solvers. So is this actually worth trying on my laptop or there's no hope at all?

——-

Update

Turn out there are many research on set covering. It seems that I was over ambitious to try to solve the problem for the parameters (17, 6, 3).

It is already an open problem for (12, 5, 3).

See here for more details.

———

Update 2

Tried to write everything in pure SAT and it’s quite a bit **faster** using cadical than z3.

Also, it is significantly faster to find a solution than to show no solutions exist.

I tried to break the symmetry by adding the constraints that the first and the last subset in lexicon order must be selected.

# Answer
> 3 votes
Optimization with SAT is usually referred as MaxSAT instead of Min SAT. In particular, I suggest looking for solvers for "weighted partial MaxSAT", for example MaxHS and RC2.

The problem size you have is fairly small in the context of modern MaxSAT-solvers, so yes it is worth trying. There are no guarantees that the solver will work efficiently, and it is very hard to predict if it will work efficiently, so the best thing to do is to try.

# Answer
> 3 votes
With SAT, it can be challenging to predict what will be feasible and what won't. It's worth a try.

I would suggest that, instead of MinSAT, you first try using binary search on $n=|\mathcal{S}|$, the number of sets you need. You can use an at-most-$n$-out-of-12376 constraint on your $X\_S$ variables. There are several techniques for encoding that in SAT, though in practice I would first try using PbLe with the Z3 solver.

Your problem has a lot of symmetry. SAT solvers can sometimes have difficulty with symmetry. You might try to do as much as you can to break the symmetry. For instance, without loss of generality we can assume that $\\{1,2,3,4,5,6\\}$ is one of the sets (otherwise permute all the numbers so it is), so you might hardcode this fact into your SAT instance. The more such lemmas you can prove, the better the SAT solver might perform.

You could also encode the sets differently. Let $S\_i$ denote the $i$th set that is chosen by $\mathcal{S}$. Introduce variabless $x\_{i,j}$ to indicate that $j \in S\_i$ and variables $y\_{i,A}$ to indicate that the $A \subset S\_i$, for each $A \subseteq \\{1,\dots,17\\}$ with $|A|=3$ and each $i \in \\{1,\dots,n\\}$ and each $j \in \\{1,\dots,17\\}$. Add a clause $\bigvee\_i y\_{i,A}$ for each $A$ to ensure that each $A$ is covered by at least one set. Add a 6-out-of-17 constraint for each $i$ to indicate that exactly 6 of the $x\_{i,j}$'s are true. Finally, add constraints to enforce consistency between the $x$'s and $y$'s. In particular, for each $A=\\{a\_1,a\_2,a\_3\\}$, add clauses $\neg x\_{i,a\_1} \lor \neg x\_{i,a\_2} \lor \neg x\_{i,a\_3} \lor y\_{i,A}$ and $\neg y\_{i,A} \lor x\_{i,a\_1}$ and $\neg y\_{i,A} \lor x\_{i,a\_2}$ and $\neg y\_{i,A} \lor x\_{i,a\_3}$. This will require about $(17+680)n$ variables and $4 \cdot 680 n$ clauses (not counting the $n$ 6-out-of-17 constraints); since I expect $n \approx 35$, this is about 24K variables and 100K clauses. That's more clauses than your encoding, and it has even more symmetry, so it might perform worse -- though they are shorter clauses, and it's hard to predict which encodings will work best with SAT, so often some experimentation is needed.

You could also try expressing this as an ILP instance instead of SAT.

---
Tags: combinatorics, satisfiability, sat-solvers
---


# Question
Title: How does C++'s type checking work when passing overloaded or templated functions as parameter
As I understand, C++ in general features 'one-way' type checking. That is checking the sub-expressions and get their types, and see if the types so far satisfy the constraints imposed by the current expression node. It's an algorithm progressing from bottom to top.

However, C++ also features overloading and template. When you pass such a function directly as the argument to another function, during type checking we cannot immediately get the type of the sub-expression since it is overloaded or using template. So how does it work?

It's possible that C++ does more than 'one-way' type checking. If that's the case, please explain to me how the feature is implemented.

# Answer
> 1 votes
Type checking occurs when the template is **instantiated**, so the compiler knows the types by then.

Overload resolution happens at call site. The sub-expressions are the arguments, when their types is known the resolution can occur, hence giving the type of the call expression (that is, the return type).

Neither templates nor overloaded functions are first-class citizen constructs than can be passed around, so I am not sure what you mean by "such a function".

---
Tags: type-checking, c++
---


title: Classifying partially labeled data

text:
# Question
Title: Classifying partially labeled data
I have 1D data for binary classification. Data includes about 10000 samples and each sample has the length of 120. Data is only partially labeled (for about 20% of samples, I am sure about the label) and I cannot label samples manually for thoes not labeled. Every ~60 samples come from same recording and therefore belong to the same class. I have tried k-mean clustering and in most cases results matches the labels. What semi-supervised learning algorithm is suitable for this problem?

There are 142 different recordings, each repeated ~60 times. About 20% (28 recording) are labeled. Samples are noisy so I need to average every 5-10 of them. I extracted 10 features based on amplitude of signal for clustering. I expect 60-80% of recordings belong to class I.

# Answer
> 1 votes
One way to interpret this as that it's indicating that points that are nearby in feature space are likely to have the same labels. So, a classifier that takes this into account might do well.

Based on that, you might try a $k$-nearest neighbor classifier. Basically, you classify each test point by finding the $k$ most similar labelled samples, and then using some kind of voting scheme among the corresponding $k$ labels. I anticipate this might give quite good results.

Alternatively, another way to use this is to use some kind of active learning algorithm to help you choose a small subset of the 10000 samples to manually label, with the goal of choosing those smartly so those additional labels help improve the performance of your classifier as much as possible. One standard approach is to train a classifier on the labelled instances, apply it to all the remaining instances, pick out the 20 instances that the classifier is least confident on, manually label those 20 instances, add them to the training set, and repeat. In your situation, a possible approach is to train a classifier on the labelled instances, apply it to all the remaining instances, from each cluster randomly sample a few instances whose predicted label disagrees with the majority label for that cluster, manually label all those instances, add them to the training set, and repeat. Or, you could train both a normal classifier and a $k$-nearest-neighbor classifier on the labelled samples, apply them to all remaining instances, find ones where the two classifiers disagree on their prediction, randomly sample 20 of them (possibly using a farthest-first heuristic to maximize their diversity), manually label them, and add them to the training set and repeat.

You might need to experiment a bit to see what works best.

---
Tags: classification
---


# Question
Title: Zero-knowledge proof of $\beta\eta$ equality
Is there some way to give a zero-knowledge proof that two $\lambda$-terms are convertible, i.e. equal modulo $\beta\eta$?

A usual (and not zero-knowledge) proof that two terms are convertible is a path of terms between the two such that each step is either a single $\beta$ reduction or a single $\eta$ expansion, or the reverse of either one. Testing that two terms are convertible is only semi-decidable because no bound can be given a priori on the length of that path.

The question is the following: Alice has two $\lambda$-terms $t\_1$ and $t\_2$, and a proof that they are convertible. Can she convince Bob that they are convertible without helping Bob find the path?

One way to do this would be that Alice gives Bob a third term $t\_3$ that she knows is convertible to the two others, and then Bob gets to ask her either to prove that it's convertible to $t\_1$ or that it's convertible to $t\_2$. I'm not sure how the term $t\_3$ can be chosen though.

# Answer
I doubt that a zero-knowledge proof is possible, because it seems likely that any finite proof will leak at least partial information about the length of the path that converts $t\_1$ to $t\_2$, and hence won't be zero-knowledge. In particular, suppose Alice and Bob's interaction takes $T$ time steps. Then in any reasonable proof I can imagine, Bob would be able to infer that $t\_1$ can be converted to $t\_2$ using a path of length at most $T$. This is partial knowledge, because there exists a pair $t\_1,t\_2$ of terms that take strictly more than $T$ time steps to convert.

I suspect that we might need an additional condition, such that there is a fixed and known upper bound $B$ on the length of the path converting $t\_1$ to $t\_2$. If you have such a bound, there is a zero-knowledge proof protocol whose complexity is polynomial in $B$, as the statement you are proving becomes a NP-statement, and it is known that there are zero-knowledge protocols for every language in NP.
> 3 votes

---
Tags: lambda-calculus
---


# Question
Title: What algorithm may be used to solve the re-assembly of shredded papers?
I was once given this question in an interview:

> Suppose a piece of paper has 80 columns of alphabets with a fixed size font, and now the paper is shredded vertically, into 80 vertical pieces (so each piece can show a series of alphabets going down vertically), and there are 300 pages of such paper shredded total. Assume they are just English words with no proper names (for people / places). Find a method to reassemble all the papers and give the O() complexity time and space.

I proposed a solution where we take one piece of stripe, and go down the row to match for consecutive occurring alphabets, for a proper stripe. So we would build up a dictionary of all English words, for example, for the word `Apple`, that will mean `ap`, `pp`, `pl`, and `le` are all valid. And if we go down both stripes, we should expect most (or all) of them match with each other if they were adjacent.

But doing this way, it looks like it would be `(180 * 300)! = 24000!` (factorial) steps, before we can finish the task? I can only find a complicated paper about re-constructing non-fixed size font paper (and it seemed way too complicated for a 20 minute interview question), and another paper that is not public. Is there a good solution to this problem?

(Actually, it seems that if it is not fixed size font, it is a easier problem? Because we can just look at the left and right edge: along the left edge, for example, if there is ink, we call it as `1`, and no ink, we call it a `0`. Or we can just scan and collect data: from top edge, go down 3.232cm of blank space, and then 0.012cm of ink, and then 0.027cm of blank space, all the way down to the end of paper, and then we can create a signature. If we do the signature for all `80 x 300` stripes, now we have `48000` signatures. Now we can actually just match the signatures up to tell which strips is adjacent to which stripe. So that would be a linear O(n) solution?)

# Answer
> 2 votes
If the cuts are in the middle of letters, then I think your solution in the last paragraph is a good one.

If the cuts go between letters, then I think your approach of finding pairs of strips of papers is a good one. I would start by finding all pairs of strips that could have been adjacent, based on which digraphs (pairs of characters) can appear in some word. Then, I would try to extend to find all triples of strips that could have been adjacent: for each possible pair of adjacent strips $s\_1,s\_2$, find all $s\_3$ such that $s\_2,s\_3$ is a pair of possible adjacent strips; then test whether if you past together $s\_1,s\_2,s\_3$ that all trigraphs (triples of characters) can appear in some word. Then, I would extend to 4-tuples of strips, filtering them based on 4-graphs of characters, and so on. The worst-case complexity could be horrible in principle, but in practice I expect that you'll very quickly filter out all false matches, so running time will probably be very good.

For fun, you might enjoy reading about the DARPA shredding challenge (summary on Wikipedia).

# Answer
> 2 votes
So... for the fixed-size font problem, if it were me, I'd use a stochastic global optimisation method. Specifically, I would try to find the permutation of the columns which optimises the compressibility of the text if it were compressed using a static model (e.g. PPM or DMC) trained on English text.

I'd probably use simulated annealing to start with. I'd pick some mutation operations, one of which is "swap two columns", one of which is "move a column to a random other place", and one of which (chosen with low probability) is "restart with a random permutation", and then let Metropolis and Hastings do their thing.

I can't think of a good "crossover" operation off the top of my head, but if so, a genetic algorithm might also be appropriate.

The space usage is $O(nk)$ where $k$ is the population size that you want to retain. The run time is exponential in the worst case, but likely faster than most deterministic algorithms.

---
Tags: algorithms, time-complexity
---


# Question
Title: Find all nodes on simple paths between two nodes in cyclic directed graph
Given two nodes `U` and `V` in a cyclic directed graph, how can I find the set of nodes that are part of a simple path from `U` to `V`?

**Attempt 1**

I've tried using a DFS from `U` that stores the set of visited nodes when `V` is reached, and backtracks when a cycle is detected. But this algorithm must traverse all paths, and can hence be very slow for large graphs.

I cannot stop the DFS early when a node that has already been deemed to be part of a simple path is reached:

If the DFS goes `U -> A -> B -> C -> D -> E -> V`, those nodes are deemed to be part of a simple path. After backtracking to `E` and traversing to `F` and `A`, a cycle is found. After backtracking to `U` and traversing to `C`, a node that is already part of a simple path is found, but the DFS cannot stop, since further traversal is necessary to figure out that `F` is also part of a simple path: `U -> C -> D -> E -> F -> A -> V`.

The same argument shows that I can't stop the DFS early when a node that has already been deemed to be part of a cycle is reached.

**Attempt 2**

Another idea I've tried is to store on the edges sets of *potential cycle root* nodes that must be traversed in order to reach `V` from the edge's sink. For instance for the edge `E -> F`, `A` must be traversed in order to reach `V`. Hence the DFS does not have to traverse this edge if `A` has already been visited.

It is not straight-forward to decide which nodes are potential cycle roots, and on which edges they need to be stored. My implementation attempts have unfortunately been too slow for large and complex graphs. After the potential cycle roots have been calculated, however, performing the DFS has been fast.

**Question**

Are there any efficient algorithms for finding the set of nodes that are part of a simple path between two nodes?

**Examples**

Just to make things really clear, these are the outputs I am looking for for a few different graphs:

**Example 1**

Nodes that are part of simple paths: `U`, `A` and `V`.

**Example 2**

Nodes that are part of simple paths: `U`, `A`, `B`, `C`, `D`, `E` and `V`.

**Example 3**

Nodes that are part of simple paths: `U`, `A`, `C`, `D`, `E`, `F` and `V`.

**Example 4**

Nodes that are part of simple paths: `U`, `A`, `B`, `C`, `D`, `E`, `F` and `V`.

# Answer
This problem is NP-hard. It is actually NP-Hard to prove if a vertex $w$ lays on a simple path from $u$ to $v$. Here is a prove of hardness through a reduction from the two disjoint paths problem.

Given a directed graph $G = (V, E)$ and two pairs of vertices $(s\_1, t\_1)$ and $(s\_2, t\_2)$, we build the new graph $G'$ by adding a new vertex $w$ to $G$ and add an edge from $t\_1$ to $w$ and an edge from $w$ to $s\_2$. The new graph admits an $s\_1, t\_2$ simple path passing through $w$ if and only if the original graph admits two disjoint paths one from $s\_1$ to $t\_1$ and the other from $s\_2$ to $t\_2$. Try to prove this claim as an exercise!
> 3 votes

# Answer
**EDIT: The answer below is not correct. It finds all vertices that are on some path from $U$ to $V$, not on some *simple* path from $U$ to $V$. It seems we need a directed analog of biconnected components for this to work.**

---

Add an edge from $V$ to $U$, then find all vertices in the strongly connected component containing $U$ and $V$. (They will be in two different SCCs if and only if there is no path from $U$ to $V$ in the original graph.)

This works because two vertices are in the same SCC if and only if there is a simple cycle containing both vertices.

Credit to bennos on Stack Overflow for providing me the answer when I asked the analogous question for undirected graphs back in 2012. For undirected graphs, you use biconnected components instead of strongly connected components.
> -1 votes

---
Tags: graphs, graph-traversal
---


# Question
Title: Understanding of big-O massively improved when I began thinking of orders as sets. How to apply the same approach to big-Theta?
Today I revisited the topic of runtime complexity orders – big-O and big-$\Theta$. I finally fully understood what the formal definition of big-O meant but more importantly I realised that big-O orders can be considered sets.

For example, $n^3 + 3n + 1$ can be considered an **element** of set $O(n^3)$. Moreover, $O(1)$ is a subset of $O(n)$ is a subset of $O(n^2)$, etc.

This got me thinking about big-Theta which is also obviously a set. What I found confusing is how each big-Theta order relates to each other. i.e. I believe that $\Theta(n^3)$ **is not** a subset of $\Theta(n^4)$. I played around with Desmos (graph visualiser) for a while and I failed to find how each big-Theta order relates to other orders. A simple example Big-Theta example graphs shows that although $f(n) = 2n$ is in $\Theta(n)$ and $g(n) = 2n^2$ is in $\Theta(n^2)$, the graphs in $\Theta(n)$ are obviously not in $\Theta(n^2)$. I kind of understand this visually, if I think about how different graphs and bounds might look like but I am having a hard time getting a solid explanation of why it is the way it is.

So, my questions are:

1. Is what I wrote about big-O correct?
2. How do big-Theta sets relate to each other, if they relate at all?
3. Why do they relate to each other the way they do? The explanation is probably derivable from the formal definition of big-Theta (might be wrong here) and if someone could relate the explanation back to that definition it would be great.
4. Is this also the reason why big-O is better for analysing complexity? Because it is easier to compare it to other runtimes?

# Answer
> 29 votes
> Is what I wrote about big-O correct?

Yes.

> How do big-Theta sets relate to each other, if they relate at all?

They are a partition of the space of functions. If $\Theta(f)\cap \Theta(g)\not = \emptyset$, then $\Theta(f)=\Theta(g)$. Moreover, $\Theta(f)\subseteq O(f)$.

> Why do they relate to each other the way they do? The explanation is probably derivable from the formal definition of big-Theta (might be wrong here) and if someone could relate the explanation back to that definition it would be great.

A function $f$ is in $\Theta(g)$ if and only if there are constants $c\_1,c\_2\>0$ such that $c\_1 g(n)\leq f(n) \leq c\_2g(n)$ for all sufficiently large $n$. Seeing that the above relation holds is a simple case of doing some substitutions:

Suppose there is some $a\in \Theta(f), a\in \Theta(g)$ and $b\in \Theta(f)$, then we know there exist constants such that (for sufficiently large $n$)

$c\_1 f(n)\leq a(n) \leq c\_2f(n)$

$c\_3 g(n)\leq a(n) \leq c\_4g(n)$

$c\_5 f(n)\leq b(n) \leq c\_6f(n)$

then

$c\_5 c\_3 g(n)/c\_2 \leq c\_5 a(n)/c\_2 \leq c\_5 f(n)\leq b(n)\leq c\_6f(n)\leq c\_6 a(n)/c\_1\leq c\_6c\_4g(n)/c\_1$

and thus $b\in \Theta(g)$.

> Is this also the reason why big-O is better for analysing complexity? Because it is easier to compare it to other runtimes?

It is not "better". You could say it is worse, because an algorithm being $\Theta(f)$ implies that it is $O(f)$ (but not vice-versa), so "$\Theta$" is a strictly stronger statement than "$O$".

The reason "$O$" is more popular is because "$O$" expresses an upper bound on the speed of an algorithm, i.e., it is a guarantee it will run in at most a given time. "$\Theta$" also expresses the same upper bound, but, in addition, also expresses that this upper bound is the best possible upper bound for a given algorithm. E.g., an algorithm running in time $O(n^3)$ can actually turn out to also run in $O(n^2)$, but an algorithm running in time $\Theta(n^3)$ can not also run in $\Theta(n^2)$ time.

From a practical perspective, if we want to know whether an algorithm is fast enough for a practical purpose, knowing it runs in $O(n^2)$ time is good enough to determine whether it is fast enough. The information that it runs in $\Theta(n^2)$ time is not really important to the practical use. If we have determined that an $O(n^2)$-time algorithm is fast enough for our application, then who cares if the algorithm that was claimed to be $O(n^2)$ is actually $\Theta(n)$?

Obviously, if you are going to give an upper bound on the running time of an algorithm, you will endeavor to give the best possible upper bound (there is no sense in saying your algorithm is $O(n^3)$ when you could also say it is $O(n^2)$). For this reason, when people say "$O$" they often implicitly mean "$\Theta$". The reason people write "$O$" is because this is easier on a normal keyboard, is customary, conveys the most important information about the algorithm (the upper bound on the speed) and people often can't be bothered to formally prove the lower bound.

# Answer
> 4 votes
I'd just like to add some to the already posted answer and comments.

I'm currently studying CS, and every single time big O notation came up, the lecturer at some point mentioned that they in fact are sets, and that $f(n) = O(g(n))$ really is just wrong notation used for historical reasons, and $\in$ is what would be correct.

In fact, the way we defined big-O notation from day 0 was explicitly as sets of functions.

Another thing I'd like to mention is using big O for runtimes.

Getting upper bounds for problems tends to be way easier than lower bounds. For an upper bound, all you need is to find an algorithm. For a lower bound, you need to prove that no algorithm that solves the problem can run faster than some limit.

As an example, proving that arrays can be sorted by comparing elements in $O(n \\; \log(n))$ is easy, just point at mergesort. Proving $\Omega(n \\; \log(n))$ is not nearly as easy, though it can be done (has been done, remember I'm talking about comparison-based sorting).

---
Tags: time-complexity, asymptotics, big-o-notation
---


# Question
Title: How do I analyze Mergesort that uses Insertion Sort for small inputs?
I know that Insertion Sort is faster when size $N$ is a small number, hence by modifying Merge Sort to use Insertion Sort when size $N$ reaches $K$, can help improve the performance.

How do I analyze this and prove that the running time of Merge Sort, $O(N \log N)$ is turned into $O(NK + N\log N(\frac{N}{K}))$?

I would really like to understand the analysis of this.

# Answer
It probably should be $O(NK + N \log \frac{N}{K})$.

Please try to figure out what do $NK$ and $N \log \frac{N}{K}$ represent.

Answer with details left blank:

> Consider the recursion tree. It has $\sim \frac{N}{K}$ leaves, and its height is $\sim \log \frac{N}{K}$.
> At the leaves level, insertion sorts cost $\Box \cdot \Box = NK$ in total.
> Then $\Box$ (how many?) merge stages follow, each of which costs $\Box$.
> 1 votes

# Answer
The solution is just like Merge Sort upto Lg (n) levels but here we are merging only upto Lg (n/k) levels.At the last level there are n/k sub-lists each sub-list having k elements assuming uniform distribution (though same argument works for even if there's some sub-lists with less than k elements) although when they all have k elements it will be kind of the worst case since we have to sort maximum number of keys for each sub-list. Each sub-list when sorted by Insertion-sort take theta(k^2) complexity and since there are n/k such sub-lists therefore total = (k^2)*(n/k) = n*k.

and now merging involves comparison at each level in the worst case we'll have to make at-most n comparisons at each level and total no of level can be calculated mathematically which comes out to be around Lg(n/k) or Lg(n/k)+1 which is almost same. Total cost of merging is n\*Lg(n/k) complexity.

Hence the total complexity of n*k + n*Lg(n/k).
> 0 votes

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


title: How does Bifunctor in Haskell work?

text:
# Question
Title: How does Bifunctor in Haskell work?
I was reading 'Category Theory for Programmers' by Bartosz Milewski and got really confused by the implementation of bimap in `Bifunctor` typeclass.

```
class Bifunctor f where
    bimap :: (a -> c) -> (b -> d) -> f a b -> f c d
    bimap g h = first g . second h
    first :: (a -> c) -> f a b -> f c b
    first g = bimap g id
    second :: (b -> d) -> f a b -> f a d
    second = bimap id

```

This is the definition of the `Bifunctor` typeclass taken directly from the library Control. If `bimap` evaluates to `first` and `second`, which in turn evaluates to `bimap` itself, how is this supposed to end? Could you please explain how the evaluation of `bimap` works? Thank you!

# Answer
A Haskell type class defines a set of functions (sometimes called *methods*) that belong to the type class. In most cases, specific instances must supply specific implementations of one or more of these.

An instance can implement all methods, or just enough to make the instance work. If an instance doesn't implement all methods, the default implementations are used.

Type classes are typically documented with the minimal implementation required. This is also true for Bifunctors:

```
Minimal complete definition

bimap | first, second

```

This means that an instance *must* implement either `bimap`, or both `first` and `second`. An instance can also implement all three, but that's not required.

The tuple instance, for example, is implemented using `bimap`:

```
instance Bifunctor (,) where
  bimap f g ~(a, b) = (f a, g b)

```

This means that the `first` and `second` implementations are the default implementations you quoted above. They call the instance's `bimap` implementation.
> 5 votes

---
Tags: haskell
---


# Question
Title: if a graph G(V,E) is connected $|E|\geq|V|-1$
If a graph G(V,E) is connected the number of edges is at least the number of Vertices-1. It is pretty evident if you think about it but how do i prove it formally?

# Answer
Imagine a process in which you start with the empty graph, and add the edges one by one. Keep track of the number of connected components. In the beginning, there are $|V|$ connected components. Each edge you add either belongs inside a connected component, or merges two connected components, and in any case, the number of connected components decreases by at most 1. Hence after adding $|E|$ edges, the number of connected components is at least $|V| - |E|$. If the graph is connected, $|V| - |E| \leq 1$, and so $|E| \geq |V| - 1$.
> 3 votes

---
Tags: graphs, proof-techniques, connected
---


# Question
Title: Algorithm for smallest number in array larger than threshold
We define the problem SmallestAbove as follows:

> Given an array $A$ of $n$ integers and a value $v$, compute the smallest value in $A$ that is strictly greater than $v$. Return $\infty$ if no such value exists.

(Here $\infty$ is just a very large integer constant.)

You may assume that $A$ has at least one value ($n \geq 1$) and that $v$ and all integers in $A$ are smaller than $\infty$.

1. Describe an algorithm for SmallestAbove that runs in $O(n)$ time. You do not need to prove its correctness.
2. Analyze the running time of your algorithm.
3. Now assume that $A$ is sorted. Provide an $O(\log n)$-time algorithm for SmallestAbove. You do not have to prove correctness nor analyze its running time.

# Answer
> 1 votes
When we say that an algorithm is O(n), it means that if we have an algorithm that operates on n elements, our algorithms will 'touch' or 'visit', in the worst case, n elements (This is a loose definition of big-O, but it will do for our example, if you don't understand Big-O see here).

So think about the sort of code that would be required for a problem like this. For starters, we're probably going to need a `for` loop that hits every elements (Based on the question, it says we're looking for an O(n) algorithm, so our loop would go from 1 to *n*).

Outside this loop we initialize our value "smallest value" variable to be MAX\_INT. Then in our for loop, we have a simple `if` statement that does the following: If ***A****\[i\]* (The current value in the array we're looking at) is greater than *v*, and less then our "smallest value", then set "smallest value" to be equal to ***A****\[i\]*.

As for the run time of this algorithm, the time complexity would be: *n*.

This is because every time we run this algorithm, we must visit every element once.

For question 3. Think about how we can optimize this algorithm now that we know it's sorted. If its sorted' we can use this to visit less elements.

In terms of 'O(logn)', this can sometimes be confusing with the 'log' as to what it means. An example of a 'logn' sorting algorithm would be searching through a dictionary. Assume we have an 1000 page dictionary and I want to find the word 'Zoo'. First i split the dictionary in have and go to page 500, then i see words with the letter 'M' so i know i need to go further into the dictionary, so i split the 2nd half of the dictionary in half again and reach page 750. I see the words start with the letter Q and R, so i know that i need to do it again. So i reach page 875 and i keep repeating until i reach Zoo. If I used a 'n' time complexity algorithm, i would have had to visit every page till i found the word. As you can see, logn is much faster.

Use this example to help you come up with a O(logn) algorithm. See if you can modify out 1st algorithm now that we know the list is sorted.

---
Tags: algorithms, integers
---


# Question
Title: Proof of $\mathsf{NP}^\mathsf{BPP} \subseteq \mathsf{BPP}^\mathsf{NP}$
How to show that $\mathbf{NP}^{BPP} \subseteq \mathbf{BPP}^{NP}$?

I tried to build $NTM$ $M\_{NP1}$, which uses $PTM$ $M\_{BPP1}$. Show that there will always be $PTM$ $M\_{BPP2}$, which uses $L ($$NTM$ $M\_{NP2}$$)$ as the oracle language and repeats the actions of $NTM$ $M\_{NP1}$ with the oracle $L ($$PTM$ $M\_{BPP1}$$)$. Unfortunately, I could not do this. It turns out that the $NTM$ output that uses $PTM$ will also happen with some probability?

Hope You can help me to show it.

# Answer
> 3 votes
Suppose that $M$ is a machine in $\mathsf{NP}^\mathsf{BPP}$ accepting some language $L$. We can think of $M$ as accepting an input $x$ and a witness $y$. The machine $M$ runs a polytime algorithm, and has oracle access to $\mathsf{BPP}$. We can further assume that the witness contains, for each oracle call to $\mathsf{BPP}$, both the input and the output — the witness might be longer, but it still has polynomial length. Denoting the pairs by $z\_i,w\_i$ and the $\mathsf{BPP}$ languages by $L\_i$, we thus deduce that there is a polytime machine $A$ such that $$ x \in L \Leftrightarrow \exists y,\vec{z},\vec{w},\vec{L} \\; A(x,y,\vec{z},\vec{w},\vec{L}) \land \bigwedge\_i L\_i(z\_i) = w\_i, $$ where the quantification is over polynomial length strings. (We elide the issue of how $L\_i$ is represented.)

Suppose furthermore that $L\_i$ is computed by some $\mathsf{BPP}$ machine $A\_i$ with small error probability. We can think of $A\_i$ as accepting two inputs: the actual input $z\_i$, and a randomness string $r\_i$.

This suggests the following $\mathsf{BPP}^\mathsf{NP}$ machine for $L$. The machine gets input $x$ and randomness string $\vec{r}$. Using a single oracle call to $\mathsf{NP}$, it checks whether there exist $y,\vec{z},\vec{w},\vec{L}$ such that $$ A(x,y,\vec{z},\vec{w},\vec{L}) \land \bigwedge\_i A\_i(z\_i,r\_i) = w\_i. $$

If $x \in L$, let $y,\vec{z},\vec{w},\vec{L}$ the $M$-witness for it. For the vast majority of randomness strings $\vec{r}$, we will have $$ A(x,y,\vec{z},\vec{w},\vec{L}) \land \bigwedge\_i A\_i(z\_i,r\_i) = w\_i, $$ and so our machine will accept $x$.

The other direction is a bit more subtle, and I'll let you work it out carefully. It requires the $\mathsf{BPP}$ machines to have really small error, which can be achieved via repetition.

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


# Question
Title: Simplifying a logic function using Boolean algebra
Consider this Logic function : D = A B C + A B’ C + A’ B’ C + A B C’ + A’ B C’ + A B’ C’ I am trying to simplify it using Boolean algebra , I am stuck in this step : D= AB +B'C+ A’ B C’ + A B’ C’ So how do I continue simplifying it ?

# Answer
I'm not sure how to simplify this equation from the point you've gotten to without backtracking (e.g., recognizing that AB implies ABC' + ABC). The way I would do it is, starting from the beginning:

`D = ABC + AB’C + A’B’C + ABC’ + A’BC’ + AB’C’`

If we rearrange this as follows:

`D = ABC + ABC’ + AB’C + AB’C’ + A’B’C + A’BC’`

Then you may notice that we have:

`D = A(BC + BC' + B'C + B'C') + A’B’C + A’BC’`

Simplifying for C, we get:

`D = A(B + B') + A’B’C + A’BC’`

Which of course is just:

`D = A + A'B'C + A'BC'`

Since we know that D is always true when A is true, this implies:

`D = A + A'B'C + A'BC' + AB'C + ABC'`

Which can be rearranged as:

`D = A + (A' + A)B'C + (A' + A)BC'`

Giving us the final result:

`D = A + B'C + BC'`

I'm sure there's a way to do this with De Morgan's law, but it's been a while since I've used any Boolean algebra and I couldn't be bothered to look it up.

Alternatively, you can draw out a truth table

```
D | A  B  C
------------
0 | 0  0  0
1 | 0  0  1
1 | 0  1  0
0 | 0  1  1
1 | 1  0  0
1 | 1  0  1
1 | 1  1  0
1 | 1  1  1

```

and recognize that D will always be true if A is true (A), and that if A is not true then D will be true when B'C or BC' (B'C + BC'), thus giving us `D = A + B'C + BC'`

Although the more "correct" way to do this via truth tables would be to use a Karnaugh map
> 1 votes

---
Tags: logic
---


# Question
Title: Proof of the inclusion-exclusion principle
The inclusion-exclusion principle for $n$ sets is proved by Kenneth Rosen in his textbook on discrete mathematics as follows:

> **THEOREM 1 — THE PRINCIPLE OF INCLUSION-EXCLUSION** Let $A\_1,A\_2,\ldots,A\_n$ be finite sets. Then $$ \begin{multline\*} |A\_1 \cup A\_2 \cup \cdots \cup A\_n| = \sum\_{1 \leq i \leq n} |A\_i| - \sum\_{1 \leq i \< j \leq n} |A\_i \cap A\_j| \\ + \sum\_{1 \leq i \< j \< k \leq n} |A\_i \cap A\_j \cap A\_k| - \cdots + (-1)^{n+1} |A\_1 \cap A\_2 \cap \cdots \cap A\_n|. \end{multline\*} $$ *Proof:* We will prove the formula by showing that an element in the union is counted exactly once by the right-hand side of the equation. Suppose that $a$ is a member of exactly $r$ of the sets $A\_1,A\_2,\ldots,A\_n$, where $1 \leq r \leq n$. This element is counted $\binom{r}{1}$ times by $\sum |A\_i|$. It is counted $\binom{r}{2}$ times by $\sum |A\_i \cap A\_j|$. In general, it is counted $\binom{r}{m}$ times by the summation involving $m$ of the sets $A\_i$. Thus, this element is counted exactly $$ \binom{r}{1} - \binom{r}{2} + \binom{r}{3} - \cdots + (-1)^{r+1} \binom{r}{r} $$ times by the expression on the right-hand side of this equation. Our goal is to evaluate this quantity. The binomial formula shows that $$ 0 = (1-1)^r = \binom{r}{0} - \binom{r}{1} + \binom{r}{2} - \cdots + (-1)^r \binom{r}{r}. $$ Hence $$ 1 = \binom{r}{0} = \binom{r}{1} - \binom{r}{2} + \binom{r}{3} - \cdots + (-1)^{r+1} \binom{r}{r}. $$ Therefore, each element in the union is counted exactly once by the expression on the right-hand side of the equation. This proves the principle of inclusion-exclusion.

Although the proof seems very exciting, I am confused because what the author has proved is $1=1$ from the LHS and RHS.

Thus, is this still a valid proof? We need to prove that the total cardinality of LHS is the RHS. The RHS produces a $1$ for each member of the union of the sets.

I think in order to produce the cardinality of the union, an extra summation sign should be appended before the expression in RHS. Could someone please clarify?

# Answer
> 5 votes
Let me slightly rephrase the argument. Let $N\_r$ be the number of elements contained in exactly $r$ of the sets $A\_1,\ldots,A\_n$. Then the left-hand side is $$ |A\_1 \cup \cdots \cup A\_n| = \sum\_{r=1}^n N\_r. $$ The first sum on the right-hand side is $$ \sum\_{1 \leq i \leq n} |A\_i| = \sum\_{r=1}^n \binom{r}{1} N\_r. $$ The second sum on the right-hand side is $$ \sum\_{1 \leq i \< j \leq n} |A\_i \cap A\_j| = \sum\_{r=2}^n \binom{r}{2} N\_r. $$ More generally, the $m$th sum on the right-hand side is $$ \sum\_{1 \leq i\_1 \< i\_2 \< \cdots \< i\_m \leq n} |A\_{i\_1} \cap A\_{i\_2} \cap \cdots \cap A\_{i\_m}| = \sum\_{r=m}^n \binom{r}{m} N\_r. $$ Therefore the right-hand side is equal to $$ \sum\_{r=1}^n \binom{r}{1} N\_r - \sum\_{r=2}^n \binom{r}{2} N\_r + \sum\_{r=3}^n \binom{r}{3} N\_r - \cdots + (-1)^{n+1} \sum\_{r=n}^n \binom{r}{n} N\_r. $$ Rearranging, the right-hand side is equal to $$ \left\[ \binom{1}{1} \right\] N\_1 + \left\[ \binom{2}{1} - \binom{2}{2} \right\] N\_2 + \left\[ \binom{3}{1} - \binom{3}{2} + \binom{3}{3} \right\] N\_3 + \cdots + \\ \left\[ \binom{n}{1} - \binom{n}{2} + \binom{n}{3} - \cdots + (-1)^{n+1} \binom{n}{n} \right\] N\_n. $$ The coefficient of the general term $N\_m$ is $$ \binom{m}{1} - \binom{m}{2} + \binom{m}{3} - \cdots + (-1)^{m+1} \binom{m}{m}. $$ By the binomial theorem, this equals $1$, and so the right-hand side equals $$ 1 \cdot N\_1 + 1 \cdot N\_2 + 1 \cdot N\_3 + \cdots + 1 \cdot N\_n = \sum\_{r=1}^n N\_r, $$ which is exactly the same as the left-hand side.

# Answer
> 2 votes
Yes, you are right that an extra summation needs to be appended to the beginning of both sides to prove the inclusion-exclusion formula. This can be understood by using indicator functions (also known as characteristic functions), as follows. Let $U$ be some finite set (the universe), and let $S \subseteq U$. The indicator function (or characteristic function) of $S$ is the 0,1-valued function $I\_S: U \rightarrow \\{0,1\\}$ on the domain $U$, defined by $I\_S(x) = 1$ if $x \in U$, and $I\_S(x)=0$ if $x \notin U$. Observe that $|S| = \sum\_{x \in U} I\_S(x)$. In other words, the number of elements in $S$ is equal to a sum of $0$'s and $1$'s, where the number of $1$'s is of course the size of $S$. We are interested in the case where $S = A\_1 \cup A\_2 \cup \cdots \cup A\_n$.

What the proof given in text shows is that the indicator function $I\_S$ (where $S = A\_1 \cup A\_2 \cup \cdots \cup A\_n$) is equal to a particular sum of indicator functions (where the subscripts for these latter indicator functions are intersections of the $A\_i$'s). More specifically, it is proved that $$I\_{A\_1 \cup \cdots \cup A\_n} = (I\_{A\_1} + \cdots + I\_{A\_n} ) - (I\_{A\_1 \cap A\_2} + \cdots + \cdots I\_{A\_{n-1} \cap A\_n}) + (I\_{A\_1 \cap A\_2 \cap A\_3} + \cdots )+ \cdots + (-1)^n I\_{A\_1 \cap \cdots \cap A\_n}.$$ This formula holds because, as you show, if an element $x \in U$ appears in exactly $r$ of the $A\_i$'s for some $r \ge 1$, then the LHS indicator function trivially evaluates to $1$, and the RHS sum of indicator functions also evaluates to $1$ (by the binomial formula). Similarly, both sides evaluate to $0$ if $r=0$ (i.e. if $x \in U, x \notin S$). Thus, the two 0,1-valued functions are equal, meaning the two functions take the same value for each $x$ in the domain $U$. This means the many terms in RHS sum cancel out to give either a $0$ or a $1$, for any $x \in U$ that you pick.

If two functions $f, g$ on domain $U$ are equal, i.e. if $f(x)=g(x)$ for all $x \in U$, then the summations $\sum\_{x \in U} f(x)$ and $\sum\_{x \in U} g(x)$ are also equal. So, take the summation of the LHS indicator function's values over $x \in U$, and similarly for the RHS. Recall that for any set $X \subseteq U$, we have $\sum\_{x \in U} I\_X(u) = |X|$. So, for the left hand side, the sum $\sum\_{x \in U} I\_{A\_1 \cup \cdots \cup A\_n}(x)$ evaluates to $|A\_1 \cup \cdots \cup A\_n|$. For the right hand side, we are taking the sum of all those indicator functions over $x \in U$. Use the fact that $\sum\_{x \in U} I\_{A\_i}(x) = |A\_i|$, that $\sum\_{x \in U} I\_{A\_1 \cap A\_2}(x) = |A\_1 \cap A\_2|$ (by taking $X = A\_1 \cap A\_2$), and so on, to get the inclusion-exclusion formula.

---
Tags: combinatorics, discrete-mathematics
---


title: AVL tree worst case height proof

text:
# Question
Title: AVL tree worst case height proof
The worst case height of AVL tree is $1.44 \log n$. How do we prove that? I read somewhere about Fibonacci quicks but did not understand it.

# Answer
We want to show that the number of nodes $n$ in a height-balanced binary tree with height $h$ grows exponentially with $h$ and at least as fast as the Fibonacci sequence.

Let $N\_h$ denote the minimum number of nodes in a height-balanced binary tree having height $h$. Recall that in a height-balanced binary tree of height $h$, the subtree rooted at one of the children of the root has height $h-1$, and the subtree rooted at the other child of the root has height $h-1$ or $h-2$. Thus, $N\_h \> N\_{h-1} + N\_{h-2}$. Thus, $N\_h$ is at least $f\_h$, the $h$th term of the Fibonacci sequence, where $f\_h \approx \phi^h / \sqrt{5}$ and $\phi$ is the golden ratio $\frac{1+\sqrt{5}}{2}$.

So, if $n$ is the number of nodes in an AVL tree of height $h$, we have $n \ge \phi^h / \sqrt{5}$. Taking $\log\_2$ of both sides, we get $h \le \frac{\log\_2 n}{\log\_2 \phi} + c = 1.4404 \log\_2 n + c$, for some constant $c$. Thus, an AVL tree has height $h = O(\log n)$

An easier proof, if you don't care about the constants as much, is to observe that $N\_h \> N\_{h-1}+N\_{h-2} \> 2N\_{h-2}$. Hence, $N\_h$ grows at least as fast as $\sqrt{2}^h$. So the number of nodes $n$ in a height-balanced binary tree of height $h$ satisfies $n \> \sqrt{2}^h$. So $h \log\_2 \sqrt{2} \< \log n$, which implies $h \< 2 \log n$.
> 3 votes

# Answer
Try and create the "worst" AVL tree, that is, the AVL tree in which the height is as large as possible, with as least nodes as possible.

Once you get to the Fibonacci sequence (the answer to the question above), you can use the fact the the $n$-th Fibonacci number is $O(\phi ^n)$ (where $\phi = 1.618\ldots$), it should be easy to conclude that the worst case height of the tree is $\log\_\phi n = O(\log n)$.
> 1 votes

---
Tags: complexity-theory, binary-trees, balanced-search-trees, avl-trees
---


# Question
Title: Integer programming to MAX-SAT translation
Reading A Comparison of Methods for Solving MAX-SAT Problems, I can see that a MAX-SAT problem can be translated to an integer programming (IP) problem.

Definition of MAX-SAT \[Wikipedia\]:

> The maximum satisfiability problem (MAX-SAT) is the problem of determining the maximum number of clauses, of a given Boolean formula in conjunctive normal form, that can be made true by an assignment of truth values to the variables of the formula.

Definition of integer programming \[Wikipedia\]:

> An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers

Is there a similar translation backwards? Given an IP problem that can be translated to a MAX-SAT.

The MAX-SAT problem is NP-hard \[\] and Integer programming is NP-complete \[\]. technically it might not be very suitable to solve a (in principle) simpler problem using a formulation which is (in principle) harder to solve. But it will be great to understand the encoding both ways. My motivation is to compare MAX-SAT solvers with IP solvers.

More precisely given an IP problem like: $$x\_1 + x\_{2} + \neg x\_3 \leq 1 \\ \neg x\_1 + x\_4 + x\_3 \leq 1 \\ ... $$

with total **n** inequalities/equations and each $x\_i \in \mathbb{B}$. Such that maximize as many as equations (from total n). Encode it as a MAX-SAT problem.

First Attempt: Each inequality encodes AtMostOne of the complement of the variables (or AtleastN-1 of the original IP inequality). But representing AtMostOne in CNF will create multiple clauses and destroys the possible use of direct MAX-SAT.

# Answer
> 2 votes
The decision versions of both MaxSAT and integer programming are in fact NP-complete, so there is polynomial reduction from integer programming to MaxSAT.

In the context of solvers, modern MaxSAT solvers support "weighted partial MaxSAT"-encodings (weighted clauses with possibly infinite weights), so you can add any SAT encoded hard constraints by encoding them as clauses with infinite weight.

For comparing MaxSAT and IP solvers, I would strongly suggest looking at modern literature on "implicit hitting set" algorithms for MaxSAT. The solvers using this algorithm use both IP solvers and SAT solvers as subroutines for solving MaxSAT. It might even be that if you use some direct translation from IP to MaxSAT and give the resulting instance for these solvers, the solver will under the hood just directly solve the original IP instance with the IP solver. Also, there is a lot of recent research comparing IP and MaxSAT solvers for solving specific problems (just search "integer programming maxsat" in Google Scholar).

---
Tags: satisfiability, integer-programming
---


title: Performance speedup with Amdahl's law

text:
# Question
Title: Performance speedup with Amdahl's law
Consider this question: A program has 1M instructions and 30% of them are SQRT with CPI=8. The CPI of the rest of the instructions are 3. If we reduce the CPI of SQRT to 2, how much speedup is obtained?

I have two solutions for that:

1- Using Amdahl's law, We have

```
              1
 S= --------------------
      (1-alpha) + alpha
                  -----
                    n

```

So, we have 1/(0.7+(0.3/4)) where 0.7 is the fraction that is not affected. and 4 is the speedup of reducing CPI of SQRT from 8 to 2. That speedup will be 1.29.

2- We can calculate

```
CPI_avg = sigma( I * CPI_class )

```

and we know SQRT instructions are 300K and the rest are 700K. So

```
CPI_old = (300000*8 + 700000*3) / 1000000 = 4.5
CPI_new = (300000*2 + 700000*3) / 1000000 = 2.7

```

So, the speedup will be 4.5/2.7 which is 1.66

The question is, which one is correct? 1.29 or 1.66?

# Answer
> 1 votes
Amdahl’s formula assumes that you know the percentage of execution time, but you only know the percentage of instruction. The percentage of execution time is 53.33%, not 30%.

The approach “total time before, divided by total time after” also works in more complicated cases.

---
Tags: performance
---


# Question
Title: Can a programming language be designed to use a fixed amount of memory?
I have been toying around with the idea of creating a programming language as a side-project, specifically trying to get extreme performance out of a machine.

I have been thinking about the efficiency-memory tradeoff, and was wondering if it would be at all possible to design a language which always uses a fixed amount of memory. That is, it allocates a large chunk of memory (16K, 64K, 1M, depending on the task), and instead of allocating from a heap, just gives some more memory out of the block we've already allocated.

The idea here is not to be practical, but rather to pose a challenge: design a fast algorithm that works on a fixed amount of memory.

If this sounds like a fun project, please let me know and I'll get on it.

If, however, this is a very naive thing to say (I don't know much about the inner workings of programming languages), I would very much appreciate some resources as to where I can learn more.

# Answer
> 1 votes
Yes. At least one variant of C supports this. Its call stacks are bounded in size: you can't call functions within functions indefinitely. It is used for embedded devices.

# Answer
> 0 votes
There is No need to create a new language. Use as example c. Get a chunk of memory with malloc() and do wharever you wish with it.

On a typical operating system today you might need to use low level OS functions of you want to keep the memory from beeing swapped due to virtual memory.

---
Tags: programming-languages, memory-management, stacks
---