Algorithms exercise: Find mistakes in Wikipedia articles

Rene — Wed, 11 Jan 2012 14:47:20 +0000

Today I started an experiment I created an excercise for coursework in algorithms and data structures that is very unusuale and many people have been criticle if this was a good idea. The idea behind the exercise is that studens should read wikipedia articles to topics related to lectures and find mistakes or suggest things that could be improoved. Thereby I hope that people will do something that many people in science don’t do often enough: Read something critically and carefully and question the things that you have learnt. (more discussions after the exercise)
Read the following wikipedia articles:

Find at least 5 mistakes or passages that could be improved. Write down what is wrong or what could be improved. Give a justification for your statements and write down your suggested new version of this very passage.
To get inspired you can find mistakes by looking at the discussion page of the articles or at the version history. You might also be able to look the same article in versions of other languages!
Here are some example types / things that could possibly be improoved:

pure mistakes
semantics of links
semantics of pictures
articles could explain easy concepts in difficult words
missing cites
missing links to original scientific work
…

Further discussion
I am really excited how many students will try to do this exercise and how well it is accapted and what the quality of the answers will be…
I would also love to receive your feedback, thoughts and comments about this kind of exercise! Mabe you have some ideas that could be extended or you asked students to do similar coursework?

balanced binary search trees exercise for algorithms and data structures class

Rene — Tue, 29 Nov 2011 14:20:40 +0000

I created some exercises regarding binary search trees. This time there is no coding involved. My experience from teaching former classes is that many people have a hard time understanding why trees are usefull and what the dangers of these trees is. Therefor I have created some straight forward exercises that nevertheless involve some work and will hopefully help the students to better understand and internalize the concepts of binary search tress which are in my oppinion one of the most fundamental and important concepts in a class about algorithms and data structures.

Part A: finding elements in a binary search tree – 1 Point

You are given a binary search tree and you know the root element has the value 2. Considering that the path to for finding an element in the tree is unique decide which of the following two lists can be an actual traversal part in order to receive the element 363 from the binary search tree? Why so?

2, 252, 401, 398, 330, 344, 397, 363
2, 252, 397, 398, 330, 344, 401, 363

Part B: Create binary search trees – 1 Point

You are given an empty binary search tree and two lists of the same elements.

10, 20, 5, 15, 2, 7, 23
10, 5, 7, 2, 20, 23, 15

For both lists draw all the trees that are created while inserting one element after the other one.

Part C: skewed binary search trees and traversing trees – 1 Point

Compare the trees from part B to the tree you would get if inserting the numbers in the order of 2, 5, 7, 10, 15, 20, 23
To understand the different tree traversals please give the result of the inorder and preorder traversal applied to the trees from part B and C.

Part D: Balanced binary search trees. Counting Permutations – 2 Point

We realize that trees can have different topologies as soon as the order of the inserted items changes. Since balanced trees are most desired your task is to count how many permutations of our 7 elements will lead to a balanced binary search tree!
To do so it is sufficient to write down all the permutations that will lead to a balanced binary search tree. But you do not have to do this explicitly. It is also ok to write down all classes and cases of permuations and count them.
Compare the number to all permutations of 7 elements (= 7!) and give the probability to end up with a balanced binary search tree when given a random permutation of 7 different elements.

Part E: A closed formular for the probability to create a balanced binary search tree – 2 Extra Points

Your task is to find and prove a formular that states the number of permutations of the natural numbers 1, 2,…, 2^k-1 such that inserting the numbers will create a balanced binary search tree.
Give a closed forumlar for the probability P(k) to end up with a balanced search tree. Give the explicit results for k = 1,…,10