Statistics, Economics, and Social Sciences

DONATELLA FIRMANI

Learning goals.
The primary objective is to learn how to describe simple processes in a formal way, through the definition of algorithms, and to acquire a methodology to evaluate the complexity of an algorithm.
Students must be able to:
- unambiguously define a problem,
- identify precisely which data should be processed,
- how to represent such data,
- how to decompose a procedure in steps that solves the problem.
These skills are expressed through the use of the Java programming language.
Knowledge and understanding.
After attending the course the students know and understand the concept of algorithm and how an algorithm can be expressed using a programming language.
They use the basic constructs of the Java language and are aware of the possibility of solving the same problem with different computational complexity algorithms.
They also know various algorithms for solving basic problems, such as searching and sorting, and some numerical algorithms.
Applying knowledge and understanding.
At the end of the course students are able to formalize algorithms for simple problems, implement them in Java language, passing through all phases: design, writing the source code, compilation, debugging and execution. They know the notations that allow to express asymptotically the complexity of an algorithm.
They know how textual, numerical, and other information can be encoded.
Making judgements.
Students are able to appreciate the difference between solving a problem and formally describing a resolutive process.
They manage to evaluate how different implementation choices can lead to solutions with different efficiency characteristics, applying paradigms studied in the context of basic problems.
Through intense laboratory activities they acquire a greater awareness of the processes underlying the use of a computer.
Communication skills.
Students acquire the formal rigor necessary to use a programming language.
They are able to appreciate and foresee the repercussions, in terms of complexity, of the application of different resolution techniques.
They know how to apply decomposition techniques, in order to reduce the solution of complex problems to the solution of simpler problems.
Learning skills.
Students who pass the exam can analyze the structure of a program, even complex, can easily be productive using any other imperative or object-oriented programming language, can distinguish for which problems an automated solution may exist.

a) Knowledge and understanding
By the end of the course, students will know what an algorithm is, what the difference is between data and its computational representation, and how to reason using abstraction tools. They will be able to write programs in the Python language to solve new problems, also making use of theoretical knowledge in algorithm analysis.

b) Applying knowledge and understanding
Learning elements of algorithm theory and a programming language allows students to flexibly solve new computational problems.

c) Making judgements
The algorithmic (or computational) thinking that students develop in this course provides the tools for precise and unambiguous analysis of problems, relying on relevant information.

d) Communication skills
Students acquire the technical and scientific language of computer science, which must be appropriately used in both written and oral examinations. Furthermore, writing documentation for code trains students to explain their work clearly.

e) Learning skills
The course introduces students to new concepts (programming, algorithm theory). The effort made to understand and apply them allows students to study and evaluate unknown algorithmic techniques and new programming languages.

None

History of computer science and its evolution.
- algorithms
- representation of data
- encoding of text and numbers
- binary, decimal, hexadecimal representation
- ASCII, UTF-8, Latin1

** Programming in Python

Chapters and parts of the textbook / Thinking in Python / by Allen B. Downey ed. 2.2.23

1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12.1-12.3, 13.1-13.5, 14.1-14.5, 19.1-19.2, Appendix A, Appendix B

- variables, expressions and statements
- numeric data types
- calling and defining functions
- conditional statement
- iteration statement
- iteration and recursion
- stack diagrams and recursion bounds
- data types: strings and text manipulation
- lists and sequences of data
- dictionaries
- file manipulation
- exception handling
- conditional expressions, list comprehension

** Development tools

- interactive Python interpreter
- text editor
- IDE (Thonny)

** Efficient algorithms

- Complexity of algorithms
- Big O notation
- sequential search and binary search
- recursion, call stack, Fibonacci successon
- maximum common divisor (Euler's method)
- Sorting by insertion
- Mergesort
- stable sorting
- numerical algorithms

Teacher's notes: chapters 1, 2, 3, 7, 8, 9, 11

Traditional in-person
Lectures with PC lab activities

Not mandatory

The exam will consist of a test including two parts, corresponding to the two parts of the course. Both parts will include programming exercises on computer, followed, if necessary, by an oral examination at the discretion of the instructor.
There will be no midterm tests.
The practical programming test will be carried out on a computer, according to procedures very similar to those used during lectures. Students are strongly encouraged to practice using the same methods at home.

Here is an example of a programming test
https://massimolauria.net/informatica2022/docs/esempio_prova_programmazione.zip

Check the Moodle website for more exercises https://elearning.uniroma1.it/course/view.php?id=15154

• Introduction to Python


• Values, Variables and Expressions


• Conditional Statements and Logic


• Functions


• Iteration and Algorithms


• Strings


• Lists


• Complexity, Search and Matrices


• Tuples, Dictionaries and Sorting


• Files, Text Encoding and Number Encoding