Computing desk
< May 25	<< Apr \| May \| Jun >>	May 27 >

Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

May 26

proving that a recursive algorithm creates a balanced binary tree from a sorted array

Hello,

The following Python function receives an sorted array and returns a balanced binary tree. it creates the root as the middle value of the array, and then creates left and right subtrees by recursively applying the function on left and right sub-arrays:

(the method BinaryTree(rootValue) creates a binary tree root with rootValue as a value. left and right subtrees are initialized as None.)

def SortedArrayToBalancedTree(sortedArray):
   l = len(sortedArray)
   if l==0: return None
   mid = l/2
   t = BinaryTree(sortedArray[mid]) 
   t.left = SortedArrayToBalancedTree(sortedArray[:mid])
   t.right = SortedArrayToBalancedTree(sortedArray[mid+1:])
   return t

I intuitively understand how it works, but how can I prove that this algorithm actually yields a balanced tree?

Thanks! 31.154.135.123 (talk) 08:09, 26 May 2016 (UTC)[reply]

First prove what happens with a null array, and what happens with a single element array. Then show that if the function works making a balanced tree for length <n that it will work for length n also. A proof by induction then shows that it works for all lengths of input. Graeme Bartlett (talk) 10:52, 26 May 2016 (UTC)[reply]

Thank you, but should the induction be on the size of the array or on the height of the tree? 31.154.135.123 (talk) 21:15, 26 May 2016 (UTC)[reply]

That would be the size of the array, as that is the input. Graeme Bartlett (talk) 21:48, 26 May 2016 (UTC)[reply]

VB Class Interests

This is purely an opinion-seeking question... Background: VB classes in university are geared towards people who have no interest in learning to program. It is all mind-numbingly boring repetition with no relevance to the real world. Question: I have been tasked with taking over VB programming this fall. It is historically the most abhorred class in the curriculum. I know that most people who answer questions here know how to program. If you were stuck in a VB class, what (if anything) could the professor do to make the class bearable? I personally cannot even make it through the slides that have been used for the last five years without pleading for a quick and sudden death. 209.149.114.20 (talk) 15:41, 26 May 2016 (UTC)[reply]

You mean Visual Basic right? I'd structure the class so that smaller stand-alone assignments can be snapped together at the end. Here's [1] an interesting implementation of Zelda in VB, here [2] another random game tutorial. So I guess my suggestion is 1)small assignments that can be utilized later 1b) At some point you'll have to release working examples to not screw over people who messed up the first assignments 2) video games. 3)... 4) a less crappy VB class! Also maybe consider having them make Twitter bots like so: [3]. SemanticMantis (talk) 17:50, 26 May 2016 (UTC)[reply]

Yes, VB is Visual Basic. Thanks for the simple game link. I teach all other programming classes as a sequence of assignments that complete a larger project. I will see if I can simplify the game to their level. 209.149.114.20 (talk) 18:55, 26 May 2016 (UTC)[reply]

I would recommend asking them to create malware or non-malicious jokeware (not necessarily destructive stuff and not necessarily virii, but just fun and creative ways to mess with a computer user, like taking a screenshot and setting that as the desktop background). I assure you that this will make some students far more interested than they would be if you would ask them to create a basic game. Another famous example is a message box where the OK button moves away when the mouse comes close to it. When they understand the basics they can create a server and a client that allows them to mess with their friends over a LAN, e.g. opening the DVD-tray, flipping the screen upside down, switching the mouse buttons etc. etc.. The Quixotic Potato (talk) 20:41, 27 May 2016 (UTC)[reply]

This sounds to me like teaching chemistry by simply showing kids how to blow stuff up. 209.149.114.20 (talk) 12:13, 30 May 2016 (UTC)[reply]

Emulating Nokia

I've been thinking about old Nokia cellphone games, and the time I've spent playing them, I was looking for a way to play this games on computer too, but I've not found emulators or system images, there's an ARM emulator, but I wouldn't know how to make it play Symbian. There's this game called Space Impact, I've been looking for it, with no success, where can I find it? --186.155.48.247 (talk) 18:02, 26 May 2016 (UTC)[reply]

Here [4] is a video of a PC port of the game. We also have some info at Space_Impact#Clones_and_remakes. SemanticMantis (talk) 18:09, 26 May 2016 (UTC)[reply]