Algorithms and Data Structures

Code:

EIC0013

Acronym:

AEDA

Keywords
Classification	Keyword
OFICIAL	Programming

Instance: 2010/2011 - 1S

Active?	Yes
Web Page:	http://arocha.liaccfeup.com/doku.php?id=shared:aeda2010
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	123	Syllabus since 2009/2010	2	-	7	70	189

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++.

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

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 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 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

Cute C++ Unit Testing Framework
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	70,00
	Trabalho escrito	60,00
	Exame	6,00
	Total:	-	0,00

Amount of time allocated to each course unit

Description	Type	Time (hours)	End date
	Estudo autónomo	50
	Total:	50,00

Eligibility for exams

Students must be subjected to all practical assessments (individually and in group).

Calculation formula of final grade

Final mark is computed up from two basic components: namely individual (CI) and in group (CG). CI consists of four individual tests, carried out on computers, with a practical programming part (using tests units) and a few theoretical problems. CG consists of a small project to be implemented in group. Final mark (NF) is given by:

CF = CI*0,6 + CG*0,4

Where CI is the average mark obtained with the four individual tests. Students should achieve a minimum success of 35% in every assessment component.

Examinations or Special Assignments

Individual assessment is performed on the SIGEX platform.

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

Not applicable!