Data Structures and Algorithms
Objectives:
This course surveys the most important algorithms and data structures in use on computers today. Particular emphasis is given to algorithms for sorting, searching, and string processing as well as graph algorithms. The course will concentrate on developing implementations, understanding their performance characteristics, and estimating their potential effectiveness in applications.
Skills:
Ability to analyze the performance of advanced data structures and algorithms. Ability to implement advanced data structures with Java an Object Oriented language. Ability to understand the usefulness of a data structure for a particular problem. Ability to adapt a data structure according to the requirements of a problem. Ability to combine data structures.
Prerequisites:
Graduates with IT background. Knowledge of fundamental data structures and Java programming language.
Content:
The Data Structures and Algorithms is one of the most important and historic disciplines of Computer Science, with continuous development providing solutions to fundamental problems of sorting, organizing, managing and searching information. While recent years have seen tremendous growth of the Internet to support a wide range of activities. The internet is promoted as a universal means support human activities. The provision and distribution of information on the Internet has led to the development of Networked Information Systems. Is of the utmost importance to effectively search this information and therefore the search algorithms for locating data in a large volume of information is fundamental. Also, graph algorithms allow us to address many of the difficult and important problems: Communication, circuit, mechanical, financial stock, transportation, internet, game, social relationship, neural network, protein, chemical compound. Finally, string algorithms face the problem of text matching, as the cases of: text editors, search word(s) in the contents of a website or a DNA sequence.
Contents
Symbol Tables Elementary symbol tables (sets, dictionary clients, indexing clients). Binary Search Trees. Balanced Search Trees. AVL. 2-3 tress, Red-Black Trees. B-Trees, Hash tables.
Graphs. Graph API. Components of a graph. Graph traversal (DFS, BFS), applications (Facebook, Kevin Bacon numbers, Fewest number of hops in a communication network).. Directed graphs (transportation, web, food, WordNet, scheduling, financial stock, cell phone,
infectious disease, game, citation, object graph, inheritance, control flow).
Strings: Sorting Strings (key-indexed counting, LSD string sort, MSD string sort, 3-way string quicksort, suffix arrays), String Symbol Tables, Substring Search (brute force, Knuth-Morris-Pratt, Boyer-Moore, Rabin-Karp), Pattern Matching (regular expressions, REs and NFAs, NFA simulation, NFA construction, applications).
Textbooks:
1. Robert Sedgewick, Kevin Wayne, Algorithms, 4th Edition, Addison-Wesley, 2011
2. T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms, MIT Press.
3. J. Kleinberg and E. Tardos, Algorithm Design, Pearson,2014.
4. Michael T. Goodrich and Roberto Tamassia, Data Structures and Algorithms in Java, Wiley
5. Mark Allen Weiss, Data Structures and Problem Solving Using Java (Fourth Edition), Addison-Wesley, 2010
6. Mark Allen Weiss, Data Structures and Algorithm Analysis in Java (Third Edition), Addison-Wesley, 2012
7. Kurt Mehlhorn, Peter Sanders, Algorithms and Data Structures: The Basic Toolbox, Springer Verlag, 2008
8. Selected papers on: Searching, Graphs, Strings algorithms
Assessment:
(50%) Homework assignments : (5) Programming exercises & (1) study & written presentation of a paper (1 assignment every 2 weeks)
(50%) Written Final examination
