AE4M33PAL - Advanced algorithms

Individual implementation of variants of standard (basic and intermediate) problems from several selected IT domains with rich applicability. Algorithmic aspects and effectiveness of practical solutions is emphasized. The lectures provide a necessary theoretical background.

The course requires programming skills in at least one of programming languages C/C++/Java.
There are also homework programming tasks. Understanding to basic data structures such as arrays, lists, and files and their usage for data processing is assumed. Students who should have difficulties with elementary programming tasks will not be assigned PAL credit. We recommend to cancel the subject attendence.

Seminars contain:
Depending on the level, expertise and demands of the students
1. Exercising of selected topics from lectures.
2. Analysis of homework task specifications, discussions of different variants of solutions and their effectiveness.

The semester includes homework programming problems that are required to be solved, implemented, and uploaded by the given deadlines into the Upload system. The homework problems represent examples of algorithmically slightly more involved problems. Typically, few different algorithms and/or data structures must be correctly interconnected to solve the task. The time for solution is about 20 days.

1. The correctness of the solution is checked automatically using test data sets (unknown to the students).
2. Running time, is critical. The time in which the submitted solution processes each of the data files is monitored and it is compared to the running time of the reference code processing the same data file. Typically, the student solution is expected to run at most two times as long as the reference solution. Slower student solutions are regarded as unacceptable.

 The timetable of the homeworks: 
 1. assignment    7.10. -       - deadline   27.10.  
 2. assignment   14.10. -       - deadline    3.11. 
 3. assignment   29.10. -       - deadline   17.11. 
 4. assignment   11.11. -       - deadline    1.12. 
 5. assignment   18.11. -       - deadline    8.12. 
 6. assignment    2.12. -       - deadline     5.1.

The deadlines are also defined for each homework tasks in the Upload system.

In addition to the participation in the seminars it is necessary to deliver successful solutions in term of programming tasks.
Each tasks is executed against 10 testing data sets of different size and complexity. The solution is considered as successful if the correct results are returned for at least 9 test data sets. Therefore, the assessment of tasks according to the number of correctly processed input files is following:

Grading of the homework problems according to the number of correctly processed data sets:

 .... 8 and less................ 0 pts ............... unsuccessful solution  :-(
 .... 9 ........................ 1 pts ............... successful solution    :-)
 ... 10 ........................ 2 pts ............... successful solution    :-D

At least 13 points is necessary to obtain to the final credit. It does not matter how many of which homeworks one solves.
All tasks are required to be developed separately while avoiding plagiarism, see plagiarism.
A student who can not continually fulfill the requirements of the subject because of declared important reasons (illness, study trip, etc), needs to make an agreement with his/her seminar assistent of the lecture on an individual treatment conditions of completing the course.

Dates and locations of examinations
They will be announced at the end of the semester.

Programming part of exam(0 - 12 points), acceptable minimum 6 points
It includes one programming task which must programmed and submitted by the student during the examination. The task solution is evaluated in the same way as any other tasks during the semester, the solution must function properly for at least 6 out of 12 test files at the examination. Each test file represents one grade point. Time for programming is 4-5 hours. Solutions can be provided in any language of Java/C/C++.
During the practical part of the applicant can use any printed or electronic material on CD/DVD/flash drive, which he/she brings himself. Any access to the public internet sites is denied with the exception of cw.felk.cvut.cz upload system during the examination. Working with the upload system, i.e. entering and submitting jobs is the same as it is in the semester.

Theoretical part of exam (0 - 12 points), acceptable minimum 6 points
In the theoretical part the student receives several questions and prepares a written outline of answers to them or a more detailed answer, if a specific question requires it. The answers will be discussed with the examiner, who determines the final rating. The student must obtain at least 6 of the possible 12 points.

The classification scheme
The rating of the student is proposed after a successful completion of practical and theoretical part of the exam. The rating points are summed from points received from the solutions of programming tasks in the semester, points received from the programming part of the exam, and points received from the theoretical part. The sum of points corresponds to a grade according to the following table:

 Points range:
 ---------------------------------
 homework problems:   13 - 24 pts
 programming exam:     6 - 12 pts
 theoretical exam:     6 - 12 pts
 ---------------------------------
 Total:               25 - 50 pts    

 Total sum
 of points         grading
   0 -- 24           F, failed exam attempt
  25 -- 29           E
  30 -- 34           D
  35 -- 39           C
  40 -- 44           B
  45 -- 53           A

Additional examination trials
A student who does a retake and succeeded in the previous exam in either its practical or theoretical part, may not participate in this part again, the points are completely transferred to the retake. He/she may also try to improve his/her performance and to participate in this section again, the final score is then counted from the better performance trial. These rules apply to all of these exam retake trials.

We wish you good luck and determination.

Marko Genyk-Berezovskyj	Daniel Průša

Marko Genyk-Berezovskyj