Notes
Notes - notes.io |
lars, 4 pounds), (16 dollars, 1 pounds), (8 dollars, 8 pounds) and (20 dollars, 5 pounds) and
the thief can take at most 12.6 pounds. Use the greedy algorithm to get the items that
maximize the total value of those items.
3-8 3/8=.375
5-4 5/4=1.25
16-1 =16
8-8 =1
20-5 =4
12.6 max tot: 12*(16/1) + 0.6(20/5) = 194.4
There are 8 lectures with starting time and finish time as fol-
lows: (3, 8), (7, 9), (2, 4), (10, 11), (10, 12), (4, 7), (4, 6), and (5, 7). Give the schedule that
minimizes the number of classrooms used.
(2,4) (4,6) (7,9)
(3,8) (10,11)
(4,7) (10,12)
(5,7)
http://www.cs.rit.edu/~lr/courses/alg/student/1/minspan.pdf
Analysis of Prim's Algorithm
Running Time = O(m + n log n) (m = edges, n = nodes)
If a heap is not used, the run time will be O(n^2) instead of O(m + n log n).
However, using a heap complicates the code since you’re complicating the
data structure. A Fibonacci heap is the best kind of heap to use, but again, it
complicates the code.
Unlike Kruskal’s, it doesn’t need to see all of the graph at once. It can deal
with it one piece at a time. It also doesn’t need to worry if adding an edge
will create a cycle since this algorithm deals primarily with the nodes, and
not the edges.
For this algorithm the number of nodes needs to be kept to a minimum in
addition to the number of edges. For small graphs, the edges matter more,
while for large graphs the number of nodes matters more.
Analysis of Kruskal's Algorithm
Running Time = O(m log n) (m = edges, n = nodes)
Testing if an edge creates a cycle can be slow unless a
complicated data structure called a “union-find” structure is
used.
It usually only has to check a small fraction of the edges, but in
some cases (like if there was a vertex connected to the graph
by only one edge and it was the longest edge) it would have to
check all the edges.
This algorithm works best, of course, if the number of edges is
kept to a minimum.
|
|
Notes.io is a web-based application for taking notes. You can take your notes and share with others people. If you like taking long notes, notes.io is designed for you. To date, over 8,000,000,000 notes created and continuing...
With notes.io;
- * You can take a note from anywhere and any device with internet connection.
- * You can share the notes in social platforms (YouTube, Facebook, Twitter, instagram etc.).
- * You can quickly share your contents without website, blog and e-mail.
- * You don't need to create any Account to share a note. As you wish you can use quick, easy and best shortened notes with sms, websites, e-mail, or messaging services (WhatsApp, iMessage, Telegram, Signal).
- * Notes.io has fabulous infrastructure design for a short link and allows you to share the note as an easy and understandable link.
Fast: Notes.io is built for speed and performance. You can take a notes quickly and browse your archive.
Easy: Notes.io doesn’t require installation. Just write and share note!
Short: Notes.io’s url just 8 character. You’ll get shorten link of your note when you want to share. (Ex: notes.io/q )
Free: Notes.io works for 12 years and has been free since the day it was started.
You immediately create your first note and start sharing with the ones you wish. If you want to contact us, you can use the following communication channels;
Email: [email protected]
Twitter: http://twitter.com/notesio
Instagram: http://instagram.com/notes.io
Facebook: http://facebook.com/notesio
Regards;
Notes.io Team
