Academic year 2015-16

Programming Fundamentals

Degree: Code: Type:
Bachelor's Degree in Computer Science 21406 Compulsory subject, 1st year
Bachelor's Degree in Telematics Engineering 21297 Compulsory subject, 1st year
Bachelor's Degree in Audiovisual Systems Engineering 21595 Compulsory subject, 1st year

 

ECTS credits: 8 Workload: 200 hours Trimester: 2nd and 3rd

 

Department: Dept. of Information and Communication Technologies
Coordinator: Sergi Jordà
Teaching staff:

Sergi Jordà, Dolors Sala, Janine Kleinhans, Carthach O'Nuanain, Javier Segovia, David Soto, Vicky Vouloutsi, Jordi Ysard.
Language:

Catalan and Spanish
Timetable:
Building: Communication campus - Poblenou

 

Introduction

This course is part of a programming and algorithms bloc of courses done in first and second year of the degrees in Computer Engineering, Telematics Engineering and Audiovisual Systems Engineering. Fundamentals on programming is the first course and hence it assumes no previous programming knowledge. It establishes the foundations of algorithms, data structures and programming in c language. The following courses, Object Oriented programming, and Data structures and algorithms, build on and strengthen the target competences so that at the end of the first quarter of the second year the student can develop programs of a considerable size with the adequate data structures, in imperative as well as object oriented form. It is important to highlight that the foundations acquired in Programming Fundamentals are required to perform the lab assignments of a large number of courses along the degree.

 

The learning activities have been divided in several categories:

 

Prerequisites

This course does not require any previous knowledge of programming or algorithms. However, some exercises require the mathematical knowledge at the high school level.

 

Associated competences

The fundamental objective of the course is to acquire the basics of algorithms and data structures, as well as to be able to develop middle size programs in c language fluently.

This chapter provides the competencies to acquire by the end of the course. First, the general competences are abilities no directly related to computer programming. Instead they are related to the general competences to be acquired by an engineer. The specific competences are related to the aspects directly related to the course.

 

General Competences

Instrumentals

CG1

Synthesis capacity

The student has to be able to write solution with the essential elements, in a simple form, elegant, and as efficient as possible.

CG2

Analysis capacity

The students have to be able to analyze a concrete problem and propose solutions to the problem.

Systematic

CG3

Capacity to apply knowledge in practice

The student has to be able to apply the acquired knowledge to solve concrete problems, selecting the most appropriate technique each place.

CG4

Interest for the quality

The student has to be able to write efficient code easy to read and maintain. Likewise, it is important to correctly document the codi with comments inside as well as in a document.

 

Specific Competences

CE1

Capacity to work with programming tools

The student has to be able to work with the basic programming tools: compiler, debugger, programming editor and an IDE (integral development environment). This competence is crucial for the correct development of the other competences.

CE2

Have command of static data types: basic and structures

The student has to be able to distinguish the different types of data (basic and structures) and decide the most adequate type for each situation.

CE3

Have command of the control structures

The student has to be able to distinguish the different control structures and decide the most adequate to solve a particular problem.

CE4

Capacity to solve problems through top-down design and command of the functions and libraries

The student has to be able to solve problems of considerable complexity using the top-down design techniques. In particular, the student has to understand the operation of function calls, passing parameters, command the use and creation of libraries, and be able to divide a problem in the appropriate units.

CE5

Command of dynamic data structures and management of dynamic memory

The student has to understand the mechanism of memory management as well as the use of pointers and dynamic control of data structures. It includes also the mapping of text files.

CE6

Documentation and code structure

The student has to acquire the habit of structure and document the code appropriately with the objective to facilitate the future comprehension of this code.

CE7

Capacity to read c code at a reasonable speed

The student has to be able to understand code written by other programmers at a reasonable speed.

CE8

Command of the fundamental elements of algorithms

The student has to know and be able to adequately apply the fundamental concepts of algorithms such as recursion and search and order algorithms.

 

Assessment

