85442 - COMPUTATIONAL THINKING AND PROGRAMMING (1) (LM)

Conoscenze e abilità da conseguire

At the end of the course, the student knows the high-level principles, as well as the historical and theoretical backgrounds, for solving problems efficiently by using computational tools and information-processing agents. The student is able to understand and use the main data structures for organising information, to develop algorithms for addressing computational-related tasks, and to implement such algorithms in a specific programming language.

Contenuti

The course is organised in a series of lectures. Each lecture introduces a specific topic, includes mentions to some related historical facts and to people (indicated between squared brackets) who have provided interesting insights on the subject. The lectures are accompanied by several hands-on sessions for learning the primary constructs of the programming language that will be used for implementing and running the various algorithms proposed.

List of lectures

• Introduction to Computational Thinking [Chomsky]
  - What is a computer?
  - Comparing natural languages and programming languages
  - Abstraction: the main tool of Computational Thinking
• Algorithms [Lovelace]
  - What is an algorithm?
  - First machines and programmers
  - How to develop an algorithm: flowcharts
  - Our first algorithm: input, process, decision, output
• Computability [Turing]
  - The computational cost of an algorithm
  - The halting problem (or, can we compute everything?)
  - Assessing the output: test-driven development
• Programming Languages [Hopper]
  - History of programming languages
  - Python
  - Writing our first algorithm in Python: variables, assignments, and conditional statements
• Organising information: ordered structures [Knuth]
  - What is a data structure?
  - List
  - Stack
  - Queue
• Brute-force algorithms [Holberton]
  - Iterations: for and while constructs
  - Linear search
  - Insertion sort
• Organising information: unordered structures [Borges]
  - Can data structures be infinite?
  - Set
  - Dictionary
• Recursion [Hofstadter]
  - An intuition: the Little Harmonic Labyrinth
  - Recursive approaches in Linguistics and Physics
  - Recursive algorithms
• Divide and conquer algorithms [von Neumann]
  - Ordering billions of books
  - Merge sort
• Dynamic programming algorithms [Fibonacci]
  - Golden ratio and rabbits: how do they relate to each other?
  - Keeping track of past solutions to sub-problems
  - Fibonacci sequence
• Organising information: trees [Garcia Marquez]
  - Genealogy and document markup
  - Tree
• Backtracking algorithms [AlphaGo]
  - Playing board games with trees
  - Peg solitaire
• Organising information: graphs [Euler]
  - The city of Königsberg
  - Graph
• Greedy algorithms [Evelyn Berezin]
  - Wordprocessors
  - Line wrap

The dates and times of all the lectures above are available in the section "Schedule" of the GitHub repository of the course.

Testi/Bibliografia

Lecture notes will be made freely available to students in the GitHub repository of the course before the beginning of the course. Slides and any additional material will be made also available a few days before each lecture in the same repository. No additional books or papers are needed for passing the final exam successfully.

The following suggested readings could be helpful to students as background material, in order to practice basic terminologies of the course:

• The "Computational Thinking and Programming book" created for the course.
• Tagliaferri, L. (2018). How To Code in Python. ISBN: 978-0999773017. Full text available online.
  
• Papert, S. (1980). Introduction: Computer for Children. In "Mindstorms: children, computers, and powerful ideas", pp. 3-18. New York, USA: Basic Books, Inc. ISBN: 0-465-04627-4. Full text available online.
  
• Wing, J. M. (2008). Computational thinking and thinking about computing. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 366 (1881): 3717. DOI: https://doi.org/10.1098/rsta.2008.0118. Full text available online.
  
• Nardelli, E. (2019). Do we really need computational thinking? Communications of the ACM, 62 (2): 32-35. DOI: https://doi.org/10.1145/3231587

Metodi didattici

Face-to-face classes for 30 hours, plus face-to-face hands-on sessions in the laboratory for max. 16 hours.

Modalità di verifica e valutazione dell'apprendimento

The exam consists of:

1. a (non-mandatory) workshop to be held after the last lecture of the course, where the students are asked to organise themself in groups of 3-4 people - maximum score: 4 points;
2. a final written examination held after the lectures, for assessing the overall competences and analytical skills acquired by the students on all the topics of the course - maximum score: 32 points.

The final evaluation of the student is the sum of the scores gained for each of the aforementioned points (any score greater than 30 will be registered as 30 cum laude). In particular:

• excellent evaluation (final score greater than 26): reaching an in-depth view of all the course topics;
• sufficient evaluation (final score between 18 and 26): reaching a partial view of the course topics;
• insufficient evaluation (final score lesser than 18): not reaching an inappropriate view of the course topics.

It is strongly suggested to attend the course in person since it would enable collegial discussions with the professor and the other students. Indeed, these discussions are extremely important since they simplify a lot the study of the course topics. However, even if discouraged, it is possible to follow the course as non attender. For non attenders, the organisation of the course should be discussed with the professor in advance.

Strumenti a supporto della didattica

Classes are held in a classroom equipped with personal computers connected to the Intranet and Internet.

Theory lessons will always be accompanied by practical parts, which will be reinforced during several hands-on sessions. All the material of the course - including lecture notes and slides - will be made available in the GitHub repository of the course. A group in a free messaging application will be set up so as to allow all the students of the course to communicate directly with each other and with the professor.

Link ad altre eventuali informazioni

https://github.com/comp-think/2023-2024/

Orario di ricevimento

Consulta il sito web di Silvio Peroni