General information
| Course type | AMUPIE |
| Module title | Introduction to algorithms |
| Language | English |
| Module lecturer | prof. UAM dr hab. William Mance |
| Lecturer's email | wilman@amu.edu.pl |
| Lecturer position | Professor |
| Faculty | Faculty of Mathematics and Computer Science |
| Semester | 2024/2025 (summer) |
| Duration | 60 |
| ECTS | 5 |
| USOS code | 06-DITALW0-E |
Timetable
The schedule of this course is expected to roughly follow the given outline. There will be a significant degree of flexibility given to cover topics of interest to the particular students in the class.
Week 1: Basic mathematical topics needed in the course such as proof by induction, techniques from calculus, graphs and trees, summation formulas
Week 2: Recursion, correctness proofs, Big O Notation, the halting problem
Week 3: Searching and sorting
Week 4: Algorithms from number theory
Week 5: Approximation algorithms
Week 6: Approximation algorithms
Week 7: Randomized algorithms
Week 8: Geometric algorithms
Week 9: Graph and tree algorithms (for example, breadth-first search and depth-first search)
Week 10: Graph and tree algorithms
Week 11: Lower bounds and NP-completeness
Week 12: Algorithms for computer graphics
Week 13: String algorithms
Week 14: More mathematical algorithms
Week 15: Computability
Module aim (aims)
To introduce students to basic algorithms from many different areas. In particular, students will be expected to learn how to analyze efficiency of algorithms.
Pre-requisites in terms of knowledge, skills and social competences (where relevant)
Experience programming and at least some basic calculus. Students from all different backgrounds are encouraged to sign up as there will be a significant amount of flexibility on which topics will be covered.
Syllabus
Reading list
Introduction to algorithms by