Design and Analysis of Algorithms, Fall'11 &nbsp;&nbsp;&nbsp;&nbsp; Tu,Fri 12-14, D122 (6.9-14.10), <a href="http://www.cs.helsinki.fi/u/polishch/">Valentin  Polishchuk</a> &nbsp;&nbsp;&nbsp;&nbsp; Exercises: We 16-18(D122), Fri 14-16(D123) (12.9.-14.10),  <a href="http://www.cs.helsinki.fi/u/jltsiren/index.shtml">Jouni Sirén</a>
<p>
Course code: <a href="https://www.cs.helsinki.fi/en/courses/582630%20">582630</a>. 4 credits. Subprogramme: Algorithms and machine learning. Level: Advanced studies.
<p>
Prerequisites: the course Data Structures or equivalent. <a href="http://www.cs.helsinki.fi/u/floreen/tira/k09/index.en.html">2009</a>, <a href="http://www.cs.helsinki.fi/u/mluukkai/tirak2010/english.html">Spring 2010</a>
<!--<p>
Final grade: Up to 6 points can be earned in exercise sessions, and up to 54 points -- on the exam. For a grade of 1 you need to get at least 30 pts. For a grade of 5 -- more than 50 pts.  &nbsp;&nbsp;&nbsp;&nbsp;  Exam: 20.10 16-19, CK112 and A111. One handwritten two-sided A4 cheat-sheet is allowed on the exam.
-->
<p><hr>
Description: General design principles of algorithms. Examples of central problems and typical solutions. Average case analysis. Amortised complexity. Recurrences. NP-completeness.
<p>
Course book: T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms, 3rd ed., MIT Press, 2009.
<p>
Additional material: <a href="http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/">DAA@MIT.OCW</a>, <a href="http://www.tug.org/texshowcase/cheat.pdf">TCS cheatsheet</a>
<!-- <hr><a href="quiz.pdf">Quiz</a> on prerequisites from 6.9. The Quiz is not graded. -->
<hr>
<p><a href="https://docs.google.com/present/edit?id=0Afs7PqOETk00ZGNuNnMyN21fOTQxZnFndHRuZnM&hl=en_US">Lectures</a>
<!-- ;&nbsp <a href="average_case.pdf">Lecture by the TA</a> -->
</p>
<hr>
<p>Problem set 1
<OL>
<LI>Solve the recurrence <em>T(n) = aT(n/b)</em> for <em>a,b>1</em>.</LI>
<LI>Find  u<sub>n</sub> if u<sub>0</sub>=6, u<sub>1</sub>=7, u<sub>2</sub>=15, u<sub>n+3</sub>=2u<sub>n+2</sub>+u<sub>n+1</sub>--2u<sub>n</sub>.
(NB: exact formula, not asymptotic.)</LI>
<LI>CLRS, 3rd ed.: 2.3-7* (don't let the asterisk scare you), 2-4, 4.2-6, 4.2-7.  The last two problems are 28.2-5, 28.2-6 in the 2nd ed.</LI>
<LI>Study Section 15.2 "Matrix-chain multiplication"</LI>
</OL>
<!-- <a href=solutions01.pdf>Solutions</a>-->
<hr>
<ul>
<li><a href="https://www.cs.helsinki.fi/webfm_send/89">Problem set 2</a> 
<!-- <a href=solutions02.pdf>Solutions</a> -->
</li>
<li><a href="https://www.cs.helsinki.fi/webfm_send/99">Problem set 3</a>. 
<!-- <a href=solutions03.pdf>Solutions</a>.-->
  &nbsp;<a style="margin: 0px; padding: 0px; color: rgb(39, 99, 140); text-decoration: none;" href="http://www.nada.kth.se/~viggo/problemlist/compendium.html">Compendium</a>&nbsp;of NP-complete problems. A sister&nbsp;<a style="margin: 0px; padding: 0px; color: rgb(39, 99, 140); text-decoration: none;" href="http://en.wikipedia.org/wiki/List_of_NP-complete_problems">page</a>&nbsp;at Wiki</li>
<li><a href="hw4.pdf">Problem set 4</a>. 
<!-- <a href="solutions04.pdf">Solutions</a>-->
</li>
<!--<li><a href="https://www.cs.helsinki.fi/webfm_send/113">Problem set 5</a></li>-->
</ul>
<hr>
<a href="feedback.txt">Summary</a> of the course feedback (in compliance with the department's <a href="http://www.cs.helsinki.fi/en/administration/processing-course-feedback">new course feedback process</a>)