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:52]
etesami 		en:courses:2011-2012:a [2016/06/23 11:26] (current)
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 induction, techniques 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 queues, binary 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. Of the exercises, some are 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 English, while 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 BM5202, GCA331, 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 23rd, 2011.
-The textbook for the course ​is: +
-  * Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein: //​Introduction to algorithms//,​ Third Edition, MIT Press, 2009.+
  
-For the curious student, some subset of the topics covered in the course have  been treated also in the interesting multivolume //The Art of Computer Programming//​ by Donald E. Knuth.+===== Course Materials =====
  
-/* +  ​* You can find the latest polycopies of the course  
-==== Exercises ==== +{{:​en:​courses:​2011-2012:​polycopie-2012c.pdf|here}} 
-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.+ 
 +  * 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}} 
 +   
 +\\ 
 + 
 +===== Exercises ===== 
 +\\ 
 +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 36: Line 38:
  
 \\ \\
-*/+===== **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**: {{:​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.**
  
-==== Exam ====+Please refer to the mail sent on December 13, with the rooms allocation by alphabetical order.
 \\ \\
-You are allowed to use an A4-age ​on which one can write anything on both sides. (You are not allowed ​to look at it using a magnifying glass!)+ 
 +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)
  
 \\ \\
-==== Homepage of the course in previous years ==== +==== Schedule: ​====
-[[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]]+
  
 +  * 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. ​