Computer Science > LECTURE NOTES > Monash University FIT 2004 SuperHumanTiger3477 (All)

Monash University FIT 2004 SuperHumanTiger3477

Document Content and Description Below

FIT2004 Algorithms and Data Structures The original version of the course notes were developed by Daniel Anderson. Over the course of the years, additions, removals and modifications were done by ... members of FIT2004’s teaching teams including: Nathan Companez, Rafael Dowsley. a b c d e f g 5 8 2 1 4 16 4 8 9 10 d a f b e c s 0 2 4 6 9 7 5 7 10 3 2 1 8 5 4 7 6 9 Last updated February 16, 2023 Contents 1 Analysis of Algorithms 1 1.1 Program Verification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1.1 Arguing Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.2 Arguing Termination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Complexity Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.1 Common Recurrence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 Asymptotic Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4 Measures of Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.5 Analysis of Basic Sorting Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.5.1 Selection Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.5.2 Insertion Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.5.3 Algorithms’ Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2 Divide and Conquer 15 2.1 Karatsuba’s Multiplication Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2 Merge Sort (Revision) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.3 Counting Inversions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3 Fast Sorting Algorithms 23 3.1 Heapsort (Revision) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.2 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.3 Complexity Lower Bounds for Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.4 Sorting Integers Fast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.4.1 Counting Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.4.2 Radix Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4 Order Statistics and Selection 41 4.1 Order Statistics and the Selection Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.2 The Quickselect Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 4.3 Randomised Pivot Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.4 Median of Medians . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 5 Graphs Basics 49 5.1 Modelling with Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 5.2 Representation and Storage of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 5.3 Graph Traversal and Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 5.3.1 Depth-First Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 5.3.2 Finding Connected Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 5.3.3 Cycle Finding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 5.3.4 Breadth-First Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 5.4 Shortest Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 5.4.1 Properties of Shortest Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 5.4.2 Shortest Path Problem Variants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 5.4.3 Unweighted Shortest Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 5.5 The Topological Sorting Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 5.5.1 Kahn’s Algorithm for Topological Sorting . . . . . . . . . . . . . . . . . . . . . . . . . 66 5.5.2 Topological Sorting Using DFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 5.6 Incremental Graph Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 5.6.1 The Union-Find Disjoint-Set Data Structure . . . . . . . . . . . . . . . . . . . . . . 68 6 Greedy Algorithms 73 6.1 Shortest Path in Graphs with Non-negative Weights . . . . . . . . . . . . . . . . . . . . . . 73 6.2 Minimum Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 6.2.1 Prim’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 6.2.2 Kruskal’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 7 Dynamic Programming 83 7.1 The Key Elements of Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 7.2 Top-down vs. Bottom-up Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . . 87 7.3 Reconstructing Optimal Solutions to Optimisation Problems . . . . . . . . . . . . . . . 89 7.4 The Unbounded Knapsack Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 7.5 The 0-1 Knapsack Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 7.6 The Edit Distance Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 7.7 Matrix Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 7.8 The Space-Saving Trick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 8 Dynamic Programming Graph Algorithms 101 8.1 Shortest Paths with Negative Weights . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 8.2 The All-Pairs Shortest Path Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 8.2.1 The Floyd-Warshall algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 8.3 Transitive Closure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 8.4 The Critical Path Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 9 Network Flow 111 9.1 The Ford-Fulkerson Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 9.1.1 The Residual Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 9.1.2 Augmenting Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 9.1.3 Implementation Using Depth-First Search . . . . . . . . . . . . . . . . . . . . . . . 116 9.2 The Minimum Cut Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 9.2.1 The Min-cut Max-flow Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 9.3 Bipartite Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 9.4 Circulations with Demands and Lower Bounds . . . . . . . . . . . . . . . . . . . . . . . . . 123 10 Hashing and Hashtables 131 10.1 Hashtables (Revision) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 10.2 What is a Good Hash Function? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 10.3 Hashing Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 10.4 Hashing Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 10.5 Universal Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 10.6 Cuckoo Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 11 Balanced Binary Search Trees 141 11.1 AVL Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 11.1.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 11.1.2 Rebalancing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 12 Prefix Tries and Suffix Trees 147 12.1 The Prefix Trie / Retrieval Tree Data Structure . . . . . . . . . . . . . . . . . . . . . . . . . . 147 12.1.1 Applications of Tries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 12.2 Suffix Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 12.2.1 Building a Suffix Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 12.2.2 Applications of Suffix Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 13 Suffix Arrays 155 [Show More]

Last updated: 6 months ago

Preview 1 out of 161 pages

Reviews( 0 )

Recommended For You

 Physiology> LECTURE NOTES > Gastrointestinal physiology- GI motility (All)

preview
Gastrointestinal physiology- GI motility

This document is regarding gastrointestinal physiology- stomach, small intestinal, large intestinal and enteric nervous system. GI motility is defined by the movements of the digestive system, and...

By Dan18268 , Uploaded: Jan 17, 2024

$7

 BioChemistry> LECTURE NOTES > C785 BIOCHEMISTRY NOTES (WESTERN GOVERNORS UNIVERSITY) (All)

