# Tadao Takaoka

### Position

Professor Emeritus

### Qualifications

B.E., M.E., Ph.D.

### Room

Erskine Building 302

### Contact Details

Phone: +64 3 364 2987, Ext: 7773

Fax: +64 3 364 2569

T.Takaoka@cosc.canterbury.ac.nz

### Postal Address

**Department of Computer Science and Software Engineering,**

College of Engineering,

University of Canterbury,

Private Bag 4800,

Christchurch 8140,

New Zealand.

### Undergraduate Courses (old)

- COSC222 Home Page.
- COSC460 eval.
- COSC460 thesis eval.
- COSC229 Algorithims Home Page.
- COSC230 Home Page.
- COSC329 Algorithms & Languages Home Page.

### Undergraduate Courses (new)

### Graduate Courses

- COSC413 Advanced Topics in Algorithms.
- COSC413 Home Page.

### Research Interests

Shortest paths, combinatorial generation, priority queues, maximum sum/subarray algorithms

### Brief CV

### Detailed CV

### Recent Publications

A full **list of my recent publications** is
avaliable as a
PDF.

### Approximate pattern matching

- Approximate Pattern Matching with Samples, ISAAC'94, LNCS 834, pp. 234-242.
- Approximate Pattern Matching with Grey Scale Values, CATS '96.

### Adaptive sorting and entropy

- CATS 98

A New Measure of Disorder -- Entropy. - MFCS 2009

Partial Solution and Entropy. - Journal of Information Processing

Entropy as Computational Complexity.

### All pairs shortest path algorithms

- Sub-cubic Algorithms for the All Pairs Shortest Path Problems, WG '95, Algorithmica 20, 309-318, 1998.
- Shortest Path Algorithms for Nearly Acyclic Directed Graphs, WG '96.
- Efficient Algorithms for the Maximum Subarray Problem by Distance Matrix Multiplication, CATS '02.
- Improved Shortest Path Algorithms for Nearly Acyclic Graphs, Theoretical Computer Science 293, 535-556, 2003.
- Solving SHortest Paths Efficiently on Nearly Acyclic Directed Graphs, Theoretical Computer Science, 2006.
- A Faster Algorithm for the All-Pairs Shortest Problem and its Application, COCOON 2004, LNCS 3106.
- An O(n^3loglogn/logn) time algorithm for the all-pairs shortest path problem, Information Processing Letters 96, 155-161, 2005.
- Improved Shortest Path Algorithms For Nearly Acyclic Directed Graphs. PDF file.
- Improved Shortest Path Algorithms For Nearly Acyclic Directed Graphs. Power Point.
- Efficient Algorithms for the 2-Center Problem, ICCSA 2010, Fukuoka, JAPAN, LNCS 6017, pp 519-532, 2010.
- Matrix Multiplication and All Pairs Shortest Paths In encyclopedia
- An O(n^3loglogn/log^2 n) Time Algorithm for All Pairs Shortest Paths In SWAT 2012

### Parallel Program Verification

### Data Structures

- Theory of 2-3 Heaps, Cocoon '99.
- Theory of 2-3 Heaps, Discrete Applied Math 126, 115-128, 2003.
- Theory of Trinomial Heaps, Cocoon '00.

### Combinatorial Generation

- An O(1) Time Algorithm for generating Multi-set Permutations, ISAAC '99.
- A Pascal program.
- O(1) Time Algorithms for Combinatorial Generation by Tree Traversal, Computer Journal, vol. 42, no. 5, pp400-408, 1999
- Combinatorial Generation by Fusing Loopless Algorithms, CATS06, Hobart.
- O(1) Time Algorithm for Fibonacci sequences.

### Subarray Problems

- Efficient Algorithms for the Maximum Subarray Problem by Distance Matrix Multiplication, CATS '02.
- The Reverse Problem of Range Query, CATS '03.
- Improved Algorithms for the K-Maximum Subarray Problem for Small K, COCOON 2005, LNCS 3595.
- Sub-cubic Algorithms for the K-Maximum Subarray Problem, ISAAC 2007, LNCS 4835.

### Data Mining

- Algorithms for data mining. PDF.
- ACM SAC 2007. Power Point.
- C program for k maximum subarrays.
- ISPAN2004.ppt
- BlueGene

### Algorithm Engineering

- Algorithm Engineering.
- Entropy. Power Point.