AN INTRODUCTION TO PROGRAMMING (PYTHON)
Instructional goals
The aim of the course is to introduce the concept of computational problem and automatic solving through the design, analysis and implementation of computationally efficient algorithmic solutions in a high level programming language. At the end of the course the student will be able to find solutions to simple computational problems in the form of programs and will be able to evaluate their efficiency. To this aim, will be introduced the concepts underlying any high-level programming language: data types; conditional control structures and instructions; file management; exceptions and memory management.
Several lectures will be devoted to: object-oriented programming methodology; libraries for data science oriented applications; libraries for big data manipulation.
Intended learning outcomes
Knowledge and understanding: the student will acquire the fundamentals of the computational method; he will be introduced to the basic algorithms, data structures and the methods to evaluate the efficiency of the algorithms; he will learn the principles of programming languages with particular reference to the Python language.
Applying knowledge and understanding: the student will acquire the ability to analyze simple computational problems; he will be able to describe the problem by using suitable formalism; he will be able to find an efficient algorithmic solution and code it by using the Python language.
Making judgments: the student will acquire the ability to solve new computational problems by transferring the known techniques to the new domain.
Communication skills: The student will be able to interact about a computational problem with non-experts.
Learning skills: the student will be ready to continue his training to keep up to date on technological evolution.
Course Contents
Automatic resolution of problems; algorithms and programs; computational models; programming languages; types of programming languages; imperative languages; the structure of a program; simple and structured data types; variables; control structures; functions; recursion; input output; elementary data structures; object programming; useful libraries.
Reference Books
Allen B. Downey (2016). Think Python: How to Think Like a Computer Scientist 2nd Edition. O'Reilly Media.
Teaching Methods
Theoretical frontal lessons with computer exercises.
Assessment Method
The student will be evaluated on the basis of the individual scores achieved on:
- Written exam, this is divided into two parts that will take place on the same day.
---- The first part consists of a set of multiple choice questions that serve to establish the student's ability to analyze code written in the Python programming language from a syntactic, semantic and computational complexity point of view. A score ranging from 0 to 12 will be awarded.
---- In the second part it is assigned to the student a computational problem that she/he will have to solve by designing an algorithm and its coding in the Python programming language. This part is used to evaluate the student's ability in designing, coding and analyzing algorithmic solutions. A score ranging from 0 to 22 will be awarded.
The scores of the two tests will be added together to obtain the final score of the written test. The failure to achieve at least the score of 18 will result in failure to pass the exam.
- Oral exam. It focuses on a discussion of the written test to the aim of analyzing the ability of verbal synthesis and to establish whether during the written test the student has worked in complete autonomy. This part can assign up to 2 points to be added to those of the written test. However, the evidence of learning gaps during this phase can induce a negative evaluation up to, in extreme cases, the failure to pass the exam.
Achieving 32 points will result in a score of 30/30 cum laude.
Thesis assignment criteria
Passing the exam
Interest for the discipline
Week 1
The computational method: problem, model, algorithm, program. Introduction to Python programming language: the interpreter, variables, while loop operator and conditions, assignment operator, mathematical operations, data types, assignment and binding of variables; test operations; string operations; while loop and blocks via indentation.
Week 2
The print() and input() functions; the conversions from types; managing the program flow; checking the input to prevent user typing errors; the try...except structure and the error codes; string indexing and character operations; the len() function with input a string; the for loop structure.
Week 3
The range() function; the slicing operator on strings; the ord() and chr() functions. Defining new function in Python; assign a default values to function parameters. The methods in Python; string methods.
Week 4
The in statement; scope or visibility of local variables and parameters of functions. Introduction to the computational cost of algorithms and programs. The list data structure: definition; empty list; the append() method; the indexing operator; the slicing operator; deleting and editing items; aliasing and cloning; list as parameters of function; the max() function.
Week 5
List operators + and * for concatenation and repetition. The tuples: definition; properties; packing and unpacking. The sort() list method and the sorted() function; using the key parameter to modify the sorting criterion; the stability of sorting (when multiple records have the same key, their original order is preserved); the computational cost of the sorting in Python
Week 6
The dictionary data structure: definitions; add items; updating items; deleting items; the keys() and values() methods; the computational cost of the operations on dictionaries. The in statement in dictionaries and the average computational cost; the dictionary as a convenient way to represent sets. The list().
Week 7
Computational cost: worst case cost vs high probability cost vs average case cost; Big-O notation; the cost of some methods and functions. Sorting dictionary with sorted() function by keys and by values; the items() method. Reading text files, the open() function; simple text analysis.
Week 8
Output on formatted file: the parameter mode of the open() function. Recursion and programming: definition of recursive funtions. The stack of active functions: how the stack changes during a chain of recursive calls. Common errors in design a recursive function (infinite recursion). Python modules (libraries): import a module; the math and os modules. Think recursively. The binary search strategy for searching in sorted sequences. The computational cost of the binary search algorithm.
Week 9
Iterative implementation of the binary search algorithm. The quick sort algorithm, implementation and computational cost. Making quick sort algorithm stable. The zip() function and the unpack (*) operator.
Week 10
The counting sort algorithm: code and computational cost. Writing custom modules in Python. Classes and objects in Python: attributes and methods. Defining custom classes: initialization, introducing attributes, defining methods and operands behavior, public and hidden attributes.
Week 11
The matplotlib, numpy and pandas libraries.
Week 12
Introduction on machine learnng and classification problems: the k-NN model