[author : Jon Louis Bentley] #Algorithm #Method #Book

Extract : «  “Algorithm design—that’s the field where people talk about programs and prove theorems about programs instead of writing and debugging programs.” Statements along these lines have been uttered by applications programmers and academicians alike. But there are also some who say, “No! Proper algorithm design has helped us to save kilobucks at our installation every month.” Here we will investigate the field of algorithm design (also know as “analysis of algorithms” and “concrete computational complexity,” among other names) and better equip the reader to judge the field for himself. [...]

This survey discusses algorithm analysis from three viewpoints. We first examine five problems and some algorithms for solving them. Having considered these concrete examples, we next take a systematic tour of the field. We then investigate some current research directions and conclude with an assessment of the field’s value to practitioners. [...]

Subset testing [...]

Hashing [...]

Substring searching [...]

The fast Fourier transform [...]

Matrix multiplication [...]

Public-key cryptography [...]  »

[author : Marvin A. Konopik] #BASIC

Extract : «  I have broken some of the secrets of the Poly 88 BASIC version A00 that might be helpful to others in understanding their BASIC as well, or at least help to get a handle on it. The Poly BASIC Manual contains a great deal of technical information, but the many ways this information can be used is not fully explained. After retyping a program for the third time, I threw in the towel, and decided there must be an easier way. So, I have listed below some short-cuts that make computer life a whole new game and a lot more fun. [...]  »

[author : D.V. Schorre] #Programming #Language #Algorithm #Listing #Book

Extract : «  This classic paper describes a metacompiler developed as a project of the Los Angeles Chapter of SIGPLAN, the Association for Computing Machinery’s special interest group in programming languages. Several artifacts of the time appear - the use of ”.,” rather than ”;” and the use of “/" rather than “|” is due to the limited character set on the IBM 026 keypunch. The original Meta II ran on the IBM 1401, a machine with limited resources by today’s standards. We’ve reprinted it here because it is still a good tool for experimenting with languages and their implementation. To install a Meta II system on your computer, you must hand-compile the Meta II compiler given in the article (an instructive exercise in itself] and write an interpreter for the Meta II machine in some suitable language (Microsoft BASIC wouldn't be a bad choice). To check the whole thing, the compiler should compile itself exactly. If not, fix the bug(s) and try again. In the end, you’ll have a nice tool for experimenting with programming languages and learn a bit about the compiling process to boot. - Dennis R. Allison [...]  »

[author : Titus Purdin] #Listing #Assembly #Programming

Extract : «  In the course of two years of micro computing, I cannot count the number of times friends and acquaintances have offered me copies of programs they have written, only to be disappointed because their BASIC and my BASIC were so vastly different. In many cases, when the offered programs were just too good to pass up, I have locked myself in the study for an evening and made the necessary conversions. It isn’t a job that I relish. And while I haven’t found an easy way to accomplish it, I have developed, over time, some tools to ease the burden. [...]  »

[author : John W. Carter] #Listing #Assembly #Programming

Extract : «  Many new users of microcomputer systems purchase those systems with one predominant software objective: BASIC programming. Such a high-level language is certainly convenient and relatively powerful. However, BASIC and other high-level languages have a distinct disadvantage in terms of execution time and memory usage. Two major types of high-level languages are now in common use: compilers and interpreters.

Compilers are programs which convert an entire high-level source program into object (binary) code, and generate an object program which is later executed without aid of the compiler. In generating the object program, the compiler generates and calls object subroutines when processing is required. Repetition of these subroutines makes the object program inefficient in terms of execution time and memory usage. However, this trade-off can be more than offset by the convenience of the high-level language.

Interpreters are programs which convert a high-level source program into object code one line at a time. That is, each line or source code is compiled and executed individually, requiring recompilation for each execution. No object code is preserved. Therefore, in order to execute such a source program, both the source program and the interpreter must reside in the memory space (usually RAM). This procedure is extremely slow and consumes large quantities of memory space. A good example of this is evident in the long looping operations of BASIC interpreters. For example, the execution time of a bubble sort of more than 1000 elements is formidable. You can expect to wait as long as an hour for such a sort to execute — depending, of course, on the data structure. [...]  »

[author : Robert D. Fusfeld] #Listing #Assembly #Sciences #Book

Extract : «  [...] The importance of Fourier Transforms is that spectral analysis is an extremely valuable tool in many types of engineering and scientific investigations. Applications occur in electrical engineering, vibration analysis, meteorology, speech recording and synthesis, music, etc. Naturally, due to the widespread use, many computer programs to perform the FFT calculation are readily available, particularly in high level languages such as ALGOL and FORTRAN (Ref. 2). When it comes to the microcomputer, BASIC programs are available such as the one by Stanley and Peterson (Ref. 3). However, in the interest of economy of memory and of computation time, implementation of the FFT in machine language is highly desireable. This was done for the 6800 CPU by Lord (Ref. 4). The program listed here is a similar one for the 8080 CPU. [...]  »

[author : Dennis Allison ] #Listing #C #Algorithm

Extract : «  With this issue of Dr. Dobb’s Journal we begin a new series concentrating on the building-blocks of systems rather than the systems themselves. One of the failings of most of us is the inability or disinclination to take and use the work of others. Everyone writes his own sort program, his own integration program, and so on ad infinitum. Often it would be better and faster to take an existing program and reuse it. Of course that is not always possible, but often one can take the algorithm and adapt it easily. [...]  »