h

karin

INTRODUCTION

Brian Wilson Kernighan was born in Toronto, Ontario, Canada in 1942. He is currently employed by Princeton University. He wrote The C Programming Language and The Practice of Programming. He has worked as a computer scientist and a programmer, and his current occupation is scientist. who coined the term Unix in the 1970s. The original term he coined was Unics (for Uniplexed Information and Computing Service, a play on Multics), which was later changed to Unix, worked at Bell Labs alongside Unix creators Ken Thompson and Dennis Ritchie and contributed to the development of Unix. He is also coauthor of the AWK and AMPL programming languages. The ‘K’ of K&R C and the ‘K’ in AWK both stand for ‘Kernighan’. Brian Kernighan is currently a Professor at the Computer Science Department of Princeton University, where he is also the Undergraduate Department Representative.
Brian W. Kernighan is head of the Computing Structures Research Department, BellLaboratories, Murray Hill, New Jersey. He received a B.A.Sc in engineering physics from theUniversity of Toronto in 1964, and a Ph.D. in electrical engineering from Princeton University in1969. Since joining Bell Labs in 1969, he has worked in combinatorial optimization, documentpreparation systems, programming languages, and software tools. His current research interests are in application-oriented programming languages, programming methodology, and user interfaces.
Dr. Kernighan is the co-author of several books, including “The C Programming Language” and“The UNIX Programming Environment”.
Brian Kernighan is in the Computing Science Research Center at Murray Hill, where he has beenin the same office since 1969. (It has been painted once.) He writes programs and occasionally books. The latter are better than the former, and certainly need less maintenance.
Kernighan was the software editor for Prentice Hall International. His “Software Tools” series spread the essence of ‘C/Unix thinking’ with makeovers for BASIC, FORTRAN, and Pascal – and most notably his ‘Ratfor’ (rational FORTRAN) was put in the public domain.

BRIAN KERNIGHAN’S PROGRAMMING STYLE TIPS

Here is a summary of the very important programming style tips from Brian Kernighan’s 1994 guest CS50 lecture.
 
  Say what you mean, simply and directly.
 Use the “telephone test” for readability.
Write clearly – don’t be too clever.
Don’t use conditional expressions as a substitute for a logical expression.
Parenthesize to avoid ambiguity.
 Each time you make a test, do something.
Follow each decision as closely as possible with its associated action.
Use the good features of a language; avoid the bad ones.
Capture regularity in control flow, irregularity in data.
Each module should do one thing well.
Make sure comments and code agree.
Don’t just echo the code with comments – make every comment count.
Don’t comment bad code – rewrite it.
 Use symbolic constants for magic numbers.
Watch out for side effects and order of evaluation.
Macros are not functions.
Watch out for off-by-one errors.
Test programs at their boundaries.
Program defensively.
Make sure input cannot violate the limits of the program.
Make it right before you make it faster.
Keep it right when you make it faster.
Don’t sacrifice clarity for small gains in “efficiency.”
Don’t stop with your first draft.

KERNIGHAN–LIN ALGORITHM

                                Key terms and concepts: a cost matrix plus connectivity matrix models system • measure isthe cut cost, or cut weight • careful to distinguish external edge cost and internal edge cost •net-cut partitioning and edge-cut partitioning • hypergraphs with stars, and hyperedges modelconnections better than edges • the Fiduccia–Mattheyses algorithm uses linked lists to reduce O(K–L algorithm) and is very widely used • base logic cell • balance • critical net

k

A HYPERGRAPH

 (a) The network contains a net y with three terminals.
 (b) In the network hypergraph we can model net y by a single hyperedge (B, C, D) and a star node.
 Now there is a direct correspondence between wires or nets in the network and hyperedges in the graph.

Untitled-1 copy

PARTITIONING A GRAPH USING THE KERNIGHAN–LIN ALGORITHM

 (a) Shows how swapping node 1 of partition A with node 6 of partition B results in a gain of g =1.
 (b) A graph of the gain resulting from swapping pairs of nodes.
