4CM508 — Computer Systems, Data Structures, and Data Management
Fundamental data structures and algorithms with an introduction to database systems.
Instructor: Ioannis Tsioulis
Term: Level 4 (UG)
Location: Mediterranean College, Athens
Overview
This module introduces the fundamental data structures and algorithms of computer science, together with the principles of data management. All programming in the module is carried out in Python. Where Python abstracts away the underlying machine, as in the representation of data in memory or the use of pointers, short C++ examples are used in lectures to make these mechanisms visible. Students are expected to read, trace and explain such fragments, although their own programs are written in Python.
The first part of the module examines how computers represent data, from number systems and primitive data types to arrays, records and references. It then develops the analysis of algorithms and applies it to searching, to linear data structures and to hashing. The second part addresses sorting, priority queues and graph algorithms, and concludes with an introduction to relational databases, normalisation and SQL.
Topics
- Number systems and the representation of data in memory
- Primitive data types, variables and control flow
- Arrays, records and references
- Analysis of algorithms and Big O notation
- Searching: linear and binary search
- Linear data structures: dynamic arrays, linked lists, stacks and queues
- Hashing, hash tables and the Map abstract data type
- Sorting algorithms, including divide-and-conquer methods
- Heaps, priority queues and shortest paths in graphs
- Relational databases, normalisation and SQL
Companion notebooks
Two open courses on the teaching page provide hands-on notebooks, executable in Google Colab, that accompany the topics of this module. They are written in Python, the language of the module, but were designed as general courses rather than for this module alone; the weekly lab sheets indicate which notebooks are covered in each session. The table maps each topic to the corresponding notebooks.
| Topic | Open course | Notebooks |
|---|---|---|
| Variables, data types, control flow and functions | From Zero to Data Structures and Algorithms in Python | 1 to 4 |
| Lists as dynamic arrays | From Zero to Data Structures and Algorithms in Python | 5, 9 |
| Objects and references | From Zero to Data Structures and Algorithms in Python | 7 |
| Analysis of algorithms: Big O notation | From Zero to Data Structures and Algorithms in Python | 11 |
| Recursion | From Zero to Data Structures and Algorithms in Python | 12 |
| Searching: linear and binary search | From Zero to Data Structures and Algorithms in Python | 13 |
| Sorting algorithms | From Zero to Data Structures and Algorithms in Python | 14 |
| Stacks and queues | From Zero to Data Structures and Algorithms in Python | 15 |
| Linked lists | From Zero to Data Structures and Algorithms in Python | 16 |
| Hash tables and the Map abstract data type | From Zero to Data Structures and Algorithms in Python | 17 |
| Trees and binary search trees | From Zero to Data Structures and Algorithms in Python | 18 |
| Databases and the relational model | From One Table to a Cluster | 1 |
| SQL: queries, joins and aggregation | From One Table to a Cluster | 1, 2 |
Students who wish to go further with the C++ examples may use the optional worksheets, with solutions, on first programs, arrays and pointers in the repository Teach-C-.