Analyse algorithms for time and space bounds. Growth of functions. Asymptotic notation. Recurrences: substitution, iteration, master method. Review and analysis of data structures: stacks, queues, linked lists hash tables, binary search trees, graph, spanning trees. Review and analysis of sorting methods: insertion sort, merge sort, heapsort, quicksort. Algorithms design techniques. Brute force. Dynamic programming, Greedy algorithms. Divide-and-conquer algorithms. Graph algorithms. String matching algorithms. Approximation algorithms. Examples of problems which can be solved using each of these techniques.Write programs which employ any or all of these techniques.
|Final Examination - One 2-hour written paper||60%|