SubjectsSubjects(version: 807)
Course, academic year 2017/2018
   Login via CAS
Programming I - NPRG030
Czech title: Programování I
Guaranteed by: Department of Software and Computer Science Education (32-KSVI)
Faculty: Faculty of Mathematics and Physics
Actual: from 2014
Semester: winter
E-Credits: 6
Hours per week, examination: winter s.:3/2 C [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Guarantor: RNDr. Tomáš Holan, Ph.D.
doc. RNDr. Pavel Töpfer, CSc.
RNDr. Martin Pergel, Ph.D.
Class: Informatika Bc.
Classification: Informatics > Programming
Incompatibility : NMIN101, NMIN102, NPRM044, NPRM045
Is incompatible with: NMUG103, NMUG104
Is pre-requisite for: NPGR033
Annotation -
Last update: doc. RNDr. Pavel Töpfer, CSc. (09.10.2017)

A first course about programming and algorithms for first-year students studying computer science and computer science education. The course covers principles of algorithms, basic algorithms, data structures, programming techniques, typical programming environments and practical program design and debugging.
Terms of passing the course -
Last update: Adam Thomas Dingle, M.Sc. (07.10.2017)

Students will receive a credit for this course by successfully completing the following requirements:

  • Active participation in the practice sessions in the computer lab. Generally this means that students must complete the assigned programming exercises, either during the lab session or later on at home.

  • Completion of a semester programming project by the deadline fixed by the instructor.

  • Passing a written test at the end of the semester.

Due to the nature of the first two requirements, a failed attempt cannot be repeated as is possible for exams. The instructor may establish conditions whereby a student can make up for missing homework assignments or resubmit their semester project after improving deficiencies that were found the first time around.

A student has three chances to pass the written test, normally by the end of the winter exam period. The instructor may choose to allow a student to make one or more of these attempts during the following summer semester.

Literature -
Last update: Adam Thomas Dingle, M.Sc. (07.10.2017)

P. K. McBride: Pascal Made Simple (Butterworth-Heinemann, 2011)

Cormen, Leiserson et al: Introduction to Algorithms, Third Edition (MIT Press, 2009) (selected chapters)

Syllabus -
Last update: Adam Thomas Dingle, M.Sc. (07.10.2017)

a) Basic algorithms, data structures and programming techniques

  • basic notions of algorithmic efficiency
  • divisibility, Euclid's algorithm
  • primality testing, the sieve of Eratosthenes
  • Horner's rule
  • dividing an integer into digits, positional notation for numbers
  • array search algorithms (sequential, binary, sentinel)
  • sorting data in an array (internal sorting)
  • basic matrix operations
  • implementing stacks and queues using an array
  • higher-precision arithmetic ("long numbers")
  • recursion, backtracking, divide and conquer
  • depth-first search and breadth-first search
  • the minimax algorithm
  • heaps and heap operations
  • factor sets
  • dynamic data structures, linked list operations
  • binary search trees, balanced binary trees (AVL trees)
  • multiway binary trees (B-trees)
  • representing and evaluating arithmetic expressions
  • external sorting

b) Typical programming language elements and mechanisms, as exemplified in the Turbo Pascal language

  • variables, constants, types, variable initializers
  • primitive and compound data types (numbers, characters, booleans, enumerated types, arrays, lists, strings of symbols)
  • simple and compound statements (assignment, if, while, repeat, for, case, with)
  • text files (including formatted output)
  • procedures and functions (local identifiers, parameter passing mechanisms, recursion)
  • the goto statement
  • pointers and dynamically allocated data
  • basic compiler directives (memory limits, run-time checks)

c) Working with an IDE (integrated development environment), creating and debugging programs - practically demonstrated using the Turbo Pascal or Free Pascal IDE (editor, compiler, debugging tools - tracing, examining variable values etc.)

 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html