Algorithms by Jeff Erickson: a very short review

I recently followed a link from somewhere to Professor Jeff Erickson's algorithms web site. Erickson, who has been a professor at the University of Illinois for 20 years, maintains a wonderful textbook simply entitled Algorithms.

Although you can read the entire book (and many additional supplements) online, I splurged and got the paper copy, because it was easier to read on my commute.

The biggest advantage of the paper copy, besides that I can read it on my commute where it's easier to read printed material than to bring up my computer, is that it's inexpensive. Most other modern algorithms textbooks nowadays are roughly five times the price of Erickson's book.

The biggest disadvantage of the paper copy is that it is in black-and-white, so the marvelous multi-color diagrams from the online book are rendered in a sort of gray-scale. But the diagrams are carefully-enough built that you can understand them even without the color coding, and if you're really stuck on one you can go online and look at just that one diagram.

Anyway, bottom line: I really like Erickson's book. His writing style is clear and engaging (for a computer science textbook, that is!); he includes a very nice selection of modern, relevant, important algorithms, with plenty of pointers to further areas for the interested reader (many of which are also online at Erickson's site); and the exercises at the end of each chapter are very useful for practicing the techniques that have just been discussed.

Bonus links: if you find Erickson's book hard going because you're a bit out of date on some of the fundamentals, Erickson kindly links to two other great sites: Professor Margaret Fleck's Building Blocks for Theoretical Computer Science, and Lehman, Leighton, and Meyer's Mathematics for Computer Science.

Now, all I need is more time to read.

Up, up, and away

Big news here at the East Cut: Malcolm Drilling have removed the amazing Liebherr 873 mobile crane which supported their 30-month sub-project of deep-foundation work at the Oceanwide Center.

They took that crane away overnight! Monday at 4:00 PM, it was there. Tuesday at 7:30 AM, it was not. Check the link above for the sketch of what was involved in disassembling and removing it. Boy I wish I had known to be there to watch. Sigh.

Now the project changes from building down, to building up.

Things have been a bit challenging for the Oceanwide Center project. Oceanwide is a Chinese developer, and the trade war and global economic conditions have greatly complicated things. They have halted work on the partially-completed Oceanwide Plaza in Los Angeles, but the San Francisco project is still underway, it seems.

At least, there are still crews on the site in San Francisco, and a new pedestal crane was recently installed, so I think they are still moving forward.

Time will tell, I guess.

I hope that the building gets built, because we are out of room across the street and we need new office space!

Sez the Chron:

The dearth of space and continued demand from the tech industry has led to leases for future buildings that haven’t even been approved by the city, such as Salesforce’s lease at 564 Howard St. and Pinterest’s deal at 88 Bluxome St.

The 564 Howard Street site, if it gets built, will connect directly to the Salesforce Park:

The site known as Transbay Parcel F is a dirt lot. In five years, the site at 564 Howard St. is set to become a soaring 800-foot glass high-rise with space for 1,500 workers, along with 165 condos and 190 hotel rooms.

If it gets built.

I have this feeling that growth is slowing rapidly across the country, and very specifically in the tech industry, as the impending recession begins to be felt everywhere. Tech is still an enormous generator of economic activity, but the global conditions are worsening fast.

So I think all these plans from three years ago are being frantically re-thought.

Meanwhile, since across the street means the Salesforce Tower, the tallest building west of Mississippi (by some measures), you should take some time to look at this gorgeous portfolio of pictures taken by photographer Gary Leonard during the topping out of the Wilshire Grand Hotel 3 years ago.

I found Leonard's photos via this nice short Snopes article that's making the rounds right now.

Onwards and upwards!

Some music I've been listening to...

... somewhat ranked. Sorta.

• Local Natives: Sunlit Youth. I can't believe this band isn't getting more attention. They burst onto the scene with Gorilla Manor in 2010, followed up with Hummingbird in 2013, then Sunlit Youth in 2016, and this summer they released Violet Street.

  Every one of these albums is wonderful, but Sunlit Youth is somehow my personal favorite. I've gotta figure out a way to see them live, but their 2019 tour didn't come anywhere close to my part of the world, sigh.

• Sufjan Stevens: Carrie & Lowell. This is probably the most heart-breakingly perfect 40 minutes of music you will ever hear. Honest, intimate, tragic, compelling, unforgettable: all of these apply to Carrie & Lowell, an album which largely consists of Stevens trying to come to grips with his feelings about his mother and her premature death.

  The only hesitation I have about this album is that, each time I play it, there is a recovery period. I have to rest, and contemplate, and reflect.

