This space contains all the material related to the Computational Thinking and Programming course of the Digital Humanities and Digital Knowledge degree at the University of Bologna.
Keys:
- the = theoretical lecture
- lab = laboratory session
- exa = partial examination
- add = additional material
- [14/10/19, the] Introduction to the course
- slides: HTML
- [14/10/19, the] Introduction to Computational Thinking
- [16/10/19, the] Algorithms
- [18/10/19, the] Computability
- [21/10/19, the] Programming languages
- slides: HTML
- lecture notes: PDF
- Python: first_algorithm_empty.py, first_algorithm_no_assignments.py, first_algorithm.py
- exercises: 1, 2, 3
- solutions: 1, 2, 3
- [23/10/19, lab] 1st Lesson
- instructions: GitHub
- [28/10/19, the] Organising information: ordered structures
- slides: HTML
- lecture notes: PDF
- Python: define_functions.py, list_instructions.py, stack_instructions.py, queue_instructions.py
- exercises: 1, 2, 3
- solutions: 1, 2, 3
- [30/10/19, lab] 2nd Lesson
- material: GitHub
- [4/11/19, the] Brute-force algorithms
- slides: HTML
- lecture notes: PDF
- Python: stack_from_list.py, run_forever.py, linear_search.py, insertion_sort.py
- exercises: 1, 2, 3, 4, 5
- solutions: 1, 2, 3, 4, 5
- additional material: Atari Go + special exercise
- [6/11/19, the] Organising information: unordered structures
- slides: HTML
- lecture notes: PDF
- Python: set_instructions.py, dictionary_instructions.py
- exercises: 1, 2, 3
- solutions: 1, 2, 3
- [11/11/19, exa] First partial examination
- content: test 1, test 2
- solutions:
- exercise 1:
- solution to "Highlight whether the data structures in the table (queue, set, list) are compliant or not with the characteristics shown": queue and list are compliant with all the characteristics, while set is compliant with countability only.
- solution to "Highlight whether the data structures in the table (dictionary, queue, stack) are compliant or not with the characteristics shown": queue and stack are compliant with all the characteristics, while dictionary is compliant with countability only.
- exercise 2:
- solution to "Describe what is the form of the production rules of a regular grammar":
<non-terminal> ::= "terminal"and<non-terminal> ::= "terminal" <non-terminal>. - solution to "Describe what is the form of the production rules of a context-free grammar":
<non-terminal> ::= γ, beingγany possible combination of terminal and non-terminal symbols.
- solution to "Describe what is the form of the production rules of a regular grammar":
- exercise 3: an execution of the flowchart will modify the input string until it is not lesser than four characters, and then it will compare the last character of the string. In particular, if such character is not contained in the string
"did you get it?", the character will be returned, otherwise the input string (as modified by the execution of the flowchart) will be returned. - exercise 4: Python script to calculate the output of the function
f - exercise 5:
- solution to with vowels: implementation of the function
do_it - solution to with consonants: implementation of the function
do_it
- solution to with vowels: implementation of the function
- exercise 1:
- [11/11/19, the] Recursion
- slides: HTML
- lecture notes: PDF
- Python: run_forever_recursive.py, multiplication.py
- exercises: 1, 2
- solutions: 1, 2
- [13/11/19, lab] 3rd Lesson
- material: GitHub (same material of the previous laboratory lesson)
- [15/11/19, lab] 4th Lesson
- material: GitHub
- [18/11/19, the] Divide and conquer algorithms
- slides: HTML
- lecture notes: PDF
- Python: immutable_values.py, mutable_values.py, immutable_and_mutable_variables.py, merge.py, merge_sort.py
- exercises: 1, 2, 3
- solutions: 1, 2, 3
- [21/11/19, lab] 5th Lesson
- material: GitHub
- [25/11/19, the] Dynamic programming algorithms
- [27/11/19, lab] 6th Lesson
- material: GitHub
- [02/12/19, the] Organising information: trees
- [04/12/19, the] Backtracking algorithms
- [09/12/19, the] Organising information: graphs
- slides: HTML
- lecture notes: PDF
- Python: graph_instructions.py, multigraph_instructions.py, graph_attribute_instructions.py
- exercises: 1, 2
- solutions: 1, 2
- [13/12/19, exa] Second partial examination
- content: test 1, test 2
- solutions:
- exercise 1:
- solution to "Describe the steps characterising the divide and conquer algorithmic approach": [base case] address the problem directly on the input material if it is depicting an easy-to-solve problem; otherwise [divide] split the input material into two or more balanced parts, each representing a sub-problem of the original one; [conquer] run the same algorithm recursively for every balanced part obtained in the previous step; [combine] reconstruct the final solution of the problem using the partial solutions obtained from running the algorithms on the smaller parts of the input material.
- solution to "Describe the steps characterising a recursive algorithm": A recursive algorithm must have one or more basic cases and at least one recursive step. Each basic case describes a terminating scenario and does not use any recursion to produce the answer to a specific (sub-)problem. Instead, the recursion step is where the same algorithm is executed again with a different (and, usually, reduced) input.
- exercise 2:
- solution to "Describe the main components and characteristics that the data structure tree has": A tree is a data structure that simulates a hierarchical tree, composed by a set of nodes related to each other by a particular hierarchical parent-child relation. The originating (or starting) node is called root node, placed at the very top of the tree. Instead, the terminating nodes, called leaf nodes, are placed at the very bottom. Taking into consideration a node of a tree, we can name precisely all the other nodes surrounding it as parent, ancestors, siblings, children and descendants.
- solution to "Describe the main components and characteristics that the data structure graph has": A graph is a data structure composed by nodes connected by edges. We can distinguish two different kinds of graphs: undirected graphs and directed graphs. In undirected graphs, one can traverse an edge in one way or the other indifferently. In directed graphs, instead, the edge specifies the direction for traversing it.
- exercise 3:
- solution to "Write down the Python function def
fib_recursive(n)implementing the fibonacci recursive algorithm": implementation of the functionfib_recursive(n)(in the file, it is namedfib_dc). - solution to "Write down the Python recursive function def
multiplication_recursive(n, m)implementing the multiplication operation between two non-negative integer numbers": implementation of the functionmultiplication_recursive(n, m)(in the file, it is namedmultiplication).
- solution to "Write down the Python function def
- exercise 4: Python script to calculate the output of the function
f - exercise 5: implementation of the function
depth_first_visit
- exercise 1:
- [13/12/19, the] Project
- [16/12/19, the] Greedy algorithms
- [13/12/19, the] Ask a thesis
- slides: HTML
| Date | Time | Title |
|---|---|---|
| 14/10/19 | 9:30-11:30 | Introduction to Computational Thinking |
| 16/10/19 | 9:30-11:30 | Algorithms |
| 18/10/19 | 12:30-14:30 | Computability |
| 21/10/19 | 9:30-11:30 | Programming Languages |
| 23/10/19 | 9:30-11:30 | Laboratory |
| 28/10/19 | 9:30-11:30 | Organising information: ordered structures |
| 30/10/19 | 9:30-11:30 | Laboratory |
| 04/11/19 | 9:30-11:30 | Brute-force algorithms |
| 06/11/19 | 9:30-11:30 | Organising information: unordered structures |
| 11/11/19 | 9:30-11:30 | Recursion |
| 13/11/19 | 9:30-11:30 | Laboratory |
| 15/11/19 | 12:30-14:30 | Laboratory |
| 18/11/19 | 9:30-11:30 | Divide and conquer algorithms |
| 20/11/19 | 9:30-11:30 | Laboratory |
| 25/11/19 | 9:30-11:30 | Dynamic programming algorithms + evaluation questionnaire |
| 27/11/19 | 9:30-11:30 | Laboratory |
| 02/12/19 | 9:30-11:30 | Organising information: trees |
| 04/12/19 | 9:30-11:30 | Backtracking algorithms |
| 06/12/19 | 12:30-14:30 | Laboratory |
| 09/12/19 | 9:30-11:30 | Organising information: graphs |
| 11/12/19 | 9:30-11:30 | Laboratory |
| 13/12/19 | 12:30-14:30 | Project: specification |
| 16/12/19 | 9:30-11:30 | Greedy algorithms |
- 30 January 2020
- 14 May 2020
- 22 June 2020
- 9 July 2020
- 24 September 2020
- 10 December 2020
- Written examination: sources and solutions