1.  General Evaluation Criteria

The course has a duration of two quarters. Each quarter is evaluated separately. The final grade in each quarter represents 50% of the final grade, and it is compulsory to pass (grade >= 5) each quarter to pass the entire course.

The evaluation of each quarter has two parts: one part of “theoretical/practical fundamentals” (T) and a practice part (P).

Each of the two parts (T and P) has same weight (50%) in the final quarter grade for each quarter. This means QF = 50% T + 50% P

Theoretical/practical fundamentals (T)

The theoretical-practical fundamentals are evaluated in a written exam at the end of the quarter (for each quarter). These tests focus on the theory materials and on the exercises provided during the quarter. The written test grade is the initial T grade.

In the seminars, the professors review the work done by the students along the quarter. In each session, they ask to submit a particular exercise by the end of the session. The evaluation of this submissions can add up to (and never reduce) 1,5 points to the T grade, as long as the written test grade is equal or better than 4 out of 10 point.

In addition, there are self-evaluation activities at the end of each learning block for the students validate their own learning progress. These activities are in the form of multiple choice test questions similar to the questions asked in the written tests. The self-evaluation activities do not impact in the final grade of the course.

Practice (P)

There is a practice grade at each quarter. This grade is computed from the practice assignments submitted each quarter. In addition, as part of the global practice evaluation, the professors may review the student progress along all practice sessions. If a group does not do this review, or the review is not good enough, the group will be required to orally defend the practice submission.

In addition to submitted practices, there are other practice sessions where students can evaluate their own progress. These activities do not contribute to the final grade.

July recovery

The written test of the T part can be repeated in July. However, the practice part cannot be recovered. Therefore:

In case of failing (or not submitting) the recovery in July, the student fails the entire (two-quarter) course, even if one quarter was passed.

 

2. Details

First Practice Assignment

This practice evaluates the acquisition of concepts and competences work during the first third of the course. In particular it evaluates competences CE2, CE3 and some aspects of CE4 and CE6 (structuring of commented code). The practice consists of the resolution of a problem, including the analysis and the programming of the solution in c language. The student has to decide the static data structures to use and the operation flow of the solution and perform a simple top-down design. Likewise, the four general competencies are also evaluated.

Second Practice Assignment

It evaluates the level of acquisition of the concepts of two thirds of the course, specially the second third. In particular it evaluates the competences CE2, CE3, CE4, CE5 and CE6. The practice consist in the resolution of a problem considerably complex, including the analysis, selection of appropriate data structures (static and dynamics), top-down approach, the programming of a suitable solution in c programming (following the good practice recommendations) and the correct documentation of the problem solution with a report justifying the decisions taken. Likewise, the four general competencies are also evaluated.

Third Practice Assignment

It evaluates all concepts and competences included in the entire course. In particular it evaluates competences CE2, CE3, CE4, CE5, CE6 and CE8. The practice consist in the resolution of a problem considerably complex, including the analysis, selection of appropriate data structures (static and dynamics), top-down approach, the programming of a suitable solution in c programming (following the good practice recommendations) and the correct documentation of the problem solution with a report justifying the decisions taken and also including a complexity analysis of part of it. Likewise, the four general competencies are also evaluated.

First block written test (end of second quarter)

It evaluates the understanding and application of concepts and techniques acquire during the first half of the course (corresponding to the second quarter). In particular, it evaluates the competences CE2, CE3, CE4, CE5 and in particular CE7. The evaluation method consists in a multiple-choice test of about 20 questions with 4 choices each where there is only one correct choice. The questions are taken (with small modifications) from the exercise sessions and self-evaluation activities. The evolution takes place during the exam period of the second quarter.

Second block written test (end of third quarter)

It evaluates all concepts and competences included in the entire course with small programs. In particular, it evaluates CE2, CE3, CE4, CE5, CE7, and CE8. The evaluation method consists of a multiple choice exam of about 15 questions with each question having 4 choices with only one correct choice. The evaluation takes place during the exam period of the third quarter.

 

