Algorithms and Data Structures
Keywords |
Classification |
Keyword |
OFICIAL |
Programming |
Instance: 2009/2010 - 1S
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!