509477 - COMPUTER PROGRAMMING, ALGORITHMS AND DATA STRUCTURES

insegnamento

ID:

509477

Durata (ore):

110

CFU:

SSD:

INFORMATICA

Anno:

2024

Periodo di attività

Annualità Singola (30/09/2024 - 13/06/2025)

Obiettivi Formativi

The course introduces the student to programming in Python and solving computational problems using algorithms. The main notions of imperative programming (variables, expressions, loops, functions, recursion, input / output) and the fundamental elements of object-oriented programming are provided during the first module. The second module illustrates the most important data structures (linear, trees and graphs) and the main algorithms that work on them. The students will also learn how to analyze algorithms and how to use them to solve problems of medium complexity.

Prerequisiti

None

Metodi didattici

For both modules:
Frontal lessons (theory) and laboratories (programming in Python)

Verifica Apprendimento

Module 1:

In-class computer-based test with multiple choices and open questions, and programming exercises.

Module 2:

Written test (open questions and exercises about theory)
Programming (solve a problem applying the concepts learned during the theoretical and laboratory lectures).

Testi

For Module 1:

Think Python: How to Think Like a Computer Scientist by Allen B. Downey
Beijing: O'reilly Media

For Module 2:

Problem Solving With Algorithims and Data Structures Using Python, 2nd edition, By Brad Miller and David Ranum
Franklin Beedle & Assoc

(Optional) Data Structures & Algorithms in Python (1st Edition) by John Canning, Alan Broder, Robert Lafore
Pearson Education

(Optional) Introduction to Algorithms, 3rd edition By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein
The MIT Press

Contenuti

Module 1: Computer Programming

Imperative programming
- top-down / bottom-up programming
- values, variables, expressions
- I/O instructions
- constructs, selection, loop
- functions, recursion
- I/O file
- libraries

Object-oriented programming
- fields and methods
- encapsulation, abstraction, inheritance, and polymorphism
- data types (arrays, lists)

++++++++++++++++++++++++

Module 2: Algorithms and Data Structures

Introduction
- Definitions of algorithm and structured data
- Methods for algorithms analysis (Big-O Notation, worst case, average, best case)

Main data Structures
- Linear (stack, queues, linked lists)
- Trees
- Graphs

Search and Sort
- Search (binary search, binary search trees, hash table)
- Sort (SelectionSort, InsertionSort, BubbleSort, HeapSort, MergeSort, QuickSort)

Algorithms on trees and graphs
- visit/traversal
- connected components
- topological sorting
- minimum spanning tree
- shortest path

Main algorithm approaches:
- Divide and Conquer
- Greedy algorithm
- Dynamic Programming