Contents

Block 1: Introduction and general concepts

Concepts

Procedures

- Brief history of programming and its languages and paradigms 
- Compilation and interpretation Mechanisms
- Difference between program and algorithm 

 

Block 2: Basic data types 

Concepts

Procedures

- Variables and constants 
- The different basic data types
• Numeric types
• Characters
• Booleans

- Declaration of constants and variables of different types

Block 3: Expressions, sentences and control structures

Concepts

Procedures

- Construction of expressions 
- Introduction of Boolean logic 
- Sentences or instructions:

• Assignment 
• Input and output operations 
• Order of precedence of operators 
- Control structures: 
• Conditional structures 
• Iterative structures 

- Expression Evaluation 

- Resolution of small problems using the appropriate statements and control structures

 

Block 4: The functional decomposition and the top-down approach 

Concepts

Procedures

- Top-down design
- Function declaration
- Definition of parameters

- Function calls and passing parameters 

- The void  type

 - Decomposition of problems in sub-problems 

- Resolution of small problems defining adequate functions

Block 5: Static data structure types

Concepts

Procedures

- Uni-dimensional Arrays
- Multi-dimensional Arrays 
- Strings or sequence of characters 
- Structures (structs)

- Resolution of small problems about typical operations of each data type 

Block 6: Declaration of new types 

Concepts

Procedures

- The types of the structures 
- Definition of types using typedef 
- Types conversions 

- Resolution of small problems of new data type definitions

Block 7: Pointers and dynamic memory management

Concepts

Procedures

- Pointers declaration 
- Direction and indirection operations 
- Assignment of pointer values 
- Null pointer 
- Arrays and pointers in C

 - Resolution of small problems on the typical pointer operations 

- Resolution of small typical problems of arrays using pointers

Block 8: The functional decomposition and the top-down design (second part) 

Concepts

Procedures

- Passing parameters by reference 
- The main function and its arguments 
- Visibility and scope 
- The libraries and the pre-processor

 - Resolution of problems by decomposition using functions passing parameters by reference

Block 9: Text Files

Concepts

Procedures

- The file type (FILE) 
- File operations: 
• Open
• Close 
• Write 
• Read 
- Standard input-output

 

- Resolution of small problems about typical operations with text files

Block 10: Style and good practices

Concepts

Procedures

- Style, readability and obfuscation 
- Good practices 
- Common mistakes 
- Code analysis 
- Depuration

- Resolution of small problems of error detection and style improvement  

- Use of code analysis tools  

Block 11: Functional decomposition and top-down design (Third part)

Concepts

Procedures

- Programming of libraries 
- Code segmentation in different files 
- Header files 

- Resolution of problems on the creation and us of libraries

 Block 12: Search and sort algorithms

Concepts

Procedures

- Linear and binary search 
- Basic sorting algorithms
• Bubble
• Insertion
• Selection

- Resolution of problems on search and sorting algorithms  

Block 13: Recursion

Concepts

Procedures

- Recursion concept 
- Recursive algorithms 
- Base case and recursive rule 
- Advantages and drawbacks 
- Direct and indirect recursion 
- Transformation to iterative algorithms
- Specific examples of recursive algorithms (fractals, towers Hanoi towers, Quicksort, etc)

 - Resolution of problems through the definition of recursive functions

Block 14: Advanced memory management

Concepts

Procedures

- Pointers of pointers 
- Arrays of pointers 
- Punter to functions 
- Memory dimensioning
- Concrete examples of advanced memory management (lists, binary trees, etc) 

- Resolution of problems of advanced memory management

 

Methodology

The learning process in a learning unit starts with a theory session where the theory-practical fundamentals are presented.  These activities are performed in big group sessions. The student has to complement this session with the study of the class notes and materials. As example, a typical theory session of 2 hours, followed appropriately by the student, requires at least 1 additional hour of independent study by the student to consolidate the presented concepts.

