Algorithms and Data Structure

Code:

EBE0116

Acronym:

EDA

Keywords
Classification	Keyword
OFICIAL	Biomedical Engineering

Instance: 2013/2014 - 1S

Active?	Yes
Web Page:	http://moodle.fe.up.pt/1011/course/view.php?id=339
Responsible unit:	Department of Informatics Engineering
Course/CS Responsible:	Master in Bioengineering

Cycles of Study/Courses

Acronym	No. of Students	Study Plan	Curricular Years	Credits UCN	Credits ECTS	Contact hours	Total Time
MIB	23	Syllabus	3	-	6	70	162

Teaching language

Suitable for English-speaking students

Objectives

The main objectives of this course are:
1) to complement the knowledge on computer programming, acquired in a previous course, using the C language for program development;
2) to transmit fundamental concepts on data structures and the analysis and conception of algorithms. On completion of this course, the student should be able to: describe some aplications of the studied data structures; create /select data structures and algorithms to solve programming problems with low/medium complexity; compare alternative implementations of data structures / algorithms; apply the acquired knowledge for developing C programs, according to a project specification, using the most appropriate data structures and algorithms.

Learning outcomes and competences

The students who complete successfully this curricular unit must be able:
- to identify the main concepts of procedural and object oriented programming;
- to describe typical applications of the studied data structures and algorithms and to select / create data structures and algorithms to solve low/medium complexity problems;
- to solve programming problems using the C++ programming language and the abstractions from the C++ standard template library (STL), implementing their own data structures and algorithms whenever necessary.

Working method

Presencial

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

Attendance to the Introduction to Scientific Programming course, with approval, is recommended.

Program

INTRODUCTION TO C/C++
Fundamental data types and basic I/O.
Operators. Arithmetic and Boolean expressions.
Flow control structures: selection; repetition. S
tructured data types: arrays and C strings; STL vectors and C++ strings.
Pointers and dynamic memory allocation.
Functions: definition and declaration; local and global variables; parameter-passing mechanisms (call-by-value and call-by-reference) and return values; function overloading; templates. Recursive functions.
Streams: input/output using text files; stringstreams.
INTRODUCTION TO CLASSES AND DATA ABSTRACTION
Fundamental concepts. Classes and structs.
Encapsulation.
Data-members and function-members.
Constructors; constructors with parameters.
Template classes.
Introduction to the design of object-oriented code.
Relationships among classes; implementing associations. Introduction to UML.
STANDARD TEMPLATE LIBRARY
Containers: string, vector, list, map, set.
Iterators and algorithms.
CLASSES – ADDITIONAL CONCEPTS
Special qualifiers: const, static, friend.
Copy-constructors.
Destructors.
Operator overloading.
INHERITANCE AND POLYMORPHISM
Inheritance and polymorphism concepts.
Derived classes. Accessing base-class members.
Function overloading, function overriding (virtual functions) and templates.
Abstract classes. 
APPLICATION EXAMPLES (along the whole course)
Program conception using object oriented design.

Mandatory literature

Cay Horstmann, Timothy Budd; Big C++, Wiley, 2009. ISBN: ISBN 978-0-470-38328-5

Complementary Bibliography

Walter Savitch; Problem Solving with C++, Addison-Wesley, 2009. ISBN: ISBN-13: 9780321531346
H. M. Deitel, P. J. DeitelDeitel; C++ how to program. ISBN: 0-13-185757-6
Mark Allen Weiss; Data structures and algorithm analysis in C++. ISBN: 0-201-36122-1

Teaching methods and learning activities

- Theoretical-practical classes: will be based on the oral presentation of the themes, accompanied with problem solution and discussion, and the presentation of good programming practices.
- Practical classes: will be based on the development of computer programs, in C/C++, to solve the proposed exercises, and on the partial development of two programming projects. 
-Self-learning: study of the program subjects, using the bibliography and the material provided in the Web page of the curricular unit, resolution of exercises and development of the projects.

Software

Ambiente de desenvolvimento em C/C++ (Windows ou Linux)

Evaluation Type

Distributed evaluation with final exam

Assessment Components

Designation	Weight (%)
Exame	50,00
Trabalho laboratorial	50,00
Total:	100,00

Amount of time allocated to each course unit

Designation	Time (hours)
Estudo autónomo	35,00
Frequência das aulas	70,00
Trabalho laboratorial	57,00
Total:	162,00

Eligibility for exams

To attend the classes, as specified in the general rules, and to achieve a minimum grade of 40% in the distributed component. The distributed component (cDist) is given by: cDist = 0,5*cTP1 + 0,5*cTP2, where cTP1 e cTP2 = grade of two programming projects to be done out of class, during the semester.

Calculation formula of final grade

The final grade is given by: cFINAL = 0,5 * cDIST + 0.5 * cEXAM where cDIST and cEXAM represent, respectively, the distributed component grade and the exam grade. To complete the course, students have to achieve a minimum mark of 40% in both components.

Special assessment (TE, DA, ...)

Students with a special status will be assessed in the same way as ordinary students. They should to do all the projects and deliver them on the dates scheduled for regular students. Final exam is also mandatory.

Classification improvement

Students can only improve the mark of the distributed assessment component in the following year. Students can improve the mark of the written exam at the corresponding seasons (according to the rules).