Design and Analysis of Algorithms (5 ECTS) 175311

The Course code: CIMET DAA

Course description

Aim and learning outcomes: Specification of the concept of algorithm and analysis of its computational complexity. Design principles of algorithms and their application to computing problems. Topics include theory of NP-completeness, analysis techniques, and the main design principles such as divide-and-conquer, dynamic programming, branch-and-bound. Heap data structure and advanced binary search trees are also studied. Approximation, randomized and optimization techniques are considered for finding suboptimal solutions to NP-complete problems.
On completion of this course the students will be able to:

• Design algorithms for difficult problems.
• Analyze and understand their complexity.
• Being able to implement the algorithms in practice

Topics to be taught

• Introduction to complexity theory. Why is complexity an important topic? What are the elements that influence the fact that a program solves in an acceptable mount of time a problem? How complexity is computed: recurrences, asymptotics.
• Greediness. Characterisation. Examples: minimum spanning trees, other graph algorithms
• Divide and conquer. Characterisation, complexity.
• Dynamic Programming: Optimal allocation of constrained resource, Optimal partition of data sequence, Shortest path in graph (including Trellis and directed acyclic graphs), Edit Distance algorithm;
• Organising the data once the best possible algorithm is found, what else can we do? We can aim to find an alternative representation of the data, in which case (but usually at a price) we can find new, faster algorithms.
• Proving that a problem is intractable: NP-hard problems. NP completeness, NP-hardness. Reduction techniques. Classes P and NP, polynomial certificate.
• Visiting different NP-complete problems. Giving different examples of reductions and therefore of NP-complete problems.

Lecture Materials

1. Introduction
   1. Introduction by A.Levitin (PDF Handouts)

2. Complexity Analysis
   1. Fundamentals of the Analysis of Algorithm Efficiency by A. Levitin, (PDF Handouts)
   2. Bascic of Algorithm Analysis by by J.Kleinberg and E.Tardos, (PDF Handouts)

3. Brute Force
   1. Brute Force by A. Levitin
      Closest Pair Problem, Traveling Salesperson Problem, Knapsack Problem, Independent Set Problem. (PDF handouts)

4. Divide-and-Conquer. Master Theorem 1.
   1. Divide-and-Conquer by J.Kleinberg and E.Tardos,
      Mergesort, Closest-Pair Problem, Integer Multiplication - Karatsuba's algorithm, Matrix Multiplication. (PDF handouts)
   2. Demo: Mergesort by J.Kleinberg and E.Tardos, (PDF handouts)
   3. Divide-and-Conquer by A.Levitin
      Mergesort, Closest-Pair Problem, Multiplication of Large Integers, Matrix Multiplication. (PDF handouts)

5. Decrease-and-Conquer. Master Theorem 2.
   1. Graphs by J.Kleinberg and E.Tardos,
      Basic Definitions and Applications; Graph Traversal: Breadth-First Search. (PDF handouts)
   2. Decrease-and-Conquer by A.Levitin
      Insertion Sort, Breadth-First-Search, Depth-First-Search. Exponentiation, Binary Search. (PDF handouts)

6. Transform-and-Conquer
   1. Introduction to Heapsort by T.Cormen, C. Leserson, R. Rivest and C. Stein. (PDF handouts)
      Heaps, Priority Queue.
   2. Transform-and-Conquer by A.Levitin
      Heapsort, Proprity Queues, Binary Search Tree,AVL Trees. (PDF handouts)

7. Greedy Technique
   1. "Greed is good, greed works, ..". :-)
   2. Greedy Algorithms 1 by J.Kleinberg and E.Tardos,
      0/1-Knapsack Problem, Fraction Knapsack Problem, Interval Scheduling, Shortest Paths: Dijkstra's algorithm, Change-Making Problem.
   3. Shortest Paths: Dijkstra's algorithm by J.Kleinberg and E.Tardos
      Shortest Paths: Dijkstra's algorithm
   4. Greedy algorithms 2 by J.Kleinberg and E.Tardos,
      Minimum Spanning Tree: Prim's MST algorithm, Kruskal's MST algorithm.

