Algorithms and Data Structures

Objectives

Upon completion of the course, students should be able to:
1. develop and implement A&DS and analyse them regarding correctness;
2. understand basic concepts in complexity theory;
3. analyse how efficient A&DS are based on different measures on efficiency, such as time and memory complexity;
4. write programs that use A&DS with help of good programming principles such as the specification of APIs and the use of tests that utilise A&DS;
5. solve problems through the use of DS such as linear lists, stacks, queues, hash tables, binary trees, heaps, binary search trees,and graphs, and write programs for the solutions;
6. solve problems by using algorithm design methods such as greedy algorithms, decomposition, dynamic programming, backtracking, and write programs for the solutions;
7. given a specific problem, either design the appropriate DS or create and algorithm that solves the problem or identify the problemas one that cannot be solved efficiently.

Program

1. Basic analysis: Introduction to Complexity; Asymptotic analysis of complexity; Standard notations. The Master theorem; The most common complexity classes; Empirical estimate of complexity; Complexity in time and memory; The use of recursion to analyse algorithms.Best, average and worst-case complexity.
2. Basic DS: lists, stacks, queues, hash tables, heaps, trees, graphs.
3. Strategies for algorithms and data abstraction.
Brute-force algorithms; Greedy algorithms; Decomposition algorithms; Backtracking; Heuristics
4. Basic algorithms: Simple numerical algorithms; Sequencial and binary search; Quadratic sorting (selection insertion, bubble); Sorting in O(N log N)(Quicksort, Heapsort, Mergesort); Hash tables; Binary search trees; Representations of graphs (adjacency lists and matrices); DFS,BFS, and PFS; Shortest path algorithms (Dijkstra and Floyd); Minimum spanning trees (Prim and Kruskal)

Teaching Methodologies

The teaching methodologies are intended to foster problem-based and project-based learning, reinforcing the practical component, active learning, autonomous work, and the student's responsibility. The evaluation model includes continuous evaluation elementsin the scope of active learning (lab assignments, on line quizzes) compatible with a significant reduction of the weight of evaluationby exams, amounting to 50% continuous evaluation / 50% non-continuous evaluation.

Bibliography

Main:
Algorithms in C, Parts 1-5 (Bundle): Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms", Robert Sedgewick, 2001, Addison-Wesley Professional

Other:

Brian W. Kernighan e Dennis M. Ritchie. The C Programming Language. 2ª edição. Prentice-Hall. ISBN-13: 978-0131103627.

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein. Introduction to Algoritms. 3ª edição. The MIT Press. 1999. ISBN-13: 978-0262533058