Babes-Bolyai University of Cluj-Napoca
Faculty of Mathematics and Computer Science
Study Cycle: Graduate
SUBJECT
| MID0040 | Programming and Lrogramming Languages |
| Teaching Staff in Charge |
Lect. PREJMEREAN Vasile, Ph.D., per cs.ubbcluj.roLect. GURAN Adriana Mihaela, adriana cs.ubbcluj.roLect. IONESCU Clara, Ph.D., clara cs.ubbcluj.ro |
| Aims |
|
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. |
| Content |
|
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 |
| References |
|
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. 11. Vaduva, I., Baltac, V., V.Florescu, I.Floricica, M.Jitaru, Ingineria programarii, Editura Academiei RSR, Bucuresti, 1985. |
| 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 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 + 25%P+ 10%L + 15%D. |
| Links: | Syllabus for all subjects Romanian version for this subject Rtf format for this subject |