(13 intermediate revisions by 9 users not shown)
Line 1: Line 1:
−
= Rhea Section for MA 375 Professor Walther, Spring 2012  =
+
= Rhea Section for [[MA375]] Professor Walther, Spring 2012  =
  
 
Welcome to the [[MA375|MA 375]] course page. Preferred Browser is Firefox.  
 
Welcome to the [[MA375|MA 375]] course page. Preferred Browser is Firefox.  
Line 8: Line 8:
  
 
----
 
----
−
<div style="border-bottom: #448 1px solid; text-align: center; border-left: #338 4px solid; padding-bottom: 2em; margin: auto; padding-left: 2em; width: 30em; padding-right: 2em; background: #eef; border-top: #448 1px solid; border-right: #448 1px solid; padding-top: 2em">
+
<div style="border-width: 1px 1px 1px 4px; border-style: solid; border-color: rgb(68, 68, 136) rgb(68, 68, 136) rgb(68, 68, 136) rgb(51, 51, 136); text-align: center; padding: 2em; margin: auto; width: 30em; background: none repeat scroll 0% 0% rgb(238, 238, 255);">
−
If you cre
+
<br>  
−
<pre>• A covering for Figure 2 is {1, 2, 3, 17}.
+
 
−
• Show the minimum cover for the bipartite graph shown in Figure 2.
+
[Category:MA375Spring2012Walther] at the bottom of the page.  
−
o The cover is {1, 16, 17}.
+
−
Figure 2 Bipartite Graph
+
−
• Examples:
+
−
o Suppose you have a set of interpreters and a set of languages that need to be
+
−
interpreted. Edges represent “can interpret.” We want to find the minimal
+
−
number of interpreters to hire so that you can interpret all languages.
+
−
o Set of people and a set of categories (male, Asian, CS major, single, ...). We want
+
−
to form a committee with representation from all groups.
+
−
• Set cover – given a collection of subsets, find a minimum number of subsets such that
+
−
their union is the universe.
+
−
o Can you see how to map this problem to the bipartite cover problem?
+
−
Nodes for each subset. Nodes for each element. Edges represent “contains.”
+
−
• This ability to map one problem into another is key to using knowledge of “algorithms community.” This is likely the reason why I always try to find similarities between things that seem different (e.g., cleaning up for company).
+
−
• NP-hard – no one has developed a polynomial time algorithm. o Also called intractable or exponential.
+
−
o We use greedy algorithms to approximate.
+
−
• Greedy criterion – Select the vertex of A that covers the largest number of uncovered vertices of B. Also keep a Boolean array that tells whether each node is covered or not.
+
−
o This idea could be implemented via a max tournament tree of “willCover” – take the biggest.
+
−
Shortest Paths
+
−
• Given a digraph with each edge in the graph having a nonnegative cost (or length).
+
−
• Try to find the shortest paths (in a digraph) from a node to all other nodes.
+
−
• Greedy criterion – From the vertices to which the shortest path has not been generated,
+
−
select one that results in the least path length (the smallest one).
+
−
• Have a reached set of nodes and an unreached set of nodes.
+
−
1. Initially, only the start node is reached.
+
−
The Greedy Method Page 4
+
−

