Abner's Postgraduate Days

Ref. Continuing the early post, Note on Empirical Methods in CS and AI

Ref. : A Theoretician's Guide to the Experimental Analysis of Algorithms, D. S. Johnson. in Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Implementation Challenges, M. H. Goldwasser, D. S. Johnson, and C. C. McGeoch, Editors, American Mathematical Society, Providence, 2002, 215-250.

This paper discuss more explicit on EA. D. S. Johnson also gave a summary in this paper.







Ref. Catherine McGeoch, "Analyzing algorithms by simulation: variance reduction techniques and simulation speedups," ACM Comput. Surv., volume 24, number 2, 1992, pp. 195--212.

Ref. Catherine C. McGeoch and Bernard M. E. Moret, "How to present a paper on experimental work with algorithms," SIGACT News, volume 30, number 4, 1999, pp. 85--90.

I am tired. Every time I do homeworks, I got negative feeling. I like to study those intellectuals' wisdom and seminal idea, but I always feel blue for the huge drop between those smart people and me when I study those problems.

This is a big problem for me.

However, I need to take a rest now.

It's strange that "all computable functions are continuous."

Andrej Bauer writes an article "Sometimes all functions are continuous" on his blog "Mathematics and Computation"

He use different definition of function, i.e., a function f is a computational procedure which takes as an input x and yields as output a uniquely determined y. And he prove that all functions are continuous.

When constructive mathematicians says that ¡§all functions are continuous¡¨ they have something even better in mind. They are telling you that all functions are computably continuous. This is where interesting stuff begins to happen.

It's fun to me, but the rest of this article about programming language is more strange for me. I totally lost.

I read the papers which I mentioned before.

"On The Emerging Future Of Complexity Sciences" is funny; it is a good introductory paper. I don't know that there exist two schools of thought on complexity:

This has led to different schools of thought that have their own language and priorities: one looks into complexity as an emerging phenomenon to be understood, while the other looks into complexity as an engineering problem to be tackled.

I like the parts about historical material.

"On modeling the immune system as a complex system" gives some comprehensible definitions such as

Definition 1. A complex system (Smith, 2003), is the one with multiple interacting elements whose collective behavior cannot be simply inferred from the behavior of its elements.

Definition 2. An emergent property of a complex system is the property of the complex system as a whole but it does not exist in each individual element.

However, the reason which attracted me to read this paper is the following sentences :

We agree that CA type systems are more suitable to model complex biological systems but such systems suffer from a main drawback namely the difficulty of obtaining analytical results. The known analytical results about CA-type systems are very few compared to the known results about ODE and PDE.

This paper argued that immune system is a complex system and introduced "telegraph reaction diffusion equations".(Ref. 1)

This paper doesn't tell much about the detail, and the PDE method, telegraph reaction diffusion equations, is not my interest. However, it is still a guidepost for me.



Ref. 1 : On Diffusion in Some Biological and Economic Systems, E. Ahmed and S. Z. Hassan, Zeitschrift f Êr Naturforschung A, vol 55, no 8, 2000, pp. 669.(This paper proposed that they could construct Cattaneo CA corresponding to telegraph reaction diffusion equations with game theory. It seems really interesting!)

Ref. 2 : Louzoun, Y., Solomon, S., Atlan, H., Cohen, I.R., 2003. Proliferation and competition in discrete biological systems. Bull. Math. Biol. 65, 375¡V396. (This paper argued that PDE/ODE are not good for modeling biological systems.)

From Wikipedia,

In mathematics, computational group theory is the study of groups by means of computers. It is concerned with designing and analysing algorithms and data structures to compute information about groups.

Are there any interesting applications of CGT for computer science?

I found some resources about CGT, but it seems no applications of computer science. Although Knuth contributed an algorithm in this field. But I couldn't understand the delights of classification of finite simple groups.

The course, 18.317 Combinatorics, Probability and Computations on Groups (Fall 2001), which was given by Igor Pak might be clues for applying CGT to computer science.

Ref. C. Blum and A. Roli (2003). Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys 35(3)

This word "Metaheuristic" seems hard to define. Blum and Roli quote several definitions or descriptions of that word on pp. 270. For example :