(c) The total gain is equal to the sum of the gains obtained at each step.
 

ggg

TERMS USED BY THE KERNIGHAN–LIN PARTITIONING ALGORITHM

(a) An example network graph.

(b) The connectivity matrix, C; the column and rows are labeled to help you see how the matrix entries correspond to the node numbers in the graph.For example, C 17 (column 1, row 7) equals 1 because nodes 1 and 7 are connected.In this example all edges have an equal weight of 1, but in general the edges may have different weights.


PUBLICATIONS

  • The C Programming Language home page.
  • The Practice of Programming home page.main
  • The Unix Programming Environment home page.
  • The AWK Programming Language home page.
  • AMPL: A Modeling Language for Mathematical Programming home page.
  • Scanned pages of An Efficient Heuristic Procedure for Partitioning Graphs (Bell System Technical Journal, February, 1970); 750KB pdf.
  • Scanned pages of An Effective Heuristic Algorithm for the Travelling-Salesman Problem (Operations Research, March, 1973); the format needs work.
  • Why Pascal is Not My Favorite Programming Language (April, 1981).
  • WiSE – A Wireless System Engineering Tool, an application of computational geometry, optimization and visualization to wireless.
  • Experience with Tcl/Tk for Scientific and Engineering Visualization, programming issues in the wireless work above; a version appeared in the Tcl/Tk Workshop, Toronto, 1995. (Careful: 11Mb of Postscript when unzipped.)
  • Extracting Geometric Information from Architectural Drawings, with Chris Van Wyk, from the Workshop on Applications of Computational Geometry, Philadelphia, May, 1996. (630K)
  • Timing Trials, or, the Trials of Timing: Experiments with Scripting and User-Interface Languages, with Chris Van Wyk, describes experiments to see how fast various scripting and user interface languages, from Awk to Visual Basic, run on a spectrum of representative tasks. Postscript version (250KB). The tests themselves are also available, as is the input data (1.7Mb). Updated 11/30/97.
  • “An AWK to C++ Translator” (Postscript) describing an early experiment; published in the Usenix C++ conference in 1991 but hard to find.
  • Bibliography in bibtex format or in html format.

SOFTWARE (CAVEAT EMPTOR)

Information about the AMPL modeling language for mathematical optimization.

 I have had trouble updating this code, so the current version (October 23, 2007) is found at Princeton: newest Awk source

✔ Source for the one true awk, updated May 1, 2007. Shell archive; gzipped tar file; zip file. There is also a Windows executable.

  Examples from The AWK Programming Language by Aho, Kernighan, and Weinberger as text (120KB) or zipped (30KB).

All the example code from The Unix Programming Environment by Kernighan and Pike: gzipped tar file; zip file.

  Source for the hoc calculator from The Unix Programming Environment by Kernighan and Pike.

 Software Tools programs

Software Tools in Pascal programs

✔  Source for learn, the original Unix computer-aided instruction program. This works but is mostly of historical interest; it dates from about 1979. (If your version of the ar command gives you trouble, this version has the files already extracted and does not use ar.)

✔  A very dusty version of code for algorithm animation (with Jon Bentley).

✔  Code for timing tests (with Jon Bentley and Chris Van Wyk, updated 7/96).

 Miscellaneous ancient typesetting code, including chem and indexing tools (with Jon Bentley).

BRIAN W.KERNIGHAN QUOTES

The most effective debugging tool is still careful thought, coupled with judiciously placed print statements

Brian W. Kernighan, in the paper Unix for Beginners (1979)

Controlling complexity is the essence of computer programming.

Brian W. Kernighan

“Everyone knows that debugging is twice as hard as writing a program in the first place. So if you’re as clever as you can be when you write it, how will you ever debug it?”

Brian W. Kernighan

“I’d give my right arm to be ambidextrous.”

Brian W. Kernighan

Advertisements