Binary Search Algorithms

In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array.  Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array. Even though the idea is simple, implementing binary search correctly requires attention to some subtleties about its exit conditions and midpoint calculation.

Binary search runs in logarithmic time in the worst case, making O(log n) comparisons, where n is the number of elements in the array, the O is Big O notation, and log is the logarithm. Binary search takes constant (O(1)) space, meaning that the space taken by the algorithm is the same for any number of elements in the array. Binary search is faster than linear search except for small arrays, but the array must be sorted first. Although specialized data structures designed for fast searching, such as hash tables, can be searched more efficiently, binary search applies to a wider range of problems.

There are numerous variations of binary search. In particular, fractional cascading speeds up binary searches for the same value in multiple arrays. Fractional cascading efficiently solves a number of search problems in computational geometry and in numerous other fields. Exponential search extends binary search to unbounded lists. The binary search tree and B-tree data structures are based on binary search.

Implementation Issues

Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky 

                                     ... — Donald Knuth

When Jon Bentley assigned binary search as a problem in a course for professional programmers, he found that ninety percent failed to provide a correct solution after several hours of working on it, mainly because the incorrect implementations failed to run or returned a wrong answer in rare edge cases. A study published in 1988 shows that accurate code for it is only found in five out of twenty textbooks. Furthermore, Bentley's own implementation of binary search, published in his 1986 book Programming Pearls, contained an overflow error that remained undetected for over twenty years. The Java programming language library implementation of binary search had the same overflow bug for more than nine years.

In a practical implementation, the variables used to represent the indices will often be of fixed size, and this can result in an arithmetic overflow for very large arrays. If the midpoint of the span is calculated as (L + R) / 2, then the value of L + R may exceed the range of integers of the data type used to store the midpoint, even if L and R are within the range. If L and R are nonnegative, this can be avoided by calculating the midpoint as L + (R − L) / 2.

If the target value is greater than the greatest value in the array, and the last index of the array is the maximum representable value of L, the value of L will eventually become too large and overflow. A similar problem will occur if the target value is smaller than the least value in the array and the first index of the array is the smallest representable value of R. In particular, this means that R must not be an unsigned type if the array starts with index 0.

An infinite loop may occur if the exit conditions for the loop are not defined correctly. Once L exceeds R, the search has failed and must convey the failure of the search. In addition, the loop must be exited when the target element is found, or in the case of an implementation where this check is moved to the end, checks for whether the search was successful or failed at the end must be in place. Bentley found that most of the programmers who incorrectly implemented binary search made an error in defining the exit conditions.

Many further details at:  https://en.wikipedia.org/wiki/Binary_search_algorithm

The Holy Grail

The Holy Grail is a vessel that serves as an important motif in Arthurian literature. Different traditions describe it as a cup, dish or stone with miraculous powers that provide happiness, eternal youth or sustenance in infinite abundance, often in the custody of the Fisher King. The term "holy grail" is often used to denote an elusive object or goal that is sought after for its great significance.

A "grail", wondrous but not explicitly holy, first appears in Perceval, le Conte du Graal, an unfinished romance written by Chrétien de Troyes around 1190. Here, Chrétien's story attracted many continuators, translators and interpreters in the later 12th and early 13th centuries, including Wolfram von Eschenbach, who perceived the Grail as a stone. In the late 12th century, Robert de Boron wrote in Joseph d'Arimathie that the Grail was Jesus's vessel from the Last Supper, which Joseph of Arimathea used to catch Christ's blood at the Crucifixion. Thereafter, the Holy Grail became interwoven with the legend of the Holy Chalice, the Last Supper cup, a theme continued in works such as the Vulgate Cycle, the Post-Vulgate Cycle, and Thomas Malory's Le Morte d'Arthur.

Etymology of Graal

The word graal, as it is earliest spelled, comes from Old French graal or greal, cognate with Old Provençal grazal and Old Catalan gresal, meaning "a cup or bowl of earth, wood, or metal" (or other various types of vessels in different Occitan dialects). The most commonly accepted etymology derives it from Latin gradalis or gradale via an earlier form, cratalis, a derivative of crater or cratus, which was, in turn, borrowed from Greek krater (κρατήρ, a large wine-mixing vessel). Alternative suggestions include a derivative of cratis, a name for a type of woven basket that came to refer to a dish, or a derivative of Latin gradus meaning "'by degree', 'by stages', applied to a dish brought to the table in different stages or services during a meal".