A metaheuristic is a set of concepts that can be used to define heuristic methods that can be applied to a wide set of different problems. In other words, a metaheuristic can be seen as a general algorithmic framework which can be applied to different optimization problems with relatively few modifications to make them adapted to a specific problem. [Metaheuristics Network Website 2000].

However, I think that listing some metaheuristic algorithms is helpful to understood this word, i.e., Ant Colony Optimization (ACO), Evolutionary Computation (EC) including Genetic Algorithms (GA), Iterated Local Search (ILS), Simulated Annealing (SA), and Tabu Search (TS).

Actually, as I had said, I don't like EC, ACO, GA....etc. I think my taste is applied mathematic oriented, but the metaheuristic approach might be more computer science oriented. Because this approach can't appear before invention of computer, those approaches are more depending on the power of computing. I think those algorithms are really computer science style.

2006-12-03 Update:

• Metaheuristic - Wikipedia, the free encyclopedia
• Tabu Search -- from Wolfram MathWorld
• Tabu search - Wikipedia, the free encyclopedia
• Sandia National Laboratories: Global Optimization Survey:: Tabu Search

  The basic concept of Tabu Search as described by Glover (1986) is "a meta-heuristic superimposed on another heuristic. The overall approach is to avoid entrainment in cycles by forbidding or penalizing moves which take the solution, in the next iteration, to points in the solution space previously visited ( hence "tabu").

Last night, the material of LEAST Meeting was "Stochastic Context-Free Grammars for tRNA Modeling," by Yasubumi Sakakibara, Michael Brown, Richard Hughey, I. Saira Mian, Kimmen Sjolander, Rebecca C. Underwood and David Haussler. Nucleic Acids Research ,22(23):5112--5120, 1994.

Stochastic context-free grammars (SCFGs) are applied to the problems of folding, aligning and modeling families of tRNA sequences. SCFGs capture the sequences' common primary and secondary structure and generalize the hidden Markov models (HMMs) used in related work on protein and DNA. Results show that after having been trained on as few as 20 tRNA sequences from only two tRNA subfamilies (mitochondrial and cytoplasmic), the model can discern general tRNA from similar-length RNA sequences of other kinds, can find secondary structure of new tRNA sequences, and can produce multiple alignments of large sets of tRNA sequences. Our results suggest potential improvements in the alignments of the D- and T-domains in some mitochdondrial tRNAs that cannot be fit into the canonical secondary structure.

The main idea is easy. We know that tRNA has good preservation of secondary structure such as cross structure. Therefore, we could write down a kind of context-free grammar to generate all possible structures. However, it is not good enough for 2ed structure prediction of tRNA, because there exist a lot of ambiguous condition. Therefore, they add stochastic property to CFG, and use machine learning to train the possibility values. After getting the trained possibility, they use CYK algorithm which is a dynamic programming approach to generate a parse tree to generate a most possible parse tree. That is a most possible 2ed structure.

Recently, I assisted my adviser to review NSC proposal. To judge a proposal, there are many criteria, e.g., the ability of proposer, the experience of proposer, and direction and method in this proposal.

I thought about a funny thing, i.e., how to write a proposal for theoretical research?

How do we know what last and critical method for solving problem is?

The reporter today is Yu-Han. He report this paper, Daniel A. Spielman and Shang-Hua Teng, Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time, J. ACM, volume 51, number 3, 2004, pp. 385--463.

The main idea is that if we could get the expected running time for corresponding case, we can introduce the idea "neighborhood" to calculate the value of neighborhood of a case. They measure the maximum over inputs of the expected performance of an algorithm under small random perturbations of that input.

What do we benefit from the method?

In smoothed analysis, the authors told us that simplex method is in polynomial time. However, does it really tell us something? The smoothed analysis inherited some defects of traditional analysis method. It could point out some properties in some algorithms with huge difference between worst-case and average-case, but it couldn't avoid some problems like huge coefficients.

From some practical testing, we had known that simplex method is efficient at most cases and with small possibility to cost exponential time; it couldn't save our time for doing some practical experiments, because it inherited some defects of traditional analysis method.

I don't know the real advantage of smoothed analysis.

