Algorithms and Abstract Data Types

Scholar Year: 2019/2020 - 2S

Courses

Head Teacher Responsability Bruno Miguel Nunes da Silva Head

Weekly workload Hours/week T TP P PL L TC THE EL OT OT/PL TPL S Type of classes 3 2 Lectures Type Teacher Classes Hours Theorethical and Practical classes Totals 3 9,00 Bruno Silva   3,00 Filipa Ferrada   9,00 Prática Laboratorial Totals 1 2,00 João Capinha   4,00 Bruno Silva   2,00 Filipa Ferrada   2,00 Patrícia Macedo   8,00

Teaching language

Portuguese

Intended learning outcomes (Knowledges, skills and competencies to be developed by the students)

The student will obtain knowledge, skills and proficiency in:

- interpretation, analysis, specification and implementation of trivial computing algorithms, e.g., selection, search and sorting algorithms; iterative and recursive algorithms; when analysing an algorithm emphasis will be given to its temporal complexity.
- specification and manipulation of linear data structures (static and dynamic) and hash tables;
- comprehension, use and implementation of most commom abstract data types (collections) , e.g., Stack, Queue, List, Map;
- specification of new ADTs, choosing the appropriate data structure, its implementation and use;
- (in parallel) acquisition of proficiency in procedural programming, pointers and memory management.

Syllabus

1 – Algorithms, algorithmic complexity and algorithm formalization in pseudo-code;
2 – Pointers and memory management; passing arguments by reference in a function;
3 – Structs and modular programming in C;
4 – Search and selection algorithms;
5- Simple sorting algorithms O(n²) - Bubble Sort e Selection Sort;
6 – Iterative versus recursive algorithms;
7 – Complex sorting algorithms, e.g., O(n log n) - Quick Sort;
8 – Use of an ADT given its interface; creating test units to check an ADT implementation;
9 - Definition and manipulation of static, semi-static and dynamic linear data structures, i.e., arrays and linked lists;
10 – Specification and implementation of common ADT (collections), e.g, Stack, Queue, List and Map, using the lectured data structures;
11 – Hash tables data structure and its use in implementing the Map ADT.

Software

NetBeans + Plugin C/C++ + MinGW

Visual Studio Code

GCC

GDB

Make

Doxygen

Valgrind

Demonstration of the syllabus coherence with the UC intended learning outcomes

The syllabus is aligned with the curricular unit’s learning objetives and the order by which each topic is lectured guarantees a supported, cumulative and integrative knowledge acquisition process.

Teaching methodologies

The practical implementation of theoretical concepts draws upon the C programming language C. To do so, are taught the fundamental concepts of language, closely related to the operationalization of algorithms, data structures and abstract data types, which are discussed in the broader context of software development.


--- Distance Learning Methodology ---

- ** Students must adhere to synchronous sessions **. This makes it possible to maintain an adequate work pace in addition to some assessment elements taking place in those times.

### Organization of weekly topics in Moodle

- ** Note: ** the exercises included in the weekly laboratory refer to the set of subjects taught up to the TPs of the previous week.

### TP

- Elements made available in ** Moodle ** (component * asynchronous *):

  - ** Skills ** to be acquired;
  
  - ** Slides **;
  
    - They may contain bibliographic references to consult;
    
    - They may contain exemplary solved exercises.
    
  - ** Bibliography ** (may be separate or included in the slides)
  
  - Small ** video (s) ** that are needed to illustrate some concept - providing link (s);
  
  - ** Exercises ** - for autonomous resolution and not included in the slides;
  
      - Access to the exercises by answering (multiple choice) to some questions on the slides (not evaluated).
  
  - Existing forums:
  
    - ** Forum doubts ** about the weekly article;
    
    - ** Forum for sharing resolutions for proposed exercises **.