Next, there are one or more seminar and/or practice sessions. In the seminar sessions the student puts in practice the concepts and techniques presented in the theory session by implementing the programs that solve small problems. The objective is to consolidate the student’s knowledge of fundamentals with the intention to apply them in bigger problems. This activity is done individually, in a class with about 15 students (small group). Each activity of this type is programmed with a total duration of 4 hours, where 2 of them are done in class with the support of the practice professor and 2 additional hours of independent work. The exercises provided with solutions in the first part of the handouts are supposed to be done before the session. The professor requests to submit one of the exercises listed in the handouts by the end of the session.

The practice sessions allow tackling bigger problems, especially in the three practice assignments, that require a previous design of the solution to implement and integrate different concepts and techniques. The last practice assignment covers all specific competencies to be acquired in the course. Each activity of this type is worked out in teams of two students, and performed in middle-size group class rooms (30 students). The assignment has to be developed outside the class sessions.

Seminar and practice sessions dedicate part of the time to discuss the most important problems presented in the previous sessions.

The last step involved in a learning unit is the resolution of self-evaluation exercises. This allows the student validating the level of acquisition of the competences evaluated in the written tests.

1. Learning Units

Learning unit 1 First steps: introduction, basic data types and control structures

Content blocks
Learning activities

1: Introduction and general concepts
2: Basic data types
3: Expressions, sentences and control structures

 Theory sessions 

Seminar sessions 

 Practice sessions

 Self-evaluation

 T1, T2, T3 and T4

 S1 and S2

 P1

 A1

Total Dedication of learning unit 1: 21 hours (12 in class, 9 independent)

Details of the activities:

Theory session T1: 3 hours (2 in class, 1 independent): Brief programming history, including compilation and interpretation models.
Theory sessions T2, T3 and T4: 9 hours (2 in class for each session, 1 independent): Explanation of the basic data types and most important examples of their use. Explanation of construction of expressions and basic sentences including discussion of the most important examples using them. Iterative and conditional control structures and discussion of the most important examples where to use them.

Seminar sessions S1 and S2: 8 hours (4 in class, 4 independent): Exercises on expressions construction and on conditional and iterative control structures.
Practices Session P1: 3 hours (2 in class, 1 independent): It explains how to install the compiler, how to edit, compile and execute a program. The students work out small programs with errors so that to get used to typical compiler error messages.

Self-evaluation A1: 1 hour (independent): Resolution of self-evaluation exercises on expressions construction and control structures.


Learning unit 2: Functions and top-down approach

Content blocks 
Learning Activities

4: The functional decomposition and top-down design

 Theory sessions

Seminar sessions

Practice sessions

 Self-evaluation

T5

S3

 

A2

Total dedication learning unit 2: 8 hours (4 in class, 4 independent)

Details of the activities :
Theory session T5: 3 hours (2 in class, 1 independent): Explanation of top-down design principles, function definition, function calls and pass of parameters by value and use cases.
Seminar session S3: 4 hours (2 in class, 2 independent): exercises of top-down design and pass of parameters by value.
Self-evaluation A2: 1 hour (independent): Resolution of self-evaluation exercises on functions and pass of parameters by value.

Learning unit 3: Static and compound data types and types declaration

Content blocks
 Learning Activities

5: Compound data types

Static

Static Self-evaluation
6: Declaration of new types

Theory sessions

 Seminar sessions

Practice sessions

Self-evaluation

 T6 and T7

 S4

 P2 and P3

 A3


Total dedication Learning unit 3: 29 hours (10 in class, 19 independent)
Details of the activities:
Theory sessions T6 and T7: 6 hours (2 in class for each session, 1 independent) Explanation of compound data types (arrays, strings, and structures) with use case examples. Explanation of new data types defined by the programmer, with examples of use case.
Seminar session S4: 4 hours (2 in class, 2 independent): Exercises on compound data types.
Practice sessions P2 and P3 (first practice assignment): 18 hours (each session, 2 in class, 7 independent): Students have to resolve (in c language) mid-size problems, using arrays, strings, and structures defining new data types when required. It includes the elaboration of a report explaining the work done.
Self-evaluation A3: 1 hour (independent): Resolution of self-evaluation exercises on compound data types.