Update 20060323 :
Prof. Daniel Spielman taught a course, Behavior of Algorithms, at Spring 2002. According to his syllabus, he centered around the following three approaches, Smoothed Analysis, Condition Numbers/Parametric Analysis, Subclassing Inputs. It might be a good reference.

G. Polya write a fantastic small book, How to Solve It. In this book, he taught reader how to solve a problem. He asked us "Do you know a related problem? Do you know a theorem that could be useful?"

Although I always said that I am a theorist, I didn't know many algorithms. It made me poor when I tried to solve problem and connecting the new algorithm with my knowledge. Therefore, I decided to sit in the course Computational biology.

I unexpectedly found two interesting survey papers; Michael C. Loui, Strategic directions in research in theory of computing, ACM Comput. Surv., volume 28, number 4, 1996, pp. 575-590 ; A. Sameh and G. Cybenko and M. Kalos and K. Neves and J. Rice and D. Sorensen and F. Sullivan, Computational science and engineering, ACM Comput. Surv., volume 28, number 4, 1996, pp. 810-817

From the first paper,

For my personal taste, good algorithms mean efficient, elegant, and proven. However, in the real world, there are a lot of intractable problems. In practical perspective, heuristic algorithm might be the maximum amount of algorithms, especially in some fields as VLSI CAD, AI, etc.

The implementation part might be easy part. Although the programming optimization is a very important work, but the hardest part, especially for research, might be the part of experimental analysis.

In linear programming, simplex method is thought faster than interior point methods. How do we compare the difference of algorithms?



I will plan to read some articles about Empirical Methods in CS. It might be not so important in my field, but important for my career.(I guessed so....:-))

The materials are from "Empirical Methods in CS and AI" maintained by Toby Walsh.

Ref. : Moret, B.M.E., "Towards a discipline of experimental algorithmics," in Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Implementation Challenges, M.H. Goldwasser, D.S. Johnson, and C.C. McGeoch, eds, DIMACS Monographs 59, 197-213, American Mathematical Society, Providence, 2002

Natural scientists run experiments because they have no other way of learning from nature. In contrast, algorithm designers run experiments mostly because an analytical characterization is too hard to achieve in practice. (Much the same is done by computational scientists in physics, chemistry, and biology, but typically their aim is to analyze new data or to compare the predictions given by a model with the measurements made from nature, not to characterize the behavior of an algorithm.)

This paper also discuss drawbacks of current theoretical analysis of algorithm, i.e., the neglected coefficient of big-O might be too large to be impractical. It is a notorious drawback of big-O, but the author give a evidence :

An extreme example of this problem is provided by the theory of graph minors: Robertson and Seymour (see [42]) gave a cubic-time algorithm to determine whether a given graph is a minor of another, but the proportionality constants are gigantic¡Xon the order of 10150¡Xand have not been substantially lowered yet, making the algorithm entirely impractical.

In this paper, I also learn a funny word, metaheuristics. This word appeared on a paragraph of a important condition of EA.

All optimization metaheuristics for NP-hard problems (such as simulated annealing or genetic algorithms) suffer from this drawback: by considering a large number of parameters and a substantial slice of recent execution history, they create a complex state space which is very hard to analyze with existing methods, whether to bound the running time or to estimate the quality of the returned solu-tion. Another classic example is the deceptively simple Union-Find data structure (see, e.g., [36], Section 3.2): the combination of Union by rank (or size) and path compression was known to yield very efficient behavior, yet its exact characterization eluded researchers for many years, until Tarjan proved tight bounds [47]. (Of course, in this particular case, experimentation would have proved futile, since no amount of experimentation, on an conceivable dataset, could show supralinear growth in the running time.)

In this paper, I first time see the word, Algorithm Engineering.

More specifically, however, algorithm engineering seeks to produce the most efficient, as well as most usable, implementation possible.

(pp. 8) I will collect some info. about it at a new entry.

Section 5. Experimental Setup

This section is what I really want to learn, but the author doesn't spend too much efforts on it. The author just enumerate some potential pitfalls:

