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:36]
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, while some of the exercises are in English and some may be in French. The students are free to choose the final exam in either ​of English or French.+
  
-==== Prerequisites ==== +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.
-  * Some programming experience, in particular understanding recursive procedures and simple data structures such as arrays ​and linked lists. +
-  * Facility with mathematical proofs, especially proofs by mathematical induction. +
-  * Some mathematical background including graphs ​and trees, counting and probability,​ matrices, summation formulas, elementary calculus: If you are not familiar with some of these or have forgotten them, you can review them in the Appendix at the end of your course textbook mentioned bellow.+
  
-\\ +The course starts on September ​23rd and ends on December ​23rd, 2011.
-==== Schedule ==== +
-  * 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 ​==== +===== Course Materials =====
-The textbook for the course will be +
-  * Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein: Introduction to algorithms, Third Edition, MIT Press, 2009.+
  
 +  * 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 a subset of the topics covered in the course, the multi-volume book "Art of Computer Programming"​ by Donald E. Knuth provides interesting treatment. ​ 
  
-/* 
 ===== Exercises ===== ===== Exercises =====
 \\ \\
Line 46: 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. ​