Data Structures and Algorithms (21417)
Degree/study: Bachelor's degree in Computer Sciences (3377)
Year: 2nd
Term: 1st
Number of ECTS credits: 4 credits
Hours of studi dedication: 100 hours
Teaching language or languages: catalan
Teaching Staff: Narcís Parés
1. Presentation of the subject
Data Structures and Algorithms is one of subjects in the programming languages' area, along with Programming Fundamentals (1st year, during the 2nd and 3rd quarters) and Object Oriented Programming (2nd year, during the 1st quarter and in parallel with our subject). While these last two subjects are common to the three degrees (Computer Science Engineering, Telematics Engineering and Audiovisual Systems Engineering), our course is a specialization for Computer Engineering only. Thus, the first objective of this subject is that students start thinking as problem analysts and not just programmers. However, the capabilities and skills of data structures programming and abstract data types are important in this subject.
To take this course, students are supposed to have acquired basic knowledge and skills in the first-year course of Programming Fundamentals. After the two quarters of this subject, students will have mastered basic techniques and elemental programming structures as well as flow control structures. In Data Structures and Algorithms we will study it in depth, concentrating ourselves on ways of structuring information used in a program, how to manage this information and how to get it so that there are no collateral effects on rest of the program. We will also study how to evaluate their implementation both in respect to optimal use of memory space and to runtime operations and algorithms with which data are managed.
This course is devoted to the following basic structures: Linear Structures, Tree Structures and Associative Structures, which will be programmed in the C language, which students already know from the Programming Fundamentals Course. In addition, the course will specially promote the ability to analyze a problem from the standpoint of the information used and managed in a program, and how to design and program the best solution in terms of data structures and management operations. Student learning is much aimed at solving problems that present the closest possible scenarios in real cases.
Learning activities are structured in the following way:
• Lectures: teachers present a series of concepts and techniques as well as some examples. Students need to revise their notes on the course after it so that they become acquainted with what they learn.
• Seminar Sessions: in small groups, students will solve exercises that help consolidating the theoretical concepts and which link them to the practical work. Students will work individually and during class time. These exercises will be supervised by the teachers who will solve any questions that may arise and help students in this consolidation process.
• Practical Sessions: in teams of three people, students will be confronted to practical aspects related to the solution of the course's problems. They will basically train their data structures programming and operations management abilities. However, they will have to be able to analyse these aspects in the best way. Students will start these exercises during the practical session but, since they are demanding, they will have to finish them after it.
• Self-Evaluation Exercises: these exercises can be found in a list on the Aula Global so that students can do them outside class and keep track of their learning progress.
2. Prerequisites to follow this course
Students are supposed to have acquired basic knowledge and skills in the first-year course of Programming Fundamentals (2nd and 3rd quarter of the 1st year). Essentially, they are expected to have some knowledge and abilities on basic programming and flow control structures.
3. Competences to be obtained in this subject
Here are the skills which students in Data Structures and Algorithms must have acquired at the end of the course. These skills are related to the analysis, design and development of data structures and operations for its management in medium-size programs.
|
Transferable Competences |
Specific Competences |
|
CG2: Capacity to analyze
Interpersonal CG3: Capacity to understand someone else's needs when solving a problem CG4: Dialogue and teamwork
Systemic CG5: Capacity to apply knowledge in practice
CG6: Interest in quality |
CE1: Knowledge on the concept of Abstract Type Data its components (Set of Support and Interface or Signature) and the concepts implied (encapsulation, implementation independence, reuse, robustness, etc.) and how they are formally defined (set of building operations, pure/impure sets, etc.) CE2: Knowledge on the basic data structures. Specifically: linear structures (stacks, queues and lists), tree structures (binary search trees, self-balancing trees or AVL, partially ordered trees), associative structures (tables, hash tables, AVL tables), priority queues (stacks or heaps). CE3: Knowing how these structures can be combined with basic structures to build more complex ones CE4: Knowledge on the algorithms associated to structures. Basic management operations (creation, insertion, modification, elimination, etc.); Search algorithms, hash functions, etc. CE5: Knowing the concepts of complexity function or space and execution cost. Essentially, worst case function O().
Abilities (Know How) CE6: Capacity for analysis and abstraction of structural and functional needs of a problem. CE7: Formal specification of computer science problems, specifically their structural and functional needs. CE8: Adaptation of basic data structures to some archetypical problems. CE9: Applying the elemental implementation data structures strategies, optimizing their memory use and time of execution complexity. CE10: Capacity of understanding new data structures and using them. |
4. Learning Objectives
Ultimately, the subject wants students to acquire a first view of the tasks associated with computer analysts. That is, students should be able to design and develop abstract data types (ADT) from the verbal / textual problem to be solved in the computer. To do so, these essential steps must be followed:
* Understanding and formally specifying functional needs of the problem, that's to say, specifying the ADT's (Abstract Data Type) signature needed.
* Choosing and designing the data structures which will be used in the ADTs, optimizing their memory use and time of execution complexity.
* Making a complete scheme of the selected data structures.
* Implementing the designed ADTs in an optimal way so that they can be added to the application that solves the initial problem.
Besides, students need to be able to understand new and more complex data structures they find in the future and to add them to their possible options to solve and analyse problems.
These needs to be coherent with the program design philosophy of the previous Programming Fundamentals course and to be obviously linked with the parallel course on Object-Oriented Programming.
5. Grading
5.1. General Grading Criteria
Following the spirit of the EHEA, students will be evaluated using mixed a formula: both continuously and globally through a final exam.
Seminar Mark (NS): students will be evaluated on the basis in class exercises, which will be done during the seminar session. Each of these will give a mark of 0, 0.5 or 1.0, which will be averaged will all the seminar marks and added to the final exam mark. These exercises, done individually in small classes, will let the teachers monitor students more closely and to get to know them better and so to evaluate the different phases of the course (seminars, practical sessions, exam) more accurately.
Practice Mark (NP): students will write 4 practical exercises during this course. They will start working on them during the practical sessions but will have to finish them after that. These exercises will be done in teams of 3 people so that students learn how to work in groups. Each assessment will be graded and the mark will be the same for the three member of the group. Assessments will only be graded if they compile correctly and there are no system errors. To grade practical exercises the solution's adequacy to the problem, its efficiency, the code's clarity and cleanness, its documentation and the correct operation of the code according with the set of data provided by teachers will be taken into account. The overall grade for the practice mark (NP) is calculated by averaging the grades of the 4 practical exercises.
Exam Mark (NE): at the end of the course, students will take a three-part exam: (a) a multiple-choice questionnaire that will assess general concepts (b) a part with two short answer exercises and/or exercises where students will be asked to calculate the performance of some data structures and, finally, (c) a long problem that will assess students' capacity to analyse a problem, designing the adequate data structures for it, formally specifying its solution and the abstract data types together with the interface's operations and the structures' scheme, and to analyse its time and space complexity.
Self-assessment: Students will have access to a series of exercises with solutions so that they can do a self-assessment during the course. They are optional and are not part of the final mark.
Final Mark (NF): the final mark will be calculated as follows:
NF = (NE + NS) * 0,4 + NP * 0,6
The average will be calculated if and only if: NE >= 5,0 and NP >= 5,0
5.2. Competences' Specification
|
Competences to be Achieved |
Indicator of Achievement |
Evaluation Procedure |
Timing |
|
|
Answering the final exam's short questions correctly. Solving the final exam's long problem correctly. Solving the seminar exercises and problems correctly.
|
In-class exercises during the seminar sessions.
|
Exercises to be solved during seminar sessions, approximately in weekly sessions.
|
|
CE5: Knowing the concepts of complexity function or space and execution cost. Essentially, worst case function O(). CE6: Capacity for analysis and abstraction of structural and functional needs of a problem. CE7: Formal specification of computer science problems, specifically their structural and functional needs. CE8: Adaptation of basic data structures to some archetypical problems. CE10: Capacity of understanding new data structures and using them. |
Answering the final exam's short questions correctly. Solving the final exam's long problem correctly. Solving the seminar exercises and problems correctly.
|
In-class exercises during the seminar sessions.
|
Exercises to be solved during seminar sessions, approximately in weekly sessions.
|
|
CE9: Applying the elemental implementation data structures strategies, optimizing their memory use and time of execution complexity. |
|
|
|
6. Contents
6.1. Content Blocks
•- Content Block 1: Introduction to Abstract Data Types
•- Content Block 2. Linear Structures
•- Content Block 3. Tree Structures
•- Content Block 4. Associative Structures
•- Content Block 5. Priority Queues and Heaps
•- Content Block 6. Problem Analysis
º
6.2. Content Organization and Specification
Content Block 1. Introduction to Abstract Data Types
|
Concepts |
Procedures |
Attitudes |
|
1. Introduction a les Structures de Data 2. Brief historical context 3. Need for Abstract Data Types 4. Definition of Abstract Data Types 5. Concept of Time and Space Cost-> Cost Order Function: O() 6. Advantages of Abstract Data Types |
1. Examples of problems when Abstract Data Types are not used.
|
1. Abstraction 2. Mathematics understanding |
Content Block 2. Linear Structures
|
Concepts |
Procedures |
Attitudes |
|
1. Structural Approximation to Linear Structures 2. Introduction to forma specification of Abstract Data Types from Linear Structures 3. Linear Structures Implementation 4. Linear Structures Comparison. |
1. Linear Structures analogy to the way everyday activities are 2. Formal expression of ADTs interface operations: building, modifying and consult operations 3. Linear structures static and dynamic implementation 4. Linear Structures' Time and Space Complexity.
|
1. Abstraction 2. Analysis |
Content Block 3. Tree Structures
|
Concepts |
Procedures |
Attitudes |
|
1. Properties, terminology and concepts associated to Trees. 2. Binary Trees' Paths. 3. Binary Trees' (BT) Structures. 4. Binary Search Tree (BST). 5. Self-balanced BSTs: Adelson-Velskii Landis Trees (AVL) 6. Partially Ordered Trees (POT) |
1. Binary Trees' Paths' algorithms. 2. BT formal specification. 3. BT dynamic implementation. 4. BT static implementation. 5. AVLs balance operations. 6. Insertion, modification and erase operations. 7.Time and Space Complexity of Trees. |
1. Abstraction 2. Analysis
|
Content Block 4. Associative Structures
|
Concepts |
Procedures |
Attitudes |
|
1. Associative Structures: Tables 2. Notion of the Key and Key-Value relation, etc. concepts 3. Introduction to List with Tables: Efficiency 4. Hash Tables: Concepts, Properties, Efficiency. 6. Hashing Formulae. 7. Hashing Overflow Management: Chaining, Open Addressing, etc. 8. Taules amb AVL: Concepts, Eficiència. |
1. Informal Specification: General Operations 2. Implementing Hash Tables. 3. Implementing AVL Hash Tables. |
1. Abstraction 2. Analysis
|
Content Block 5. Priority Queues and Heaps
|
Concepts |
Procedures |
Attitudes |
|
1. Functional differences with respect to an ordinary queue. 2. Informal Specification 3. Function from Partially Ordered and Complete Trees à Heaps. |
1. Partially Ordered Treed Operations: Insertion (Flotation), Consult, Erase (Sink) 2. Static Implementation from Stacks with Heaps 3. Heapsort. |
1. Abstraction 2. Analysis
|
Content Block 6. Problem Analysis
|
Concepts |
Procedures |
Attitudes |
|
1. Understanding and formal specification of functional needs of problems. 2. Choosing and designing the appropriated data structures to be used in the ADTs, optimizing their memory use and time execution complexity. 3. Reviewing and consolidating al the ADTs studied. |
1. Formal specification of the signature of the needed ADTs. 2. Writing a complete scheme on the selected data structures. 3. Implementing the designed ADTs in the best possible way so that they can be added to the application solving the initial problem. |
1. Abstraction 2. Analysis
|
7. Information and teaching resources
These information resources come from two different sources: Library and others, on the one hand, or other teaching resources needed during the learning process, on the other one.
We have made an effort to classify them according to different criteria: their typology and their relevance for the subject's contents.
7.1. Information resources for the learning process. Basic readings (paper and electronic)
•- AHO, A.V. et al. Data Structures and Algorithms. Addison-Wesley, 1983.
•- FRANCH GUTIÉRREZ, X. Estructuras de datos. Especificación, diseño e implementación. Edicions UPC, 1994.
7.2. Information resources for the learning process. Further readings (paper and electronic)
•- WEISS, M. Data Structures and Algorithm Analysis in C. Benjamin Cummings, 1993.
•- PEÑA, R. Diseño de programas. Prentice Hall, 2nd Edition, 1999.
7.3. Information resources for the learning process. Support readings (paper and electronic)
•- NYHOFF, L. TADs, Estructuras de datos y resolución de problemas con C++ (2nd Edition), Pearson/Prentice Hall, 2005.
7.4. Didactic Resources. Teaching material for the course
•- Power Point presentations for the course
•- List of problems for the course
7.5. Didactic Resources. Support materials and tools
•- Website for the subject with interesting links and punctual information on the exercises' instructions, their time and day assessment as well as solutions for the given exercises, etc.
8. Metodology
From a theoretical point of view, each block corresponds to a new topic, which will be more complex than the previous one so that in the last one students face problem resolution using all the material on which they have previously worked.
Each block may contain several lectures (that all students have to attend) introducing concepts to be reinforced on the seminars, where exercises are done to consolidate these concepts. Students need to take notes during the lectures and to read them after class. Seminars, with small groups of students, aim at the students' individual work during the session, which can be accurately assessed by the teacher. S/he will clarify potential doubts and allow the students face problems on their own but knowing there is no danger to be blocked.
The last block is designed to train the student's analytical capacities and their ability to apply structure design to problems which are more similar to real situations.
At the end of the blocks 2, 3, 4 and 5 there will be a practical session in which students have to do practical project in groups of three people. These sessions are useful to understand the instructions and to solve any doubts that may arise. They are also useful to start working on the project even though it will have to be finished after class. Programming language for the projects is the C one as a continuation of the first-year course Programming Fundamentals.
The first three practical exercises are focused on developing the students' programming skills although they promote analysis and abstraction in some way, too. The last practical exercise will be longer than the other ones and will promote a deeper and more serious work solving a problem, which is closer to the real ones.
All in all, the theory and the practical component progress in a parallel and coordinated way.