• The choice of machine (caching, addressing, data movement), of language (register manipulation, built-in types), or of compiler (quality of optimization and code generation).
• The quality of the coding (consistency and sophistication of programmers).
• The selection or generation of instances (we must use sufficient size and variety to ensure significance).
• The method of analysis (many steps can be taken to improve the significance of the results as well as to bring out trends)
• Uninteresting work: comparing programming languages or specific platforms, in particular unusual ones; comparing algorithms with widely different behavior (linear and quadratic, say); etc.
• Bad setup: testing up to some fixed running time or space without verifying whether the asymptotic behavior has manifested; testing too few instances; using rough code without any attempt at optimization and measuring running times; using ``found code'' without any documentation (a temptation these days on the net); ignoring existing test suites; ignoring existing and widely used libraries; etc.
• Bad analysis or presentation: discarding data that do not fit without any explanation or even warning; presenting all of the data without analysis; using comparisons to undefined ``standards'' (e.g., to the system sort routine).

I had thought that we can build a virtual machine as a platform for testing algorithms. It might avoid some difficult in gathering clear experimental data. However, it might not match the goal of algorithm engineering.

Further Reading (for myself):

• Metaheuristic - Wikipedia, the free encyclopedia
• C. Blum and A. Roli A. (2003). Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys 35(3) 268-308
• Robert Sedgewick, Implementing Quicksort programs, Commun. ACM, volume 21, number 10, 1978, pp. 847--857.
• Chekuri, C.S., Goldberg, A.V., Karger, D.R., Levine, M.S., and Stein, C., ``Experimental study of minimum cut algorithms,'' Proc. 8th ACM/SIAM Symp. on Discrete Algs. SODA97, SIAM Press (1997), 324¡V333.
• Johnson, D.S., Aragon, C.R., McGeoch, L.A., and Schevon, C., ``Optimization by simulated annealing: an experimental evaluation. 1. Graph partitioning,'' Operations Research 37 (1989), 865¡V892.
• Johnson, D.S., Aragon, C.R., McGeoch, L.A., and Schevon, C., ``Optimization by simulated annealing: an experimental evaluation. 2. Graph coloring and number partitioning,'' Operations Research 39 (1991), 378¡V406.
• Finkler, U., and Mehlhorn, K., ``Runtime prediction of real programs on real machines,'' Proc. 8th ACM/SIAM Symp. on Discrete Algs. SODA97, SIAM Press (1997), 380¡V389.
• McGeoch, C.C., ``Analysis of algorithms by simulation: variance reduction techniques and simulation speedups,'' ACM Comput. Surveys 24 (1992), 195¡V212.

Ref. : Moret, B.M.E., "Towards a discipline of experimental algorithmics," in Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Implementation Challenges, M.H. Goldwasser, D.S. Johnson, and C.C. McGeoch, eds, DIMACS Monographs 59, 197-213, American Mathematical Society, Providence, 2002

In this paper, I first time see the word, Algorithm Engineering.

More specifically, however, algorithm engineering seeks to produce the most efficient, as well as most usable, implementation possible.(pp. 8)

The following are some resources:

• Algorithm Engineering Group, Department of Computer and System Sciences, University of Rome "La Sapienza"

• . Algorithm engineering is concerned with the design, theoretical and experimental analysis, engineering and tuning of algorithms, and is gaining increasing interest in the algorithmic community. This emerging discipline addresses issues of realistic algorithm performance by carefully combining traditional theoretical methods together with thorough experimental investigations.

  from School on Algorithm Engineering, September 10-12, 2001
• Algorithm Engineering | Research | CSSE | UC
• Algorithm Engineering Research Group, University of Perugia.
• Algorithm Engineering Research Group, Home Page Dipartimento di Informatica e Automazione Universit à degli studi Roma Tre.
• The Geomblog: Why do algorithm engineering ?<

  But ultimately, the goal of algorithm engineering, or of good experimental algorithmic work, is to tease out the tradeoffs, parameters and special cases that govern which algorithm is the right one for a specific setting. If I am a practitioner, I am less interested in knowing the algorithm with the best asymptotic efficiency than I am in knowing which algorithm can provide the best performance for my situation. This does not mean that we should throw proofs out of the window: it means that often a much more delicate analysis of the behaviour of an algorithm is required in order to determine what works better.

• Center for Algorithm Engineering (formerly the Center for Geometric Computing)

