Algorithms and Software Engineering

Algorithms
Research in the design of efficient algorithms. It centers on finding algorithms that improve the asymptotic efficiency of solutions to classical problems, such as sorting, shortest path, all pairs shortest paths, shortest paths on polyhedron, connected components, minimum spanning tree and variations of these that limits input variables to being integers.

Software Engineering
Research on software engineering includes software design methodology, software lifecycle, object-oriented design, unified modeling language, middleware, COM, CORBA, Java/RMI, lexical analysis, syntax analysis, web design, HTML, Javascript, CGI. Formal software specification. Architectural design, interface design, detailed design, implementation, testing and verification, deployment.

Recent and Current Research

All-pairs Shortest Paths

It has been known that all-pairs shortest paths can be computed in subcubic time when edge weights are small integers. When edge weights are real the complexity has been improving with the work of many researchers, but it has always been near cubic time. This project is aimed at studying whether truly subcubic time can be achieved for all-pairs shortest paths.

Matrix Multiplication

The current fastest matrix multiplication algorithm of Coppersmith and Winograd has kept record for almost 30 years and has become the bottleneck of many other algorithms or applications. This project is to study whether breakthrough can be obtained over the current record of n2.376 time.

Maximum Flow

There are many aspects of maximum flow. Currently we have a result that achieved certain degree of success over previously best results. The algorithm we have now faces some obstacles to generalize its results to all extent. Our intention is to generalize the algorithm so that it applies to all ranges of parameters.