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 – revision

Variables

Flow control

Arrays and C-strings

Data structures

Pointers

Functions

Recursion

 

2. Procedural programming in C++

C++ Strings

Input/Output

Dynamic memory allocation

Files

Reference and returning a reference

Function overload

 

3. Fundamental concepts of algorithms and sort and search algorithms

Notion of algorithm

Algorithms’ efficiency – the Big O notation

Complexity analysis of sorting and search algorithms

Selection sort, bubble sort, insertion sort, quicksort

Sequential search and binary search

Sorting of complex data structures using indexing arrays

Techniques for the design of algorithms

Practical examples of algorithms design – from problem abstraction to solution

 

4. Object-oriented programming in C++

Classes, objects, attributes, and methods

Operators overloading

Static members

Friend functions and friend classes

Composition

Inheritance and polymorphism

Class

 

5. Dynamic data structures

Linked lists

Stacks and queues

Binary search trees.

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.