MC202: Data Structures

Since 2011.

Prerequisite:  MC102

Description:

Basic structures for information representation: lists, trees, graphs and their generalizations. Algorithms for construction, querying and manipulation of such structures. Development, implementation and tests of programs using such structures in specific applications.

Programme:

1.     Linked structures: node, pointer, pointer variable, memory dynamic allocation

2.     Singly linked list: basic operations

3.     Comparison of linked list with vectors

4.     General algorithms for singly linked lists: enumeration, inversion, copy, concatenation

5.     Stacks, queues and their applications (including elimination of recursion)

6.     Merge of lists and mergesort: informal analysis

7.     Variations: headed circular lists, headed doubly linked lists, free lists

8.     Sorting algorithms

9.     Binary trees: representation and traversal (recursive)

10.  Application: search trees (insertion and deletion)

11.  Balanced search binary trees

12.  Heap: implementation with array and heapsort

13.  General trees: definition, representation with lists, traversal

14.  Generalized lists and its use to represent linked structures in general

15.  B-trees and generalizations

16.  Introduction to hashing: concept, implementation with linked lists. Hashing techniques for files

17.  Graphs: concept, representations by matrices and linked lists

18.  Graph traversal in width and depth

19.  Implementation of data structures in disk

Recommended Literature:

      I.        A. V. Aho, J. E. Hopcroft, J. Ullmann. Data Structures and Algorithms. Addison-Wesley, 1983

     II.        W. Celes, R. Cerqueira, J. L. Rangel. Introdução a Estruturas de Dados. Campus, 2004

    III.        T. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Algoritmos - Teoria e Prática. Campus, 2002

   IV.        M. J. Folk and B. Zoellick. File Structures. Addison-Wesley, 1992

    V.        F. Lorenzi, P. N. de Mattos, T. P. de Carvalho. Estruturas de Dados. Thomson, 2007

   VI.        S. L. Pereira. Estruturas de Dados Fundamentais. Érica, 1996

  VII.        E. M. Reingold and W. J. Hanson, Data Structures. Little-Brown (1983)

 VIII.        R. Sedgewick, Algorithms in C. Addison-Wesley ,1990

   IX.        J. L. Szwarcfiter and L. Markenzon. Estruturas de Dados e Seus Algoritmos. Editora LTC (1994)

    X.        D. E. Knuth, The Art of Computer Programming, Vol I: Fundamental Algorithms. Addison-Wesley (1978)

   XI.        N. Wirth, Algorithms + Data Structures = Programs. Prentice-Hall (1976)

  XII.        A. M. Tenembaum. Estruturas de Dados Usando C. Makron Books, 1995

 XIII.        N. Ziviani. Projeto de Algoritmos. Thomson, 2004