Algorithms and Data Structures

Code:

EIC0013

Acronym:

AEDA

Keywords
Classification	Keyword
OFICIAL	Programming

Instance: 2020/2021 - 1S

Active?	Yes
Responsible unit:	Department of Informatics Engineering
Course/CS Responsible:	Master in Informatics and Computing Engineering

Cycles of Study/Courses

Acronym	No. of Students	Study Plan	Curricular Years	Credits UCN	Credits ECTS	Contact hours	Total Time
MIEIC	174	Syllabus since 2009/2010	2	-	7,5	70	202,5

Teaching language

Portuguese

Objectives

Following up the former course on Programming, with this unit we intend: to use notions already acquired and systematically apply data structures and algorithms to solve certain categories of problems; to use object-oriented programming; give emphasis to the organisation of programs on the basis of abstract data types. Practice is to be achieved with exercises and implementation of a small project in C++.

Learning outcomes and competences

At the end of this unit course, students should: model problems following the object-oriented paradigm; solve problems using abstract data types and simple data structures (linear and non linear)

Working method

Presencial

Pre-requirements (prior knowledge) and co-requirements (common knowledge)

Student should have basic knowledge of programming and C++.

Program

Object-oriented programming. Inheritance and polymorphism. Basics of UML. C++ programming language. Analysis of algorithms: classes and complexity. Searching and sorting algorithms. Abstract data types. Iterators. Linear data structures and their implementation: lists, stacks, and queues. Binary trees, Binary search trees and related algorithms. Hash tables and related algorithms. Priority queues. Disjoint Sets. Balanced binary trees: AVL and Splay trees. Examples.

Mandatory literature

Weiss, Mark Allen; Data structures and algorithm analysis in C++. ISBN: 0-201-36122-1
Sedgewick, Robert; Algorithms in C++. ISBN: 0-201-35088-2

Complementary Bibliography

Deitel, H. M.; C++ how to program. ISBN: 0-13-185757-6
Stroustrup, Bjarne; The C++ programming language. ISBN: 0-201-88954-4
Koenig, Andrew; Accelerated C++. ISBN: 0-201-70353-X
Cormen, Thomas H.; Introduction to algorithms

Teaching methods and learning activities

Formal concepts, definitions and related issues are presented, exemplified and discussed in theoretical classes. Practical classes are carried out in computer labs, where students must implement programming exercises in C++. Practical assessments are carried out throughout the term, whose schedule and format is made available in advance. Students are then expected to implement small programs and and answer to a few theoretical problems. Groups of two or three students are expect to implement a small project throughout the course, on a theme that is suggested in the beginning of the course.

Software

Doxygen: Documentation system for C++
Google Tests: unit testing
CLion: a cross-platform IDE for C++

keywords

Physical sciences > Computer science > Programming
Physical sciences > Mathematics > Algorithms

Evaluation Type

Distributed evaluation without final exam

Assessment Components

Designation	Weight (%)
Teste	60,00
Trabalho laboratorial	40,00
Total:	100,00

Amount of time allocated to each course unit

Designation	Time (hours)
Elaboração de projeto	60,00
Estudo autónomo	48,00
Frequência das aulas	70,00
Trabalho laboratorial	10,00
Total:	188,00

Eligibility for exams

Student may not exceed the limit of absences.

Calculation formula of final grade

Final mark is computed up from:

CIP = practical on computer evaluation, individual programming assignments using tests units (average of two evaluation moments)

CIT = theory evaluation, multiple-choice questions to be answered on an individual basis in Moodle

CG = two small projects (GC1 and GC2) to be implemented in group (of 2 or 3 students), of equal weight; these evaluation considers both commitment and attendance of student in group work.

Final mark (F) is given by: F = 30% CIP + 30% CIT + 40% CG


Observations:

1. A minimum mark of 40% is required in every assessment component (CIP, CIT, CG1, CG2)

2. There will be a recovery test for students that did not obtain the minimum required in the component CIP or CIT. The grade of this test is limited to 50%.

Examinations or Special Assignments

Special Assignments include two components (EC and PC):

• Exam Component (EC) (60%), duration 2h30m, includes:
• a practical programming part using tests units, performed on the SIGEX platform (PEC)
• a few theoretical problems (TEC)
• Practical Work Component (PC) (40%), a small project to be implemented and presented in the day of the exam. Students should contact the professor for the practical work assignment.

Final mark (N) is given by: N = EC*0,6 + PC*0,4.

Students should achieve a minimum success of 40% in every assessment component (PEC, TEC, PC).

Special assessment (TE, DA, ...)

Students registered under any special status:

• should attend and perform the individual assessment components, as normally scheduled
• group assessment may be performed individually and the student must talk to the lecturer to make all the arrangements and fix a reasonable schedule to be assessed with this regard.

Classification improvement

Students may improve their grades in the next course term.