Algorithms

The basic topics are covered in the undergraduate course COMP 4039, Introduction to Data Structures and the more advanced topics are covered in the graduate course COMP 6785, Analysis of Algorithms.
Topics:

  • Basic notions of discrete mathematics: sets, functions, equivalence relations, recursive functions, trees, graphs, binary representation of integers and real numbers.
  • Asymptotic behavior of a function: O, Ω and Ө notation, asymptotic comparison of functions, solution of recursive functions by using induction or the Master Theorem. A proof of the Master Theorem is not required however the student should be able to apply the theorem.
  • Sorting: asymptotic analysis of the execution time of several sorting algorithms: Bubble sort, Merge sort, Heapsort, Quicksort. Lower bound of sorting algorithms based on comparisons.
  • Special sorting algorithms: Radix sort, Bucket sort y Linear sort. Order statistics
  • Analysis and implementation of elementary data structures: lists, queues, stacks, pointers.
  • Analysis, implementation and application of more advanced data structures: priority queues, disjoint sets, binary trees, search trees, balanced trees, Red-Black trees, AVL trees, interval trees,
  • Analysis of graph algorithms: breath first search, depth first search, connected components minimum spanning trees, Kruskal and Prim Algorithm, shortest paths algorithms.
  • Analysis and application of programming techniques: divide and conquer, greedy method and dynamic programming


Bibliography:

  • Introduction to Algorithms, T.H. Cormen, C.E. Leiserson and R.L. Rivest, MIT Press.
  • The Design and Analysis of Computer Algorithms, A.V. Aho, J.E. Hopcroft and J.D. Ullman, Addison-Wesley.
  • Computer Algorithms/C++, E. Horowitz and S. Sahni, Computer Science Press.
  • Algorithms and Data structures, N. Wirth, Prentice Hall.
  • The Art of Computer Programming, D. Knuth, Vol. 1-3, Addison-Wesley Professional.
  • Algorithms, R. Sedgewick, Addison-Wesley Pub, 2nd edition.
  • An Introduction to the Analysis of Algorithms, R. Sedgewick and P. Flajolet, Addison-Wesley Professional
  • Applied and Algorithmic Graph Theory, G. Chartrand and O.R. Oellermann , International Series in Pure and Applied Mathematics, McGraw-Hill, Inc.
Previous exams:

Fall-2008