(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>
  
== ECE 608 professor Ghafoor Spring 2009  ==
+
== 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 17:45, 22 October 2010


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


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"?

Alumni Liaison

Abstract algebra continues the conceptual developments of linear algebra, on an even grander scale.

Dr. Paul Garrett