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	Category	Status	
1	2+2+2	fundamental	compulsory	

II. Full status faculty members
Name and	Scientific	Didactic	Chair	Type of activity	
surname	title	title		C	S	L	
GURAN Adriana Mihaela	PhD	Lecturer	Programming  Languages and Methods	*	*	*	
Mihis Andreea		Assistant	Programming  Languages and Methods			*	
Czibula Istvan	PhD	Assistant	Programming  Languages and Methods		*		

Associated faculty members
Name and	Scientific	Institution	Type of	Type of activity	
surname	title		position	C	S	L	
Pop Ionel		Babes-Bolyai University	PhD student			*	
Craciun Florin		Babes-Bolyai University	PhD 		*	*	
Nicolae Adriana		Babes-Bolyai University	PhD student			*	

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
Schedule of courses 

Week 1: Algorithms and their description [1, ch. 1]
Week 2: Subalgorithms (Pseudocode) [1, ch. 1]
Week 3: Simple Pascal programs [1, ch. 1]
Week 4: Steps in the life of a program. Consequences. Programs testing [1, ch. 3]
Week 5: General methods to elaborate algorithms: top-down, stepwise refinement, modular programming, structured programming. Important rules in programming. Style [1, ch. 4]
Week 6: Abstract data types (part I) [1, ch. 5]
Week 7: Abstract data types (part II) [1, ch. 5]
Week 8: Algorithms complexity [1, ch. 7]
Week 9: Recursion. Backtracking [1, ch. 6], [3, ch. 3, 4]
Week 10: Division method. Greedy method. [1, ch. 6]
Week 11:. Dynamic programming. Branch and Bound [1, ch. 6]
Week 12: Search algorithms and their complexity [1, ch. 7]
Week 13: Sort algorithms and their complexity [1, ch. 7]
Week 14: Algorithms correctness. Correct algorithm development from specifications [1, ch. 2]

Schedule of seminars 

Week 1: Subalgorithms (Pseudocode)
Week 2: Subalgorithms (Pseudocode)
Week 3: Coding Pseudocode algorithms in Pascal 
Week 4: Pascal programs with subprograms
Week 5: Pascal programs with subprograms
Week 6: Top-down design
Week 7: Graded paper (include correct development of algorithms from specifications and writing simple subalgorithms)
Week 8: Specification, design, implementation and use of abstract data types 
Week 9: Specification, design, implementation and use of abstract data types
Week 10: Algorithms complexity
Week 11: Recursion. Backtracking. Complexities
Week 12: Programming techniques. Complexities
Week 13: Preparation for the practical test
Week 14: Preparation for the written exam

Schedule of labs 

The week number indicates when the lab theme has been given; the lab documents are due one week later and the lab programs are due two weeks later.

Week 1: Algorithms and their description
Week 2: Subalgorithms (Pseudocode)
Week 3: Coding Pseudocode algorithms in Pascal
Week 4: General methods to create algorithms
Week 5, 6: Top-down method and Stepwise refinement
Week 7: Testing. Text files.
Week 8, 9: Abstract data types
Week 10: Backtracking method
Week 11: Algorithms complexity
Week 12, 13: Lab delivery time (see note above)
Week 14: Practical test	

VII. Didactic methods used
Expositions: description, explanation, class lectures, dialog-based lectures, lectures with demonstrations, introductive lectures, current lectures, synthesis lectures. 
Conversations: debate, dialog, introductive conversations, conversations for knowledge consolidation, conversations to systematize and synthesize knowledge 
Use of problems: use of problem questions, problems and problem situations. 
Discovery: directed and independent rediscovery, creative discovery, inductive discovery, deductive discovery, discovery by documenting, experimental discovery. 
Other methods: case study; cooperation, simulation, brainstorming, individual study, exercise, homework study.	

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.
Further information regarding the evaluation process and the course requirements can be found following the URL:  http://www.cs.ubbcluj.ro/~adriana/Teaching.html or in the local network following the path \\Win\labor\Engleza\An1\FP\Requirements	

IX. Additional references

Dean,
PhD Prof. Leon TAMBULEA	Chair Chief, 
Prof. Bazil PARV, PhD.
	
Date,
27.09.2010	
Course responsible,
Lecturer GURAN Adriana Mihaela, PhD.

,