In the 15th century, English writer John Hardyng invented a fanciful new etymology for Old French san-graal (or san-gréal), meaning "Holy Grail", by parsing it as sang real, meaning "royal blood". This etymology was used by some later British writers such as Thomas Malory, and became prominent in the conspiracy theory developed in the book Holy Blood, Holy Grail, in which sang real refers to the Jesus bloodline.

Scholarly Hypotheses

Richard Barber (2004) argued that the Grail legend is connected to the introduction of "more ceremony and mysticism" surrounding the sacrament of the Eucharist in the high medieval period, proposing that the first Grail stories may have been connected to the "renewal in this traditional sacrament". Scavone (1999, 2003) has argued that the "Grail" in origin referred to the Shroud of Turin. Goulven Peron (2016) suggested that the Holy Grail may reflect the horn of the river-god Achelous as described by Ovid in the Metamorphoses.

https://en.wikipedia.org/wiki/Holy_Grail

Ethics of Self-Driving Cars

Massive global survey reveals ethics preferences and regional differences.
By Peter Dizikes | MIT News Office

October 24, 2018 -- A massive new survey developed by MIT researchers reveals some distinct global preferences concerning the ethics of autonomous vehicles, as well as some regional variations in those preferences.

The survey has global reach and a unique scale, with over 2 million online participants from over 200 countries weighing in on versions of a classic ethical conundrum, the “Trolley Problem.” The problem involves scenarios in which an accident involving a vehicle is imminent, and the vehicle must opt for one of two potentially fatal options. In the case of driverless cars, that might mean swerving toward a couple of people, rather than a large group of bystanders.

“The study is basically trying to understand the kinds of moral decisions that driverless cars might have to resort to,” says Edmond Awad, a postdoc at the MIT Media Lab and lead author of a new paper outlining the results of the project. “We don’t know yet how they should do that.”

Still, Awad adds, “We found that there are three elements that people seem to approve of the most.”

Indeed, the most emphatic global preferences in the survey are for sparing the lives of humans over the lives of other animals; sparing the lives of many people rather than a few; and preserving the lives of the young, rather than older people.

“The main preferences were to some degree universally agreed upon,” Awad notes. “But the degree to which they agree with this or not varies among different groups or countries.” For instance, the researchers found a less pronounced tendency to favor younger people, rather than the elderly, in what they defined as an “eastern” cluster of countries, including many in Asia.

The paper, “The Moral Machine Experiment,” is being published today in Nature.

The authors are Awad; Sohan Dsouza, a doctoral student in the Media Lab; Richard Kim, a research assistant in the Media Lab; Jonathan Schulz, a postdoc at Harvard University; Joseph Henrich, a professor at Harvard; Azim Shariff, an associate professor at the University of British Columbia; Jean-François Bonnefon, a professor at the Toulouse School of Economics; and Iyad Rahwan, an associate professor of media arts and sciences at the Media Lab, and a faculty affiliate in the MIT Institute for Data, Systems, and Society.

Awad is a postdoc in the MIT Media Lab’s Scalable Cooperation group, which is led by Rahwan.

To conduct the survey, the researchers designed what they call “Moral Machine,” a multilingual online game in which participants could state their preferences concerning a series of dilemmas that autonomous vehicles might face. For instance: If it comes right down it, should autonomous vehicles spare the lives of law-abiding bystanders, or, alternately, law-breaking pedestrians who might be jaywalking? (Most people in the survey opted for the former.)

All told, “Moral Machine” compiled nearly 40 million individual decisions from respondents in 233 countries; the survey collected 100 or more responses from 130 countries. The researchers analyzed the data as a whole, while also breaking participants into subgroups defined by age, education, gender, income, and political and religious views. There were 491,921 respondents who offered demographic data.

The scholars did not find marked differences in moral preferences based on these demographic characteristics, but they did find larger “clusters” of moral preferences based on cultural and geographic affiliations. They defined “western,” “eastern,” and “southern” clusters of countries, and found some more pronounced variations along these lines. For instance: Respondents in southern countries had a relatively stronger tendency to favor sparing young people rather than the elderly, especially compared to the eastern cluster.

