Algorithms

LECTURES
The course covers the following topics

• Introduction: Algorithms description and analysis. Algorithm design methodology. Asymptotic notation. Growth of functions. Complexity analysis. Brief mathematical review.
• Search: Linear search. Binary search. Interpolation search. Fibonacci search.
• Sorting: Selection sort. Insertion sort. Bubble sort. Interpolation sort. Recursive sorting algorithms. Merge sort and merge. Quicksort and in-place quicksort. Linear time sorting (radix sort, bucket sort, etc.) Heap sort. Miximum, maximum and median finding. 
• Graphs: Introduction and definitions. Data structures for graphs. Graph traversal (Breadth First Search, Depth First Search). Topological sorting. Strongly connected components. Minimum spanning trees (Prim, Kruskal). Weighed graphs. Single source shortest paths (Bellman-Ford, Dijskstra). All-pairs shortest paths. Euler tour.
• Algorithmic techniques: Divide and conquer. Greedy algorithms (i.e. fractional knapsack). Dynamic programming (0-1 knapsack, matrix chain multiplications). Randomized algorithms (selection of topics).

 
PRACTICAL SESSIONS
The practical sessions include programming exercises based on the material covered in the lectures using the C programming language. The instructor evaluates the design, development and results of the programming exercises and gives quizzes for all students during the course of the semester. There are also take home mini projects on which the students are examined at the end of the semester.
 
TEXTBOOKS

• “Algorithm Design: Foundations, Analysis and Internet Examples”, Michael T. Goodrich, Roberto Tamassia, John Wiley and Sons Ltd, 2003, ISBN  9780471427568.
• "Introduction to Algorithms", Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, 3rd Edition, MIT 2009.
• “Algorithms in C”, R. Sedgewick, Addison-Wesley, ISBN 0-201-31452-5.