Computational Thinking and Programming

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.

Academic year 2018/2019

Table of content

1. Material
2. Schedule
3. Links

Material

Keys:

• the = theoretical lecture
• lab = laboratory session
• exa = partial examination
• add = additional material

1. [12/11/18, the] Introduction to the course

   • slides (HTML)

   ---

2. [12/11/18, the] Introduction to Computational Thinking

   • slides: HTML
   • lecture notes: PDF, Google Docs
   • exercises: 1, 2, 3
   • additional material:
     • tweet on the result of the task describe your idea of this course with one word
     • article "Is abstraction the key to computing?" by Kramer (DOI: 10.1145/1232743.1232745)
     • book Computational Historical Thinking by Mullen
     • article "Studying How the Past is Remembered: Towards Computational History through Large Scale Text Mining" by Yeung and Jatowt (DOI: 10.1145/2063576.2063755)
     • post "How the New Science of Computational History Is Changing the Study of the Past" on MIT Technology Review

   ---

3. [14/11/18, the] Algorithms

   • slides: HTML
   • lecture notes: PDF, Google Docs
   • exercises: 1, 2, 3
   • additional material:
     • newspaper article "The Yoda of the Silicon Valley" by Roberts, dedicated to Donald Knuth

   ---

4. [16/11/18, the] Computability

   • slides: HTML
   • lecture notes: PDF, Google Docs
   • exercises: 1, 2
   • additional material:
     • article "Statistical mechanics of cellular automata" by Wolfram (DOI: 10.1103/RevModPhys.55.601)
     • section on "Turing machines" of the book "A new kind of science" by Wolfram
     • article "Alan Turing’s Legacy: Info-Computational Philosophy of Nature" by Dodig-Crnkovic (DOI: 10.1007/978-3-642-37225-4_6)
     • article "The new statistics: why and how by Cumming (DOI: 10.1177/0956797613504966)

   ---

5. [19/11/18, the] Programming languages

   • slides: HTML
   • lecture notes: PDF, Google Docs
   • exercises: 1, 2, 3
   • Python: first_algorithm.py
   • additional material:
     • solutions to Python exercises: 3

   ---

6. [22/11/18, lab] 1st Lesson

   • instructions: GitHub

   ---

7. [23/11/18, the] Organising information: ordered structures

   • slides: HTML
   • lecture notes: PDF, Google Docs
   • exercises: 1, 2, 3
   • Python: define_functions.py, list_instructions.py, stack_instructions.py, queue_instructions.py

   ---

8. [26/11/18, the] Brute-force algorithms

   • slides: HTML
   • lecture notes: PDF, Google Docs
   • exercises: 1, 2, 3, 4, 5
   • Python: stack_from_list.py, run_forever.py, linear_search.py, insertion_sort.py
   • additional material:
     • video "15 Sorting Algorithms in 6 Minutes"
     • website "Visualgo.net: sorting algorithms"
     • solutions to Python exercises: 2, 3, 4, 5

   ---

9. [27/11/18, lab] 2nd Lesson

   • content: GitHub
   • exercises: Python
   • additional material:
     • CSV file: titles.csv

   ---

10. [28/11/18, exa] First partial examination

    • content: test 1, test 2
    • solutions:
      • exercise 1:
        • solution to "Describe the main five widgets of the flowchart diagram model": Flowline = the arrow is used to define the order in which the operations are executed; Terminal = it indicates the beginning and ending of an algorithm; Process = used for expressing an instruction or operation; Decision = it depicts a conditional operation; Input / Output = allows the specification of an input or an output.
        • solution to "List the three main characteristics that the data structure list has": order, repeatability of its elements, countability of its elements.
      • exercise 2:
        • solution to "Describe what is a low-level programming language": languages that provide one abstraction level on top of the machine language, and thus it allows one to write programs in a way that is more intelligible to humans.
        • solution to "Describe what is a high-level programming language": languages which are characterised by a strong abstraction from the specifiability of the machine language. In particular, it may use natural language words for specific construct, so as to be easy to use for and to understand by humans.
      • exercise 3: Python script to calculate the output of the Turing machine provided - run with python turing_machine_1st_partial_ex3.py and follow the instructions
      • exercise 4: Python script to calculate the output of the function f - run with python f_1st_partial_ex4.py and follow the instructions
      • exercise 5: implementation of the function do_it

    ---

11. [28/11/18, the] Organising information: unordered structures

    • slides: HTML
    • lecture notes: PDF, Google Docs
    • exercises: 1, 2, 3
    • Python: set_instructions.py, dictionary_instructions.py

    ---

12. [29/11/18, lab] 3rd Lesson (included in the material of the 2nd lesson above)

    ---

13. [30/11/18, the] Recursion

    • slides: HTML
    • lecture notes: PDF, Google Docs
    • exercises: 1, 2
    • Python: run_forever_recursive.py, multiplication.py
    • additional material:
      • solution to Python exercises: 1, 2

    ---

14. [03/12/18, the] Divide and conquer algorithms

    • slides: HTML
    • lecture notes: PDF, Google Docs
    • exercises: 1, 2
    • Python: immutable_values.py, mutable_values.py, immutable_and_mutable_variables.py, merge.py, merge_sort.py
    • additional material:
      • video "Merge-sort with Transylvanian-saxon (German) folk dance"
      • video "Quicksort: Partitioning an array"
      • solution to Python exercises: 1, 2

    ---

