Subject: Data Structures and Algorithms

Scientific Area:

Computing

Workload:

80 Hours

Number of ECTS:

7,5 ECTS

Language:

Portuguese

Overall objectives:

1 - Enhance the knowledge and skills of programming, using the C++ language as a vehicle for implementing.
2 - Dynamic memory allocation and construction and manipulation of dynamic structures.
3 - Study of some useful forms of data organization and main algorithms associated.
4 - Study of algorithms for sorting and analysis of its efficiency.

Syllabus:

1 - Introduction to C++ programming language.
2 - Data types in C++. Dynamic memory allocation and construction and manipulation of dynamic structures. Abstract data types and their implementations (using sequential and linked representations on arrays, and several dynamic representations, using "pointers").
3 - Study and manipulation of structures arborescent. Trees, n-trees and binary trees: formal characterization and diverse implementations. Search trees, balanced trees and trees of Bayer: algorithms (iterative and recursive) for search, insertion and cancellation on such structures.
4 - Hashing tables and associated search, insertion and cancellation algorithms.
5 - Graphs: their representation and study of some associated algorithms.
6 - Introduction to the study of the efficiency of algorithms. Array sorting algorithms: elementary and advanced (Shellsort, Heapsort, Quicksort and binary merge). Sorting by dispersion. Combination of methods of ordination. Algorithms for sorting files.

Literature/Sources:

T.H. Cormen, C.E. Leiserson, R.L. Rivest & C. Stein , 2001 , Introduction to Algorithms , The MIT Press,
Sedgewick, R. , 1998 , Algorithms in C, Parts 1-4 ( Fundamental Algorithms, Data Structures, Sorting, Searching) , Addison-Wesley, 3rd edition
Sedgewick, R , 2002 , Algorithms in C, Part 5 ( Graph Algorithms) , Addison-Wesley, 3rd edition

Assesssment methods and criteria:

Classification Type: Quantitativa (0-20)

Evaluation Methodology:
The evaluation is based in the following mandatory elements Theoretical - Theoretical/Pratical Evaluation 70% - 2 Exams (35% + 35%), minimum grade of 9.0. possibility of recovering each exam in the recurso season Programming evaluation (groups of 4 elements) 30% of the class grade, minimum grade of 8.0 2 mandatory deliverables (minimum grade for each deliverable), with presentation/discussion with all the group elements Failing to meet the minimum grade results in failing the class Notes: The programming evaluation minimum grade is not subject to rounding. The appeal exam is divided into 2 halfs, the content of each half is related to the content of the 2 normal season exam. Students can opt to perform one or both halfs. Only the final grade is rounded to integer.