MC458 - Design and Analysis of Algorithms I

Programme:

    1. Review of concepts

       - Computational Models

       - Analysis of an algorithm

       - Cost analysis (time, space,  etc)

       - Lower bound of a problem

       - Examples: search in a sorted array, input/output

    2. Mathematical Tools for Analysis of Algorithms

       - Function Growing and Asymptotic Notation

       - Recurrence relations: asymptotic and exact solutions

 

    3. Design of algorithms by induction

       - Mathematical Induction and Design of algorithms by induction

       - Design by Simple and by Strong Induction

       - Design by Divide-and-Conquer

    4. Search, sorting and order statistics

       - Binary Search. Optional: Variations of Binary Search

       - Divide-and-conquer paradigm (mergesort, binary search, median)

       - Conquer may precede division (quicksort)

       - Average case analysis of quicksort

       - Computing the median and the k-th order statistics through quicksort partition

       - Linear worst-case algorithm for selecting the median and the k-th order statistics

       - Advantages of choosing a suitable data structure for the design of efficient algorithms

       - Lower bound for search in a sorted array, sorting, and median selection

       - Linear algorithms for sorting

   

 

5. Dynamic Programming

- Description of the method

- Applications of the method. Suggested examples:

- Matrix chain multiplication

- Longest Common Subsequence

     6. Greedy Algorithms

     - Description of the method

     - Applications of the method. Suggested de examples:

            - Activity-selection problem

            - Huffman codes