| Algorithms analysis and design |
ter |
|||||
| 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 |