| (11 intermediate revisions by 3 users not shown) | |||
| Line 2: | Line 2: | ||
| − | =Rhea Section for ECE 608 Professor Ghafoor, Spring 2009= | + | =Rhea Section for [[ECE608|ECE 608]] Professor Ghafoor, Spring 2009= |
<div style="background: #eef; border: 1px solid #448; border-left: 4px solid #338; width: 30em; padding: 2em; margin: auto; text-align: center;"> | <div style="background: #eef; border: 1px solid #448; border-left: 4px solid #338; width: 30em; padding: 2em; margin: auto; text-align: center;"> | ||
If you create a page that belongs to this course, please write | If you create a page that belongs to this course, please write | ||
| Line 11: | Line 11: | ||
</div> | </div> | ||
| − | == | + | == What's New== |
| + | *[[Discussion about the availability of hw solutions online| Discussion about the availability of hw solutions online]] <B> - <SPAN STYLE="text-decoration: blink;color:red"> New discussion! </span> </B> | ||
| + | *[[Plus_or_minus_discussion|Are you for or against using plus or minus grades?]] | ||
| + | |||
==TA== | ==TA== | ||
| Line 32: | Line 35: | ||
===Reviewed Algorithms=== | ===Reviewed Algorithms=== | ||
| + | * [[Heap sort]] | ||
* [[Insertion sort]] | * [[Insertion sort]] | ||
* [[Merge sort]] | * [[Merge sort]] | ||
| Line 38: | Line 42: | ||
Area to post questions, set up study groups, etc. | Area to post questions, set up study groups, etc. | ||
| + | |||
| + | |||
| + | == 4-4 == | ||
| + | Attempted solution for 4-4 part (d): | ||
| + | <math>T(n) = 3T(n/3+5)+n/2</math> | ||
| + | |||
| + | We use the iteration method. | ||
| + | Start with recursion tree: | ||
| + | * Root node: <math>\frac{n}{2}</math> | ||
| + | * First level: <math>3\frac{\frac{n}{3}+5}{2}</math> | ||
| + | * Second level: <math>9\frac{\frac{n}{3}+5}{4}</math> | ||
| + | * i<sup>th</sup> level: <math>\left(\frac{3}{2}\right)^i\left(\frac{n}{3}+5\right)</math> | ||
| + | |||
| + | <i>Note:</i> above is not correct | ||
| + | |||
| + | <math>\left(\frac{n}{3}+5\right)\sum{\left(\frac{3}{2}\right)^i}</math> | ||
| + | |||
| + | |||
| + | |||
| + | == Randomization (and prob 5.3-3) == | ||
| + | As we've seen, Permute-With-All does not produce a uniform random permutation. Curious to see how it affects the distribution of permutations? Here's an experiment with the erroneous randomization algorithm: | ||
| + | [[False randomize]] | ||
| + | |||
| + | In the solution given for this problem, their argument is that <math>n^n</math> is not a multiple of <math>n!</math> for <math>n\ge 3</math>. Intuitively, <math>n!</math> for <math>n\ge 3</math> includes more than one prime factor, namely 2 and 3, whereas <math>n^n</math> of course has only one. | ||
| + | |||
| + | |||
| + | |||
| + | == Prob 5.4-5 == | ||
| + | Is there an intuitive explanation as to why the nested summations in the solution evaluate to a "combination"? | ||
Latest revision as of 16:45, 22 October 2010
Contents
Rhea Section for ECE 608 Professor Ghafoor, Spring 2009
If you create a page that belongs to this course, please write
[[Category:ECE608Spring2009ghafoor]]
at the top of the page. You may also add any other category you feel is appropriate (e.g., "homework", "Fourier", etc.).
What's New
- Discussion about the availability of hw solutions online - New discussion!
- Are you for or against using plus or minus grades?
TA
Hamza Bin Sohail Office Hours: Tuesday & Thursday 4:30-5:30PM in EE306
Course Website
http://cobweb.ecn.purdue.edu/~ee608/
Newsgroup
On the news.purdue.edu server: purdue.class.ece608
One way to access: SSH to a server at Purdue (ie expert.ics.purdue.edu) and type "lynx news.purdue.edu/purdue.class.ece608"
On Ubuntu, you can use the "Pan" newsreader.
- "sudo apt-get install pan"
- Set "news.purdue.edu" as the server. You do not need to enter login information.
- Type "purdue.class.ece608" in the box in the upper-left of the screen.
- After a delay (half a minute?) the newsgroup will appear in the left pane. You can right click the group to "subscribe".
Reviewed Algorithms
Discussions
Area to post questions, set up study groups, etc.
4-4
Attempted solution for 4-4 part (d): $ T(n) = 3T(n/3+5)+n/2 $
We use the iteration method. Start with recursion tree:
- Root node: $ \frac{n}{2} $
- First level: $ 3\frac{\frac{n}{3}+5}{2} $
- Second level: $ 9\frac{\frac{n}{3}+5}{4} $
- ith level: $ \left(\frac{3}{2}\right)^i\left(\frac{n}{3}+5\right) $
Note: above is not correct
$ \left(\frac{n}{3}+5\right)\sum{\left(\frac{3}{2}\right)^i} $
Randomization (and prob 5.3-3)
As we've seen, Permute-With-All does not produce a uniform random permutation. Curious to see how it affects the distribution of permutations? Here's an experiment with the erroneous randomization algorithm: False randomize
In the solution given for this problem, their argument is that $ n^n $ is not a multiple of $ n! $ for $ n\ge 3 $. Intuitively, $ n! $ for $ n\ge 3 $ includes more than one prime factor, namely 2 and 3, whereas $ n^n $ of course has only one.
Prob 5.4-5
Is there an intuitive explanation as to why the nested summations in the solution evaluate to a "combination"?
