department of hack
670 stories
·
15 followers

Topographical Sorting in Golang

1 Share

I own a fair number of computer books that I have never read from cover-to-cover (and a slim few that I have). I tend to dip in-and-out of programming books—absorbing a chapter here and a chapter there. One of the books I pick up with some frequency is Algorithms Unlocked by Thomas H. Cormen, who is one of the authors of the often cited CLRS which is a hugely comprehensive textbook covering the topic of algorithms.

Algorithms Unlocked, in contrast to its massive textbook counterpart, is a slim and snappy little book filled with all kinds of neat algorithms. It doesn’t focus on any specific language implementations, but rather describes algorithms in pseudo-code and plain English. After an algorithm is introduced, there is a discussion of the Big-O and Big-Θ run-times.

One of the things I like to do is read about a particular algorithm and test my understanding by implementing the pseudo code in some programming language. Since I recently ran into a graph problem while working on blubber —which is a Go project—I figured I’d implement the first algorithm in the Directed Acyclic Graph (DAG) chapter in Go.

Also, since I haven’t written anything on my blog in a while, I figured I’d write up my adventure!

Directed Graphs Represented in Go

The first problem when attempting to create a topographic sort of a graph in any programming language is figuring out how to represent a graph. I chose a map with an int as a key (which seems pretty much like a slice but the use of a map makes this implementation type agnostic). Each vertex n is represented with a key in the map, each vertex that adjacent to nm—is stored as a slice in the map referenced by the key n.

package main

import "fmt"

func main() {
    // Directed Acyclic Graph
    vertices := map[int][]int{
        1:  []int{4},
        2:  []int{3},
        3:  []int{4, 5},
        4:  []int{6},
        5:  []int{6},
        6:  []int{7, 11},
        7:  []int{8},
        8:  []int{14},
        9:  []int{10},
        10: []int{11},
        11: []int{12},
        13: []int{13},
        14: []int{},
    }

    // As yet unimplemented topographicalSort
    fmt.Println(topographicalSort(vertices))
}

Topographical Sort

I implemented the algorithm in a function named topographicalSort. The inline comments are the pseudo-code from the book—also noteworthy I stuck with the unfortunate variable names from the book (although somewhat adapted to camelCase to stick, a bit, to Go conventions):

// topographicalSort Input: g: a directed acyclic graph with vertices number 1..n
// Output: a linear order of the vertices such that u appears before v
// in the linear order if (u,v) is an edge in the graph.
func topographicalSort(g map[int][]int) []int {
    linearOrder := []int{}

    // 1. Let inDegree[1..n] be a new array, and create an empty linear array of
    //    verticies
    inDegree := map[int]int{}

    // 2. Set all values in inDegree to 0
    for n := range g {
        inDegree[n] = 0
    }

    // 3. For each vertex u
    for _, adjacent := range g {
        // A. For each vertex *v* adjacent to *u*:
        for _, v := range adjacent {
            //  i. increment inDegree[v]
            inDegree[v]++
        }
    }

    // 4. Make a list next consisting of all vertices u such that
    //    in-degree[u] = 0
    next := []int{}
    for u, v := range inDegree {
        if v != 0 {
            continue
        }

        next = append(next, u)
    }

    // 5. While next is not empty...
    for len(next) > 0 {
        // A. delete a vertex from next and call it vertex u
        u := next[0]
        next = next[1:]

        // B. Add u to the end of the linear order
        linearOrder = append(linearOrder, u)

        // C. For each vertex v adjacent to u
        for _, v := range g[u] {
            // i. Decrement inDegree[v]
            inDegree[v]--

            // ii. if inDegree[v] = 0, then insert v into next list
            if inDegree[v] == 0 {
                next = append(next, v)
            }
        }
    }

    // 6. Return the linear order
    return linearOrder
}

In our vertices DAG, the only vertices with an inDegree of 0 are 1, 2, and 9, so in a topographic sort one of those number would be first. Running this code seems to support that assertion:

$ go build -o topo_sort
$ ./topo_sort
[9 1 2 10 3 4 5 6 7 11 8 12 14]