Learning unit 4: Pointers and pass of parameters by reference

Content blocks
 Learning Activities

7: Pointers and dynamic management of memory
8: Functional decomposition and top-down design (second part)

Theory sessions

Seminar sessions

Practice sessions

Self-evaluation

 T8 and T9

 S5

 P4

 A4

Total dedication learning unit 4: 18 hours (8 in class, 10 independent)
Details of the activities :
Theory sessions T8 and T9: 8 hours (each session 2 in class, 2 independent) : Explanation of the pointer operations and examples of use. Explanation of the pass of parameters by reference and examples of use. Explanation of visibility rules.
Seminar session S5: 4 hours (2 in class, 2 independent) Exercises on pointes and pass of parameters by reference.
Practice session P4: 5 hours (2 in class, 3 independent) The student has to solve (programming in c) small problems using pointers and passing parameters by reference.
Self-evaluation A4: 1 hour (independent): Resolution of self-evaluation exercises on pointers and pass of parameters by reference.

Learning unit 5: Text Files

Content blocks
 Learning Activities

9: Text Files

Theory sessions

Seminar sessions

Practice sessions

Self-evaluation

T10

S6

 

 A5

Total dedication Learning unit 5: 8 hours (4 in class, 4 independent)
Details of the activities :
Theory session T10: 3 hours (2 in class, 1 independent) : Explanation of text files and use case examples.
Seminar session S6: 4 hours (2 in class, 2 independent): Exercises on text files.
Self-evaluation A5: 1 hour (independent): Resolution of self-evaluation exercises on text files.

Learning unit 6: Good practices and library programming

Content blocks
Learning Activities


11: The functional decomposition and top-down design (third part)

Theory sessions

Seminar sessions

Practice sessions

Self-evaluation

 T11

 

 P5, P6, P7 and P8

 A6

Total dedication Learning unit 6: 33 hours (12 in class, 21 independent)
Details of the activities:
Theory session T11: 3 hours (2 in class, 1 independent): Explanation of code analysis and polishing. Explanation of the process to create libraries, and segmentation of the code in separate files. Review of the visibility rules.
Practice session P5: 4 hours (2 in class, 2 independent) Start working with an integrated development tool. Explanation of how to debug a program using the IDE tool. Students debug several small example programs.
Practice session P6: 4 hours (2 in class, 2 independent) Explanation of how to create a program structured in different files using an IDE tool. The students create a program divided in different modules.
Practice sessions P7 and P8 (Second practices assignment). 18 hours (each session, 2 in class, 7 independent) The student has to solve (programming in c) a problem of considerable size that involves the use of pointers, pass  of parameters by reference, text files, and segmentation of code in several files. The solution has to follow the good practices recommendations in design and programming. It also requires the submission of a report documenting the work submitted.
Self-evaluation A6: 1 hour (independent): Resolution of self-evaluation exercises on style, good practices and segmentation of code in modules or files.

Learning unit 7: Search, sorting and recursion

Content blocks
Learning Activities

12: Search and sorting algorithms
13 : Recursion

Theory sessions

Seminar sessions

Practice sessions

Self-evaluation

 T12, T13, T14 & T15

 S7 & S8

 

 A7


Total dedication learning unit 7: 24 hours (12 in class, 12 independent)
Details of the activities:
Theory session T12: 3 hours (2 in class, 1 independent): Explanation of the linear and binary search algorithms, and sorting algorithms (bubble, insertion, and selection).
Theory sessions T13, T14 and T15: 12 hours (T13 2 in class, 2 independent; T14 2 in class, 3 independent; T15 2 in class and 1 independent): Explanation of the recursion concept, the basis of the recursive algorithms and their advantages and disadvantages. Explanation of the different types of recursion and of the transformation of recursive algorithms to iterative algorithms. Discussion of several examples of recursive algorithms (including advanced sorting algorithms).
Seminar session S7: 4 hours (2 in class, 2 independent): Exercises on search, sorting and recursive algorithms.
Seminar session S8: 4 hours (2 in class, 2 independent): Exercises on recursive algorithms.
Self-evaluation A7: 1 hour (independent): Resolution of self-evaluation exercises on search, sorting and recursive algorithms.

