UCL - Algorithmics and programming Part1

[SINF1160]

[30h + 30h] 6 credits

This course is taught in the 1st semester.

Teacher(s): Baudouin Le Charlier

Language: French

Level: First

Aims
Main themes
Content and teaching methods

Aims

SINF1160 is an introductory course to programming methods and concepts. Students are taught methods to construct correct program from the start, without using a trial and error process. To this aim, fundamental concepts such as algorithm, specification, loop invariant, decomposition into subproblems are introduced and motivated. Fundamental concepts from programming language theory are also described with care.

Main themes

- Systematic construction of algorithms starting from a set of primitive objects and a set of primitive actions upon these objects.
- Systematic translation of an algorithm into a programming language (Java).
- Representations of numbers and characters
- Syntax and data types in a programming language

Content and teaching methods

The course is taught in a traditional way : lectures are given by the teacher in the classroom ; the theory is illustrated by simple exercices, which students solve with the help of an assistant. A few small projects are also given to students.

The material of the lectures consists of four chapters.

The first chapter of the course addresses the construction of algorithms. Primitive objects are given with primitive operations upon them. It is shown how arbitrarily complex algorithms acting on the objects can be built using sequential, conditional, and iterative composition of algorithms. The emphasis is put on specifications and on the use of assertions to derive correct code. The Java programming language is used in a controlled way as a tool to make the algorithms amenable to execution by a computer.

The second chapter is concerned with the representation of data. Decimal, binary, octal and hexadecimal notations are reviewed as well as conversion algorithms from one notation to another. The two's complement representation for negative numbers is explained as well as the representation of floating point numbers. ASCII and Unicode representations for characters are described and discussed.

In the third chapter, the CPU of a simple computer is described together with its machine language. Students are taught how to write programs in this simple machine language. The design of subprograms with standard conventions for subprogram calls and returns as well as parameter passing is discussed in details as it allows the student to better understand procedure calls and parameter passing methods in higher level programming languages.

The fourth chapter addresses programming languages concepts in a more systematic way. The Java programming language is used to illustrate the concepts but no attempt is made to provide a global overview of Java. In contrast, a limited number of topics are studied with care and in details : primitive data types, literals, variables, arrays, the String class, static methods, expressions, a small subset of composed statements, primitive type conversions, method overloading. Classical algorithms for searching and sorting are build with this subset of Java.

To understand the material of the course, simple exercices are given to students in the classroom under the supervision of an assistant. Most of the exercices are first solved with pen and paper, not directly on the computer. Three or four small projects are also proposed to teams of two students. These projects are formally evaluated and their ratings contribute up to 30% of the global rating for the course.