Skip to content

Latest commit

 

History

History
270 lines (232 loc) · 24.3 KB

README.md

File metadata and controls

270 lines (232 loc) · 24.3 KB
Raw

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

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

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

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

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

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

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

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

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

  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

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

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

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

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

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

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

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

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

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

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

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

  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

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

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

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

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

Schedule

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

Links

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