Data Structures and Algorithms

Recommended Prerequisites

Algorithmics and resolution of problems, procedural programming, object oriented programming (very important), discrete structures  and complexity analysis (very important).

Teaching Methods

The learning process is supported on the following instruments: theoretical classes, theoretical-practical classes, lab, demonstrators of data structures and sorting, platform Mooshak.

Learning Outcomes

After conclusion of this unit, the student should exhibit knowledge and understanding on the following topics: complexity analysis; general techniques for algorithm design; data structures and sorting.

Application of knowledge and understanding: complexity analysis; understanding on the recursive nature of the various data structures and algorithms; comparative analysis.

Judgement and decision making: decision on data structures, sorting algorithms and algorithm design.

Communication skills: reinforcement on the competencies on written communication for elaboration of technical reports; oral communication of decisions in context.

Self-learning skills: self-learning and identification of credible sources.

Work Placement(s)

No

Syllabus

- Complexity analysis.

- Advanced techniques of algorithm design.

- Trees. AVL, VP, heaps, skip lists, B trees.

- Graph theory.

- Sorting algorithms: shell sort, merge sort, quick sort, radix sort, MSD, LSD.

- Hash tables.

- Selected topics (e.g. string matching).

Head Lecturer(s)

Pedro Manuel Henriques da Cunha Abreu

Assessment Methods

Assessment
Practical works : 40.0%
Written exam : 60.0%

Bibliography

** WEISS, Mark Allen. Data Structures and Problem Solving Using Java, 3nd Edition. Pearson, Addison Wesley, 2006.

** DROZDEK, Adam. Data Structures and Algorithms in C++. Thomson Learning Inc., 2005.

** SEDGEWICK, Robert. Algorithms in C: Parts 1-4, Fundamentals, Data Structures, Sorting, Searching. Addison Wesley, 1998.

** SEDGEWICK, Robert. Algorithms in C: Part 5, Graph Algorithms. Addison Wesley, 2002.

** CORMEN, Thomas H., Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford. Introduction to Algorithms, 2nd Edition. The MIT Press, 2001.