Algorithms and Data Structures

Code:

EIC0013

Acronym:

AEDA

Keywords
Classification	Keyword
OFICIAL	Programming

Instance: 2009/2010 - 1S

Active?	Yes
Web Page:	http://paginas.fe.up.pt/~rossetti/rrwiki/doku.php?id=teaching:0910:aeda:start
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	134	Syllabus since 2009/2010	2	-	7	70	189

Teaching language

Suitable for English-speaking students

Objectives

1 - BACKGROUND
Following up former courses on Programming, this course unit (UC) relies on basic principles of data structures and algorithms as fundamental tools to devise solutions in a wide range of domains and problems.

2 - SPECIFIC AIMS
To rely on well-established notions of probramming and systematically use information structures and algorithms to solve different categories of problems. To use, as a supporting paradigm for programmes development, object-oriented approaches. To carry out small projects using the C++ language. To give emphasis to the organisation of programmes on the basis of abstract data types.

3 - PREVIOUS KNOWLEDGE
To increase the potential of success in this course unit, it is recommended that students had attended the following module:
EIC0012 - Programming

4 - PERCENT DISTRIBUTION
60% Theory: to introduce the various linear and non-linear data structures, as well as the main algorithms that are applied to those structures
40% Practice: laboratory hands-on practice, in which students are expected to do practical exercises on topics presented in theory classes

5 - LEARNING OUTCOMES
The learning outcomes expected in this course unit are to provide students with the ability to:
- analyse problems and identify adequate data structures and algorithms to solve them
- implement C++ programmes, using the object-oriented programming paradgim
- evaluate the efficiency (both temporal and spatial) for the devised solution
- document the implemented solution using UML

Program

1 - Object-oriented programming. Inheritance and polymorphism.

2 - Basics aspects of UML; the C++ programming language.

3 - Analysis of algorithms: classes and complexity.

4 - Searching and sorting algorithms.

5 - Abstract data types. Iterators.

6 - Linear data structures and their implementation: lists, stacks, and queues.

7 - Binary trees and related algorithms. Hash tables and related algorithms. Priority queues. 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 answer to a few theoretical problems. Groups of two students are expect to implement a small project throughout the course, on a theme that is suggested in the beginning of the term.

Software

Eclipse C++

keywords

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

Evaluation Type

Distributed evaluation without final exam

Assessment Components

Description	Type	Time (hours)	Weight (%)	End date
Attendance (estimated)	Participação presencial	65,00
Exercícios práticos e teóricos, realizado em computador com recurso ao sistema SIGEX	Exame	60,00		2010-01-08
Implementação em C++ de uma aplicação de pequena dimensaão, realizado em grupo de dois alunos ao longo do semestre	Trabalho escrito	54,00		2010-01-08
	Total:	-	0,00

Amount of time allocated to each course unit

Description	Type	Time (hours)	End date
Estudo da máteria ao longo do semestre, como preparação individual do estudante para estar apto a realizar as diversas componentes de avaliaçlão	Estudo autónomo	60	2010-01-08
	Total:	60,00

Eligibility for exams

Students must be subjected to all practical assessments (individually and in group), and must not exceed the number of absences allowed for lab classes.

Calculation formula of final grade

The assessment systems of this course unit comprises two components:
- individual component (IC) (60%)
- group component (GC), consisting of a group work by two students (40%)

The individual component is accomplished throughout the term in four distinct moments:
- each assessment moment consists of two parts, namely on theory and on practice, with same weights to the final mark
- the practice part is to be carried out on computers, with access to support material and will last no longer than 90 minutes
- the individual component mark is the arithmetic average of all four assessment moments

The group component encompasses an intermediate assessment moment (15%) and a final assessment moment (25%), each of which will account for the individual effort of the students to the group work.

The final grade (FG) is therefore calculated in the following way:
FG = IC*0,6 + GC*0,4

Where:
IC = arithmetic average of all four assessment moments of the individual component
GC = corresponding to the assessment of the group component

To be successful in this course, students should achieve a minimum of 35% in every assessment component: IC and GC.

Examinations or Special Assignments

Individual assessment is performed on computers, using the SIGEX platform.

Special assessment (TE, DA, ...)

Students registered under any special status:
- group assessment may be performed either in group or 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.
- should attend and perform the individual assessment components, as normally scheduled.

Classification improvement

Not applicable!