UCLan, CO2412: Computational Thinking, academic year 2021/22

• Lecture: Tuesday, 16.00 - 17.00, digital (until further notice).
• Practical sessions: Thursday, 09.00 - 10.00, CM026 (group #SC1); Thursday, 10.00 - 11.00, CM017 (group #SE); Thursday, 11.00 - 12.00, CM011 (group #SC2); Thursday, 12.00 - 13.00, CM016 (group #GD).
• Round table: Thursday, 16.00 - 17.30, BB240.
• Office hours: Monday, 09.00 - 12.00, CM213.

Instructors: Martin Thomas Horsch (CM213), Oliver Kerr (CM214).

Learning outcomes: Upon successful completion of this module, a student will be able to:

1. Use methods including logic and probability to reason about algorithms and data structures;
2. Compare, select, and justify algorithms and data structures for a given problem;
3. Analyse the computational complexity of problems and the efficiency of algorithms;
4. Use a range of notations to represent and analyse problems;
5. Implement and test algorithms and data structures.

Literature:

[Erciyes] K. Erciyes, Discrete Mathematics and Graph Theory, Cham: Springer (ISBN 978-3-03061114-9), 2021.
[SMDD] P. Sanders, K. Mehlhorn, M. Dietzfelbinger, R. Dementiev, Sequential and Parallel Algorithms and Data Structures, Cham: Springer (ISBN 978-3-03025208-3), 2021.

Glossary:

The glossary document introduces and defines selected key concepts from the domain.

Structure:

0. Introduction
   • Week 01: Introductory meeting slides (ODP, PDF), How to set up Jupyter Notebook
   • K. Brennan, M. Resnick, "New frameworks for studying and assessing the development of computational thinking," in Proceedings of AERA 2012, Cambridge, MA: Academic Press, 2012
   • Python Software Foundation, Python Tutorial, 2021
1. Program analysis
   • Week 02: Lecture slides (ODP, PDF), iteration vs. recursion (Jupyter notebook), tutorial document (discussion slides)
   • Week 03: Lecture slides (ODP, PDF), formal verification (Jupyter notebook), tutorial document (discussion slides)
   • Week 04: Lecture slides (ODP, PDF), iterative algorithms (Jupyter notebook), tutorial document (discussion, discussion slides)
   • Erciyes, Sections 3.1, 3.4, 10.1, and 10.2
   • SMDD, Sections 1.7 to 2.10
   • E. W. Dijkstra, "Go to statement considered harmful," Communications of the ACM 11(3), 147-148, doi:10.1145/362929.362947, 1968
2. Algorithm design
   • Week 05: Lecture slides (ODP, PDF), selection and mergesort (Jupyter notebook), maximum sublist (Jupyter notebook), tutorial document (discussion slides, discussion notebook)
   • Week 06: Lecture slides (ODP, PDF), greedy cashier (Jupyter notebook), tutorial document (discussion slides, discussion notebook)
   • Week 07: Lecture slides (ODP, PDF), singly linked list (Jupyter notebook), doubly linked list (Jupyter notebook), knapsack problem (Jupyter notebook), tutorial document (discussion slides, discussion notebook)
   • Erciyes, Sections 3.2, 3.3, and 3.5
   • SMDD, Sections 1.4, 1.5, 3.1, 3.2, 3.6 to 4.2, and Chapter 5
   • G. Dlamini, F. Jolha, Z. Kholmatova, G. Succi, "Meta-analytical comparison of energy consumed by two sorting algorithms," Information Sciences 528, 767-777, doi:10.1016/j.ins.2021.09.061, 2022
3. Graphs and trees
   • Week 08: Lecture slides (ODP, PDF), insertion-sort (Jupyter notebook), binary search tree (Jupyter notebook), tutorial document (discussion slides, discussion notebook)
   • Week 09: Lecture slides (ODP, PDF)
   • Week 10: Lecture slides (ODP, PDF), balanced BST and number matching (Jupyter notebook), incidence-list graph (Jupyter notebook), tutorial document (discussion notebook)
   • Week 11: Lecture slides (ODP, PDF), coursework assessment specification (contributes 60% to the grade), coursework template document
   • Week 16: Lecture slides (ODP, PDF), adjacency-matrix graph (Jupyter notebook), tutorial document (discussion slides, discussion notebook)
   • Erciyes, Chapters 11 and 12, Sections 13.5, 14.1 to 14.3, and 14.6
   • SMDD, Sections 2.12, 6.1, 6.2, 7.1 to 8.5, and 9.1 to 9.3
4. Logic
   • Week 17: Lecture slides (ODP, PDF), propositional logic statements (Jupyter notebook), tutorial document (discussion slides, discussion notebook)
   • Week 18: Lecture slides (ODP, PDF), tutorial document (discussion slides, discussion notebook)
   • Week 19: Lecture slides (ODP, PDF), tutorial document (discussion slides)
   • Week 21: Tutorial document
   • Week 22: Tutorial document (discussion slides)
   • Week 23: Lecture slides (ODP, PDF), knowledge graph (Jupyter notebook), tutorial document (discussion slides)
   • Week 24: Lecture slides (ODP, PDF), alternative coursework assessment problem, tutorial document
   • Erciyes, Chapter 1 and Section 2.1
   • SMDD, Section 2.13
5. Reflection and revision
   • Material provided by Oliver Kerr, see Blackboard.

Grading:

• 60% from the coursework assessment (see also the template) or the alternative coursework assessment;
• 40% from the final exam.

Index