The Hacker's Dictionary - - (the best novels to read .txt) 📗

problem' (TSP), a classical {NP-}hard problem: Suppose a person is in, say, Boston, and wishes to drive to N other cities. In what order should he or she visit them in order to minimize the distance travelled? The brute-force method is to simply generate all possible routes and compare the distances; while guaranteed to work and simple to implement, this algorithm is clearly very stupid in that it considers even obviously absurd routes (like going from Boston to Houston via San Francisco and New York, in that order). For very small N it works well, but it rapidly becomes absurdly inefficient when N increases (for N = 15, there are already 1,307,674,368,000 possible routes to consider, and for N = 1000 --- well, see {bignum}). See also {NP-}.

A more simple-minded example of brute-force programming is finding the smallest number in a large list by first using an existing program to sort the list in ascending order, and then picking the first number off the front.

Whether brute-force programming should be considered stupid or not depends on the context; if the problem isn't too big, the extra CPU

time spent on a brute-force solution may cost less than the programmer time it would take to develop a more `intelligent'

algorithm. Additionally, a more intelligent algorithm may imply more long-term complexity cost and bug-chasing than are justified by the speed improvement.

Ken Thompson, co-inventor of UNIX, is reported to have uttered the epigram "When in doubt, use brute force". He probably intended this as a {ha ha only serious}, but the original UNIX kernel's preference for simple, robust, and portable algorithms over {brittle} `smart' ones does seem to have been a significant factor in the success of that OS. Like so many other tradeoffs in software design, the choice between brute force and complex, finely-tuned cleverness is often a difficult one that requires both engineering savvy and delicate esthetic judgment.

:brute force and ignorance: n. A popular design technique at many software houses --- {brute force} coding unrelieved by any knowledge of how problems have been previously solved in elegant ways. Dogmatic adherence to design methodologies tends to encourage it. Characteristic of early {larval stage}

programming; unfortunately, many never outgrow it. Often abbreviated BFI: "Gak, they used a bubble sort! That's strictly from BFI." Compare {bogosity}.

:BSD: /B-S-D/ n. [abbreviation for `Berkeley System Distribution'] a family of {{UNIX}} versions for the DEC {VAX} and PDP-11

developed by Bill Joy and others at {Berzerkeley} starting around 1980, incorporating paged virtual memory, TCP/IP networking enhancements, and many other features. The BSD versions (4.1, 4.2, and 4.3) and the commercial versions derived from them (SunOS, ULTRIX, and Mt. Xinu) held the technical lead in the UNIX world until AT&T's successful standardization efforts after about 1986, and are still widely popular. See {{UNIX}}, {USG UNIX}.

:BUAF: // [abbreviation, from the alt.fan.warlord] n. Big Ugly ASCII Font --- a special form of {ASCII art}. Various programs exist for rendering text strings into block, bloob, and pseudo-script fonts in cells between four and six character cells on a side; this is smaller than the letters generated by older {banner} (sense 2) programs. These are sometimes used to render one's name in a {sig block}, and are critically referred to as `BUAF's. See {warlording}.

:BUAG: // [abbreviation, from the alt.fan.warlord] n. Big Ugly ASCII Graphic. Pejorative term for ugly {ASCII ART}, especially as found in {sig block}s. For some reason, mutations of the head of Bart Simpson are particularly common in the least imaginative {sig block}s. See {warlording}.

:bubble sort: n. Techspeak for a particular sorting technique in which pairs of adjacent values in the list to be sorted are compared and interchanged if they are out of order; thus, list entries `bubble upward' in the list until they bump into one with a lower sort value. Because it is not very good relative to other methods and is the one typically stumbled on by {na"ive} and untutored programmers, hackers consider it the {canonical}

example of a na"ive algorithm. The canonical example of a really bad algorithm is {bogo-sort}. A bubble sort might be used out of ignorance, but any use of bogo-sort could issue only from brain damage or willful perversity.

:bucky bits: /buh'kee bits/ n. 1. obs. The bits produced by the CONTROL and META shift keys on a SAIL keyboard (octal 200 and 400

respectively), resulting in a 9-bit keyboard character set. The MIT AI TV (Knight) keyboards extended this with TOP and separate left and right CONTROL and META keys, resulting in a 12-bit character set; later, LISP Machines added such keys as SUPER, HYPER, and GREEK (see {space-cadet keyboard}). 2. By extension, bits associated with `extra' shift keys on any keyboard, e.g., the ALT on an IBM PC or command and option keys on a Macintosh.

It is rumored that bucky bits' were named for Buckminster Fuller during a period when he was consulting at Stanford. Actually,Bucky' was Niklaus Wirth's nickname when he was at Stanford; he first suggested the idea of an EDIT key to set the 8th bit of an otherwise 7-bit ASCII character. This was used in a number of editors written at Stanford or in its environs (TV-EDIT

and NLS being the best-known). The term spread to MIT and CMU

