Algorithms and Data Structure
Keywords |
Classification |
Keyword |
OFICIAL |
Basic Sciences |
Instance: 2011/2012 - 1S
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).