Data Structures and Algorithms

Recommended Prerequisites

   Computer Programming

Teaching Methods

Lecture classes with detailed presentation of the topics of the syllabus using audiovisual means, including solving basic practical exercises that demonstrate their usefulness and exemplify their application to real cases.

Laboratory classes in which, with the guidance of the teacher, students solve practical exercises that require the application and combination of theoretical concepts taught in lecture classes, and promote creativity and critical thinking in the face of more complex programming problems

Learning Outcomes

This course aims to deepen the knowledge acquired in the Computer Programming course that precedes it. Besides consolidating basic programming skills, it is intended that the students acquire fundamental knowledge in object-oriented programming, dynamic data structures, and algorithms. They will be able to: use an object-oriented programming language to implement, test, and debug algorithms and data structures (especially linked lists, stacks, queues, and binary search trees), connected to those algorithms; identify typical applications of those data structures; analyze the complexity of algorithms; model programming problems and design data structures and algorithms that yield an efficient solution, based on knowledge about the main techniques for the design of algorithms

Work Placement(s)

No

Syllabus

1. Programming in C – revisions and consolidation
Variables
Flow control
Arrays and strings
Pointers
Files
Functions and parameter passing
Recursion
2. Object-oriented programming in C++
Classes, objects, attributes, and methods
Constructors and destructor
Pointers to objects
Operators overloading
Input/Output and Strings in C++
Static members
Friend functions and friend classes
Classes composition
Inheritance and polymorphism
Class templates
3. Dynamic data structures
Linked lists
Stacks and queues
Binary search trees – insertion, search, deletion, and balanced trees
4. Fundamental concepts of algorithms
Algorithmic efficiency – the big oh notation
Complexity analysis of sorting and search algorithms
Sorting of complex data structures using indexing arrays
Techniques for the design of algorithms
Practical examples of algorithms design – from problem abstraction to solution

Head Lecturer(s)

Rui Paulo Pinto da Rocha

Assessment Methods

Assessment
Laboratory work or Field work: 5.0%
Mini Tests: 15.0%
Project: 15.0%
Exam: 25.0%
Frequency: 40.0%

Bibliography

Langsam, Y., Augenstein, M.J., and Tenenbaum, A.M. (1996), “Data Structures Using C and C++”, 2nd edition, Pearson, ISBN: 978-0-13036-997-0.

Skiena, S.S. (2008), “The Algorithm Design Manual”, 2nd edition, Springer, ISBN: 978-1-84800-069-8.

Stroustrup, B. (2013), “The C++ Programming Language”, 4th edition, Addison-Wesley, ISBN: 978-0-32156-384-2.

Ellis, M., and Stroustrup, B. (1990), “The Annotated C++ Reference Manual”, Addison-Wesley, ISBN: 978-0-20151-459-9