CCO - 510 - Estruturas de Dados (Data Structures)

Quantidade de créditos: 8
Total de horas de aulas teóricas: 60
Total de horas de aulas de exercícios, seminários ou estudos dirigidos : 60

Objetivo

Tornar os estudantes aptos a utilizar técnicas básicas de programação em seus projetos; capacitar os estudantes a reconhecer, implementar e modificar algoritmos e estruturas de dados básicos; familiarizar os estudantes com noções de projeto e análise de algoritmos, através do estudo de uma linguagem algorítmica, exemplos e exercícios práticos; estimular os estudantes a avaliar quais técnicas de programação, algoritmos e estruturas de dados se adequam melhor a cada situação, problema ou aplicação.

Ementa

  • Introdução à recursão, com algoritmos e aplicações.
  • Visão intuitiva sobre análise de correção (invariantes) e eficiência (complexidade) de algoritmos.
  • Apresentação de busca linear e binária. Apresentação de algoritmos de ordenação elementares (insertion sort, selection sort e bubble sort).
  • Apresentação de programação por retrocesso (backtracking) e enumeração.
  • Noções de tipos abstratos de dados.
  • Detalhamento de estruturas de dados como: listas (alocação estática e dinâmica, circulares, duplamente ligadas e com nó cabeça), matrizes e listas ortogonais, pilhas e filas (alocação sequencial e ligada) com aplicações.
  • Detalhamento de árvores (definição, representação e propriedades), árvores binárias (manipulação e percursos) e árvores de busca (operações de busca, inserção e remoção).
  • Apresentação de filas de prioridade com detalhamento das implementações triviais e com heap (alocação ligada e sequencial).
  • Apresentação de exemplos e exercícios práticos, os quais podem envolver estruturas de dados compostas (como vetores de listas ligadas) e diferentes abordagens algorítmicas (gulosa, divisão e conquista, programação dinâmica, backtracking, busca em largura, etc).

Bibliografia Principal

  1. FEOFILOFF. P. Algoritmos em Linguagem C, Elsevier, 2009.
  2. AARON M.; TENENBAUM, Y. L.; AUGENSTEIN, M. J. Estruturas de dados usando C. São Paulo: Pearson Makron Books, 2009.
  3. FERRARI, R., RIBEIRO, M. X., DIAS, R. L., FALVO, M. Estruturas de Dados com Jogos. Rio de Janeiro – Elsevier, 2014.

Bibliografia Complmentar

  1. SEDGEWICK, R. Algorithms in C++, Parts 1-4: fundamentals, data structures, sorting, searching. 3rd. ed., Boston: Addison - Wesley, 1998.
  2. SEDGEWICK, R. Algorithms in C++, Part 5: graph algorithms. 3rd. ed., Boston: Addison Wesley, 2001.
  3. ZIVIANI, N. Projetos de algoritmos: com implementações em Pascal e C. 3. ed. rev. e ampl. São Paulo: Cengage Learning, 2012.
  4. ROBERTS, E.S. Programming Abstractions in C: a Second Course in Computer Science, Addison-Wesley, 1997.
  5. CIFERRI, R.R. Programação de Computadores, Edufscar, 2009.

Objective

Enable students to use basic programming techniques in their projects. Train students to recognize, implement, and modify basic algorithms and data structures. Familiarize students with concepts of algorithm design and analysis through the study of an algorithmic language, examples, and practical exercises. Encourage students to evaluate which programming techniques, algorithms, and data structures are best suited to each situation, problem, or application.

Catalog Description

  • Introduction to recursion, including algorithms and applications.
  • An intuitive view of correctness analysis (invariants) and efficiency analysis (complexity) of algorithms.
  • Presentation of linear and binary search. Presentation of elementary sorting algorithms (insertion sort, selection sort, and bubble sort).
  • Introduction to backtracking programming and enumeration.
  • Basic notions of abstract data types.
  • Detailed study of data structures such as lists (static and dynamic allocation, circular lists, doubly linked lists, and lists with a head node), matrices and orthogonal lists, stacks and queues (sequential and linked allocation) with applications.
  • Detailed study of trees (definition, representation, and properties), binary trees (manipulation and traversals), and search trees (search, insertion, and removal operations).
  • Presentation of priority queues, including details of trivial implementations and heap-based implementations (linked and sequential allocation).
  • Presentation of examples and practical exercises, which may involve composite data structures (such as arrays of linked lists) and different algorithmic approaches (greedy, divide and conquer, dynamic programming, backtracking, breadth-first search, etc.).

Main Bibliography

  1. FEOFILOFF. P. Algoritmos em Linguagem C, Elsevier, 2009.
  2. AARON M.; TENENBAUM, Y. L.; AUGENSTEIN, M. J. Estruturas de dados usando C. São Paulo: Pearson Makron Books, 2009.
  3. FERRARI, R., RIBEIRO, M. X., DIAS, R. L., FALVO, M. Estruturas de Dados com Jogos. Rio de Janeiro – Elsevier, 2014.

Complementary Bibliography

  1. SEDGEWICK, R. Algorithms in C++, Parts 1-4: fundamentals, data structures, sorting, searching. 3rd. ed., Boston: Addison - Wesley, 1998.
  2. SEDGEWICK, R. Algorithms in C++, Part 5: graph algorithms. 3rd. ed., Boston: Addison Wesley, 2001.
  3. ZIVIANI, N. Projetos de algoritmos: com implementações em Pascal e C. 3. ed. rev. e ampl. São Paulo: Cengage Learning, 2012.
  4. ROBERTS, E.S. Programming Abstractions in C: a Second Course in Computer Science, Addison-Wesley, 1997.
  5. CIFERRI, R.R. Programação de Computadores, Edufscar, 2009.