Algorithm and Programming Workshop

The aim of this course is to practice algorithmic and programming skills by implementing the data structures and algorithms studied in the first semester. The focus is on building software through successive abstractions. We study the power of such abstractions for code realization and maintenance. We study various problems posed by abstraction, in particular algorithmic complexity. All these notions are programmed in the C language, allowing us to discuss the advantages and disadvantages of different programming languages.

Implementing a set type

abstract data type
realized by an array with stop
realized by a sorted teableau
comparison of implementations and algorithmic complexity


Implementing with chained lists

realizing the set type with a chained list
back to the notion of abstraction notion of abstraction
comparison of algorithmic complexities


Memory management and parameterization

dynamic memory allocation
parameterization of processing by a function


Generic data structures

data abstraction
parameterization of a data structure by functions

Basic algorithms (see IF101, IF102) and C programming (see PG101)

Implementing a set type

abstract data type
realized by an array with stop
realized by a sorted teableau
comparison of implementations and algorithmic complexity


Implementing with chained lists

realizing the set type with a chained list
return to the notion of abstraction notion of abstraction
comparison of algorithmic complexities


Memory management and parameterization

dynamic memory allocation
parameterization of processing by a function


Generic data structures

data abstraction
parameterization of a data structure by functions

Exercise sheets