Class Algorithms and Data Structures

Many programming projects involve solving complex computational problems, for which simplistic or naive solutions may not be efficient enough. The focus of this course is on how to design good algorithms, and how to analyze their correctness and efficiency. This is among the most basic aspects of good programming which has progressively become a major concern. This is therefore a particularly relevant CU for the the studies’ cycle.

CP1: Complexity, classes, typical functions and algorithm analisys;

CP2: Complexity and recursivity (set of recursive problems);

CP3: Sorting and selection algorithms;

CP4: Sorting algorithms: Insertion Sort, Selection Sort, Merge Sort and Quicksort;

CP5: Compare the complexity of sorting algorithms (Quicksort programming);

CP6: Abstract data types: Stack and Queue;

CP7: Circular arrays, simple lists and linked lists;

CP8: Implementing Queue and List (programming using arrays and lists);

CP9: Hash functions: open hashing and closed hashing;

CP10: Hash Tables (programming with Dictionaries and Sets);

CP11: Binary Tree, AVL trees and red-black trees;

CP12: Binary Tree (binary tree programming);

CP13: Basic notions of graphs: directed graph, undirected graph, labeled graphs, path and legth;

M1: Expository teaching: The presentation of theoretical concepts is done using slides. Short video tutorials developed on the key concepts of the discipline are available on FCCN's Educast channel of the CU.

M2: Active teaching: Theoretical concepts are demonstrated using "live coding".

M3: Experimental learning: Jupyter notebooks are used for immediate experimentation of the concepts taught.

M4: Participatory learning: During classes take place group discussions of weekly exercises and projects.

M5: Self-assessment: A platform for quizzes was developed to assess all knowledge, where a submitted solution is automatically validated.

M6: Project-oriented learning: Weekly exercises and projects are carried out autonomously with exploratory challenges of complementary aspects.

M7: Continuous assessment: weekly forms, quizzes, projects, mini-tests, and frequencies.

• Tamassia, Roberto, Goldwasser, Michael H., Goodrich, Michael  T. - Data Structures and Algorithms in Python. First Edition. USA: Wiley, 2013
• Cormen, Leiserson, Rivest e Stein - Algoritmos, Teoria e Prática, tradução da 3ª edição EUA, Elsevier Editora Ltd., 2012
• Cormen, Thomas H. - Algorithms Unlocked. Cambridge, Massachusetts: MIT Press, 2013.