search

comp-think / 2019-2020

The GitHub repository containing all the material related to the Computational Thinking and Programming course of the Digital Humanities and Digital Knowledge degree at the University of Bologna (a.a. 2019/2020).
Other
12 stars 3 forks source link

readme

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 2019/2020

Table of content

  1. Material
  2. Schedule
  3. Exam sessions
  4. Links

Material

Keys:

  1. [14/10/19, the] Introduction to the course
  2. [14/10/19, the] Introduction to Computational Thinking
    • slides: HTML
    • lecture notes: PDF
    • exercises: 1, 2, 3
    • solutions: 1, 2, 3
  3. [16/10/19, the] Algorithms
    • slides: HTML
    • lecture notes: PDF
    • exercises: 1, 2, 3
    • solutions 1, 2, 3
  4. [18/10/19, the] Computability
    • slides: HTML
    • lecture notes: PDF
    • exercises: 1, 2, 3
    • solutions: 1, 2, 3
  5. [21/10/19, the] Programming languages
  6. [23/10/19, lab] 1st Lesson
  7. [28/10/19, the] Organising information: ordered structures
  8. [30/10/19, lab] 2nd Lesson
  9. [4/11/19, the] Brute-force algorithms
  10. [6/11/19, the] Organising information: unordered structures
  11. [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.
      • 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:
  12. [11/11/19, the] Recursion
  13. [13/11/19, lab] 3rd Lesson
    • material: GitHub (same material of the previous laboratory lesson)
  14. [15/11/19, lab] 4th Lesson
  15. [18/11/19, the] Divide and conquer algorithms
  16. [21/11/19, lab] 5th Lesson
  17. [25/11/19, the] Dynamic programming algorithms
  18. [27/11/19, lab] 6th Lesson
  19. [02/12/19, the] Organising information: trees
  20. [04/12/19, the] Backtracking algorithms
  21. [09/12/19, the] Organising information: graphs
  22. [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 function fib_recursive(n) (in the file, it is named fib_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 function multiplication_recursive(n, m) (in the file, it is named multiplication).
      • exercise 4: Python script to calculate the output of the function f
      • exercise 5: implementation of the function depth_first_visit
  23. [13/12/19, the] Project
  24. [16/12/19, the] Greedy algorithms
  25. [13/12/19, the] Ask a thesis

Schedule

DateTimeTitle
14/10/199:30-11:30Introduction to Computational Thinking
16/10/199:30-11:30Algorithms
18/10/1912:30-14:30Computability
21/10/199:30-11:30Programming Languages
23/10/199:30-11:30Laboratory
28/10/199:30-11:30Organising information: ordered structures
30/10/199:30-11:30Laboratory
04/11/199:30-11:30Brute-force algorithms
06/11/199:30-11:30Organising information: unordered structures
11/11/199:30-11:30Recursion
13/11/199:30-11:30Laboratory
15/11/1912:30-14:30Laboratory
18/11/199:30-11:30Divide and conquer algorithms
20/11/199:30-11:30Laboratory
25/11/199:30-11:30Dynamic programming algorithms + evaluation questionnaire
27/11/199:30-11:30Laboratory
02/12/199:30-11:30Organising information: trees
04/12/199:30-11:30Backtracking algorithms
06/12/1912:30-14:30Laboratory
09/12/199:30-11:30Organising information: graphs
11/12/199:30-11:30Laboratory
13/12/1912:30-14:30Project: specification
16/12/199:30-11:30Greedy algorithms

Exam sessions

Links