The course has been created as a part of the D spezialization in algorithms, but also students from other Chalmers programs and GU students can take the course. In addition, anyone is welcome to attend particular lectures annonced within the course.

Observe: At Studieportalen this course is reported as giving 1 credit in LP3 and 1 credit in LP4. This is wrong - the course goes from September until May, and gives 2 credits in total.

Messages

• Next seminar: Visualizing algorithms - Using Spotfire DecisionSite in gene research - Mattias Zetterlund & Mauricia Aira, Spotfire
  Thu 29/4 17:15 - 19:00, EDIT 3407

• The course will start with a short introductory meeting Thursday 18/9 2003 at 17:15, in S4. This will be a very short meeting, mainly to register the interested students, and to discuss appropriate weekdays for seminars. If you don't know where S4 is, check here.
   

• The web page from last year's course can be found here.

Seminars

• Introductory meeting, Thu 18/9 17:15 - 19:00, S4.
   

• Building a Company on Algorithms - Johan Kollind, Carmen Systems AB
Thu 16/10 17:15 - 19:00, S4
Carmen Systems AB delivers integrated planning and decision-support solutions for airlines and railways. Clients include Aeroméxico, Air France, Alitalia, British Airways, Iberia, KLM, Lufthansa, Northwest Airlines, SAS, Singapore Airlines and Deutsche Bahn. Carmen Systems is a rapidly expanding organisation and today has 180 employees from 24 countries. A brief company presentation will be given, followed by an introduction to the airline planning problem and some thoughts on the general process of building a company on an algorithm. In addition to this there will be a technical session focusing on the methods and algorithms for solving big airline planning problems.


• String Algorithms - Mattias Grönkvist, Chalmers
Wed 5/11 17:15 - 19:00, S4
Algorithms working on strings are very common in all sorts of computer programs, from word processing programs to web browsers. But these algorithms are seldom given any attention in standard algorithms courses, even though many of them are non-trivial and provide useful insights. In this seminar we will discuss a number of string matching algorithms, and if time permits we will also talk a bit about matching regular expressions.
Slides: [1/page] [4/page]


• Constraint Programming - Mattias Grönkvist, Chalmers
Thu 27/11 17:15 - 19:00, S4
In real life it is very common that problems for which we want to construct an algorithm are very complex. If we are really unlucky, the problem belongs to the class of NP-Complete problems, which in practice means that solving it will always take exponential time in the worst case. To solve such problems, one must often implement heuristic methods, which can be fast but are incomplete, or enumerative methods, which are slow but complete.

In this seminar we will discuss Constraint Programming, which is one technique for attacking very difficult problems. Constraint Programming has its roots in Artificial Intelligence and Logic Programming, but has in recent years become an increasingly useful tool for solving e.g. large-scale planning problems. The seminar will give a brief introduction to the basics of Constraint Programming, and present some practical applications of it.
Slides: [1/page] [4/page]


• Computerized Chess & Constraint Programming II - Tomas Franz & Mattias Grönkvist, Chalmers
  Tue 9/12 17:15 - 19:00, S4
  First half: Chess Programs, Thomaz Franz. Thomas will present his project about chess programs.
  Second half: Practical Applications of Constraint Programming. I'll finish the Constraint Programming thread by giving one or a few examples of constraint programming in action, e.g. aircraft scheduling or crossword solving.
  
  
• Compression Algorithms - Mattias Grönkvist, Chalmers
  Thu 22/1 17:15 - 19:00, EDIT 3407
  We will discuss various lossless compression algorithms, such as Huffman coding, arithmetic coding, Lempel-Ziv, Burrows-Wheeler and Move-To-Front. If time permits, we might also talk about lossy compression, in the form of JPEG.
  Slides: [1/page] [4/page]
  


• Algorithms in Structural Bioinformatics - Graham Kemp, Chalmers
  Wed 4/2 17:15 - 19:00, EDIT 3407
  Bioinformatics is one of the major growth areas in biotechnology and the biological sciences.  It is also an area that presents opportunities for computing science researchers to apply advanced computational techniques to challenging new problems, and often requires new algorithms to be devised. this seminar we shall consider the area of structural bioinformatics.
  
  This area deals with analysing, modelling and predicting the three-dimensional structures of biological macromolecules like proteins. This is an important area because a molecule's biological function is determined by its three-dimensional structure and, thus, knowledge about these structures can give new insights into biological processes and disease mechanisms.
  
  In the first part of the seminar I shall give a brief introduction to the beauty and complexity of three-dimensional protein structures, and the basic principles of protein conformation.  In the second part I shall describe some computational problems in structural bioinformatics to which algorithmic solutions have, or could, be applied. No previous biochemical knowledge will be assumed! More information, references etc can be found here.
  