• Lord Huron: Vide Noir. What is it about Michigan's Ben Schneider that is so compelling to me? I'm not sure, but he certainly has me hooked. Lonesome Dreams was marvelous, Strange Trails just as good, and Vide Noir builds on those successes to find something richer and more nuanced. He can somehow capture the essence of sitting around the campfire, listening to stories told by those wandering cowboys of yore.
• Lumineers: III.

  O.M.G.

  I've been a Lumineers super-fan since their break-out debut in 2011, and, like everyone else in the world, I've been waiting eagerly for III since it was announced last winter.

  But, when it finally arrived, it just blew my mind. With III, they have taken their phenomenal musicianship and married it with a deep and introspective voyage into their souls.

  I suspect that there will be many people who find III to be the wrong album for them.

  But for me, I'm thrilled.

• Joseph: Good Luck, Kid. Since their monster self-titled debut in 2016, Joseph have been near the top of my Bands To Watch. It was going to be very, very hard for them to top that debut album, but Good Luck, Kid is very, very good.
• Dave Matthews Band: Come Tomorrow. For nearly 30 years, The Dave Matthews Band has been producing magnificent work. Even if Come Tomorrow isn't their strongest album ever, it's been good enough for at least 2 dozen listens this summer.
• Elephant Revival: Break In The Clouds. I, sadly, had the bad luck to stumble upon Elephant Revival just as the band had decided to call it quits and go their separate ways; life got in the way, I guess? This is an enchanting band, nicely incorporating bluegrass, jazz, and folk influences into a lovely ensemble. I've only listened to half of the music that they managed to record during 10 lovely years. Why, oh why didn't I learn about them years ago?
• Gregory Alan Isakov: The Weatherman. Oh, everybody knows about Isakov, I'm not telling you anything you haven't already heard elsewhere. Can a musician be both dependable and revealing simultaneously? Everybody compares him to Van Morrison, which is a bit audacious because he isn't quite there, yet. Yet.
• Billie Eilish: WHEN WE ALL FALL ASLEEP, WHERE DO WE GO?. A little bit funky, a little bit smooth. A little bit edgy, a little bit elegant. But really: how can a 17-year-old possibly be this good already? Where will she go from here?
• Tame Impala: Innerspeaker. I actually got both Innerspeaker and Lonerism this summer, and, honestly, I can't tell which one I prefer. They're both atmospheric and fascinating. Tame Impala are some sort of blend of The Beatles and Pink Floyd. I guess. Or something.
• Whitney: Forever Turned Around. Whitney were another band whose debut album just captivated me. Light Upon The Lake was a collection of hook after hook, sing-along-lyrics ("I wanna drive around/with you with the windows down/and we can run all night"), and some sort of energy that just grabbed me.

  So my expectations for album number 2 were a bit too high. Still, Forever Turned Around is growing on me. So I keep moving it up and down in my Summer 2019 list.

• Nathaniel Rateliff and the Night Sweats: Tearing at the Seams. I love the term, "rock and soul". Rateliff is full of energy and emotion and heat. Lots and lots of heat. GREAT driving music.
• Shakey Graves: Can't Wake up. Again, this is a sophomore effort, after his very promising And The War Came. I really like this album, but I feel like Shakey Graves still hasn't produced his best work, and I wonder if he somehow needs something to challenge him.
• Brett Dennen: Smoke and Mirrors. This is a strong work by Dennen, who has found his groove and delivers a lovely album here.
• Young the Giant: Home of the Strange. "Cough Syrup", the stratospheric hit from Young the Giant's debut album, was such a wonder-song that it is no surprise that whatever happened next was a bit of a letdown. I skipped Mind Over Matter and went straight to their 3rd CD. And now I'm confused. What will happen next?
• Indigo Girls live with the Colorado Symphony Orchestra. If you're a super-fan, like I am, this is lovely stuff. I need to catch up with their more recent music. But, every time I think about that, I just go put on Strange Fire or Rites of Passage, and I remember when they changed the world.
• Better Oblivion Community Center. Conor Oberst loves to go make music with other musicians. Phoebe Bridgers is a HUGE talent who is just getting started. I think it was a good experience for her to perform with him, but she's going to make much better music in the future.
• Santana: Africa Speaks. WTF? Well, it's not boring. Half the tracks I was fascinated by; the other half I couldn't hit "next track" fast enough.
• Bruce Springsteen: Western Stars. Urk, what? Somebody told me that his daughter is going through a "horse phase". I guess that maybe explains this? Darkness on the Edge of Town this sure ain't.

Backpacking 2019: Ansel Adams Wilderness