8. Dynamic Programming
   1. Dynamic Programming by J.Kleinberg and E.Tardos,
      Weigthted Interval Scheduling, Knapsack Problem. String Edit Distance.

   2. Dynamic Programming I, (PDF handouts)

9. NP and Computational Intractability
   1. Polynomial-Time Reductions by J.Kleinberg and E.Tardos.
      
   2. NP Complete algorithms by J.Kleinberg and E.Tardos.

10. Coping with limitation of algorithm power
    1. Coping with limitation of algorithm power by A.Levitin
       Backtracking, Branch-and-bound. Approximation algorithms. Approximation ratio. Approximation algorithms for TSP: Nearest-neighbour, Twice-around-the-tree, k-opt. Bin packing problem. Knapsack problem. Local search. Stochastic optimization: GA, ACO, PSO, etc.

Lectures

Teacher: Alexander Kolesnikov
Schedule: 32 h, starting from 08.09.2008, Monday
Monday 12-14 (D106)
Monday 16-18 (D106)
Tuesday 12-14 (D106)

Exercises

Teacher: Ville Hautamäki: Demos 5-7, (Juha Lehtonen: Demos 1-4)
Schedule: 16 h, starting from 12.09.2008
Friday: 10-12 (D106)
Friday: 12-14 (D106)

Please send solutions by (email firstname.lastname (at) cs.joensuu.fi) before Thursday, 24.00.

Exams

Intermediate exam: 29.09.2008, Monday, 12.00-14.00

Material of Lectures #1-8:

Complexity analysis, Master Theorems.
Exhaustive search approach. Exhaustive search approach for Independent Set Problem, Knapsack Problem, Travelling Salesperson Problem (TSP), etc.
Divide-and-Conquer algorithms. Decrease-and-Conquer algorithms. Transform-and-Conquer algorithms.
Examples of solutions with these algorithms: Integer numbers multiplication, Nearest-Pair Problem, exponentiation, etc.
Sorting algorithms: Mergesort, Quicksort, Heapsort, Selection Sort, Insertion Sort.
Heap structure, Priority Queues.
Graph representation: adjacency matrix, adjacency list; Graph traversing: Breadth-First-Search (BFS) tree, Depth-First-Search (DFS) tree.
Binary search trees: AVL-trees (construction, elements adding).
Greedy algorithms. Greedy algorithms for Time Scheduling Problem, 0-1 Knapsack and Fraction Knapsack Problems.

Final exam: 30.10.2008, Thursday, 08.00-10.00 (Room 106)

Material covered by Lectures #9-16

Greedy Algorithms: Coin-changing problem, Dijkstra algorithm for Shortest Path problem, Minimal Spanning Tree (MST) problem, Prim's and Kruskal's algorithms for MST, Variable-length codes, Shannon-Fano and Huffman codes.
Dynamic Programming algorithms: Weighted Time Scheduling problem, 0-1 Knapsack problem,
Shortest path in trellis graph, Shortest path in directed acyclic graph, Min-# polygonal approximation,
Allocation of constrained resourse, OPtimal investment problem,
Partition of data sequence, Min-eps polygonal approximation,
String edit distance (Dynamic Time Warping).
Polynomial-time reduction, Decision and search problems, Certificates, P versus NP, NP-completeness.
Backtracking, Branch-and-bound. Approximation algorithms. Approximation ratio. Approximation algorithms for TSP: Nearest-neighbour, Twice-around-the-tree. Bin packing problem.

General exam dates

Recommended literature

1. Jon Kleinberg and Eva Tardos , Algorithm Design, Pearson International Edition, 2006.
2. T. Cormen, C. Leiserson, and R. Rivest: Introduction to Algorithms , MIT Press, 2nd edition, 2001.
3. Levitin, The design and analysis of algorithm, Addison Wesley, 2007.

Preliminary knowledge

Sufficient knowledge of Data structures and algorithms, and Mathematics.