Algorithm Design and Problem Solving

 

 

Doc.dr.ing.Ivana Kolingerová

 

Contents:

 

1.      Introduction into algorithms – robustness, effectivity, complexity, analysis, information resources

2.      How to design algorithms

3.      Algorithmic strategies – brute force, greedy, incremental algorithms, divide and conquer, dynamic programming, graph traversal, backtracking, branch and bound, local search, bucketing, randomized algorithms, in-place algorithms

4.      Heuristics – simulated annealing, genetic algorithms, tabu search

5.      Selected data structures

6.      How to solve difficult problems

 

Literature:

 

·        fundamental:

    • S. Skiena: The Algorithm Design Manual, Spring-Verlag, New York Berlin Heidelberg, 1998 – available on Webu over the author’s homepages or in the UWB library for presential studies
    • lecture notes and other matarials from the teacher, problems from the ACM programming contest etc.
  • other:
    • J.Hromkovič: Algorithms for Hard Problems, Introduction to Combinatorial Optimization, Randomization, Approximation and Heuristics, Springer Verlag Berlin Heidelberg New York, 2000
    • Z.Michalewicz, D.B. Fogel: How to Solve It: Modern Heuristics, Springer-Verlag, Berlin Heidelberg New York, 2000
    • G. Gonnet, R. Baeza – Yates: Handbook of Algorithms and Data Structures, Addison-Wesley, Wokingham, UK, 1991 (2nd edition)
    • G. Rawlins: Compared to What ? Computer Science Press, New York, 1992
    • B. Moret, H. Shapiro: Algorithm from P to NP: Design and Efficiency, Benjamin/Cummings, Redwood City, US, 1991

 

The exam is written and oral, in the written part there are 3 question including problems for practical solution, the oral part is devoted, first of all, to the analysis of student work and his exam. From the exam 3x20 points can be obtained, if it is evaluated less then 30 points, the student must repeat the course.

 

 

 

Requirements to get credits:

 

There will be a set of about 10 problems available during the semester. Most of them will be devoted to the algorithm design or their use of the presented methods for some application. Some tasks can be oriented to written processing of references and presentation of the results to the colleagues and other non-implementation forms. Work for this course can be done in UL 407 (OS Windows, MS Visual C++ and Delphi). If they prefer to work on some other computer or other OS, they should ensure a DOS command line version to enable an easy control of functionality.

 

The small projects solutions will be evaluated according to quality, each student should collect at least 36 points to get credits for this course. Each student can make his or her own choice from the provided hand-outs. The project should be finished within 3 weeks from the date of its hand-out. The project will be sent either by e-mail or given on CD, floppy disk, stick disk etc. After evaluation, the media will be returned to the student :-))). The project solution should contain source code, EXE version, a short documentation (2 pages can be enough but you should concentrate on the facts, not a fuzzy formulations). Sometimes implementation is not required. If the project is concentrated to references analysis or explanation, it should have about 10 pages of 10-12pt fonts and it should contain also the processed articles, at least 3 articles).