Algorithms and Data Structures

Objectives

Knowledge

1.The basics of algorithm analysis.

2.Fundamental abstract data types and data structures.

3.How the main data structures are used to solve real-world problems.

4.The fundamental algorithm design techniques, namely divide-and-conquer and memoization.

5.Several sorting algorithms, their features and application conditions.

Application

6.To calculate the running time and the space requirements of a polynomial or exponential time algorithm.

7.To model programs using abstract data types.

8.To choose, compare, adapt and use suitable data structures for a given problem.

9.To implement data structures, in particular, using dynamic memory allocation.

10.To implement recursive polynomial time algorithms.

Soft-Skills

11.To justify choices.

12.To do a programming project.

13.To evaluate solutions.

14.Time management

15.Writing communication: course project report.

16.Oral communication: course project assessment.

General characterization

Code

11154

Credits

9.0

Responsible teacher

Luís Manuel Marques da Costa Caires, Sofia Carmen Faria Maia Cavaco

Hours

Weekly - 5

Total - 71

Teaching language

Português

Prerequisites

Students should have completed the Introduction to Programming (Introdução à Programação) and the Object-Oriented Programming (Programação Orientada pelos Objectos) courses.

Students should:

  • have some knowledge of intermediate programming, including topics such as object-oriented programming and recursion;
  • be familiar with the Java programming language; and
  • have some background in discrete mathematics.

Bibliography

Main References

  • Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser. Data Structures and Algorithms in Java (6th edition). John Wiley & Sons, 2015.
  • Mark Allen Weiss. Data Structures and Algorithm Analysis in Java (4th edition). Addison-Wesley, 2013.

Advanced Reference

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms (3rd edition). The MIT Press, 2009.

Teaching method

The course consists of lectures and lab sessions. In the laboratory, students design, analyse and implement algorithms. Some lab sessions are dedicated to the programming project assessment.

Evaluation method

Any student involved in fraud, in any of the course components, will fail the course.

The course methodology consists of lectures and lab sessions. In the laboratory, students design, analyze and implement algorithms. Some lab sessions are dedicated project support.

 The programming project is developed in groups of 2 students. The project is developed in two phases, delivered in set dates. The project is compulsory for students which have not successfully acquired attendance credits and the successful development of the project provides attendance credits.

Written tests are solved individually.

Obtaining attendance credits: For students with no attendance credits, this will be given as a result of all project phases. If one of the project’s phases is not submitted for evaluation, the phase will be given the grade of 0 (zero). The global grade of the project must be equal or larger than 9.5, to be given attendance credits, and the project’s authorship must be confirmed orally.

 Evaluation:

- Combined grades of the project phases, which are worth 10%, and 20% respectively for the first, and second phases of the project’s final grade (NP);

- Combined grades of the 2 individual tests. The first test is worth 20% of the final grade and the second test 50% of the final grade (NT). 

- In the appeal season, the tests grade is replaced by the exam grade, which is worth 70% (NT) of the final grade.

- In order to be approved, NP and NT must be greater or equal to 9.5 points out of 20.

Subject matter

A.Algorithm Analysis

  • Running time and space requirements.
  • Analysis in the best-case, in the worst-case, and in the average-case.

B.Introduction to Recursion

  • Divide-and-conquer.
  • Memoization.

C.Abstract Data Types

  • Stack (LIFO).
  • Queue (FIFO).
  • List (access by position).
  • Dictionary (access by key): unordered and ordered.
  • Priority queue.

D.Data Structures

  • Circular arrays.
  • Singly and doubly linked lists.
  • Hash tables.
  • Generic trees.
  • Binary trees.
  • Binary search trees: trees without constraints; AVL trees.
  • Heaps.

E.Sorting Algorithms

  • Naïve algorithms: insertion sort; selection sort; bubble sort.
  • Efficient algorithms: heapsort; mergesort; quicksort.
  • Sorting without comparisons: bucket sort; radix sort.

Programs

Programs where the course is taught: