Data Structures and Algorithm (271063)

Learning Outcomes

The main objective of the course is to bind data structure definition as basis for software development, selecting the necessary algorithms appropriate to the problem context. In order to accomplish this, the student must be able to conceptualize the algorithms and apply them to specific cases. In this sense, the student is intended to:

  • Recognize the importance of defining data structures on software projects;
  • Relate the data handling algorithms with the working data structures;
  • Explain the main types of abstract data, in terms of behavior and representation;
  • Be aware to memory space usage required by data structures;
  • Acknowledge the details of algorithms execution in terms of speed and efficiency on data structures;
  • Know how to develop, search, import and adapt algorithms to software projects.

Study Program

I – Definition and differentiation of algorithms, data structures and programs

  • Algorithms;
  • Programs;
  • Data structures;
  • Usage and handling in Java.

II – Data types, allocation and handling in computers

  • Primitive data types;
  • Arrays;
  • Array lists;
  • Multidimensional lists;
  • Collections: interfaces, iterators, lists, list iterators, linked lists, views;
  • Usage and handling in Java.

III – Types of algorithms, philosophy, representations and performance

  • Algorithm classification;
  • Types of algorithms (simple recursive, backtracking, divide and conquer, greedy, branch and bound, brute force and random);
  • Algorithm performance interpretation applied to common examples (Fibonnaci’s sequence, travelling salesman, etc.)
  • Mathematical analysis of execution times of algorithms

IV – Bridging algorithms with the several programming languages

  • Pseudo-code relation with the Java language;
  • Correspondence between programming languages and machine code;
  • Compilation and interpretation process.

V – Advanced data structures

  • Stacks;
  • Queues, double queues;
  • Trees;
  • Binary trees;
  • Hash tables.

VI – Sorting and search on data structures

  • Insertionsort, Heapsort, Quickslect;
  • Shellsort, Mergesort, Quicksort, Bubblesort;
  • Binary search trees.

VI – String handling

  • String-related algorithms;
  • Sorting and search on Strings.

Bibliography

MAIN REFERENCES

Weiss, Mark Allen. (2012) Data Structures and Algorithm Analysis in Java. Pearson, 3th Edition.
Shaffer, Clifford. (2011) Data Structures and Algorithm Analysis. Dover Publications, 3th Edition.
Levitin, Anany. (2011) Introduction to The Design and Analysis of Algorithms. Pearson, 3th Edition.