7. ALGORITHMS

Algorithms summary

Now for the more serious stuff. Watch the following short video from Harvard University and answer the questions.

SUGGESTIONS

Improve your English speaking, listening and writing skills with Duolingo, a free, fun-to-use app.

B. Answer the questions

1. Explain how selection sort, bubble sort, and insertion sort work and what their best-case and worst-case run times are.

Bubble sort illustrated with with Hungarian dance

CHECK ANSWERS

2. What is merge sort?

Here is another video that explains how merge sort works in more detail:

CHECK ANSWER

3. What is the difference between linear search and binary search? Is binary search always the best option?

CHECK ANSWER

PART 2

READING

What do ants know that we don't?

Adapted from Deborah Gordon, Wired, 7 June 2013

Read the text and do exercise C.

NOTE: hover over words in blue for additional information

001  Ever notice how ant colonies so successfully explore and
002  exploit resources in the world? You may find it annoying.
003  But as an ecologist who studies ants and collective
004  behavior, I think it's intriguing.

005  What's especially remarkable: the close parallels
006  between ant colonies' networks and human-engineered
007  ones. One example is “Anternet”, where we, a group of
008  researchers at Stanford, found that the algorithm desert
009  ants use to regulate foraging is like the Traffic Control
010  Protocol (TCP) used to regulate data traffic on the
011  internet. Both ant and human networks use positive
012  feedback: either from acknowledgements that trigger the
013  transmission of the next data packet, or from food-laden
014  returning foragers that trigger the exit of another outgoing
015  forager.

016  But insect behavior mimicking human networks —
017  another example are the ant-like solutions to the
018  traveling salesman problem provided by the ant colony
019  optimization algorithm— is actually not what's most
020  interesting about ant networks. What's far more
021   interesting are the parallels in the other direction: What
022  have the ants worked out that we humans haven't
023  thought of yet?

024  What Ant Colony Networks Can Tell Us About What's
025  Next for Human-Engineered Ones
026  Ant colonies use dynamic networks of brief interactions
027  to adjust to changing conditions. No individual ant knows
028  what's going on. Each ant just keeps track of its recent
029  experience meeting other ants, either in one-on-one
030  encounters when ants touch antennae, or when an ant
031  encounters a chemical deposited by another.

032  Dealing with High Operating Costs
033  Harvester ant colonies in the desert must spend water to
034  get water. The ants lose water when foraging in the hot
035  sun, and get their water by metabolizing it out of the
036  seeds that they collect. Since colonies store seeds, their
017  system of positive feedback doesn't waste foraging effort
038  when water costs are high.

039  In this way, the Anternet allows the colony to deal with
040  high operating costs. In the internet, the TCP protocol
041  also prevents the system from sending data out on the
042  internet when there's no bandwidth available. Effort
043  would be wasted if the message is lost, so it's not worth
044  sending it out unless it's certain to reach its destination.

045  Scaling Up from Small to Large Systems
046  What happens when a system scales up? Like human-
047  engineered systems, ant systems must be robust to
048  scale up as the colony grows, and they have to be able
049  to tolerate the failure of individual components.

050  Since large systems allow for some messiness, the ideal
051  solutions utilize the contributions of each additional ant
052  in such a way that the benefit of an extra worker
053  outweighs the cost of producing and feeding one.

054  The tools that serve large colonies well, therefore, are
055  redundancy and minimal information. Enormous ant
056  colonies function using very simple interactions among
057  nameless ants without any address.

058  In engineered systems we too are searching for ways to
059  ensure reliable outcomes, as our networks scale, by
060  using cheap operations that make use of randomness.
061  Elegant top-down designs are appealing, but the
062  robustness of ant algorithms shows that tolerating
063  imperfection sometimes leads to better solutions.

064  Optimizing for First-Mover Advantage
065  When operating costs are low and colonies seek an
066  ephemeral delicacy, searching speed is essential if
067  the colony is to capture the prize before it dries up
068  or is taken away.

069  Since ant colonies compete with each other and
070  many are out looking for the same food, the first
071  colony to arrive might have the best chance of
072  holding on to the food.

073  How does a colony achieve this first-mover
074  advantage without any central control? The
075  challenge in this situation is for the colony to manage
076  the flow of ants so it has an ant almost everywhere
077  almost all the time.

078  One strategy ants use (familiar from our own data
079  networks) is to set up a circuit of permanent
080  highways —like a network of cell phone towers—
081  from which ants search locally. The invasive
082  Argentine ants are experts at this; they'll find any
083  crumb that lands on your kitchen counter.

084  The Argentine ants also adjust their paths, shifting
085  from a close to random walk when there are lots of
086  ants around, leading each ant to search thoroughly
087  in a small area, to a straighter path when there are
088  few ants around, thus allowing the whole group to
089  cover more ground.

090  Like a distributed demand-response network, the
091  aggregated responses of each ant to local
092  conditions generates the outcome for the whole
093  system, without any centralized direction or control.

094  Addressing Security Breaches and Disasters
095  In the tropics, where hundreds of ant species are
096  packed close together and competing for resources,
097  colonies must deal with security problems. This has
098  led to the evolution of security protocols that use
099  local information for intrusion detection and for
100  response.

101  Rather than attempting to prevent incursions
102  completely, however, ants create loose, stochastic
103  identity systems in which one species regulates its
104  behavior in response to the level of incursion from
105  another.

106  There are obvious parallels with computer security.
107  It's becoming clear that we too will need to
108  implement local evaluation and repair of intrusions,
109  tolerating some level of imperfection. The ants have
110  found ways to let their systems respond to each others'
111  incursions, without attempting to stochasticset up a
112  central authority that regulates hacks.

113  Some of our networks seem to be moving toward
114  using methods deployed by the ants.

115  Take the disaster recovery protocols of ants that
116  forage in trees where branches can break, so the
117  threat of rupture is high. A ring network, with signals
118  or ants flowing in both directions, allows for rapid
119  recovery here; after a break in the flow in one
120  direction, the flow in the other direction can re-
121  establish a link.

122  Similarly, early fiber-optic cable networks were often
123  disrupted by farm machinery and other digging: one
124  break could bring down the system because it would
125  isolate every load. Engineers soon discovered, as
126  ants have already done, that ring networks would
127  create networks that are easier to repair.

TRUE/FALSE

C. Say whether the following statements are true or false, and why.

1. Deborah Gordon is especially interested in the possibility that studying ants’ behavior could help us imagine new solutions to problems posed by human networks.

Check answer: True False

2. The ability of ants to adapt to their environment is due to the highly centralized nature of their colonies.

Check answer: True False

3. Redundancy in large colonies of ants means that each ant can be given more complex information.

Check answer: True False

4. The feedback process of the Argentine ants relies on how much food each ant finds: if an ant encounters another ant that has found food, it changes its search pattern.

Check answer: True False

5. Dual ring networks make it possible to avoid complete breakdown in a system in the event that some part of the system fails.

Check answer: True False

EXTRAS

TED TALK

Watch Deborah Gordon’s TED talk on "What ants teach us about the brain, cancer and the Internet."