Degree in Audiovisual Engineering

Degree in Audiovisual Systems Engineering

Receive training with a University Degree and become a qualified Engineer in Audio visual Engineering, specialised in Audio and Image

Advanced Programming and Data Structure

Description
This subject’s main objective is to provide an advanced vision of algorithm programming, as well as diving deep into the most used data structures. The study of algorithm efficiency and diverse techniques and structures is worked on to the detail, with the goal of solving problems efficiently and elegantly. It’s important to have consolidated the “Programming methodology and technology” subject contents, such as descendant analysis, modularity, memory management, lineal data structures, pseudocode, the C programming language, etc. After understanding the concepts considered in this subject, the student acquires abilities to propose and discuss the adequacy of solutions to complex problems.
Type Subject
Optativa
Semester
Annual
Credits
8.00

Titular Professors

Previous Knowledge

Domain programming techniques worked on Methodology and Technology of Programming (analysis top-down, modularity, passing parameters and basic data structures).
Good knowledge of the language to be used for the exercises (Pseudo / C / Java).
Ability to follow and propose mathematical reasoning.

Objectives

After completing the course, students should be able to:
- Evaluate the efficiency of an algorithm by calculating the cost.
- Design a recursive algorithm.
- Transform a recursive algorithm in iterative.
- Justify the need for formal specification of algorithms.
- Explain the main mechanisms of formal referral and formal proof of simple recursive algorithms and to implement it in exercices.
- Make the specification of a function in terms of pre- and post-conditions.
- Implement an algorithm unambiguously from the same specification.
- Choose the resolution methods most suitable combinatorial problems in every situation.
- Implement methods Backtracking, Branch & Bound and Greedy adapted to each specific problem and seeking maximum efficiency and effectiveness.
- Formally specify any abstract data type using algebraic specification.
- Implement an abstract data type from its algebraic specification.
- Design and implement the most appropriate data structure for a particular application, given certain requirements of temporal and spatial efficiency.
- Implement binary trees, n-ary, AVL, 2-3, B and heaps. Also implement the various possible paths.
- Implement the tables exposed on the subject.
- Implement the variants of different graphs. Implement the shortest path search.

Contents

This subject’s contents are divided in two clearly separated parts:

• During the first semester the focus is on the specification, analysis, design and formal verification of algorithms. Their design comprises the solving of problems with the use of simple and multiple recursive techniques. This part also includes the study and application of techniques oriented to solve problems with a combinatorial space of solutions.

• The second semester is centered around the study of advanced lineal and non-lineal data structures, alongside their practical applications.

The studied techniques include theoretical and practical knowledge, abilities, experiences and critical thinking, all of which is based in solid, corroborated and well stablished theories and techniques.

Methodology

During the subject, the following methodologies will be used, by semester:

• First Semester:
o Lectures, for those contents that require them.
o Class problems and exercises, to consolidate knowledge.
o Evaluable exercises in class (CE) and practical work.
o Self-paced learning, for contents that won’t be evaluated directly.
o Flipped-classroom, to motivate personal learning and to support students.

• Second Semester:
o Project-Based Learning, where students will learn to design and implement data structures.
o Interspersed lectures to introduce necessary concepts, complemented during PBL.
o Self-paced learning, for contents that don’t fit in the project.

Evaluation

This is an annual subject, which means that its final grade is derived from two semester grades, as long as both are greater than or equal to 5. If a student fails either semester, the whole subject is considered to be failed with a grade of 4.

Final_Grade= 0.5 · S1_Grade + 0.5 · S2_Grade

First semester:

The first semester’s grade is obtained by weighting the knowledge and projects grades:

S1_Grade = 0.5 · S1_Knowledge_Grade + 0.5 · S1_Projects_Grade

Both grades must be greater than or equal o 5 in order to pass the semester. Otherwise, the final grade will be 4.

Knowledge

To obtain this grade, the final exam and continuous evaluation grades are weighted together, only if it benefits the student and the exam grade is greater than or equal to 3.5.

S1_Knowledge_Grade = max( 0.6 · S1_CE_Grade + 0.4 · S1_Exam_Grade,S1_Exam_Grade )

The midterm will be part of the continuous evaluation grade, with a specific weight of 30%. The rest will come from exercises done in class.

If the knowledge part of the semester is failed, a second call exam will be held in July. The continuous evaluation grade will not benefit the student, and a grade of 5 is required to pass.

Projects

This semester’s projects grade is calculated by weighting together the grades of the two projects that will be carried out in pairs. Students must pass both projects with a grade of 5 or higher. Otherwise, this grade will be 4.

S1_Projects_Grade= 0.4 · Project_1_Grade + 0.6 · Project_2_Grade

Validating the final exam

If a student meets the following requirements, they can opt to validate the first semester final exam, getting their continuous evaluation grade as the semester’s final grade. In particular, the student must:

Hand in all CE exercises, including the midterm, obtaining a weighted average grade greater than or equal to 7.
Deliver all first semester projects.
Assist classes regularly and show interest in the subject.

Students are free to give up this validation, opting to take the first semester exam, whether it’s during ordinary or extraordinary calls.

The specific mechanisms of validation, alongside how to submit a request, will be made public at the end of the semester, with some margin of time for those who end up having to study for the exam.

Second semester:

The second semester is almost exclusively based on the Project-Based Learning (PBL) mechanism, and therefore its final grade will be the project’s grade, which must be greater than or equal to 5 in order to pass:

S2_Grade =S2_Project_Grade

The second semester midterm will consist of an optional exercise that will only be able to improve the student’s grade.

If the subject’s team decides to do so, interviews for the project can be carried out to groups or individual students, in order to make sure that they have interiorized the semester’s contents. If the project is failed, there will be a second call delivery in July, as the following section explains.

Evaluation Criteria
Basic Bibliography

Brass, P. (2008). Advanced Data Structures. Cambridge University Press.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2014). Introduction to algorithms (3rd Edition). MIT Press.
Sedgewick, R., Wayne, K. (2011). Algorithms (4th Edition). Addison-Wesley Professional.
Skiena, S. S. (2012). The algorithm design manual (2nd Edition). Springer.

Additional Material