Course 2024-2025

Methods for programming [IHDCB331]

  • 10 credits
  • 30h+30h
  • 1st quarter
Language of instruction: French / Français

Learning outcomes

The student will be able to :

- formalize a problem described informally ;

- systematically build a correct and efficient program solving this problem.

 
 

Objectives

Learn rigourous methods for efficient algorithm construction.

 
 

Content

We base our methods on formal proofs, of runtime and memory consumption. We use recursivity systematically. The methods selected are: 1- divide-and-conquer 2- memoization and dynamic programming 3- the greedy method 4- generate-and-test.

We study the main data structures : lists, hash tables, trees, binary search trees, red/black trees, B-trees.

 
 

Table of contents

Part O. Specification by pre- and post-conditions, of proofs by invariants and variants. Runtime evaluation (complexity). Recursivity.

Part I. Programming methods: 1- divide-and-conquer 2- memoization and dynamic programming 3- the greedy method 4- generate-and-test 5- constraint-based programming 6- heuristic methods

Part II. Data structures. Data types. Lists. Hash tables. Binary search trees. Red-black trees. B-trees.

 
 
 

Prerequisites

Algorithmique 1 [IHDCB232]

Co-requisites

Mathématiques pour l'informatique (2e partie) [IHDCB222]

Teaching methods

Course of lectures illustrated with many examples. The students should actively develop new examples by themselves.

 
 

Evaluations

70% A written examination, where new problems are posed and new, efficient solutions should be discovered by the students on basis of the methods learned in the course.

The rest will be evaluated through a project and small assignments.

 
 

Recommended readings

The course follows a selection of chapters from: Introduction to Algorithms ( Second Edition), T. Cormen, C. Leiserson, R. Rivest, C. Stein, MIT Press.

 
 

Language of instruction

French / Français

Location for course

NAMUR

Organizer

Faculté d'informatique
rue Grandgagnage 21
5000 NAMUR
P. 081725252
F. 081724967
secretariat.info@unamur.be

Degree of Reference

Undergraduate Degree