In fact, all the vertices with no inDegrees ended up right at the beginning of this slice.

Can you dig it?

DAGs are ubiquitous and have many uses both inside and outside of computers. I keep running into them again and again: I stare this dad-joke cold in the face, once again, this evening.

Algorithms Unlocked talks in approachable language about using a DAG to graph and understand things like the order of operations for cooking a meal or for putting on hockey goalie equipment—I find the plain-spoken explanations charming and helpful. I dig this book, and this is far from the first exercise I’ve hacked through out of it. I’m sure I’ll be picking up this book again sometime in the near future–who knows?–I might even finish it!

Read the whole story
brennen
8 hours ago
reply
Boulder, CO
Share this story
Delete

Winners in the Chicago Tribune’s typewriter competitions held in...

1 Share








Winners in the Chicago Tribune’s typewriter competitions held in 1895. Found by James Ryan.

Read the whole story
brennen
8 hours ago
reply
Boulder, CO
Share this story
Delete

The Silent Witness

1 Share
1_14596842780_b4cdb13391_o

From “A New Library of Poetry and Song,” by William Cullen Bryant, The Baker Taylor Co., 1903

“Young people are often amazed at the tenacity with which older folk cling to their old furniture. They will take it with them from one house to another; usually to smaller houses, to bungalows or to a room ·or two as the family grows up and goes away and old age and infirmity increases. With each move the furniture grows more unsuited to its surroundings, too big and clumsy by far, and the young people think how odd to prefer these things to the modern stuff so much more suited to their surroundings. Then the young ones go off, themselves acquire homes and start along the same well-worn path. And the old folk, left alone with the familiar things, find something in them far more precious than anyone could know; memories of children and friends, of old joys and sorrows, every line and scar with a story behind it, every fine polished surface the record of their own youthful vigour. For Time, the artist, is at work again, and this is perhaps his last, best gift to them.”

— Charles Hayward, The Woodworker magazine, 1936


Filed under: Honest Labour, Uncategorized



Read the whole story
brennen
11 hours ago
reply
Boulder, CO
Share this story
Delete

Songs of distant earth

1 Share

For a few months in the early seventies, a curious debate briefly raged about sex in space. In designing the aluminum plaques that would be carried by two of the Pioneer spacecraft in case they were ever recovered by extraterrestrials, Carl Sagan and Frank Drake had included line drawings of an anatomically correct man and woman, and the response was about what you’d expect. As Sagan recalled in The Cosmic Connection:

The principal feminine criticism is that the woman is drawn incomplete—that is, without any sign of external genitalia. The decision to omit a very short line in this diagram [for the pudendal cleft] was made partly because conventional representation in Greek statuary omits it. But there was another reason: Our desire to see the message successfully launched on Pioneer 10. In retrospect, we may have judged NASA’s scientific-political hierarchy as more puritanical than it is…

Yet it is clear that at least some individuals were offended even by the existing representation. The Chicago Sun-Times, for example, published three versions of the page in different editions all on the same day: In the first the man was represented whole; in the second, suffering from an awkward and botched airbrush castration; and in the final version—intended no doubt to reassure the family man dashing home—with no sexual apparatus at all…The Philadelphia Inquirer published on its front page an illustration of the plaque, but with the nipples of the woman and the genitalia of the man removed. The assistant managing editor was quoted as saying: “A family newspaper must uphold community standards.”

A few years later, when a team led by Sagan had a chance to include a much more elaborate message on the golden phonograph records on the Voyager spacecraft, an identical issue arose. Timothy Ferris, one of the producers of the project, reveals in the new book The Voyager Golden Record: “NASA vetoed a photograph of a naked man and pregnant woman holding hands, likely concerned about the same prudish reaction stirred up by the nude drawings on the Pioneer plaques.” In the end, the record included a pair of vague, unrevealing diagrams—on the level of a grade school sex education class—and a reduced variation of the Pioneer drawing. Any aliens who are curious about human sexual reproduction, which is probably the single most fundamental fact about our culture, will come away very confused. And this wasn’t the only instance in which the team felt political pressure. Ferris recounts of the process of choosing the music:

