Programming Basics
Targets of the knowledge area:
1. Learn the main data structures
2. Learn the object oriented programming paradigm
3. Learn a particular oriented object language, such as C++ or Java.
4. Design the most efficient data structure for a given problem, according to some temporal and memory constraints.
5. Learn to design and develop software applications with high complexity and size.
Other objectives:
6. Stimulate the skills of synthesis and analysis
7. Enhance communication skills, both at the oral and written level
8. Encourage for the search and integration of information from different sources
9. Motivate the capability to solve problems
10. Motivate applying the new knowledge to the practice
11. Stimulate work in team
12. Stimulate the capability to learn and solve problems autonomously
13. Encourage for the continuing study and work habits
1. Algebraic specification of abstract data types
1.1. The abstract data type concept
1.2. Abstract data type algebraic specification
1.2.1. Signatures and algebras
1.2.2. The equational specification
1.3. Examples.
2. Linear Data Structures
2.1. Introduction
2.2. Stacks
2.2.1. The concept of stacks
2.2.2. Algebraic specification
2.2.3. Static and dynamic representations
2.2.4. Exercises
2.3. Queues
2.3.1. The concept of queues
2.3.2. Algebraic specification
2.3.3. Static and dynamic representations
2.3.4. Exercises
2.4. Lists
2.4.1. The concept of list
2.4.2. Lists with point of interest. Concept, algebraic specification and implementation
2.4.3. Position-sorted lists. Specification and implementation
2.4.4. Lists sorted by key. Specification and implementation
2.4.5. Lists sorted by different fields
2.4.6. Other alternatives. Circular lists and doubly-linked lists
2.4.7. Multilists
3. Functional Data Structures.
3.1. Introduction.
3.2. The table ADT. Algebraic specification.
3.3. Implementation with unsorted lists.
3.4. Implementation with sorted lists.
3.5. Implementation with arrays.
3.6. Implementation with hash tables.
3.7. Hashing.
3.7.1. Hash functions
3.7.2. Representations
4. Trees
4.1. Introduction and terminology.
4.2. The n-ari tree and the binary tree ADT.
4.3. Representation of trees.
4.4. Tree Traversals.
4.5. Binary Search Trees.
4.6. Threated Binary Trees.
4.7. Balanced Trees
4.7.1. AVL Trees
4.7.2. 2-3 Trees
4.7.3. B Trees
4.8. Heaps
4.9. Tries
5. Graphs.
5.1. Introduction
5.2. Definitions
5.3. Algebraic specification
5.4. Graph representations
5.4.1. Adjacency matrices
5.4.2. Adjacency lists
5.4.3. Adjacency multilists
5.5. Elementary graph algorithms
5.5.1. Shortest path search
5.5.2. Dijkstra's algorithm
5.5.3. Floyd's algorithm
5.5.4. Warshall's algorithm
5.6. Graph traversals
5.6.1. Depth first search
5.6.2. Breath first search
5.6.3. Topological sorting
5.6.4. Acyclicity test of a Directed Graph
5.7. Minimum cost spanning trees
5.7.1. Prim's algorithm
5.7.2. Kruskal's algorithm
6. Object oriented programming and Java/C++
6.1. Object oriented design
6.2. Classes and objects in Java/C++
6.3. Interfaces and inheritance
6.4. Utility Classes
6.5. Handling exceptions
To develop this area of study the following kinds of sessions are used:
- Theory Sessions
- Sessions to resolve exercises
- Laboratory sessions
Most of the sessions are theory sessions. There is a session to resolve exercises at the end of each chapter and at the end of each term. There the new knowledge acquired is applied to practical exercises.
In the midterm, there are two laboratory sessions, each lasting for two hours, that aim at introducing the student in the practice of Java/C++. Specifically, a problem is proposed to the students and they have to build a software application that solves the given problem. In the laboratory, the student is able to compile and run the program with the help of the professor. Mainly, these sessions are presented as an introduction of the first practice of the subject.
The practical component of the subject consists of the design, implementation and test of software programs that serve to resolve particular problems. To carry it out, the student has to integrate different aspects of the subject. There are two practices, and they are designed to be solved incrementally, with an increasing difficulty level. The practices encourage the team
work.
Support to students is made on-line (personally) and off-line. Off-line support is made via the intranet, where some documents, examples, links of interest, news and so on are set.
The evaluation of this subject is done in two parts: the theory part and the practial part. The theory is evaluated from exams and from the continuous evaluation exercises (Nex). The practical part is evaluated by the practices made during the course (Nprac).
The requirements to pass the subject are the followings:
Nex >= 4.5
Nprac >= 5
The final grade of the subject (Nsubject) is computed as following:
Nsubject = Nex * 0.75 + Nprac * 0.25
Finally, the subject is passed if Nsubject >= 5
- Theory grade calculation:
To value the continuing work, the student can take three partial exams. On the contrary, the s
tudent has to take a final exam, which is made in June or in September.
If the student decides to take the partial exams, the Nex grade is the geometric average of the three terms. Otherwise, if the student takes the final exam, Nex is the one obtained in this
exam.
A continuous evaluation of the student is also made. This evaluation consists of the optative delivery of some exercises resolved by the student. There are about one or two exercises that are proposed to the student for each theory chapter. Depending on the quality of the delivered exercises, the theory mark can be increased by one point at maximum.
- Practical grade computation:
The practical grade is computed from the two practices that have to be delivered in a given deadline. To value the continuing work, if the student delivers the practice later than the established deadline, the maximum mark is 6 (out of 10).
There are two practices which the student has to pass separately. If this happens, the practices grade is the following:
Nprac = 0.25*Prac1 + 0.75*Prac2
The criteria used to evaluate the practices are the followings: - Analysis and design of the program and the data structures
- The software operation
- The software quality
- The report quality
- The personal interview
Goal 1: Learn the main data structures - Evaluation: [A, B, C, D, F, G, H]
Goal 2. Learn the object oriented paradigm - Evaluation: [A,B,C,D,F,G,H]
Goal 3. Learn a particular oriented object language, such as C++ or Java. - Evaluation: [A,B,C,D,F,G,H]
Goal 4. Design the most efficient data structure for a given problem, according to some temporal and memory constraints. - Evaluation: [A,B,C,D,F,G,H]
Goal 5. Learn to design and develop software applications with high complexity and size. - Evaluation: [B,D,F,G,H]
Goal 6. Stimulate the skills of synthesis and analysis - Evaluation: [A,B,C,D,F,G,H]
Goal 7. Enhance communication skills, both at the oral and written level - Evaluation: [A,B,F,G,H]
Goal 8. Encourage for the search and integration of information from different sources - Evaluation: [B,D,F,G,H]
Goal 9. Motivate the capability to solve problems - Evaluation: [A,B,C,D,F,G,H]
Goal 10. Motivate applying the new knowledge to the practice - Evaluation: [A,B,C,D,F,G,H]
Goal 11. Stimulate work in team - Evaluation: [B,F,G,H]
Goal 12. Stimulate the capability to learn and solve problems autonomously - Evaluation: [A,B,C,D]
Goal 13. Encourage for the continuing study and work habits - Evaluation: [A,B,C,D,F,G,H]
- Xavier Franch, Estructures de Dades. Especificació, disseny i implementació, Edicions UPC, 1993.
- Ester Bernadó, Albert Orriols, Recull d'exàmens d'estructures de dades, Enginyeria i Arquite
ctura La Salle, 2004.- Ester Bernadó, Albert Orriols, Exercicis d'Estructures de Dades, Enginyeria i Arquitectura La Salle, 2004.
- Ester Bernadó, Exercicis de C++, Enginyeria i Arquitectura La Salle, 2004.
- Ester Bernadó, Exercicis de Java, Enginyeria i Arquitectura La Salle, 2004.
Horowitz, E. and Sahni, Fundamentals of Data Structures in C++, S. Computer Science Press, 1995.
Aho, Hopcroft and Ullman, Estructuras de Datos y Algoritmos, Addison-Wesley Iberoamericana, 1998.
Mark Allen Weiss, Estructuras de datos y algoritmos, Addison-Wesley Iberoamericana, 1992.
Herbert Schildt, C++: Guia de autoenseñanza, McGraw-Hill, 1995.Bjarne Stroustrup, The C++ Programming Language (Second Edition), Addison-Wesley, 1991.
Ken Arnold, James Gosling, David Holmes, The java programming language, Addison-Wesley, 2000.
Bruce Eckel, Thinking in Java, 3rd Edition, Prentice Hall, 2002.H. Ehrig and Mahr. Fundamentals of Algebraic Specification, EATCS Monographs on Theoretical Computer Science, Springer-Verlag, 1985.
F. Escudero i J.M. Garrell, Fonaments de Programació, Bruño/EUETT, 1993