Awad suggests that acknowledgement of these types of preferences should be a basic part of informing public-sphere discussion of these issues. In all regions, since there is a moderate preference for sparing law-abiding bystanders rather than jaywalkers, knowing these preferences could, in theory, inform the way software is written to control autonomous vehicles.

“The question is whether these differences in preferences will matter in terms of people’s adoption of the new technology when [vehicles] employ a specific rule,” he says.

Rahwan, for his part, notes that “public interest in the platform surpassed our wildest expectations,” allowing the researchers to conduct a survey that raised awareness about automation and ethics while also yielding specific public-opinion information.

“On the one hand, we wanted to provide a simple way for the public to engage in an important societal discussion,” Rahwan says. “On the other hand, we wanted to collect data to identify which factors people think are important for autonomous cars to use in resolving ethical tradeoffs.”

Beyond the results of the survey, Awad suggests, seeking public input about an issue of innovation and public safety should continue to become a larger part of the dialoge surrounding autonomous vehicles.

“What we have tried to do in this project, and what I would hope becomes more common, is to create public engagement in these sorts of decisions,” Awad says.

http://news.mit.edu/2018/how-autonomous-vehicles-programmed-1024

Coming: A Much Faster Internet

Groundbreaking new technology could allow 100-times-faster internet by harnessing twisted light beams
RMIT University [Melbourne, Australia]

October 24, 2018 -- Broadband fiber-optics carry information on pulses of light, at the speed of light, through optical fibers. But the way the light is encoded at one end and processed at the other affects data speeds.

This world-first nanophotonic device, just unveiled in Nature Communications, encodes more data and processes it much faster than conventional fiber optics by using a special form of 'twisted' light.

Dr. Haoran Ren from RMIT's School of Science, who was co-lead author of the paper, said the tiny nanophotonic device they have built for reading twisted light is the missing key required to unlock super-fast, ultra-broadband communications.

"Present-day optical communications are heading towards a 'capacity crunch' as they fail to keep up with the ever-increasing demands of Big Data," Ren said.

"What we've managed to do is accurately transmit data via light at its highest capacity in a way that will allow us to massively increase our bandwidth."

Current state-of-the-art fiber-optic communications, like those used in Australia's National Broadband Network (NBN), use only a fraction of light's actual capacity by carrying data on the colour spectrum.

New broadband technologies under development use the oscillation, or shape, of light waves to encode data, increasing bandwidth by also making use of the light we cannot see.

This latest technology, at the cutting edge of optical communications, carries data on light waves that have been twisted into a spiral to increase their capacity further still. This is known as light in a state of orbital angular momentum, or OAM.

In 2016 the same group from RMIT's Laboratory of Artificial-Intelligence Nanophotonics (LAIN) published a disruptive research paper in Science journal describing how they'd managed to decode a small range of this twisted light on a nanophotonic chip. But technology to detect a wide range of OAM light for optical communications was still not viable, until now.

"Our miniature OAM nano-electronic detector is designed to separate different OAM light states in a continuous order and to decode the information carried by twisted light," Ren said.

"To do this previously would require a machine the size of a table, which is completely impractical for telecommunications. By using ultrathin topological nanosheets measuring a fraction of a millimeter, our invention does this job better and fits on the end of an optical fiber."

LAIN Director and Associate Deputy Vice-Chancellor for Research Innovation and Entrepreneurship at RMIT, Professor Min Gu, said the materials used in the device were compatible with silicon-based materials use in most technology, making it easy to scale up for industry applications.

"Our OAM nano-electronic detector is like an 'eye' that can 'see' information carried by twisted light and decode it to be understood by electronics. This technology's high performance, low cost and tiny size makes it a viable application for the next generation of broadband optical communications," he said.

"It fits the scale of existing fiber technology and could be applied to increase the bandwidth, or potentially the processing speed, of that fiber by over 100 times within the next couple of years. This easy scalability and the massive impact it will have on telecommunications is what's so exciting."

Gu said the detector can also be used to receive quantum information sent via twisting light, meaning it could have applications in a whole range of cutting edge quantum communications and quantum computing research.

