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
João Miguel da Costa Magalhães, Luís Manuel Marques da Costa Caires
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 and Roberto Tamassia. 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 three 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 the three 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, 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%, 10% and 20% respectively for the first, second and third 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 40% of the final grade (NT).
- In the appeal season, the tests grade is replaced by the exam grade, which is worth 60% (NT) of the final grade.
A student is approved if both NP and NT (rounded to units) are greater or equal to 9 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.