A few politically motivated requests did crop up, among them a strange plea that we include a third-rate Russian nightclub standard on grounds that it might please the rulers of the Soviet Union. (We listened politely, then passed.) When we arrived at the Kennedy Space Center for the first Voyager launch, a NASA official confronted me to complain, “Damn it, Tim, how could a good Irish boy like yourself not put an Irish song on the record, knowing that Tip O’Neill is speaker of the House?” I was sorry to disappoint him, but one seldom succeeds at anything by trying to please everybody.

And before we smile, let’s take a moment to reflect that if a similar project were attempted today—presumably with Neil DeGrasse Tyson in charge—it would be approximately a million times worse. Just imagining the think pieces, tweets, and cable news segments makes my head hurt.

I’ve been thinking about this because I’ve just received my copy of The Voyager Golden Record box set, a Kickstarter project that turned about as well as I could have hoped: three hefty records of translucent gold vinyl, beautiful packaging, and a fascinating book. Listening to the music is like playing the strangest, most moving mix tape ever made, although it still leaves me with the same response expressed in my favorite joke from Saturday Night Live: “Send more Chuck Berry.” But if it were compiled again right now, I doubt that Berry would even make the cut. His obituaries from earlier this year were filled with an uneasy tension between his unquestioned stature and his private misbehavior, and if we’ve never totally assimilated it, it’s mostly because we’ve never been forced to do so. If we were putting together the Voyager record today, we’d have no choice but to deal with it directly, and I have a hunch that Berry would be quietly vetoed for exactly the same reasons that Chuck Klosterman applauds his inclusion:

I suspect the main reason “Johnny B. Goode” was chosen [for the Voyager record] is that it just seemed like a reasonable track to select. But it was more than reasonable. It was, either deliberately or accidentally, the best possible artist for NASA to select…Rock music is preoccupied with sex. Berry was a sex addict whose only American No. 1 single was about playing with his penis. Rock music is lawless. Berry went to prison twice before he turned forty. Rock music is tied to myth and legend…Berry is the subject of multiple urban legends, several of which might actually be true and which often seem to involve cheapness, violence and sexual defecation.

In fact, “Johnny B. Goode” just barely made it onto the record, as Ferris recalls: “Carl initially called it ‘awful.’ But he soon came around on that one, going so far as to politely remind [Alan] Lomax, who derided Berry’s music as ‘adolescent,’ that Earth is home to many adolescents.”

If nothing else, the Voyager anniversary release reminds us that we should be grateful that it happened at all, since it occurred at perhaps the one moment in our history when such a notion was technologically, culturally, and politically possible. Ferris says that he and Sagan “backed into the concept” of a record in their attempt to encode more material in a limited amount of space, but the fact that it led them to focus on music was the happiest of accidents. (He also debunks a famous story that I’ve spread here before: “Rumors to the contrary, we did not strive to include the Beatles’ ‘Here Comes the Sun,’ only to be disappointed when we couldn’t clear the rights. We did consider that lovely track for a time but soon moved on. It’s not the Beatles’ strongest work, and the witticism of the title, if charming in the short run, seems unlikely to remain funny for a billion years.”) Ferris argues that even the phonograph format itself is charged with significance:

A diamond dances along the undulations of the groove; its intricate motions vibrate an attached crystal (in the case of ceramic phono cartridges, like the ones attached to the Voyager probes); the vibrations generate a flow of electricity that’s amplified and sent to the speakers. At no point in this process is it possible to say with assurance just how much information the record contains or how accurately a given stereo has translated it. You never know whether a record might sound even better if played with a different phono cartridge, or at a different stylus pressure, or through different equipment. The open-mindedness of the medium seemed akin to the grand gesture of sending a record to the stars—and, for that matter, to scientific research, where one is always aware that more can be learned.

I’m not sure that I entirely believe this, but I’ll buy it. The Voyager record stands as one shining instance in which the highest ideals of science fiction found an embodiment in the real world, and perhaps you need to be a teenager to be as entranced by it as I once was. But earth is home to many adolescents.








Read the whole story
brennen
1 day ago
reply
Boulder, CO
Share this story
Delete

Another study adds to growing body of evidence that chiropractic neck manipulation is a risk factor for stroke. Patients should be warned of risk.

1 Share
Dan Lyke:

Cervical artery dissection related to chiropractic manipulation: One institution's experience.:

CONCLUSION: In this case series, 12 patients with newly diagnosed cervical artery dissection(s) had recent chiropractic neck manipulation. Patients who are considering chiropractic cervical manipulation should be informed of the potential risk and be advised to seek immediate medical attention should they develop symptoms.

Another study adds to growing body of evidence that chiropractic neck manipulation is a risk factor for stroke. Patients should be warned of risk.

Read the whole story
brennen
1 day ago
reply
Boulder, CO
Share this story
Delete

You Might Be Evil

1 Comment and 2 Shares

Or at least, your employer might be. Over the years we in the tech sector have gotten used to being well-regarded. After all, we make people’s live better, on balance. That’s changing. At the moment it’s rumblings from thought leaders, not pervasive popular anger. The other thing that’s new is that they’re thought leaders who are progressives and liberals; just like most of us in the tech professions. It notably involves the M-word and those of us on the inside need to be thinking about it.

The general public, by and large, love reading the news of their friends and the world on Facebook, buying stuff cheap on Amazon, using Google maps and mail for free, and using recent Windows releases at work.

But these days, it seems like every other day I read a chilling anti-tech rant, usually written by someone smart, articulate, and (like me) leftist. Here are a few recent offerings:

  • A Serf on Google’s Farm: About how the advertising end of the business fails to combine customer support and scalability, and what it feels like to be a minor customer: “It’s a bit like being assimilated by the Borg. You get cool new powers. But having been assimilated, if your implants were ever removed, you’d certainly die.” “Google is so big and so powerful that even when it’s trying to do something good, it can be dangerous and frightening.”

  • You can’t quit Facebook, a Twitter rant by Matt Stoller: “Your data and identity is trapped inside a machine that spends huge $$$ to addict and manipulate you, your friends, and your culture.” “We cannot as individual consumers resist the tens of billions spent to manipulate us. But we as citizens can do so through politics.”

  • Margrethe Vestager’s growing American fan club, on the savvy Eurocrat who’s been tormenting Google, Apple, and Facebook: “There is growing concern … about bigness and size, and power because power corrupts absolutely.”

  • There’s Blood In The Water In Silicon Valley: “This sort of political change happens slowly until it happens fast. Uber provided a new model for a transformative tech giant to crash through with a dark, negative brand.”

  • Facebook’s Heading Toward a Bruising Run-In With the Russia Probe, interesting not so much for the Russian angle but for the visceral contempt for Facebook: “Facebook’s ‘internal policies’ amount to a kind of Stepford Wives version of civic liberalism and speech and privacy rights, the outward form of the things preserved while the innards have been gutted and replaced by something entirely different, an aggressive and totalizing business model which in many ways turns these norms and values on their heads.”

Disclosures

I’m not going to claim my curation is unbiased. I left out Microsoft because, weirdly, nobody seems to hate Microsoft that much any more. I certainly don’t. I left out Twitter because it’s not actually a company, it’s a dysfunctional non-profit that accidentally provides a valuable service. I left out Amazon (although it appears in a few of those pieces) because I’d have no chance of coming anywhere near balance.

The M-Word

It’s “Monopoly” of course. If you follow the links above and read, the authors come at the tech giants from every which direction, but always ending up banging out the monopoly melody. Sometimes they say “corporate concentration” or another euphemism, because being anti-monopoly sounds kind of old-fashioned; and anyhow, shouldn’t you be talking about Comcast or United?

Not any more. A lot of smart people think it’s good economics, good policy, and good politics to aim the anti-trust gun at the tech sector. I’m not saying they’re wrong. I’m also not predicting that they’ll get any traction, particularly in the America where the short-term focus has to be on combating Nazis and pussy-grabbers.

But this is a trend that nobody in technology leadership should ignore.

Read the whole story
brennen
1 day ago
reply
No shit, Tim? You think?
Boulder, CO
Share this story
Delete
Next Page of Stories