15. [04/12/18, lab] 4th Lesson

    • content: GitHub
    • exercises: Python

    ---

16. [05/12/18, the] Dynamic programming algorithms

    • slides: HTML
    • lecture notes: PDF, Google Docs
    • exercises: 1, 2
    • Python: fib_dc.py, fib_dp.py
    • additional material:
      • solution to Python exercises: 1, 2

    ---

17. [06/12/18, lab] 5th Lesson

    • content: GitHub
    • exercises: Python
    • additional material:
      • TXT file: military.txt
      • script for installing the needed NLTK packages
      • example of use of NLTK

    ---

18. [10/12/18, the] Organising information: trees

    • slides: HTML
    • lecture notes: PDF, Google Docs
    • exercises: 1, 2
    • Python: tree_instructions.py
    • additional material:
      • solution to Python exercises: 1, 2

    ---

19. [11/12/18, lab] 6th Lesson (included in the material of the 5th lesson above)

    ---

20. [12/12/18, the] Organising information: graph

    • slides: HTML
    • lecture notes: PDF, Google Docs
    • exercises: 1, 2
    • Python: graph_instructions.py, graph_attribute_instructions.py, multigraph_instructions.py

    ---

21. [13/12/18, lab] 7th Lesson

    • content: GitHub
    • exercises: Python
    • additional material:
      • CSV file: topics.csv
      • example.py

    ---

22. [14/12/18, the] Backtracking algorithms

    • slides: HTML
    • lecture notes: PDF, Google Docs
    • exercises: 1
    • Python: peg_solitaire.py
    • additional material:
      • solution to Python exercises: 1

    ---

23. [28/11/18, exa] Second partial examination

    • content: test 1, test 2
    • solutions:
      • exercise 1:
        • solution to "Describe the steps chatacterising the dynamic programming algorithmic approach": [base case: solution exists] return the solution calculated previously, otherwise; [base case: address directly] address directly if it is an easy-to-solve problem, otherwise; [divide] split the input material into two or more balanced parts, each depicting a sub-problem of the original one; [conquer] run the same algorithm recursively for every balanced parts obtained in the previous step; [combine] reconstruct the final solution of the problem by means of the partial solutions; [memorize] store the solution to the problem for reusing it.
        • solution to "Describe the steps characterising the backtracking algorithmic approach": [leaf-win] if current node is a leaf and it is a solution then return it, otherwise; [leaf-lose] if current node is a leaf but it is not a solution, then return no solution back the parent node, otherwise; [recursive-step] apply recursively the whole approach for each child of the current node, until one of these recursive executions returns a solution - if no solution, back the parent node of the current one.
      • exercise 2:
        • solution to "Describe the main characteristics that the data structure dictionary has": A dictionary is a countable collection of unordered key-value pairs, where the key is non-repeatable in the dictionary
        • solution to "Considering a particular central node of a tree as focus, introduce the nomenclature used to refer to all the other nodes": the parent node of a given one is a node directly connected to another one when moving close to the root node; a child node of a given one is a node directly connected to another one when moving away from the root node; a sibling node of a given one is a node that shares the same parent node; an ancestor node of a given one is a node that is reachable by following the child-parent path repeatedly; a descendant node of a given one is a node that is reachable by following the parent-child path repeatedly.
      • exercise 3:
        • solution to "Write does the Python function def merge_sort(input_list) implementing the merge sort (the function merge can be used without providing an implementation)": Python implementation.
        • solution to "Write does the Python function def merge(left_list, right_list) used in the combine step of the merge sort": Python implementation.
      • exercise 4: Python script to calculate the output of the function f - run with python f_2nd_partial_ex4.py and follow the instructions.
      • exercise 5: implementation of the function pal.

    ---

24. [17/12/18, the] Project

    • slides: HTML
    • material: GitHub

    ---

25. [18/12/18, lab] 8th Lesson (included in the material of the 7th lesson above)

    ---

26. [19/12/18, the] Greedy algorithms

    • slides: HTML
    • lecture notes: PDF, Google Docs
    • exercises: 1
    • Python: line_wrap.py
    • additional material:
      • solution to Python exercises: 1

    ---

27. [19/12/18, add] Ask a thesis

    • slides: HTML

    ---

28. [19/12/18, the] Exercises on algorithms

    • lecture notes: PDF, Google Docs

    ---

Schedule

Date	Title
12/11/18	Introduction to Computational Thinking
14/11/18	Algorithms
16/11/18	Computability
19/11/18	Programming Languages
22/11/18	Laboratory
23/11/18	Organising information: ordered structures
26/11/18	Brute-force algorithms
27/11/18	Laboratory
28/11/18	Organising information: unordered structures
29/11/18	Laboratory
30/11/18	Recursion
03/12/18	Divide and conquer algorithms
04/12/18	Laboratory
05/12/18	Dynamic programming algorithms
06/12/18	Laboratory
10/12/18	Organising information: trees
11/12/18	Laboratory
12/12/18	Organising information: graphs (+ evaluation questionnaire)
13/12/18	Laboratory
14/12/18	Backtracking algorithms
17/12/18	Project presentation (time change: 11:30-13:30)
18/12/18	Laboratory
19/12/18	Greedy algorithms

Links

It is possible to find all the 2018/2019 texts of the written examination in the folder docs/exams.