"Our nano-electronic device will unlock the full potential of twisted light for future optical and quantum communications," Gu said.

Explore further: Twisted light could dramatically boost internet speeds

More information: Zengji Yue et al, Angular-momentum nanometrology in an ultrathin plasmonic topological insulator film, Nature Communications (2018). DOI: 10.1038/s41467-018-06952-1

Journal reference: Nature Communications

https://phys.org/news/2018-10-groundbreaking-technology-times-faster-internet-harnessing.html

Strong Spider Web Silk

Researchers at San Diego State University and at Northwestern University have made strides in replicating the techniques that black widow spiders use to form strong web protein silk.  The practical result of this research would be materials almost boundless in usable applications.  See https://news.northwestern.edu/stories/2018/october/researchers-further-unravel-mystery-of-how-black-widow-spiders-create-steel-strength-silk-web/

Enthalpy and Thermodynamics

Enthalpy is a property of a thermodynamic system. The enthalpy of a system is equal to the system's internal energy plus the product of its pressure and volume. For processes at constant pressure, the heat absorbed or released equals the change in enthalpy.

The unit of measurement for enthalpy in the International System of Units (SI) is the joule. Other historical conventional units still in use include the British thermal unit (BTU) and the calorie.

Enthalpy comprises a system's internal energy, which is the energy required to create the system, plus the amount of work required to make room for it by displacing its environment and establishing its volume and pressure.

Enthalpy is defined as a state function that depends only on the prevailing equilibrium state identified by the system's internal energy, pressure, and volume. It is an extensive quantity.

Enthalpy is the preferred expression of system energy changes in many chemical, biological, and physical measurements at constant pressure, because it simplifies the description of energy transfer. At constant pressure, the enthalpy change equals the energy transferred from the environment through heating or work other than expansion work.

The total enthalpy, H, of a system cannot be measured directly. The same situation exists in classical mechanics: only a change or difference in energy carries physical meaning. Enthalpy itself is a thermodynamic potential, so in order to measure the enthalpy of a system, we must refer to a defined reference point; therefore what we measure is the change in enthalpy, ΔH. The ΔH is a positive change in endothermic reactions, and negative in heat-releasing exothermic processes.

For processes under constant pressure, ΔH is equal to the change in the internal energy of the system, plus the pressure-volume work p ΔV done by the system on its surroundings (which is > 0 for an expansion and < 0 for a contraction). This means that the change in enthalpy under such conditions is the heat absorbed or released by the system through a chemical reaction or by external heat transfer. Enthalpies for chemical substances at constant pressure usually refer to standard state: most commonly 1 bar pressure. Standard state does not, strictly speaking, specify a temperature (see standard state), but expressions for enthalpy generally reference the standard heat of formation at 25 °C.

Enthalpy of ideal gases and incompressible solids and liquids does not depend on pressure, unlike entropy and Gibbs energy. Real materials at common temperatures and pressures usually closely approximate this behavior, which greatly simplifies enthalpy calculation and use in practical designs and analyses.

Applications of Enthalpy

In thermodynamics, one can calculate enthalpy by determining the requirements for creating a system from "nothingness"; the mechanical work required, pV, differs based upon the conditions that obtain during the creation of the thermodynamic system.

Energy must be supplied to remove particles from the surroundings to make space for the creation of the system, assuming that the pressure p remains constant; this is the pV term. The supplied energy must also provide the change in internal energy, U, which includes activation energies, ionization energies, mixing energies, vaporization energies, chemical bond energies, and so forth. Together, these constitute the change in the enthalpy U + pV. For systems at constant pressure, with no external work done other than the pV work, the change in enthalpy is the heat received by the system.

For a simple system, with a constant number of particles, the difference in enthalpy is the maximum amount of thermal energy derivable from a thermodynamic process in which the pressure is held constant.

https://en.wikipedia.org/wiki/Enthalpy

Memristors Mimic Brain Activity

Understanding the Building Blocks for an Electronic Brain