It can be complicated to get the schedules of 6 different people to line up properly, so this year it turned out to be mid-September before we were able to head out on the trail.

But line up the schedules did, and so off we went!

The Ansel Adams Wilderness is a large region of the Sierra Nevada, sharing a boundary with Yosemite National Park on its north, a second boundary with the Devil's Postpile National Monument on its east, and still another boundary with the John Muir Wilderness on its south and east. The Ansel Adams Wilderness is also fascinating to backpackers because it has significant trailhead access on both the east and west sides of the Sierra Nevada.

I often refer to this part of the world as "the Heart of the Sierra", as it's full of 12,000+ foot mountains, glacier-carved valleys, pristine mountain lakes, majestic canyons with rushing waterfalls and roaring rivers: just the ticket for a perfect vacation hike!

The Ansel Adams Wilderness was originally called the Minarets Wilderness, after the sawtooth formations on the Ritter Range, which maybe you can (barely) see in this picture.

To get to the Fernandez Trailhead on the west side of the Ansel Adams Wilderness from the Bay Area, you've got a journey that breaks down into two parts.

1. First, you zoom along on 200 miles of high speed roads from San Francisco to Oakhurst; this takes you about 3 hours.
2. Then, you drive up past Bass Lake until you find Beasore Road, also known as the Sierra Vista Scenic Byway. (Who knew there were 50+ such National Scenic Byways in California?) This 30 miles of road will take you from elevation 2,000 feet up to elevation 7,500 feet, and will also take you about 2 hours. It's good to slow down and enjoy the road, but you should also take this into account in your planning!

In what might be a first for me, the driving directions in my 2016 printing of Sierra South were incorrect, and we ended up driving to the Norris Trailhead first, then realizing that we were at the wrong trailhead, then retracing our steps back to Beasore Road, then proceeding about 100 yards further down the road, then we found the road to the Fernandez Trailhead. I think that, perhaps, the road to the Norris Trailhead has changed since the book was written, and I just wasn't paying quite enough attention to the (faded) Forest Service road signs. It was but a momentary diversion, though.

To its credit, my Tom Harrison map of the Ansel Adams Wilderness showed the road clearly (I just didn't look at that part of the map closely until I'd already made the mistake, duh!)

Our hike from Fernandez Trailhead up to Vandeburg Lake was a straightforward climb of about 1200 vertical feet over about 4.5 miles of trail. Fatiguing, especially at 8,000 feet of elevation, but the trail was well-maintained and well-marked.

We had originally been intending to make it all the way to Lady Lake, but by the time we arrived at Vandeburg Lake it was already 4 PM, and there was a lovely existing campsite that matched our group size perfectly, so we declared victory.

We visited Lady Lake the next day, as well as visiting the Staniford lakes which were quite delightful.

One of the advantages of going backpacking after Labor Day is that the Sierra summer backpacking season is over, and so you (mostly) have the trails and campsites to yourself.

Another of the advantages of going backpacking at the end of the summer is that it is the driest part of the year, so the trails are clear and dry (if a bit dusty), the water crossings are generally not intimidating, and, to a first approximation, there are no mosquitoes!

Unfortunately, one of the downsides of it being the driest part of the year is that most of the mountain wildflowers had already disappeared for the year.

More importantly, another of the disadvantages of going backpacking in mid-September is that summer is almost over, and it is starting to get COLD! During our trip, the high temperatures were only in the mid-60's and low-70's, and the overnight lows were down in the low 30's.

There were even some snow fields within distance of the lake, so we had a snowball fight and I built a snowman.

I was glad that I had my nice new sleeping bag, rated for 15 degrees and true to its word.

Yet another disadvantage, which rather took us by surprise, is that late summer, particularly after a long wet winter, is apparently peak season for yellow jackets and other types of wasps. Each day, in the early afternoon, we found ourselves being annoyed and chased about by small swarms of these aggressive and very annoying insects. One of our party was stung twice, including once on his tongue (!), and had to have our "wilderness nurse" remove the stinger with a trusty pair of tweezers.

The UC Davis website has a lot of useful background information about these wasps,

But these are just the ups and downs of backpacking trips, I guess, and for the most part our trip was lovely.

The lakes were lovely.

The views were astounding.

Our intrepid fisherman, Rich, caught a fish! It was, I think, a rainbow trout? I don't know much about fish identification but maybe this was a Kern River Rainbow Trout? It certainly seemed much more like a Rainbow Trout than a Brown Trout, even though I think Brown Trout is typically what you find in these parts?

All in all, it was a wonderful trip.

1491: A very short review

