Algorithm analysis and basics of computational complexity. Introducing Python modules for the analysis of data and graphs. Developing of efficient algorithms for large-scale networks.
Think Python: How to Think Like a Computer Scientist by Allen B. Downey Beijing: O'reilly Media
Problem Solving With Algorithims and Data Structures Using Python, 2nd edition, By Brad Miller and David Ranum Franklin Beedle & Assoc
Interactive website (free translation of the above books with more exercises and other material): - http://www.andreamarino.it/python/thinkcspy/toc.html#t-o-c - http://www.andreamarino.it/python/pythonds/
Slide and notes distributed via Moodle.
Learning Objectives
The aim of this course is to introduce students to the design and analysis of efficient algorithms for the analysis of data, through the design and the application of algorithms for graphs. Learning and developing algorithms for graphs in Python will be the occasion to develop problem solving and programming abilities, learning how to use specialized Python modules. At the end of the course, students will have a good knowledge of the computational problems and solutions, and of the main techniques to design efficient algorithms. They will be able to formulate and solve data analysis problems, and to evaluate the possible solutions in terms of semantics and efficiency.
Prerequisites
Students must have (1) basic knowledge of algorithms and data structures, (2) know basic of probability theory and basic statistics, (3) basic programming skills (for instance in Python)
Teaching Methods
- Frontal lectures
- Brainstorming: discussions in order to find non-trivial solutions to complex problems, exposing objectives and soliciting students to give ideas.
- Problem solving: learning as the result of a discovering process, converging to the efficient solutions via trial and error. The method will be used to understand and plan the actions required to solve a problem.
- Moodle Platform will be used as a virtual environment to provide support and references.
Further information
Software - Spyder in Anaconda, PythonTutor or repl.it.
Type of Assessment
Project assignment with discussion and oral. Developing a solution for the project respecting the specification is necessary in order to give the oral exam. The aim of the project is to verify the ability of developing algorithms in autonomy and to apply them in a given dataset in asynchronous way. The aim of the oral examination is to evaluate the knowledge about the topics presented during the lectures, the adeguate usage of the technical language, the ability in understanding how algorithms work, the capability to develop algorithmic solution on-the-fly for new problems.
Course program
Quick review about algorithms and data structures
Python Review
Basic data structures,
Introducing Python Pandas module and visualizing data
Graphs: algorithms for visiting graphs and computing distances
Python NetworkX
Algorithms for the analysis of small-world networks: diameter, average distance, distance distribution, probabilistic counting, community detection, centrality analysis.