Algorithms and data structures 2

Lectures:
Intro: about methods of algorithm design, analysis of algorithms, and computational complexity of algorithms and problems
Divide-and-Conquer: description of the method, examples of problems and algorithms (see examples 12 below)
Greedy method: description, examples
Iterative improvement: descr., examples
Dynamic programming: descr., examples
Backtracking: description, examples
Branch&,Bound: description, examples
Linear programming: descr., Simplex algorithm, examples
Selected advanced data structures
NP-hard computational problems: lower bounds on time complexity, informally about P, NP and NP-hard problems,
Methods of solving NP-hard problems: heuristic algorithms, approximation algorithms, randomized algorithms, parameterized algorithms, exact exponential algorithms, examples
Example problems and algorithms: advanced sorting &, Heapsort, Quicksort, selection problem &, linear algorithms, matrix multiplication &, Strassen alg., Discrete Fourier Transformation &, FFT alg, string matching &, Knuth-Morris-Pratt, elementary and other graph problems and algorithms (searching a graph, topological sort, maximum flow &, Ford-Fulkerson alg., shortest paths &, algorithms of Bellman-Ford, and Floyd-Warshall), selected problems from computational geometry.

Tutorial: Students will use the topics given during the lectures to independently solve practical problems (with the assistance of the TAs if needed). They will implement several smaller programs (home works) as well as larger programs (seminars), and present them at the tutorial.
Home works and seminars:
These are necessary for a student
to independently practice the design and implementation of algorithms .

B. Robič: Algoritmi (to appear, instead of 2. below)
B. Vilfan: Osnovni algoritmi, Založba FE in FRI, 2002
Dodatna literatura:
T. Cormen et al. Introduction to Algorithms, McGraw-Hill, 3rd ed., 2009
B. Robič: Aproksimacijski algoritmi, Založba FE in FRI, 2. izdaja, 2009

To gain deeper knowledge of algorithm design methods, analysis of algorithms, use of data structures , selected problems and algorithms, and at the same time, to improve and deepen programming skills.

Knowledge and understanding:
The ability to independently design algorithms and data structures for solving particular computational problems, the ability to independently analyze computational complexity of algorithms (and sometimes problems as well), the ability to independently develop and implement computer programs.
Application: use of the principles and methods in algorithm design and implementation
Reflection: understanding of the basic principles of algorithm design and their role in efficient solving of computational problems
Transferable skills: there are many and useful in other subjects. For example, the ability to plan, design, and implement algorithmic solutions to various problems (regardless of the programming language used)

Lectures, tutorial, home works, seminars.

Continuing (homework)
Final (written and oral exam)
grading: 5 (fail), 6-10 (pass) (according to the Statute of UL)

ČIBEJ, Uroš, SLIVNIK, Boštjan, ROBIČ, Borut. The complexity of static data replication in data grids. Parallel Computing, ISSN 0167-8191. [Print ed.], 2005, vol. 31, no. 8/9, str. [900]-912, ilustr. [COBISS-SI-ID 4995412]
SULISTIO, Anthony, ČIBEJ, Uroš, VENUGOPAL, Srikumar, ROBIČ, Borut, BUYYA, Rajkumar. A toolkit for modelling and simulating data Grids : an extension to GridSim. Concurrency and computation, ISSN 1532-0626. [Print ed.], Sep. 2008, vol. 20, no. 13, str. 1591-1609, ilustr. , doi: . [COBISS-SI-ID 6533716]
TROBEC, Roman, ŠTERK, Marjan, ROBIČ, Borut. Computational complexity and parallelization of the meshless local Petrov-Galerkin methods. Computers & Structures, ISSN 0045-7949. [Print ed.], 2009, vol. 87, no. 1/2, str. 81-90. [COBISS-SI-ID 21895463]
MIHELIČ, Jurij, ROBIČ, Borut. Flexible-attribute problems. Computational optimization and applications, ISSN 0926-6003. [Print ed.], 2010, vol. 47, no. 3, str. 553-566, ilustr. [COBISS-SI-ID 7087700]
MIHELIČ, Jurij, MAHJOUB, Amine, RAPINE, Christophe, ROBIČ, Borut. Two-stage flexible-choice problems under uncertainty. European journal of operational research, ISSN 0377-2217. [Print ed.], Mar. 2010, vol. 201, no. 2, str. 399-403, ilustr. [COBISS-SI-ID 7087444]