+
−
2. Use a min priority queue to store the total path lengths of each of the reached nodes to its successors.
+
−
3. While priority queue is not empty
+
−
Pick the shortest total length node.
+
−
• If it has already been reached, discard.
+
−
• Else count it as reached.
+
−
Enqueue the total path lengths of each of the reached nodes to its
+
−
successors.
+
−
• For example, consider the digraph Figure 3 in and calculate the shortest path.
+
−
Figure 3 Shortest Path
+
−
Minimal Spanning Trees
+
−
• Problem – select a subset of the edges such that a spanning tree is formed and the weight of the edges is minimal.
+
−
• Example – need to connect all sites to sewer system - want to minimize the amount of pipe.
+
−
• Consider the spanning tree shown in Figure 4.
+
−
Figure 4 Spanning Tree
+
−
• Prim’s algorithm
+
−
o Greedy criterion – From the remaining edges, select a least-cost edge whose
+
−
addition to the set of selected edges forms a tree. Tree – set of vertices already in MST
+
−
Succ – set of vertices not in Tree but in Succ[Tree] Place any vertex (to serve as root) in MST.
+
−
The Greedy Method
+
−
Page 5
+
−
1. Find the smallest edge that connects Tree with Succ
+
−
2. Add the edge to the MST and update Tree and Succ
+
−
• Uses a greedy method – obtain a globally optimal solution by means of a locally optimal
+
−
solution.
+
−
• Using Figure 4 and Prim’s algorithm, we add the edges in the following order: (1,6),
+
−
(6,5), (5,4), (4,3), (3,2), and (2, 7).
+
−
• How do we find smallest edge? (sort or priority queue)
+
−
• Kruskal’s algorithm
+
−
o Greedy criterion – From the remaining edges, select a least-cost edge that does not result in a cycle when added to the set of already selected edges.
+
−
Let each vertex be a separate component.
+
−
1. Examine each edge in increasing order of cost.
+
−
2. If edge connects vertices in same component, discard it. Otherwise, add edge to
+
−
MST. Update components.
+
−
• Using Figure 4 and Kruskal’s algorithm, we add the edges in the following order: (1,6),
+
−
(3,4), (2,7), (2,3), (4,5), and (5,6).
+
−
• How do we find smallest edge? (sort or priority queue)
+
−
More Traversals of a Graph or Digraph
+
−
• Tour – visit each vertex in a graph exactly once and finish at the vertex started from.
+
−
• Eulerian tour – find a path/tour through the graph such that every edge is visited
+
−
exactly once. (Easy – check nodal degree; if all are even, it is possible.)
+
−
• Hamiltonian tour – find a path through the graph such that every vertex is visited
+
−
exactly once. (NP complete)
+
−
• See Figure 5 for different tours.
+
−
Figure 5 Different Tours
+
−
The Greedy Method
+
−
Page 6</pre>  
+
−
at the bottom of the page.  
+
  
−
<span style="color: red; font-size: 20px">OTHERWISE NO CREDIT&nbsp;!</span> (If you use the "Create a child page" button, this should happen automatically...)  
+
<span style="color: red; font-size: 20px;">OTHERWISE NO CREDIT&nbsp;!</span> (If you use the "Create a child page" button, this should happen automatically...)  
 
</div>  
 
</div>  
 
== Links  ==
 
== Links  ==
Line 124: Line 51:
 
For some lovely contributions, see [[Honors Project]] 2011 by Daniel Lee  
 
For some lovely contributions, see [[Honors Project]] 2011 by Daniel Lee  
  
−
{| class="wikitable" border="1"
+
{| border="1" class="wikitable"
 
|-
 
|-
 
! Topic Number  
 
! Topic Number  
Line 133: Line 60:
 
| 1  
 
| 1  
 
| [[Special sequences of numbers MA375S12Walther|Special sequences of numbers]]  
 
| [[Special sequences of numbers MA375S12Walther|Special sequences of numbers]]  
−
| Your Name Here
+
| Antong Li
 
| At Final
 
| At Final
 
|-
 
|-
Line 143: Line 70:
 
| 3  
 
| 3  
 
| [[Mysteries of probability MA375S12Walther|Mysteries of probability]]  
 
| [[Mysteries of probability MA375S12Walther|Mysteries of probability]]  
−
| Your Name Here
+
| Matt Metzger<br>
 
| At Final
 
| At Final
 
|-
 
|-
Line 158: Line 85:
 
| 6  
 
| 6  
 
| [[Explaining a Clay problem MA375S12Walther|Explaining a Clay problem]]  
 
| [[Explaining a Clay problem MA375S12Walther|Explaining a Clay problem]]  
−
| Your Name Here
+
| Stephanie Wicke
 
| At Final
 
| At Final
 
|-
 
|-
Line 173: Line 100:
 
| 9  
 
| 9  
 
| [[Greedy methods MA375S12Walther|Greedy methods]]  
 
| [[Greedy methods MA375S12Walther|Greedy methods]]  
−
| Your Name Here
+
| Yi Mao&nbsp;
 
| At Final
 
| At Final
 
|-
 
|-
 
| 10  
 
| 10  
 
| [[Cantor, sets, and continua MA375S12Walther|Cantor, sets, and continua]]  
 
| [[Cantor, sets, and continua MA375S12Walther|Cantor, sets, and continua]]  
−
| Your Name Here
+
| Qinwen Zhang
 
| At Final
 
| At Final
 
|-
 
|-
Line 197: Line 124:
 
|-
 
|-
 
| 14  
 
| 14  
−
| [[Choose Your Topic MA375S12Walther|Choose Your Topic]]  
+
| [[Choose Your Topic MA375S12Walther|Distinguished/Indistinguished Problem]]  
−
| Your Name Here
+
| Pianpian Cao
 
| At Final
 
| At Final
 
|}
 
|}
Line 244: Line 171:
  
 
[[Category:MA375Spring2012Walther]]
 
