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
Maria Armanda Simenta Rodrigues Grueau
Hours
Weekly - 6
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 (3rd edition). Addison-Wesley, 2012.
Elementary Reference
- Mark Allen Weiss. Data Structures and Problem Solving Using 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 (detected immediately or afterwards, on the pratical project, tests, or examination) will fail the course.
Teaching consists of presenting the syllabus in lectures and solving problems in practical laboratory classes. In the lab, students design, analyze, and implement algorithms. Some practical classes are dedicated to support the development of the practical project.
The work is carried out individually or in groups of 2 students enrolled in the same lab class and is carried out in 2 phases, delivered on scheduled dates. The work is mandatory for students who do not hold "frequencia" and provides "frequencia" (attendance) . Attendance, as obtained in classes, is valid for one year.
Tests and exams are done without consultation, written, face-to-face and individual. No reference materials, no access to mobile phones or calculators are allowed.
To obtain Attendance: For students without attendance, this is attributed as a result of the submission of the two phases of the pratical assignment. If one of the phases is not submitted, it will be scored 0 (zero). The overall grade of the assignment (NP) calculated according to the formula presented below, must be greater than or equal to 10 to provide attendance and the authorship of the work must be proven in a face-to-face discussion.
Assessment rules:
- Combined grades of the two phases of the practical assignment, worth respectively 10% (P1) and 20% (P2) for the 1st and 2nd phases of the work (NP). The Laboratory evaluation component (NP) thus has the value of 30% on the final grade with the following formula
NP = (P1*0.1 + P2 * 0.2) / 0.3
NP will be rounded to the unit.
- Combined grades of 2 tests, the first being 20% of the final grade and the second 50% of the final grade (NT). Test scores are rounded to the tenth. The Theoretical-Practical (NT) component of assessment thus has the value of 70% on the final grade with the following formula
NT = (T1*0.2 + T2*0.5) / 0.7
NT will be rounded up to the unit.
- On appeal, the grade of the two tests is replaced by the exam grade, which is worth 70% (NT) of the final grade.
The student obtains approval if both NP and NT grades are greater than or equal to 10 values out of 20, according to the following formula
NF = NT * 0.7 + NP * 0.3
The final grade for students with attendance but who do not succeed (NT < 10) is NT.
NF = NT.
According to the FCT evaluation regulations, last year''s frequencies are valid.
Students who have been approved last year and who wish to improve their practical grade must notify the responsible professor until the delivery of the 1st phase of the assignment and must meet the delivery dates for the current academic year. For students who only intend to improve their theoretical-practical assessment, the formula applied is NF, using the pratical grade obtained in the previous year.
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.