|
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.
|