• Metaheuristics - Mattias Grönkvist, Chalmers
  Tue 17/2 17:15 - 19:00, EDIT 3407
  We have previously talked about Constraint Programming as a solution technique for difficult combinatorial problems. This time, we will talk about several types of so-called metaheuristics used to heuristically solve very difficult optimization problems.
  
  Metaheuristics are high-level heuristics that are based on a central general idea which can be extended to fit many different problems. Well-known metaheuristics are for example simulated annealing, tabu search and genetic algorithms. These metaheuristics can often be a good way to first attack a new difficult problem, if no exact solution method is known.
  Slides: [1/page] [4/page]
  
  
• Minimum cost network flows - Mattias Grönkvist, Chalmers
  Thu 4/3 17:15 - 19:00, EDIT 3407
  Many real world problems can be formulated in terms of flows in networks. Some examples are transportation problems, communications networks, mechanics problems and various balancing and allocation problems. Basic knowledge about algorithms to solve such problems is therefore a very valuable tool for anyone solving real world problems. Some of you have already studied maximum flow algorithms in the Advanced Algorithms course.
  
  I will briefly introduce the maximum flow problem for those who are not familiar with it, and then move on to talk about the general class of minimum cost network flow problems. We will discuss two general classes of algorithms for the problem, cycle-canceling algorithms and successive shortest path algorithms.
  
  We will also mention real world examples of min-cost flow problems, and discuss the connections between linear programming (LP) and network flow problems.
  
  
• Algorithm Insights 1 - Dag Wedelin, Chalmers
  Thu 18/3 17:15 - 19:00, EDIT 3407
  Discussion session. Topics: Discrete algorithms, design techniques, how to choose algorithms, data structure insights. To prepare: Read about algorithm design techniques in a standard algorithms book.
  
  
• Algorithm Insights 2 - Dag Wedelin, Chalmers
  Thu 1/4 17:15 - 19:00, EDIT 3407
  Discussion session. Continuation of Algorithm Insights 1 above. We will discuss some assorted topics we didn't have time for last time.


• Visualizing algorithms - Using Spotfire DecisionSite in gene research - Mattias Zetterlund & Mauricia Aira, Spotfire
  Thu 29/4 17:15 - 19:00, EDIT 3407
  Spotfire is a company founded by Christopher Ahlberg, a Ph.D. from Chalmers. Spotfire is very successful in visualizing data and is today based in Boston, U.S., with developing department in Göteborg. Spotfire serves 500 of Global 2000 companies with software and customers in Sweden include Volvo, AstraZeneca and Saab.
  
  Working towards information intense companies, not only the data needs to be visualized, but also the algorithms that are used to structure the data. One such structuring method is to cluster the data and we will look at how clustering algorithms work and how Spotfire visualize this. We will see a real life example of how genes are grouped and look at how the algorithms work. Clustering is a widespread technique to group data in the medical industry. The lecture will include:
  • A brief description of Spotfire.
  • An introduction to Spotfire DecisionSite.
  • An overview of algorithms used when working with genes.
  • A more in depth look at how various clustering methods work.
  • How one can visualize algorithms such as clustering.
  • A real life example of how Spotfire DecisionSite is used to cluster genes.

Report

Deadline for hand-in is May 3, 2004. Reports should be handed in on paper, or in a printable electronic format such as PostScript, dvi, pdf. Not MS Word or html!

Some related courses at the department that might give some hints:

Algorithms

Algorithms, Advanced Course

Transport Optimization

Discrete Optimization

Algorithms for machine learning and inference

Bioinformatics

Artificial Intelligence

Practical information

Course administrator is Mattias Grönkvist (), Computing Science. (Room 6455)

The course proceeds during the entire academic year. The schedule for seminars is decided and announced on this web page, and by email to registered students.

Seminars will be held in S4, which is a seminar room located on Plan 3 in the MD building, to the left seen from the front of the building. If the door on Plan 3 is locked, just wait, and someone will come and let you in.

Requirements to pass the course:

Active participation in at least 80% of the seminars.

A written report as mentioned above.

A short oral presentation about the report.

Last modified: Wed Mar 04 11:56:06 MET DST 2004