preview
C785 BIOCHEMISTRY NOTES (WESTERN GOVERNORS UNIVERSITY)

Amino acid structure Amino acid types • Hydrophobic: ending in CHs • Polar: ending OH, NH, or SH • Charged: ending in a charge • Flow Chart: Is there a charge? → Is there S, N, or O? → Hydrophob...

By Professor Marjorie Barker , Uploaded: Sep 25, 2022

$5.5

 Management> LECTURE NOTES > Mnb1601 Summarise - Lecture Notes Unisa (All)

preview
Mnb1601 Summarise - Lecture Notes Unisa

MNB1601 NOTES OPERATIONS MANAGEMENT The operations function is that function of the business aimed at executing the transformation process. The importance of operations management:  It can reduce the...

By ACADEMICTUTORIAL , Uploaded: Nov 29, 2021

$1.5

 *NURSING> LECTURE NOTES > Mark Klimek Lecture Notes NCLEX REVIEW (All)

preview
Mark Klimek Lecture Notes NCLEX REVIEW

Mark Klimek Lecture Notes NCLEX REVIEW

By ACADEMICTUTORIAL , Uploaded: Nov 30, 2021

$3

 Psychology> LECTURE NOTES > PSYCH 104 Lecture Notes Chapters-1-7 & 11 (All)

preview
PSYCH 104 Lecture Notes Chapters-1-7 & 11

PSYCH 104 Lecture Notes Chapters-1-7 & 11

By ACADEMICTUTORIAL , Uploaded: Nov 30, 2021

$2.5

 *NURSING> LECTURE NOTES > NR 283 Pathophysiology notes ch 1,2, 21 (All)

preview
NR 283 Pathophysiology notes ch 1,2, 21

NR 283 Pathophysiology notes ch 1,2, 21

By ACADEMICTUTORIAL , Uploaded: Mar 16, 2022

$3.5

 *NURSING> LECTURE NOTES > NR 509 Adv Physical Assessment- Midterm Notes (All)

preview
NR 509 Adv Physical Assessment- Midterm Notes

NR 509 Adv Physical Assessment- Midterm Notes Soap note example for the patient. This is a great start to your learning and practice.

By ACADEMICTUTORIAL , Uploaded: Mar 20, 2022

$4

 *NURSING> LECTURE NOTES > Mark klimek lecture 1-12 notes (All)

preview
Mark klimek lecture 1-12 notes

Mark Klimek 1-12 notes for NCLEX test review.

By ACADEMICTUTORIAL , Uploaded: Mar 16, 2023

$4.5

 *NURSING> LECTURE NOTES > Mark Klimek Test taking strategies (All)

preview
Mark Klimek Test taking strategies

Mark Klimek Test taking strategies Lab Values: DEADLY DANGEROUS:  Elevated K+ ( >6) - Hold K+, Assess heart, Prepare Kayexalate/D5W, Call Dr.  Elevated pH ( >6) - Assess Vitals, Call doctor ...

By Kirsch , Uploaded: Mar 14, 2023

$9

 Biology> LECTURE NOTES > Lecture Materials > University of Louisville BIO 240 Ch 11 Cell Signaling Notes (All)

preview
Lecture Materials > University of Louisville BIO 240 Ch 11 Cell Signaling Notes

University of Louisville BIO 240 Ch 11 Cell Signaling Notes Lecture Notes  Local and Long Distance Signaling o Communication between cells using gap junctions (animal cells) or plasmodesmata (p...

By QuizMaster , Uploaded: Aug 02, 2022

$4

$8.00

Add to cart

Instant download

Can't find what you want? Try our AI powered Search

OR

GET ASSIGNMENT HELP
38
0

Document information


Connected school, study & course



About the document


Uploaded On

Aug 16, 2023

Number of pages

161

Written in

Seller


seller-icon
AGRADES

Member since 2 years

8 Documents Sold


Additional information

This document has been written for:

Uploaded

Aug 16, 2023

Downloads

 0

Views

 38

THE BEST STUDY GUIDES

Avoid resits and achieve higher grades with the best study guides, textbook notes, and class notes written by your fellow students

custom preview

Avoid examination resits

Your fellow students know the appropriate material to use to deliver high quality content. With this great service and assistance from fellow students, you can become well prepared and avoid having to resits exams.

custom preview

Get the best grades

Your fellow student knows the best materials to research on and use. This guarantee you the best grades in your examination. Your fellow students use high quality materials, textbooks and notes to ensure high quality

custom preview

Earn from your notes

Get paid by selling your notes and study materials to other students. Earn alot of cash and help other students in study by providing them with appropriate and high quality study materials.

WHAT STUDENTS SAY ABOUT US


What is Browsegrades

In Browsegrades, a student can earn by offering help to other student. Students can help other students with materials by upploading their notes and earn money.

We are here to help

We're available through e-mail, Twitter, Facebook, and live chat.
 FAQ
 Questions? Leave a message!

Follow us on
 Twitter

Copyright © Browsegrades · High quality services·