I read the book "Writing the Laboratory Notebook" by Howard M. Kanare couple weeks ago. It is good book. But it is not so suitable for me, a theoretical computer science student It's not reasonable that to note every details during attacking a problem. Although the general disciplines are nice, I still want to get more explicit help.

Well, according to my collected data, I will read the next book "An Introduction to Scientific Research" by E. Bright Wilson

Besides two assigned papers, there are some interesting papers.

Next week, my adviser and senior members have a meeting for reviewing papers of COCOON'06. I might sit in that meeting. I am interested in three papers about Folded Hypercubes, Block Design, and Auto-Scheduling, respectively.

Additionally, from Complexity Digest 2006.11, two papers catch my eyes.

E. Ahmed and A.H. Hashish, On modeling the immune system as a complex system, Theory in Biosciences, Volume 124, Issues 3-4, , 1 March 2006, Pages 413-418. [Link]

Abstract: We argued that immune system is an adaptive complex system. It is shown that it has emergent properties. Its network structure is of the small world network type. The network is of the threshold type, which helps in avoiding autoimmunity. It has the property that every antigen (e.g. virus or bacteria) is typically attacked by more than one effector. This stabilizes the equilibrium state. Modeling complex systems is discussed. Cellular automata (CA)-type models are successful, but there are much less analytic results about CA than about other less successful models e.g. partial differential equations (PDE). A compromise is proposed.

The last few sentences catch my eyes, because I just read a survey paper, Theory of cellular automata: A survey by Jarkko Kari.

The other is "On The Emerging Future Of Complexity Sciences," By Kemal A. Delic & Ralph Dum. It's funny that the word "Complexity Science" appears on CS's Magazine.

On The Emerging Future Of Complexity Sciences, Kemal A. Delic, Ralph Dum, ACM Ubiquity Magazine, 06/03/14

Excerpts: Complexity as a phenomenon is omnipresent in natural, social, business, artificial, engineered or hybrid systems. Cells, organisms, the ecosystem, companies, supply networks, markets, societies, governments, cities, regions, countries, large scale software and hardware systems, the Internet, all are examples of complex systems. Despite this omnipresence there is no commonly accepted, crisp and robust definition or classification of complex systems and one might ask why we would expect commonalities among such systems despite their obvious differences.

I had mentioned that I am a member of a one-year NSC project about Graph algorithms. The results are two conference papers. I think it is not bad. However, my publication still keep zero.

The problem I choose is to improve Martin Farber's result on chordal graph. We choose the same tool, PEO. Farber transformed this problem into a LP problem and got a very good result, but I want to use other approaches to conquer this problem. It's what I planned.

Anyway, I still can't conquer this problem. Today I find that instinct of some properties I found seem the same as Tarjan's LexicoBFS. It's not good news for me. Although I could comfort myself by that at least I know more deep about LexicoBFS now, this algorithm doesn't look like falling from the sky now.

And I am starting to doubt that Farber's algorithm has touched the bottom. I want to move my concentration to other things......

