Examination

In order to pass the course, you need to do the following:

• Pass the labs.
• Pass the exam.

The final grade is the grade from the exam.

Helping material during the exam: an A4-sheet with handwritten notes.

Have a look at old exams.

The exam is on Friday Jan. 16th, 14:00 - 18:00 in the M building.

The exam review (granskning) in on Monday Feb. 2nd, 12:00 - 14:00 in room 6128 from the EDIT building.

Rules for the exam:

• Acceptable aids: one handwritten A4 paper with any notes you may find handy.
• Bring your photo ID and student card.

The exam will cover the following topics:

• Complexity Analysis. Best and worst case scenarios. Time and space complexity. Complexity of recursive programs.
• Dynamic arrays, arrays.
• Sorting - insertion sort, merge sort, quick sort, heap sort, bucket sort. Complexities.
• Linked lists, stacks, queues.
• Priority queues, heaps, binary heaps, leftist heaps.
• Hash tables.
• Graphs (Not Kosaraju's algorithm, not shortest path algorithm for negative weights).
• Minimum Spanning Trees - Kruskal and Prim's algorithm
• Trees, binary trees, binary search trees, tree traversal.
• Balanced binary search trees - AVL and Red-Black trees.
• Knowledge from Lab 1, 2 and 3.

The assignments can be solved in either Java, Haskell or pseudocode and don't require in-depth knowledge of Java/Haskell which has not been covered in the course.

More about the structure of the exam here.

Differences from DAT036:

• Binomial heaps are replaced by leftist heaps
• No splay trees, more about red-black trees instead
• Less about amortized complexity

In case the new content appears in the exam, DAT036 students will get alternatives that use the alternative data structures (binomial heaps and splay trees).

Grades on the exam

• As usual for Chalmers exams, you need a grade of 3, 4 or 5 to pass.

• The assignments could consist of several parts, corresponding to grade 3, 4 and 5.

  In order to get a score of 4, you need to solve the part for grade 3 and the part for grade 4.

  In order to get a score of 5, you need to solve all the parts of the assignment.

  If an assignment is not divided into parts, then it is of grade 5. This means that you could either get a score of 5 by solving it correctly, and partial solutions won't get points.

• In order to get grade K you need to solve at least K assignments, of at least score K from the exam. For example, for grade 4, you need 4 assignments, all of score 4 or 5.

Dugga and Final Exam

The results from the dugga will improve your final grade in the following manner:

• If you solved assignment with number N in the dugga, you don't need to solve assignment N in the exam and you will get a score of 5 for it.

  If you solve assignment N again, this won't count, since the grade for assignment N = maximum {dugga, final exam} and solving it twice won't count as 2 assignments.

• Only the results from the duggas of this year will be taken into account.

There will be an (optional) partial exam on Monday Dec. 1st at 10:00 in HC4, instead of the usual lecture. If you pass the nth question on the partial exam, you do not need to solve the nth question on the regular exam. Passing a question on both the partial and the final exam does not give you any additional benefits. Unlike the regular exam, the dugga is not anonymous.

In order to pass a question on the exam it must be completely correct, with no mistakes save for the most inconsequential. The partial exam may be graded more strictly than the final exam.

Note that your results on the dugga can only improve your final grade, never lower it.

The results of the partial exam will (tentatively) be available about a week thereafter.

The dugga will cover the following topics:

• Complexity Analysis. Best and worst case scenarios. Time and space complexity. Complexity of recursive programs.
• Dynamic arrays, arrays.
• Sorting - insertion sort, merge sort, complexities.
• Linked lists, stacks, queues.
• Priority queues, heaps, binary heaps, leftist heaps.
• Hash tables.
• Graphs (Not Kosaraju's algorithm, not shortest path algorithm for negative weights).
• Trees, binary trees, binary search trees, tree traversal (Friday 28/11).
• Knowledge from Lab 1 and Lab 2.

The assignments can be solved in either Java, Haskell or pseudocode and don't require in-depth knowledge of Java/Haskell which has not been covered in the course.

Rules for the partial exam:

• Acceptable aids: one handwritten A4 paper with any notes you may find handy.
• Partial exam starts 10:00 sharp; late arrivals will not be permitted into the exam hall.
• If you leave the exam hall, you will not be permitted back in.
• Cheating on the partial exam is just as serious as on the final exam, and will be dealt with accordingly.
• Bring your photo ID.