Learning unit 8: Advanced memory management

Content Block
Learning Activities

 14: Advanced management of memory

Theory Sessions

Seminar Sessions

Practice Sessions

Self-evaluation

T16, T17 and T18

 

P9 and P10

A8

Total dedication of learning unit 8: 29 hours (10h in class, 19h independent)
Detail of the activities:
Theory classes T16 and T17: 7 hours (T16 2h in class, 2h independent; T17 2h in class, 1 independent): Explanation of the mechanisms and techniques for the advanced management of memory (pointers of pointers, array of pointers, pointers to functions, dimensioning of memory). Discussion of examples on advanced memory management.
Theory session T18: 3 hours (2h in class, 1 independent): general review and clarification of concepts based on student requests.
Practice sessions P9 and P10 (third evaluated practice). 18 hours (each session: 2h in class, 7h independent): the student has to solve (programming in c) a problem of a considerable size integrating all concepts and techniques involved in the course (including recursive algorithms and advanced memory management). The final program has to follow the good practices recommendations. The assignment it also requires a report explaining and documenting the submitted work.
Self-evaluation A8: 1 hour (independent): Resolution of self-evaluation exercises on advanced memory management.

Note: In addition to the work hours described above, the total student dedication includes time to prepare the written tests. The first test assumes a dedication of 10 hours (8.5 +1.5) and the second test assumes 20 (17.5 +2.5) hours.

Total course dedication: 200 hours (76h in class, 124h independent)

Activities Program

Student dedication (in hours)

 
Classroom Activities
Independent work hours
 
Activities
Big Group
Middle size group
Small Group
 

Learning Unit 1

T1

2

 

 

1

T2

2

 

 

1

P1

 

2

 

1

T3

2

 

 

1

S1

 

 

2

1

A1

 

 

 

1

Learning Unit  2

T4

2

 

 

 

S2

 

 

2

 

A2

 

 

 

1

Learning Unit 3     

T5

2 

 

 

1

S3

 

 

2 

2

T6

 2

 

 

1

P2

 

2

 

7

P3

 

2

 

7

A3

 

 

 

1

Learning Unit 4    

T7

 2

 

 

2

S4

 

 

 2

2

T8

2 

 

 

2

P4

 

2 

 

3

A4

 

 

 

1

Learning Unit 5  

T9

 2

 

 

2

S5

 

 

 2

2

A5

 

 

 

1

Learning Unit 6       

 T10

2 

 

 

1

 P5

 

2 

 

2

 T11

2 

 

 

1

 P6 

 

2

 

2

 P7

 

2

 

7

 P8

 

2

 

7

 A6

 

 

 

1

Learning Unit 7      

 T12

2

 

 

1

 T13

2

 

 

2

 T14

2

 

 

3

 S6

 

 

2

2

 T15

2

 

 

1

 S7

 

 

2

1

 A7

 

 

 

1

Learning Unit 8 

T16

2

 

 

2

T17

2

 

 

1

S8

 

 

2

2

P9 

 

2

 

7

 

Resources

Resources for the learning process: Basic Bibliography

Resources for the learning process: Complementary Bibliography

Other c language books

Other well-known books in algorithms (more advanced):

Didactic resources: course materials

Several course materials are posted in the aula global. The format material depends on each session or activity. The different materials available are: slides of theory sessions, class notes, handouts for seminar sessions, handouts for practice sessions and assignments, self-evaluation exercises, some code examples in c to practice (also used in theory classes), some on-line resources.