2015.2

Lecture 01. Administrative informations; introduction; concepts: computation problems, program analysis. Friday July 31st, 2015. Lecture 02. Program complexity: an introduction; complexity functions; asymptotic behaviour. Monday August 3rd, 2015. Lecture 03. Program complexity: best case, worst case, average case. Introduction to amortized analysis. Wednesday August 5th, 2015. Lecture 04. Program complexity: notation for asymptotic behaviour analysis. Monday August 10th, 2015. Lecture 05. Program complexity: analysis of iterative algorithms. Wednesday August 12th, 2015. Lecture 06. Program complexity: analysis of recursive algorithm. Master Theorem. Friday August 14th, 2015. Lecture 07. Algorithms: linear search, binary search. Monday August 17th, 2015. Lecture 08. Algorithms: insertion sort. Wednesday August 19th, 2015. Lecture 09. Algorithms: merge sort. Monday August 24th, 2015. Lecture 10. Algorithms: heap sort. Wednesday August 26th, 2015. Lecture 11. Algorithms: quick sort. Friday August 28th, 2015. Lecture 12. Algorithms: the complexity of sorting, sorting in linear time. Wednesday September 9th, 2015. Lecture 13. Basic data structures: stacks, queues and deques. Friday September 11th, 2015. Lecture 14. Linked lists. Monday September 14th, 2015. Lecture 15. Hash tables. Wednesday September 16th, 2015. Lecture 16. Binary search trees. Monday September 21st, 2015. Lecture 17. AVL trees. Wednesday September 23rd, 2015. Lecture 18. Red-black trees. Friday September 25th, 2015. Lecture 19. B trees. Monday September 28th, 2015. Lecture 20. Union-find data structures. Wednesday September 30th, 2015. Lecture 21. Amortized analysis. Monday October 5th, 2015. Lecture 22. Splay trees. Wednesday October 7th, 2015. Lecture 23. Extending data structures. Friday October 9th, 2015. Lecture 24. Graphs: definition. Computational representation. Breadth-first search and depth-first search. Wednesday October 21st, 2015 - Friday October 23rd, 2015. Lecture 25. Topological search; strongly connected components. Friday October 23rd, 2015 - Monday October 26th, 2015. Lecture 26. Minimum spanning trees: Prim's algorithm, Kruskal's algorithm. Monday October 26th, 2015. Lecture 27. Single-source shortest paths: Dijkstra's algorithm, Bellman-Ford's algorithm. Wednesday October 28th, 2015. Lecture 28. Dynamic programming. Wednesday November 4th, 2015. Lecture 29. Greedy algorithms. Monday November 9th, 2015. Lecture 30. Introduction to NP-completeness. Wednesday November 11th, 2015.