early and is now in general use. See {double bucky}, {quadruple bucky}.

:buffer overflow: n. What happens when you try to stuff more data into a buffer (holding area) than it can handle. This may be due to a mismatch in the processing rates of the producing and consuming processes (see {overrun} and {firehose syndrome}), or because the buffer is simply too small to hold all the data that must accumulate before a piece of it can be processed. For example, in a text-processing tool that {crunch}es a line at a time, a short line buffer can result in {lossage} as input from a long line overflows the buffer and trashes data beyond it. Good defensive programming would check for overflow on each character and stop accepting data when the buffer is full up. The term is used of and by humans in a metaphorical sense. "What time did I agree to meet you? My buffer must have overflowed." Or "If I answer that phone my buffer is going to overflow." See also {spam}, {overrun screw}.

:bug: n. An unwanted and unintended property of a program or piece of hardware, esp. one that causes it to malfunction. Antonym of {feature}. Examples: "There's a bug in the editor: it writes things out backwards." "The system crashed because of a hardware bug." "Fred is a winner, but he has a few bugs" (i.e., Fred is a good guy, but he has a few personality problems).

Historical note: Some have said this term came from telephone company usage, in which "bugs in a telephone cable" were blamed for noisy lines, but this appears to be an incorrect folk etymology. Admiral Grace Hopper (an early computing pioneer better known for inventing {COBOL}) liked to tell a story in which a technician solved a persistent {glitch} in the Harvard Mark II machine by pulling an actual insect out from between the contacts of one of its relays, and she subsequently promulgated {bug} in its hackish sense as a joke about the incident (though, as she was careful to admit, she was not there when it happened). For many years the logbook associated with the incident and the actual bug in question (a moth) sat in a display case at the Naval Surface Warfare Center. The entire story, with a picture of the logbook and the moth taped into it, is recorded in the `Annals of the History of Computing', Vol. 3, No. 3 (July 1981), pp. 285--286.

The text of the log entry (from September 9, 1945), reads "1545

Relay #70 Panel F (moth) in relay. First actual case of bug being found". This wording seems to establish that the term was already in use at the time in its current specific sense --- and Hopper herself reports that the term bug' was regularly applied to problems in radar electronics during WWII. Indeed, the use ofbug' to mean an industrial defect was already established in Thomas Edison's time, and bug' in the sense of an disruptive event goes back to Shakespeare! In the first edition of Samuel Johnson's dictionary one meaning ofbug' is "A frightful object; a walking spectre"; this is traced to `bugbear', a Welsh term for a variety of mythological monster which (to complete the circle) has recently been reintroduced into the popular lexicon through fantasy role-playing games.

In any case, in jargon the word almost never refers to insects.

Here is a plausible conversation that never actually happened: "There is a bug in this ant farm!"

"What do you mean? I don't see any ants in it."

"That's the bug."

[There has been a widespread myth that the original bug was moved to the Smithsonian, and an earlier version of this entry so asserted. A correspondent who thought to check discovered that the bug was not there. While investigating this in late 1990, your editor discovered that the NSWC still had the bug, but had unsuccessfully tried to get the Smithsonian to accept it --- and that the present curator of their History of American Technology Museum didn't know this and agreed that it would make a worthwhile