Algorithms
Algorithms
An algorithm is a systematic method for solving a problem (usually using a computer). Algorithmics is the study of algorithms: the design of algorithms, the analysis of algorithms, and the investigation of when problems cannot have efficient algorithms. The group in Algorithmics at SDU has research interests concentrated within data structures, online algorithms, bioinformatics, cheminformatics, cryptography, constraint-solving, graph algorithms, and combinatorial optimization.
The group’s research is all either directly practically motivated or aimed at facilitating the development of better algorithms for practical problems – it is theory with a practical focus. The group’s interests are in efficient algorithms, as well as in quality improvements of approximative solutions to computationally hard problems, many of which have important industrial variants.
People
| Jørgen Bang-Jensen | Professor | jbj @ imada.sdu.dk |
| Joan Boyar | Associate Professor | joan @ imada.sdu.dk |
| Marco Chiarandini | Associate Professor | marco @ imada.sdu.dk |
| Rolf Fagerberg | Associate Professor | rolf @ imada.sdu.dk |
| Lene Monrad Favrholdt | Associate Professor | lenem @ imada.sdu.dk |
| Kim Skak Larsen | Professor | kslarsen @ imada.sdu.dk |
| Daniel Merkle | Associate Professor | daniel @ imada.sdu.dk |
| Peter Schneider-Kamp | Assistant Professor | petersk @ imada.sdu.dk |
Group Leader
Joan Boyar
Bachelor Courses
Algorithms and data structures; combinatorics, probability, and randomized algorithms; algorithms and complexity; introduction to linear and integer programming; computability. (Many other courses are taught by the computer science group at IMADA, including programming A & B; operating systems; databases, etc.)
Graduate Courses and Independent Studies
Cryptology; advanced data structures; graph algorithms with practical applications; multicriteria optimization and sensitivity analysis; scheduling, time-tabling, and routing; on-line algorithms; I/O effective algorithms and data structures; combinatorial optimization 1, 2 & 3; algorithms for web-indexing and searching; string algorithms; introduction to machine learning; modeling and solving constrained optimization problems; parallel programming; bioinformatics. (Other courses taught by the computer science group include programming for computer games 1, 2, 3, & 4.)
Bachelor Projects
Most computer science students choose a compiler project for the bachelor project. Other possibilities in the past have included various topics in algorithmics.
Master Projects
Some sample recent projects have been:
Minimizing the number of XOR gates in circuits computing linear forms
Attacks on and combining cryptographic hash functions
The online Dial-a-Ride problem
Course timetabling at the Faculty of Science of SDU
Long term unit commitment with heating constraints
Approximation algorithms for optimal certificates for graph connectivity
Algorithms for finding well-balanced pairs of edge-disjoint spanning trees in weighted graphs
Approximation of newer variants of the knapsack problem
Analyzing the quality of online bin packing algorithms
Online and offline coloring of interval graphs
Space complexity of external-memory three-sided range search
Computer-aided generation of building instructions for LEGO models
GPU-based rendering of terrains
Ray tracing on IBM’s cell processor
A dynamic and kinetic data structure for convex hull
Theoretical and experimental analysis of new paging algorithms
Patterns in chemical reaction networks
Barrier trees for continuous fitness landscapes
Inferring genomic rearrangements based on common intervals
PhD Students
The group currently has 9 PhD students, coming from Germany, India, Italy, and Denmark. The group’s former PhD students are currently employed many places, including permanent research (in all cases but one, faculty) positions at Aarhus University; AT&T Labs; Royal Holloway, University of London; University of Calgary; (and two have returned to) University of Southern Denmark.