Centre for Discrete Mathematics and Theoretical Computer Science

Combinatorial Algorithms and Optimization

Combinatorial optimization is related to operations research, algorithm theory and computational complexity theory. Combinatorial optimization algorithms solve instances of problems that are believed to be hard in general, by exploring the usually-large solution space of these instances. Combinatorial optimization algorithms achieve this by reducing the effective size of the space, and by exploring the space efficiently.

Members of this CDMTCS research area are also interested in computational techniques for discovering/processing several types of combinatorial objects such as network design (via algebraic and ad-hoc graph constructions) and utilization of bounded pathwidth/treewidth for computing obstruction sets and coping with hard ``real-world'' problems in VLSI design and bioinformatics.

Algorithmic Information Theory

Algorithmic information theory (AIT) is the result of putting Shannon's information theory and Turing's computability theory into a cocktail shaker and shaking vigorously. The basic idea is to measure the complexity of an object by the size in bits of the smallest program for computing it.(G. J. Chaitin)

Programming Contest Resources

The CDMTCS is a proud supporter of local teams participating in programming contests. It encourages and builds skills in algorithmic problem solving and real-world practical coding efficiency. Some regional contest homepage links:

Here are a few links to past problems, past results and selected solutions.

There are many online training resources and we recommend a few popular ones here: Google Code Jam, TopCoder, Project Euler and UVa Online-Judge.

If interested in competing (or help training) please contact Miao Qiao or Michael Dinneen.

Please give us your feedback or ask us a question

This message is...

My feedback or question is...

My email address is...

(Only if you need a reply)

A to Z Directory | Site map | Accessibility | Copyright | Privacy | Disclaimer | Feedback on this page