Faculty of Mathematics and Computer Science

Algorithms analysis and design |

Code |
Semes-ter |
Hours: C+S+L |
Credits |
Type |
Section |

Teaching Staff in Charge |

Lect. IONESCU Clara, clara@cs.ubbcluj.ro |

Aims |

At the end of the course, the student is expected to:
* realise the problems involved in designing and building significant computer systems. * understand the need to design systems that fully meet the requirements of the intended users * appreciate the availability of a range of appropriate tools that assist in the development of effective computer systems, and can apply them, as appropriate |

Content |

1. Introduction (1)
1.1. Algorithms 1.2. Algorithm analisys 1.3. Algorithm design 2. Analisys tools (2) 2.1. Asymptotic notations 2.2. Standard notations and common functions 2.3. Amortized cost analysis 3. Sums (3-4) 4. Recurences and recursion 5. Sets 6. Numbering and probabilities 7. Number theory algorithms (5-6) 7.1. Iterative combinatorial algorithms 7.2. Dirichlet@s box 7. Programming techniques 7.1. The clasification of problems by complexity. NP-completness (7) 7.2. Divide et Impera (8) 7.3. Sorting (9) 7.4. Searching (10) 7.5. Pattern matching (11) 8. Advanced programming techniques(12-13) 8.1. Greedy algorithms 8.2. Greedy heuristics 8.3. Dinamic programming 9. Solving NP-complete problems and the comparison of different solving techniques (14) 9.1. Backtracking 9.2. Greedy heuristics 9.3. Probabilistic algorithms 9.4. Approximative algorithms 9.5. Genetic and evolutive algorithms |

References |

1. T. Cormen, C. Leiserson, R. Rivest, Introducere in algoritmi, Computer Libris Agora, Cluj-Napoca, 2000
2. James A. Storer, An Introduction to Data Structures and Algorithms, Springer, New York, 2002 |

Assessment |

* Lab activity: 4 pct
* Written exam - a minicase study: 6 pct |