Today, I only did one thing, i.e., to write a scanner for C. (it's homework actually)

I spent much time on it. The keypoint making things hard is the incomplete manual. Flex is powerful but not heavy. Regular expression isn't too hard to learn. Actually I am stuck by the string manipulation of Flex. What kind of conditions do the ESCAPE operate?

My senior Ying Chih, the theoretical subgroup leader, saw my bookrack and said that you seem to be interested in broad fields. I felt little embarrassed. Actually, I am curious but not studious.

Another thing is that Ying Chih asked me to help him to review a paper of local combinatorics conference. I suddenly thought about that if in a poor school or country a scholar who is asked to review a paper by a editor has no enough literature resources to accomplish this mission, then how he should reply his difficulties.

The other thing is that Ying Chih asked me who decide the name of our laboratory. I got a little surprising. It should be decided by our adviser prof. Tang obviously. But Ying Chih told me that the word "biocomputing" is infrequent, we sometimes called it "bioinformatics" or "computational biology".

I guessed that the name was decided by adviser of our adviser, Prof. Lee, because his LAB. in NCNU is also called Algorithm & Biocomputing LAB.

Because of the graduation requirement, I need to take the undergraduate courses, compiler construction. (It's additional requirement for postgraduates whose major at undergraduate is not computer science.)

The term-project is to construct a compiler. The usual choice is C or some other PLs, but I want to write a compiler for a the other type PL, such as Functional PL or Logic PL.

At present, I prefer Haskell. But.....in fact, I didn't learn anything about Haskell before, more precisely, I didn't learn anything about Functional or Logic PL before. I just think that it might be possible to learn a new, different perspective programming language by the goal, compiler construction, in this course.

BTW, in their FAQ, Haskell seems not slow.

Aren't functional programs very slow?

They used to be, perhaps 20 years ago. But the compilers have long since caught up. Haskell programs run fast for all but the most performance-demanding applications. At the time of writing, Haskell compiled via GHC is in 2nd place (behind C) in the Great Language Shootout, with other functional languages also ranked highly.

2006-03-10 Update: :

• The Lex & Yacc Page
• ANTLR Parser Generator, ANother Tool for Language Recognition, (formerly PCCTS) is a language tool that provides a framework for constructing recognizers, compilers, and translators from grammatical descriptions containing Java, C#, C++, or Python actions.
• JTC1/SC22/WG14 - C

2006-03-11 Update: :

• ANSI C Yacc grammar
• flex: The Fast Lexical Analyzer
• Compiler Construction using Flex and Bison, by Anthony Aaby
• Bison
• A lexical analyzer generator for Standard ML. Version 1.6.0, October 1994, by Andrew W. Appel, James S. Mattson, and David R. Tarditi

Btw, I seems to overrate my ability. I decided to write a simple C compiler.

Rafiqul Islam, Nasim Adnan, Nur Islam and Shohorab Hossen, A new external sorting algorithm with no additional disk space, Information Processing Letters, Volume 86, Issue 5, 15 June 2003, Pages 229-233.

Abstract: This paper is concerned with an external sorting algorithm with no additional disk space. The proposed algorithm is a hybrid one that uses Quicksort and special merging process in two distinct phases. The algorithm excels in sorting a huge file, which is many times larger than the available memory of the computer. This algorithm creates no extra backup file for manipulating huge records. For this, the algorithm saves huge disk space, which is needed to hold the large file. Also our algorithm switches to special merging process after the first phase that uses Quicksort. This reduces the time complexity and makes the algorithm faster.

My adviser have devised a algorithm and proved that it is optimal for times of accessing disk. But this algorithm might overlook the total running time.

In this paper, their algorithm divide the data of several blocks, and the size of each block is half size of memory. They load block_1 and block_n into memory and sort by Quicksort, then store upper half of memory into the position of block_n. Next, load block_{n-1} into memory and sort all data in memory again. Repeat this process. Eventually, the lower half of memory is smallest in all data. We put it back into disk.

Then, the algorithm enter the second phase. Load the block_n and block_{n-1} and sort it by the modified merge sort technique.(because the two block are ordered.) And repeat this procedure. The whole algorithm looks like bubble sort.

To design the practical algorithm, we need to consider a lot of things, e.g., memory and disk management of OS. The improvements of system might destroy the performance of an efficient tricky algorithm.

Ref. Computational Complexity: Elsevier and TCS

This is an interesting post.

TCS was one of the top 2 or 3 theory journals and around 2000 pages annually until 1989 when it decided to go to bi-weekly publication and a much larger editorial board and upped its page count to 3500, raising its prices drastically overnight to keep the same price per page. The average quality declined markedly at this time as the good papers were swamped with more lower quality fare. TCS still publishes many good papers but it is nowhere near as high quality as it was in the 1980's when it got many of the top papers in the field.

I didn't know that TCS was so good before. I know it is a pretty good journal now, but it seems at lower rank.

But I think it is hard to say that keeping its high quality is the best decision as the computer science community growing so fast.

Referring to the appearance of SODA, if the accept rates of STOC and FOCS didn't fall year by year, I think SODA might not appear. Of course, if TCS keeps it quality, then some new journals will get those papers. But.... Does the clear cut great?

I think that we need journals with fast refereeing, quality, and many papers. Theory of Computing might have high quality and charge free, but it is too slow and too small. There are 9 papers of 2005 volume and 3 papers of 2006 volume now.....