85442 - Computational Thinking and Programming (1) (LM)

Learning outcomes

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.

Course contents

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 topic. The lectures are accompanied by several hands-on sessions for learning the main 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, according to its broader definition
  - Abstraction: the main tool of Computational Thinking
  - Comparing natural languages and programming languages
• Algorithms [Lovelace]
  - What is an algorithm?
  - First machines and programmers
  - How to write an algorithm: pseudocode
  - Our first algorithm: variables, assignments, and conditional statements
• Computability [Turing]
  - Computational cost of an algorithm
  - The halting problem (or, can we compute everything?)
• 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: from Linguistics to Computer Science
• Divide and conquer algorithms [von Neumann]
  - Sorting a billion books by title
  - Merge sort
• Dynamic programming algorithms [Fibonacci]
  - Golden ratio and rabbits: how do they relate to each other?
  - Fibonacci sequence
  - Tower of Hanoi
• Programming Languages [Hopper]
  - Computers as calculating machines
  - History of programming languages
  - Python
• 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 [Olivetti]
  - Line wrap
  - Minimum spanning tree

Readings/Bibliography

Lecture notes, slides, and any additional material will be made freely available to students in the GitHub repository of the course few days before each lecture. 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:

• 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 at https://docs.google.com/viewer?a=v&pid=sites&srcid=ZGVmYXVsdGRvbWFpbnxha2hsYWdoZWF8Z3g6NzgyOWYxNWNjMjE5ZjVh
• 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. https://doi.org/10.1098/rsta.2008.0118
• Wikipedia article about "Algorithm" (last visited, 3 July 2017): https://en.wikipedia.org/wiki/Algorithm

Teaching methods

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

Assessment methods

The exam consists of:

1. two partial written examinations held during the lectures, for assessing the emergent methodological knowledge gained by the student during the course;
2. the implementation of a project in the programming language learnt during the course;
3. an oral colloquium on the project implemented, for assessing the programming language skills gained by the student;
4. 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.

Students are mandatorily asked to organise themself in groups of 3-4 people for implementing the project. The personal contribution of each member of a group will be assessed during the oral colloquium.

The final evaluation of the student is based on the scores gained for each of the aforementioned points. In particular:

• excellent evaluation: reaching an in-depth view of all the course topics + active involvement in the development of the project following all the theoretical principles and practical guidelines provided to the student during the lectures;
• sufficient evaluation: reaching a partial view of the course topics + providing a minor contribution to the development of the project;
• insufficient evaluation: either not reaching even partial view on the course topics or not providing any contribution to the project.

Teaching tools

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 mailing-list will be set up so as to allow all the students of the course to communicate directly with each other and with the professor.

Links to further information

https://github.com/essepuntato/comp-think

Office hours

See the website of Silvio Peroni