University of Groningen [Netherlands] – October 18, 2018 -- Computer bits are binary, with a value of 0 or 1. By contrast, neurons in the brain can have all kinds of different internal states, depending on the input that they received. This allows the brain to process information in a more energy-efficient manner than a computer. University of Groningen (UG) physicists are working on memristors, resistors with a memory, made from niobium-doped strontium titanate, which mimic how neurons work. Their results were published in the Journal of Applied Physics on 21 October.

The brain is superior to traditional computers in many ways. Brain cells use less energy, process information faster and are more adaptable. The way that brain cells respond to a stimulus depends on the information that they have received, which potentiates or inhibits the neurons. Scientists are working on new types of devices which can mimic this behaviour, called memristors.

UG researcher Anouk Goossens, the first author of the paper, tested memristors made from niobium-doped strontium titanate during her Master’s research project. The conductivity of the memristors is controlled by an electric field in an analogue fashion: ‘We use the system’s ability to switch resistance: by applying voltagpulses, we can control the resistance, and using a low voltage we read out the current in different states. The strength of the pulse determines the resistance in the device. We have shown a resistance ratio of at least 1000 to be realisable.’ Goossens was especially interested in the time dynamics of the resistance states.

Forgetting

Goossens observed that the duration of the pulse with which the resistance was set determined how long the ‘memory’ lasted. This could be between one to four hours for pulses lasting between a second and two minutes. Furthermore, she found that after 100 switching cycles, the material showed no signs of fatigue.

‘There are different things you could do with this’, says Goossens. ‘By “teaching” the device in different ways, using different pulses, we can change its behaviour.’ The fact that the resistance changes over time can also be useful: ‘These systems can forget, just like the brain. It allows me to us time as a variable parameter.’ In addition, the devices that Goossens made combine both memory and processing in one device, which is more efficient than traditional computer architecture in which storage (on magnetic hard discs) and processing (in the CPU) are separated.

Before building brain-like circuits with her device, Goossens plans to conduct experiments to really understand what happens within the material. ‘If we don’t know exactly how it works, we can’t solve any problems that might occur in these circuits. So, we have to understand the physical properties of the material: what does it do, and why?’

Questions that Goossens want to answer include what parameters influence the states that are achieved. ‘And if we manufacture 100 of these devices, do they all work the same? If they don’t, and there is device-to-device variation, that doesn’t have to be a problem. After all, not all elements in the brain are the same.’

 

CogniGron

This brain-like architecture for microelectronics is one of the topics of CogniGron, a new research institute at the Faculty of Science and Engineering. The institute is currently in the process of hiring 12 full professors and some 40 PhD students. It is an interdisciplinary institute, which is necessary for this type of research, says Goossens. ‘For example, I’m working on new materials, but I don’t know much about the learning algorithms that the systems that could be made from our devices would be able to run. This is where the multidisciplinary nature of CogniGron becomes crucial; for example, my co-promotor is Professor Lambert Schomaker from Artificial Intelligence.’

Anouk Goossens conducted the experiments described in the paper during a research project as part of the Master’s in Nanoscience degree programme at the University of Groningen. Goossens’ research project took place within the group of students supervised by Dr Tamalika Banerjee of Spintronics of Functional Materials. She is now a PhD student in the same group.

Challenge

‘When I started my bachelor’s in physics, I initially considered pursuing theoretical physics, but we were introduced to a lot of new subjects in the first year. For example, I had never heard of spintronics before.’ The introduction to more applied subjects made Goossens change direction. ‘I love it when something I build comes to life. In theory, everything works, but when you start building, you run into all sorts of problems. That is a challenge I like!’

The experience in her Master’s research project gave Goossens a taste for more. ‘So, I welcomed the opportunity of four more years on a PhD project.’ In four years’ time, she hopes to have built a circuit by connecting a ‘fairly large number’ of the devices that she has made. ‘And I would like to run a self-learning algorithm on it.’ Goossens is not quite certain what she will do after finishing her thesis. ‘I like to take things one step at a time. Maybe I will continue in academic research, but I’m keeping all of my options open.’

Reference: A.S. Goossens, A. Das, and T. Banerjee: Electric field driven memristive behavior at the Schottky interface of Nb-doped SrTiO₃. Journal of Applied Physics, special topic section: New physcis and materials for neuromorphic computation. 21 October 2018

https://www.rug.nl/sciencelinx/nieuws/2018/10/20181020_goossens