Charles Mann would certainly be the first to admit that 1491: New Revelations of the Americas Before Columbus is now getting "old".

It was published 15 years ago, after all, and even though Mann has revised it a tad, that's a significant period of time, and the revelations are certainly no longer new.

With a (slightly) deeper interpretation, however, one of Mann's major points is that books such of these are of necessity always old, even the moment after they are written:

Meanwhile, new disciplines and new technologies were creating new ways to examine the past. Demography, climatology, epidemiology, economics, botany, and palynology (pollen analysis); molecular and evolutionary biology; carbon-14 dating, ice-core sampling, satellite photograph, and soil assays; genetic microsatellite analysis and virtual 3-D fly-throughs -- a torrent of novel perspectives and techniques cascaded into use. And when these were employed, the idea that the only human occupants of one-third of the earth's surface had changed little for thousands of years began to seem implausible. To be sure, some researches have vigorously attacked the new findings as wild exaggerations. ("We have simply replaced the old myth [of untouched wilderness] with a new one," scoffed geographer Thomas Vale, " the myth of the humanized landscape.") But after several decades of discovery and debate, a new picture of the Americas and their original inhabitants is emerging.

When I started reading 1491, I had no idea what genetic microsatellite analysis was, and I had to look it up (this is a pretty approachable overview), but 1491 isn't really a book about how anthropologists, historians, and other similar disciplines operate.

Rather, it's (at least) two other books:

• It's a lively and entertaining look at what we currently know about what the Americas were when the enormous waves of immigration from Renaissance Europe began in the late 1400's
• But it's also an attempt to help you, the reader, become a better consumer of the information you receive about how we got to this point, how the world is changing, and what it might mean for what you think you know.

Much of 1491 flies by, Mann leads us at a frenetic pace through much memorable history:

Dazzled as he was, Cortes was also aware that with a single command Motecuhzoma could order his army "to obliterate all memory of us." The Spaniards counteracted this thread by inventing a pretext to seize the tlatoani in his own palace, making him first their captive and then their puppet.

In both Europe and Mesoamerica kings ruled by the dispensation of the heavens. The Mexica reacted to the sacrilegious abduction of their leader with the same baffled horror with which Europeans later reacted to Cromwell's execution of Charles I in 1649. Not wanting to act in a way that could result in Motecuhzoma's death, the Mexica took seven months to mount a counterattack. Fearing the worst, the debased tlatoani made a begging public appearance on behalf of the Spanish. He soon died, either murdered by the Spaniards (according to Mexica accounts) or slain by his own countrymen (as Spanish chronicles tell it). Soon after came the long-delayed assault. Under the leadership of a vigorous new tlatoani, Cuitlahuac, the Indians force the invaders into narrow alleys where horses were of little advantage. Under a pitiless hail of spears, darts, and arrows, Cortes and his men retreated down the long causeways that linked the island city to the mainland. In a single brutal night the Mexica utterly vanquished Cortes, killing three-quarters of his men. Although the Alliance destroyed causeways in front of the Spaniards, the remnants of the invaders were able to cross the gaps because they were so choked with the dead that the men could walk on the bodies of their countrymen. Because the Mexica did not view the goal of warfare as wiping out enemies to the last man, they did not hunt down the last Spaniards. A costly mistake: Cortes was among the escapees.

A man of unfathomable determination, Cortes never thought of giving up. He persuaded several other vassal states to join his anti-Alliance alliance with Tlaxcala. Negotiating furiously, he assembled a force of as many as 200,000 men and built thirteen big ships in an audacious plan to assault Tenochtitlan from the water.

...

When Cortes and his Indian allies finally attacked, the Mexica resisted so fiercely despite their weakness that the siege has often been described as the costliest battle in history -- casualty estimates range up to 100,000.

Yet, I suspect that Mann began his book fascinated by the first topic, and set out to write that "first book," but along the way he became even more fascinated by how challenging it is to avoid thinking that we now know everything there is to know about the past, and so he ended up writing that "second book" as well, trying to open our eyes to just how little we know, and just how alert we should be to the possibility that what we think we know, we do not in fact know at all:

At first he did nothing about his observation. Historical demography was not supposed to be his field. Six years later, in 1959, he surveyed more archives in Hermosilla and found the same disparity. By this point he had almost finished his doctorate at Cornell and had been selected for Holmberg's project. The choice was almost haphazard: Dobyns had never been to Peru.

