Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licenţă
Domeniul: Informatică
Programul de studii: Informatică - în limba engleză
Limba de predare: Engleză

SYLLABUS

I. General data
Code	Subject	
MID0001	Fundamentals of Programming	

Semester	Hours: C+S+L+P	Category	Status	
1	2+2+2+0	fundamental	compulsory	

II. Full status faculty members
Name and	Scientific	Didactic	Chair	Type of activity	
surname	title	title		C	S	L	
GURAN Adriana Mihaela		Lect.	Programming  Languages and Methods	*			

Associated faculty members
Name and	Scientific	Institution	Type of	Type of activity	
surname	title		position	C	S	L	

III. Course objectives
1. To understand what an algorithm is. To learn PSEUDOCOD as a language for designing algorithms. 
2. To gain skils of designing algorithms. 
3. To write algorithms for some classes of problems: operations on vectors, matrices, and polynoms; solving linear equations and systems; sorting and searching. 
4. To learn Pascal, and to get used to Pascal programming, running, testing, and debugging programs. 
5. To acquire and improve the programming style.	

IV. Course contents
1. Algorithms and their description
- Notion of algorithm
- Variable, type, specification
- logic diagrams
- Pseudocode language
- linear structure
- alternatives structure
- repetitions structure

2. Subalgorithms (Pseudocode)
- notion of subalgorithm
- formal parameters
- defining a subalgorithm (function and procedure)
- calling a subalgorithm
- importance of subalgorithms in programming

3. Coding Pseudocode algorithms in Pascal
- basic elements of the Pascal language
- declarations and statements
- structure of a Pascal program
- coding

4. Phases in the life-cycle of a program
- phases in the development of a program: specification, design, coding, testing, documentation, verification
- programs maintenance: corrective, adaptive, perfective
- programs testing
- black box method
- white box method

5. Algorithms correctness
- state in the execution of a program
- computation performed by an algorithm
- result of the computation performed by an algorithm
- partial correctness
- program termination
- (total) correctness
- Floyd method to prove algorithm correctness

6. Correct algorithm development from specifications
- abstract algorithm
- concept of refinement
- refinement rules
- examples

7. General methods to create algorithms
- modular programming
- structure diagram
- modules specification
- structured programming
- Bohm-Jacopini theorem
- importance of clarity in programming
- elements of clarity: indentation, spacing, names, ...
- style in programming

8. Top-down method and Stepwise refinement
- top-down method
- bottom-up method
- stepwise refinement

9. Recursion
- notion of recursion
- direct and indirect recursion
- examples

10. Abstract data types
- specification of an ADT
- Pascal unit
- implementation of an ADT in Pascal
- the use of ADTs in programming

11. Division method
- general presentation
- description of the subalgorithm

12. Backtracking method
- general presentation of the Backtracking method
- Backtracking algorithm (subalgorithm)
- extensions of the Backtracking method

13. Greedy method
- general presentation of the Greedy method
- Greedy algorithm

14. Other methods
- dynamic programming method
- Branch and Bound method
- heuristic methods

15. Algorithms complexity
- definition of complexity
- complexity as running time
- complexity as amount of required supplementary memory
- empiric analysis and asymptotic analysis
- asymptotic notation: big-o, little-o, big-omega, little-omega, theta; properties
- examples of magnitude orders
- comparison of algorithms from an efficiency point of view
- structural complexity

16. Search algorithms and their complexity
- specification of the search problem
- search methods
- sequential traversal
- binary search
- complexity of search algorithms

17. Sort algorithms and their complexity
- specification of the sort problem
- sort methods
- BubbleSort
- SelectionSort
- InsertionSort
- QuickSort
- MergeSort
- complexity of sort algorithms	

V. Bibliography
1. Frentiu, M., H.F. Pop, Fundamentals of Programming, Cluj University Press, 2006, 220 pagini
2. M.Frentiu si altii, Manualul incepatorului in Programarea Pascal, Ed. Microinformatica, Cluj-Napoca, 1995, 252 pagini, ISBN 973-9215-04-1
3. M.Frentiu si altii, Programare Pascal. Programe ilustrative, probleme propuse, pentru elevi si studenti, Ed. Promedia, 1995, 229 pagini, ISBN 973-96862-1-4.
4. M.Frentiu, V.Prejmereanu, Algoritmica si programare, Lito. Univ. Babes-Bolyai, Cluj-Napoca, 1995, 261 pagini.
5. Frentiu, M., I.Lazar, S.Motogna si V.Prejmereanu, vol.I - Elaborarea algoritmilor, 1997, 188 pagini; vol.II - Programare Pascal, 392 pagini; Ed.Universitatii Babes-Bolyai, Cluj-Napoca.
6. M.Frentiu si B.Parv, Elaborarea programelor. Metode si tehnici moderne, Ed.Promedia, Cluj-Napoca, 1994, 217 pag.
7. Kasa Z., Ismerkedes az informatikaval, Editura Dacia, 1983.	
8. Kasa, Z., Algoritmusok tervezese, Ed. Studium, Cluj, 1994.
9. Knuth, D., Tratat de programarea calculatoarelor, Ed. Tehnica (Algoritmi fundamentali;  Cautare si sortare)
10. Livovschi, L., H.Georgescu, Sinteza si analiza algoritmilor, Editura St. si Enciclopedica, Bucuresti, 1986.	

VI. Thematic of didactic activities per weeks

VII. Didactic methods used

VIII. Assessment
Knowledge evaluation will take into account both the theoretical and the practical knowledge, and also, the abilities to use the computer for solving concrete problems. The laboratory activity consists of designing programs (as homework which is controlled by the assistants) and running them. Attention will be given to the way the students design, implement, and document their programs. At the end of term the activity is followed by an exam consisting of two parts: a written exam, and a practical one. The first one must verify the theoretical knowledge and the capacity to design and implement correct Pascal programs, and a first grade (E)is given for this. The practical examination consists in designing, testing and debugging a Pascal program, for which a second grade (P) is given.
The students will take a graded paper (G) at the seminar. The laboratory activity of students will be graded by a third mark (L), and the documentation written during the term will received the fourth grade (D). The final mark is the average of these four gradess, but only if they are at least 5, otherwise the exam is not given.  Therefore, final grade = 50%E + 15%P + 15%G + 10%L + 10%D.
WebPage: http://www.cs.ubbcluj.ro/~per/Fp.html	

IX. Additional references

	Dean,							Chair head,

	Date,							Course responsible,
								Lect. GURAN Adriana Mihaela,