This is an old revision of the document!

# Algorithmique

In this course you will get familiar with the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, the design of algorithms by induction, Sorting and searching, Merge sort, quicksort, heapsort, binary search, graph algorithms and data structures, graph traversals, shortest paths, spanning trees, matching, network flows, and elements of the theory of NP-completeness.

This is a course for second year students of both the systÃ¨mes de communication and informatique sections. The main classes will be in English, while the exercise classes and course material will be in French.

The course starts on September 23rd and ends on December 23rd, 2011.

## Course Materials

• You can find the latest polycopies of the course
• The examples of Quick Sort and Heap Sort used in Ola's lecture can be found here.

## Exercises

The placement for the exercises is arranged according to the alphabet order of the beginning of your last name as following:

A to B: GCA 331

C to J: GCB 330

K to Z: GCC 330

## **EXAM INFORMATION**

Exam review: You may take a look at your corrected final exams on Feb. 03, 2012 between 10:00 - 12:00 in BC 129

Exam sample: Jan. 20th, 2010

Final exam : January 19, 2012 from 12:15 - 15:15 in rooms : CE1, CE6 and CESPO (salle Polyvalente)

You are allowed to use an A4-age on which on can write anything on both sides.

Please refer to the mail sent on December 13, with the rooms allocation by alphabetical order or see attached list.

Note: You may take a look at your corrected final exams on Feb. 03, 2012 between 10:00 - 12:00 in BC 129.

• The course notes.
• Udi Manber: Introduction to algorithms: A creative approach. (Addison Wesley publishing, 1989)
• Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein: Introduction to algorithms. (MIT Press, 2001)

### Schedule:

• Mondays : 14:15 - 16:00 - room CE1 (course)
• Mondays : 16:15 - 18:00 - room GCA331, GCB 330 and GCC 330 (exercice)
• Fridays : 13:15 - 15:00 - room CM1 (course)

### Lectures video recordings

Last year's lectures have been video recorded and are available on line here together with two lectures from this semester.