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	
POP Horia Florin	Ph.D.	Prof.	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., Pop H. F., Fundamentals of Programming, Cluj University Press, 2006, 220 pages (library)
2.	Frentiu M., Pop H. F., Serban G., Programming Fundamentals, Cluj University Press, 2006, 234 pages (library)

3.	Frentiu M., Lazar I., Bazele programarii. Proiectarea algoritmilor, Ed.Univ. Petru Maior, Targu-Mures, 2000, 184 pagini (library)
4.	Kasa Z., Algoritmusok tervezese, Ed. Studium, Cluj, 1994 (library)	

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: Algorithms correctness. Correct algorithm development from specifications [1, ch. 2]
Week 6: General methods to elaborate algorithms: top-down, stepwise refinement, modular programming, structured programming. Important rules in programming. Style [1, ch. 4]
Week 7: Abstract data types (part I) [1, ch. 5]
Week 8: Abstract data types (part II) [1, ch. 5]
Week 9: Algorithms complexity [1, ch. 7]
Week 10: Recursion. Backtracking [1, ch. 6], [3, ch. 3, 4]
Week 11: Division method. Greedy method. [1, ch. 6]
Week 12:. Dynamic programming. Branch and Bound [1, ch. 6]
Week 13: Search algorithms and their complexity [1, ch. 7]
Week 14: Sort algorithms and their complexity [1, ch. 7]

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: Develop correct algorithms from specifications
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: Recursion
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 written exam 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 test 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 awarded a fourth grade (L), and the documentation written during the term will receive a fifth grade (D). If all these grades are at least 5, the final grade is determined as follows: Grade = 50%E + 15%P + 15%G + 10%L + 10%D.	

IX. Additional references
1.	Knuth, D.E., Tratat de programare a calculatoarelor. Algoritmi fundamentali. Ed.Tehnică, Bucureşti 1974 (library)
2.	Knuth, D.E., Tratat de programare a calculatoarelor. Sortare şi cautare. Ed.Tehnică, Bucureşti 1976 (library)	

	Date,							Course responsible,
	April 10, 2007						Prof. POP Horia Florin, Ph.D.