[[Category:MA375Spring2012Walther]]
 +
[[Category:MA375]]
 +
[[Category:math]]

Latest revision as of 13:59, 20 September 2012

Rhea Section for MA375 Professor Walther, Spring 2012

Welcome to the MA 375 course page. Preferred Browser is Firefox.




[Category:MA375Spring2012Walther] at the bottom of the page.

OTHERWISE NO CREDIT ! (If you use the "Create a child page" button, this should happen automatically...)

Links

(See more below in Miscellaneous)

First time? Read this general note

corner/How to get started

  • Getting started
    • To start, click the "Help" button above and read what's there.
    • To edit pages, first log in (with your purdue account to create pages. Then click "edit" (under "Page" above) and remember to click "Save Page" after you are done editting.).
    • To get a quick idea what works how, click "edit" on this page to see how to do the things visible on this page.
    • Note that the "edit" mode has a spell-checking feature: look for red-underlined stuff.
  • Creating pages
    • To create a new page named "B" from a page A, go to edit page A and insert the text [[B]]. (Note that "B" is like a web address for a webpage. Each page also has a name, but you can call the link anything (like fancy_title) by typing [[B|fancy_title]] rather than just B. After saving, find the new red link on page A that appeared. When you click it, you'll note you are now on page B (which of course is empty at this point).
    • NOTE: if the "new" link comes out blue, instead of red, you chose a title of an existing page and did not create a new one. The blue link gets you simply to the already existing one. Use distinctive names for your new creations!
    • If you place "Category:MA375Spring2012Walther" enclosed by square brackets on top of a new page it will be parsed by the system as belonging to this course. It can then be searched (for) in a meaningful way.
  • Advanced Rhea techniques
    • You can look at other Rhea pages by clicking "main page" and then "course pages". Especially the ECE pages will get you an idea where one can take Rhea...
    • Do you want to display pages in other pages?

Course Related Material

Your turn! A bonus point opportunity

Students in MA375 (Walther) have the opportunity to earn up to a 5% bonus by contributing a Rhea page on a subject related to linear algebra. To pick a subject, simply write your name next to it. Please no more than one student per subject. Your page will be graded based on content as well as interactions with other people (page views, comments/questions on the page, etc.). The number of links to other courses and subjects will also be taken into account: the more the merrier! Please do not simply copy the lecture notes and do not plagiarize. Read Rhea's copyright policy before proceeding.

For some lovely contributions, see Honors Project 2011 by Daniel Lee

Topic Number Topic Description Student Name Deadline
1 Special sequences of numbers Antong Li At Final
2 Games and mathematics Carolyn Hanes At Final
3 Mysteries of probability Matt Metzger
 At Final
4 Hyperplane arrangements Your Name Here At Final
5 The use of graph theory Yuedong Fang At Final
6 Explaining a Clay problem Stephanie Wicke At Final
7 Coloring problems Chencheng Wang At Final
8 What is homology? Your Name Here At Final
9 Greedy methods Yi Mao  At Final
10 Cantor, sets, and continua Qinwen Zhang At Final
11 Paradoxa come in different kinds Your Name Here At Final
12 What really IS a real number? Edward Gier At Final
13 Making Friends With ... Theresa Blaisdell At Final
14 Distinguished/Indistinguished Problem Pianpian Cao At Final

Note: if you want to make a matrix, look at the source code for this page (click "edit") to see the syntax for the following matrix: $ \left(\begin{array}{cccc}1&2&3&4\\5&6&7&8\end{array}\right) $



  • Discussion of Homework Problems (Just keep adding to it!)


Other Discussions

Exam Related

Miscellaneous

Retrieved from "https://www.projectrhea.org/rhea/index.php?title=2012_Spring_MA_375_Walther&oldid=52293"
Shortcuts
Help Main Wiki Page Random Page Special Pages Log in
Search

Alumni Liaison

Ph.D. 2007, working on developing cool imaging technologies for digital cameras, camera phones, and video surveillance cameras.

Buyue Zhang