Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
en:courses:2011-2012:a [2012/09/07 17:57]
etesami
en:courses:2011-2012:a [2013/02/26 11:40]
cangiani
Line 1: Line 1:
 ====== Algorithmique ====== ====== Algorithmique ======
-\\ +In this course you will get familiar with the theory ​and practice ​of basic concepts and techniques in algorithms. The course covers mathematical inductiontechniques for analyzing algorithms, 
-In this course you will get familiar with design ​and analysis ​of algorithms. ​ +elementary data structures, the design of algorithms ​by induction, Sorting ​and searching, ​ 
-The course covers ​ +Merge sort, quicksort, heapsort, binary search, ​graph algorithms ​and data structures, ​graph traversals, ​ 
-  * proving correctness of algorithms by mathematical induction +shortest paths, spanning trees, matching, network flows, and elements ​of the theory  ​of NP-completeness.
-  * techniques for analyzing ​running time of algorithms +
-  * study of various sorting algorithms +
-  *  ​elementary data structures ​as well as priority queuesbinary search trees, and data structures for disjoint sets +
-  * the design of algorithms ​using divide-and-conquer and dynamic programming +
-  ​* ​graph algorithms ​including ​graph traversals, shortest paths, spanning trees, matching, ​and network flows +
-  * probabilistic analysis ​of algorithms. +
-\\ +
-This is a course for second year students of both the systèmes de communication and informatique sections. The lectures will be in English, but the students are free to choose the final exam in either ​of English or French. Some of the exercises can be in English and some in French.+
  
-==== Schedule ==== +This is a course for second year students of both the systèmes de communication ​and informatique sections. The main classes will be in Englishwhile the exercise classes ​and course ​material will be in French.
-  * Lectures on Mondays : 14:15 - 16:00 (room CE1) and Fridays : 13:15 - 15:00  (room CM1) +
-  * Exercise sessions on Mondays 16:15 - 18:00  (rooms BM5202GCA331, GCB330 ​and GCC330) +
-\\ +
-The course ​starts on September 21st and ends on December 21st, 2012.+
  
-==== Reading ==== +The course ​starts on September 23rd and ends on December 23rd2011.
-The textbook for the course ​is: +
-  * Thomas CormenCharles Leiserson, Ronald Rivest, Clifford Stein: //​Introduction to algorithms//,​ Third Edition, MIT Press, 2009.+
  
 +===== Course Materials =====
 +
 +  * You can find the latest polycopies of the course ​
 +{{:​en:​courses:​2011-2012:​polycopie-2012c.pdf|here}}
 +
 +  * The examples of Quick Sort and Heap Sort used in Ola's lecture can be found {{:​en:​courses:​2011-2012:​sortingexamples.pdf|here}}.
 +
 +  * {{:​en:​courses:​2011-2012:​algorithmique-flows-2011.pdf|Maximum Flow on graphs}}
 +
 +  * {{:​en:​courses:​2011-2012:​algorithmique-mst-2011.pdf|Minimum Spanning Trees}}
 +
 +  * {{:​en:​courses:​2011-2012:​algorithmique-cycles-2011a.pdf|Negative cycle detection}}
 +  * {{:​en:​courses:​2011-2012:​algorithmique-NPCompleteness-2011c.pdf|NP Completeness}}
 +  ​
 \\ \\
-For the curious student, some subset of the topics covered in the course have  been treated also in the interesting multi-volume book //The Art of Computer Programming//​ by Donald E. Knuth. 
  
-/* +===== Exercises ====
-==== Exercises ==== +\\ 
-The placement for the exercises is arranged according to the alphabet order of the beginning of your last name. How it actually happens will be specified shortly.+Click [[en:​courses:​2011-2012:​hand_outs|here]] for 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 A to B: GCA 331
Line 37: Line 38:
  
 \\ \\
-*/+===== **EXAM INFORMATION** ===== 
 +\\
  
-==== Exam ==== +**Exam review**: ​You may take a look at your corrected final exams on //Feb03, 2012// between 10:00 - 12:00 in //BC 129//
-You are allowed to use an A4-page ​on which you can write anything on both sides(You are not allowed to look at it using a magnifying glass!)+
  
 +**Exam sample**: {{:​en:​courses:​2011-2012:​algo:​final_sample2.pdf|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.
 \\ \\
-==== Homepage of the course in previous years ==== 
-[[en:​courses:​2011-2012:​a|2011-2012]],​ [[en:​courses:​2010-2011:​a|2010-2011]],​ [[en:​courses:​2009-2010:​a|2009-2010]],​ [[en:​courses:​2007-2008:​algo|2007-2008]],​ [[en:​courses:​2006-2007:​algo|2006-2007]] 
  
 +Note: You may take a look at your corrected final exams on Feb. 03, 2012 between 10:00 - 12:00 in BC 129. 
 +
 +==== Recommended reading: ====
 +
 +  * 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 [[http://​slideshot.epfl.ch/​events/​3|here]] together with two lectures from this semester. ​