- ** Zoom meetings ** (component * synchronous *):

  - In the ** first TP ** the synchronous part takes place at the beginning of the slot.
  
    - Using a Kakoot! or Qustionário Moodle focusing on the material from the previous week and where the current week is framed and the skills to be acquired.
    
      - The results of the responses are analyzed and discussed synchronously with the students.
      
    - When it's ** question class ** week (answered in Moodle), this replaces Kahoot! / quiz.
    
    - Grades:
    
      - This organization gives time to solve the proposed exercises and read the respective bibliography;
  
  - In the ** second TP ** the synchronous part takes place at the end of the slot.
  
    - Doubts in the matter and / or in the interpretation of the proposed exercises.


### Lab

- Elements made available in ** Moodle ** (* asynchronous component *):

  - ** Statement made available at the beginning of the week ** (Monday at 8:00 am) in PDF;
  
    - Contains the expected result (output) of each level to be able to independently verify the correction of the obtained solution.
  
  - Group work is imposed in the preparation of laboratories, except in duly justified situations;
  
  - There is a * link * of submission for each laboratory class;
  
    - ** Single delivery time at the end of the week ** (Friday at 23:00) for all classes;
    
    - Use of the submission template provided in the "Distance Learning" area in Moodle.
    
      - The notes related to the submitted works will be shared continuously through Moodle (directly or indirectly).
      
  - Laboratory correction is made available (individually) and ** conditionally ** (after verification of both the following conditions): 1) at the end of the respective week, and; 2) after the student answers a short questionnaire about the laboratory.
  

- ** Zoom meetings ** (synchronous component);

  - ** Teacher available and online ** during class time;
  
  - Possibility of creating individual "rooms" for each group of students. It allows them to collaborate remotely between the group and the teacher can enter to follow up. Follow-up can be spontaneous or requested by the group.
   
  - All students must continue to participate in the session related to their SI enrollment class.

Demonstration of the teaching methodologies coherence with the curricular unit's intended learning outcomes

Teaching methodologies cover the transmission of knowledge (concepts and techniques), an immediate teacher-student feedback mechanism to assess the comprehension of concepts and techniques in the class environment (“active-learning”) and opportunities for the student to apply that knowledge in practice.

In TP classes knowledge is passed and is applied to simple problems, while in PL classes the student is asked to apply and integrate that knowledge to more complex problems.

Assessment methodologies and evidences

Elementos de avaliação:
- Questões Aula;
- Testes ou Exame;
- Laboratórios avaliados;
- Projeto;

- The exams will work the same way as we decide for the test.
- The evaluation of the ** TP ** and ** LAB ** components can be carried out in separate regimes.
- Plagiarism situations in any job will be referred to the competent bodies for disciplinary measures.

### To be continued

- ** There is no attendance requirement ** for access to continuous assessment;
 
- Final = 50% TP + 50% LAB (average> = 9.5)

    - TP (minimum grade: weighted average> = 9.5val):
    
        - ** 1 test ** (in person and / or remote; to be decided) - ** 55% ** (minimum score 8.5 points)
        
        - ** 3 class questions ** (synchronous in Moodle) - ** 15% ** each = 45%

    - Lab (minimum score: weighted average> = 9.5val):
    
        - Project (groups of 2 students) - 90% (minimum score 9val)
        
        - Best 6 out of 8 laboratories evaluated - 10%

- Regarding the ** test **, we are waiting for instructions on how to proceed in this chapter. This document will be updated with the new procedure in due course.)

### Non-continuous

- Final = 50% TP + 50% LAB (average> = 9.5)

    - TP (minimum grade:> = 9.5val):
    
        - ** 1 exam ** (face-to-face and / or remote; to be decided) - ** 100% ** (minimum score 9.5 points)
       
    - Lab (minimum score:> = 9.5val):
    
        - Project (groups of 2 students) - 100% (minimum score 9.5 points)

### Project

- The total score for ** Project ** is further sub-divided by:

Attendance system

Not applicable.

Assement and Attendance registers

Primary Bibliography