Work on homework in advance; Algorithms: Design and Analysis Week 2

Schedule

Let's start with writing a small program, using whatever language you prefer. Panda is confident. Whatever score she gets, she thinks that's the standard score a student should get. A score lower than hers is put into "not good enough" group. A score higher than hers is put into "excessive" group.

Let's describe the above using an array, [3, 4, 1, 2, 5]. The first item, 3, is Panda's score. She re-arranges the array into [2, 1, 3, 4, 5], i.e. scores lower than hers are put on the left and scores higher than hers are put on the right. Note that 2, 1 is not ordered. From Panda's view, it doesn't matter. They just belong to "not good enough" group. Similarly, 4, 5 can be ordered as 5, 4. It doesn't matter. They just belong to "excessive" group.

In short, your program will pick the first element of an array as a dividing item, then put elements smaller than the dividing item to the left side, put elements bigger than the dividing item to the right side,

i.e.

re-arrange

[3, 4, 1, 2, 5]

to

[2, 1, 3, 4, 5]

To put it in a general way, re-arrange

[first element, other elements]

to

[elements smaller than the dividing item, the dividing item, elements bigger than the dividing item]

Note that elements in the left subarray or the right subarray don't need to be ordered.

After writing and discussing the program, we'll discuss each of the 5 questions in problem set-2:

https://class.coursera.org/algo-008/quiz/attempt?quiz_id=32

After that, we'll discuss each of the 3 programming questions:

https://class.coursera.org/algo-008/quiz/attempt?quiz_id=33

----

We had a great discussion on August 2 (week 1). Instead of talking about answers to the homework, we discussed the key ideas in the lectures, problem sets, and programming questions.

Let's continue to meet for 5 more weeks.

Algorithm is the foundation of hacking skill. Work on homework in advance. Come to discuss homework:
https://class.coursera.org/algo-008/wiki/Syllabus