29526 - Algorithms and Data Structures

Learning outcomes

By the end of the course, students will have acquired the fundamental knowledge necessary for the design and analysis of correct and efficient algorithms and data structures. In particular, they will be able to• design correct and efficient algorithms for common computational problems; • analyze the performance and correctness of existing algorithms and data structures; • design and evaluate new algorithms and data structures to address novel computational challenges.

Course contents

The course introduces the fundamental concepts of algorithms and data structures, with particular emphasis, where appropriate, on applications and problems in computational biology.

The topics covered include:

• Introduction to algorithm complexity analysis: computational cost, asymptotic notation, and algorithm performance analysis.
• Sorting algorithms: study of the main sorting algorithms (Insertion Sort, Merge Sort, and Quick Sort), lower bounds for comparison-based sorting, and linear-time sorting algorithms such as Counting Sort.
• Basic data structures: arrays, linked lists, stacks, and queues.
• Advanced data structures: binary trees, general trees, hash tables, and graphs.
• Fundamental algorithmic techniques: algorithm design paradigms including brute force, divide and conquer, dynamic programming, and greedy algorithms.
• Algorithms for computationally hard problems: introduction to approximation algorithms, branch-and-bound techniques, and heuristic algorithms.

Throughout the course, algorithms will be presented using pseudocode and illustrated through Python implementations, with examples and exercises inspired, where appropriate, by applications in computational biology.

Readings/Bibliography

It is fundamental to use the electronic slides and material provided during the classes, including live exercises. The slides will be made available on the course web page.

The readings below are suggested, but need not to be necessarily purchased.

Books more specific on computational biology topics:

- Carlos Setubal, Joao Meidanis, Introduction to computational molecular biology, Cengage Learning eds., 1997;
- C. Gibas, P. Jambeck, Developing Bioinformatics Computer Skills, O'Reilly media, 2001

Books more general on computer algorithms and data structures topics:

- Alfred V. Aho, Jeffrey D. Ullman, John E. Hopcroft. Data Structures and Algorithms. Addison Wesley, 1983.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms. McGraw-Hill, 2001.
- Donald E. Knuth. The Art of Computer Programming, Volumes 1-3. Addison-Wesley Professional, 1998.
- S.B. Kishor Data Structures, Edition 3. Das Ganu Prakashan, Nagpur, 2008.

Teaching methods

The teaching methods consist of frontal lectures (supported by slides and whiteboard) and the discussion of exercises to be solved on the paper.

Assessment methods

The final examination consists of a 2-hour written exam comprising four exercises covering the entire course syllabus. Two exercises are of intermediate difficulty, while the remaining two require more advanced analytical skills.

The two more challenging exercises are worth 9 points each, while the two intermediate exercises are worth 7 points each, for a maximum total of 32 points. The final grade is reported on a 30-point scale. Honours (cum laude) may be awarded to students who achieve a score greater than 30.

During the examination, the use of books, notes, electronic devices, or any other reference material not explicitly authorized is strictly prohibited.The use of artificial intelligence (AI) during the assessment is prohibited. Any use of AI constitutes a breach of academic integrity.

Students with learning disorders and\or temporary or permanent disabilities: please, contact the office responsible ( https://site.unibo.it/studenti-con-disabilita-e-dsa/en ) as soon as possible so that they can propose acceptable adjustments. The request for adaptation must be submitted in advance (15 days before the exam date) to the professor, who will assess the appropriateness of the adjustments, taking into account the teaching objectives.

Students recognized as “working students”: please consult the dedicated website ( https://www.unibo.it/en/study/guide-to-choosing-your-programme/balancing-study-and-work ) to apply for this status and to learn about the available measures.

Teaching tools

• Electronic slides and projector
• Personal computer
• Tablet
• White board

Office hours

See the website of Pietro Di Lena