Peru, Dobyns learned, was one of the world's cultural wellsprings, a place as important to the human saga as the Fertile Crescent. Yet the area's significance had been scarcely appreciated outside the Andes, partly because the Spaniards so thoroughly ravaged Inka culture, and partly because the Inka themselves, wanting to puff up their own importance, had actively concealed the glories of the cultures before them. Incredibly, the first full history of the fall of the Inka empire did not appear until more than three hundred years after the events in chronicled: William H Prescott's History of the Conquest of Peru, published in 1847.

Read 1491 because it's wildly entertaining and endlessly engrossing.

But remember 1491 because it makes you a better reader, and a better thinker, in general.

One way or another, however, read 1491.

Updates from The Ocean Cleanup Project

Boyan Slat and the team at The Ocean Cleanup Project are working along, tinkering and learning.

Here's their latest report: Into the Twilight Zone

First, they remind us where they were a year ago:

Our first attempt at doing so was deployed last year: System 001, also known as Wilson. After months of testing, we took Wilson back to port in the first days of this year after it suffered a fatigue fracture. This was not ideal, but both the diagnosis and solution came quite easily.

And then, they bring us up to date on where they are now:

The more complicated challenge was the system’s inability to retain plastic; instead of consistently going faster than the plastic, it alternated between going faster and going slower than the plastic. This meant plastic would float into the system, as planned, but then float out again.

...

We launched System 001/B in late June, which was followed by a six-week testing campaign to test slowing down the system using a parachute anchor and test speeding up the system using large inflatable buoys.

...

the winning concept is the slow-down approach, in which we use a parachute anchor to slow down the system as much as possible, allowing the natural winds and waves to push the plastic into the system.

...

there’s always a twist in each episode; well, here’s ours: the plastic is currently able to cross over the cork line into The Twilight Zone. While it is technically still within the boundaries of the system, there is no screen underneath the floater pipe, so we cannot consider this plastic caught because it is not securely retained in front of the screen.

...

we will now be using three rows of 32 cm floats stacked on top of each other, creating a total height of about half a meter.

It's a wonderful article, with great diagrams and deeper explanations throughout.

This is incremental engineering at its best: start with something; it does some things properly but fails in other ways; test, improve, repeat.

I'm looking forward to more great updates!

Scrappers

I was completely enthralled by Scrappers: The Big Business of Scavenging in PostIndustrial America.

Hypnarowski later told me that his company, New Enterprise Stone and Lime, also owned some of the land where Bethlehem Steel once existed. The steel mills had been scrapped long ago, but there were still nuggets to be had — or “buttons” to be precise. Buttons are essentially giant metal boulders that weigh as much as 20 tons. When the mills were still operating, iron ore was melted and poured into great big ladles, at which point the less desirable slag would form at the bottom. This slag was then dumped onto Lake Erie’s shoreline, where it hardened and formed buttons. Together, Hypnarowski and Levin worked to salvage these buttons from the lakeside. They had, it seemed, thought of every conceivable way to mine big scrap. Over time, scrappers have remade Buffalo’s landscape. The city has survived, in part, by devouring itself.

Back when steel mills first closed, Lou Jean Fleron, an emeritus professor at Cornell’s school of industrial and labor relations, ran a series of educational programs for the workers who had been laid off. She got close with the families that became destitute. It was a very hard time, she recalled, and whenever she visited Buffalo’s waterfront, her eyes inevitably drifted toward the derelict mills. “Oh, God, it was like a ghost town — like a skeleton — a big, massive black skeleton,” she recalled. Then the demolition crews and the scrappers arrived to do their work. Now when Fleron goes down to the waterfront, she sees young families with their children having birthday parties. The scene is almost pastoral.

“It was important to take it all down,” Fleron told me. “It does make some of the pain go away.”

The hero of the story is the incredibly hard-working Adrian Paisley:

Paisley typically takes scrap from his piles and moves it inside his garage, where he processes it. This is where Paisley makes his money, by extracting the most valuable nuggets. The air-conditioner that he found, for example, was promising because it contained copper tubing, copper wiring and an ACR (an aluminum-copper radiator). The scrapyard might pay him only $4 to $6 for the air-conditioner in its current form, but if he processed it and removed the copper, he might earn three times as much. For this reason, Paisley spends much of his day surgically removing the most valuable metals. He even removes each screw and sells them together in bulk. Scrapyards are willing to pay a premium for scrap like this because it saves them the trouble of having to process it themselves.

It was great to read of Paisley's dream of one day no longer having to do this back-breaking work:

It was all crystal clear in his mind: “I want to see the fog hovering across the ground on a nice cool fall morning. And I don’t want to hear nothing but the birds, and the insects chirping. I want to stand there, man, and drink my coffee and look at the fog. Peaceful.

Amen, Mr. Paisley.