Algorithms and Data Structures (11154)

Additional information: https://moodle.fct.unl.pt/course/view.php?name=AED1718

Introduction to the fundamental concepts of algorithm analysis and to the main data structures and algorithms, as essential tools to build efficient programs.

Two approaches are deeply encouraged: algorithms should be analysed before being implemented, and specifications (abstract data types) should be separated from their implementations (data structures).

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.

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.

Main References

Michael T. Goodrich and Roberto Tamassia. Data Structures and Algorithms in Java (5th edition). John Wiley & Sons, 2010.
Mark Allen Weiss. Data Structures and Algorithm Analysis in Java (2nd edition). Addison-Wesley, 2007.

Elementary Reference

Mark Allen Weiss. Data Structures and Problem Solving Using Java (4th edition). Addison-Wesley, 2010.

Advanced Reference

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

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.

	Hours per credit		28
	Hours per week	Weeks	Hours
Aulas prÃ¡ticas e laboratoriais			26.0
Aulas teÃ³ricas			42.0
AvaliaÃ§Ã£o			4.0
Self study			42.0
OrientaÃ§Ã£o tutorial			3.0
Project			130.0
Total hours			247
ECTS			9.0