Page of Data Structures

Objetives and learning outcomes

The main goals of this course are related with the students’ understanding of complex and advanced data structures and algorithms and their use for solving classical and new computational problems. Students should understand:

- Advanced Data Structures such as balanced and unbalanced trees, directed and undirected graphs, sparse and dense graph representations, string processing.

- How to select the most appropriate data structures, given a practical problem.

- How to select the most appropriate algorithms for a given set of data structures.

- Mathematical techniques to analyse the spatial and algorithms’ temporal complexity.

Upon the conclusion of the course, students shall be able to:

- Explain the requirements of efficiency and performance for algorithms and data structures.

- Analyse the computational (spatial, temporal) complexity of programs.

- Implement programs using the algorithms and data structures studied.

Contents/Syllabus

Computational Complexity of Algorithms

1. Complexity analysis: Big-O

2. Amortized analysis

Abstract Data Structures

1. Simple linked lists

2. Stacks

3. Queues

4. Binary trees

5. Binary search trees

Balanced binary search tree

1. Binary insertion

2. Adelson-Velskii Landis (AVL)

3. Red-Black

Balanced search tree

1. 2-3 trees

2. Interval Tree

Priority queue (Heap)

1. Binary heap

2. Binomial heap

3. Fibonacci heap

Graphs

1. Types of Graphs

2. Data structures for graph representation

3. Graph search algorithms: Breadth First Search and Depth First Search

4. Graph problems: Minimum Spanning Tree, Shortest Path, Maximum Flow, and Optimal Matching Problems

Strings

1. String Sets

2. String sorting: Radix Sort

3. String searching: Binary Search

4. Exact sub string matching: Knuth-MorrisPratt and Boyer-Moore

5. Prefix Tree, Suffix Tree, and Suffix Arrays

Bibliography

"Algorithms in C, Parts 1-5 (Bundle): Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms". By Robert Sedgewick. Addison-Wesley Professional; 3rd Edition, 2001.

"Data Structures and Algorithm Analysis", Latest Edition (C++ Version). Clifford A. Shaffer, March 28, 2013. (free download in http://people.cs.vt.edu/~shaffer/Book/C++3elatest.pdf)

"Data Structures and Algorithm Analysis", Latest Edition (JAVA Version). Clifford A. Shaffer, March 28, 2013. (free download in http://people.cs.vt.edu/~shaffer/Book/JAVA3elatest.pdf)

"Data Structures in ANSI C". S. Sengupta, Academic, 1991.

"Mastering algorithms in C". Kyle Loudon, O'Reilly, 1999.

"Programs and Data Structures in C", 2nd edition. L. Ammeraal, John Wiley & Sons, 1996.

"Data Structures and Algorithm Analysis in C++", 2nd edition. Mark Allen Weiss, Addison-Wesley, 1999.

Evaluation

The evaluation is carried out by

- Two written tests (16 points - 8 points each)

- Two practical tests (4 points - 2 points each), in practical class

- Written test 1: April, 7; 6 pm

- Written test 2: Mai, 26; 6 pm

- Practical test 1: March, 24-27; practical class room

- Practical test 2: Mai, 05-08; practical class room