Algorithms and Data Structure

Code:

EBE0116

Acronym:

EDA

Keywords
Classification	Keyword
OFICIAL	Basic Sciences

Instance: 2011/2012 - 1S

Active?	Yes
Web Page:	http://moodle.fe.up.pt/1011/course/view.php?id=339
E-learning page:	http://moodle.fe.up.pt/
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	28	Syllabus	3	-	6	56	162

Teaching language

Portuguese

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 conception and analysis 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.

Program

Introduction to the C programming language
- program structure;
- simple data types and their representation; operators and expressions;
- data input and output;
- execution flow control; conditional and repetition statements;
- arrays, strings and structs, and their representation;
- pointers; dynamic memory allocation;
- functions; passing parameters and obtaining results; recursive functions;
- files;
- some advanced topics.

Data structures and algorithms
- Fundamental data structures:
-- lists, queues and stacks;
-- trees;
-- graphs.
- Fundamental algorithmics concepts:
-- algorithm analysis (efficiency and correction).
- Algorithm design techniques:
-- divide and conquer;
-- greedy algorithms;
-- dynamic programming;
-- backtracking algorithms;
- Application examples:
-- sorting and searching algorithms;
-- string searching;
-- decision trees;
-- and others.

Mandatory literature

Paul J. Deitel, Harvey M. Deitel; C: How to Program, 6/E, Prentice-Hall, 2009. ISBN: 0136123562
Anany Levitin; Introduction to the design & analysis of algorithms. ISBN: 0-321-36413-9

Complementary Bibliography

Brian W. Kernighan, Dennis M. Ritchie; C. ISBN: 85-7001-327-2
Luís Damas; Linguagem C. ISBN: 972-722-156-4
Marque de Sá; Fundamentos de programação usando C. ISBN: 972-722-475-X

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, to solve the proposed exercises.
Out of class work:
development of small programming projects, envolving the studied themes.

Software

Microsoft Visual Studio

Evaluation Type

Distributed evaluation with final exam

Assessment Components

Description	Type	Time (hours)	Weight (%)	End date
Attendance (estimated)	Participação presencial	56,00
Problem resolution	Teste	28,00		2011-12-16
Projects	Defesa pública de dissertação, de relatório de projeto ou estágio, ou de tese	30,00		2011-12-16
Exams / Mini-test	Exame	3,00		2012-02-10
	Total:	-	0,00

Amount of time allocated to each course unit

Description	Type	Time (hours)	End date
Theory	Estudo autónomo	28	2011-12-16
Exam preparation	Estudo autónomo	16	2012-02-10
	Total:	44,00

Eligibility for exams

To be admitted to exams students have to attend to 75% of the classes and have to achieve a minimum grade of 40% in the distributed component.
The distributed component (cDist) is given by:
cDist = 0,4*cMT + 0,2*cTP1 + 0,4*cTP2
where
cMT = grade of a mini-test, to be done by the middle of the semester, on the C programming language
cTP1 e cTP2 = grade of two practical assignments 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 have to do the mini-test and all the assignments, delivering these last on the scheduled dates.

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