Summary and Flashcards - Data Structures and Algorithm
16 views 0 purchase
Course
Data Structures and Algorithms (COM1029)
Institution
University Of Surrey (UNIS)
In depth coverage of algorithms and data structures. Covers algorithmic efficency, time and space complexity for all O notation (big 0, little 0, omega). Linear, quadratic to exponential algorithms. Kadane's algorithm, brute force algorithm. Summary of all sorting algorithms, trees (AVL, B-trees), ...
https://www.inf.ed.ac.uk/teaching/courses/inf2b/algnotes/note02.pdf
(Data Structures and Algorithms Notes | University of Edinburgh)
https://sd.blackball.lv/library/Introduction_to_Algorithms_Third_Edition_(2009
).pdf
(Introduction to Algorithms Book)
https://www.vlebooks.com/Product/Index/2025761?page=0
(Algorithmics Book)
https://www.cs.bham.ac.uk/~jxb/DSA/dsa.pdf
(Data Structures and Algorithms Notes | University of Birmingham)
https://jeffe.cs.illinois.edu/teaching/algorithms/book/Algorithms-JeffE.pdf
(Algorithms Notes)
https://www.geeksforgeeks.org/data-structures/?ref=shm
(Data Structure Notes)
https://www.geeksforgeeks.org/fundamentals-of-algorithms/?ref=shm
(Algorithm Notes)
1) What is an Algorithm? An algorithm is a finite sequence of rigorous
instructions, typically used to solve a class of
specific problems or to perform a computation.
2) What is a Program? A program is a sequence or set of instructions in a
programming language for a computer to
execute.
,3) Why do we analyse algorithms? ● To predict the behaviour of an algorithm
without implementing it on a specific
computer.
● It is much more convenient to have
simple measures for the efficiency of an
algorithm than to implement the
algorithm and test the efficiency every
time a certain parameter in the
underlying computer system changes.
● It is impossible to predict the exact
behaviour of an algorithm. There are too
many influencing factors.
● The analysis is thus only an
approximation; it is not perfect.
● More importantly, by analysing different
algorithms, we can compare them to
determine the best one for our purpose.
Types of Algorithm Analysis:
● Best case
● Worst case
● Average case
Best case: Define the input for which algorithm
takes less time or minimum time. In the best case,
calculate the lower bound of an algorithm.
Example: In the linear search when search data is
present at the first location of large data then the
best case occurs.
Worst Case: Define the input for which algorithm
takes a long time or maximum time. In the worst
case, calculate the upper bound of an algorithm.
Average case: In the average case take all random
inputs and calculate the computation time for all
inputs. And then we divide it by the total number
of inputs.
Average case =
all random case time / total no of case.
,4) What is Algorithm Efficiency? Algorithmic efficiency is a property of an
algorithm which relates to the amount of
computational resources used by the algorithm.
An algorithm must be analysed to determine its
resource usage, and the efficiency of an algorithm
can be measured based on the usage of different
resources.
To measure how efficient an algorithm is,
two resources are commonly considered in
algorithm execution:
5) What is Time Complexity? How do we The time complexity is the computational
measure it? complexity that describes the amount of computer
time it takes to run an algorithm.
Time complexity is commonly estimated by
counting the number of elementary operations
performed by the algorithm, supposing that each
elementary operation takes a fixed amount of
time to perform. Thus, the amount of time taken
and the number of elementary operations
performed by the algorithm are related by a
constant factor.
, 6) How do we use Time Complexity to
Compute the Average of an Array of Size
N?
7) What are Linear Time Algorithms? An algorithm is said to take linear time, or
O(n) time, if its time complexity is O(n).
Informally, this means that the running time
increases at most linearly with the size of the
input.
More precisely, this means that there is a constant
c such that the running time is at most cn for
every input of size n. For example, a procedure
that adds up all elements of a list requires time
proportional to the length of the list, if the adding
time is constant, or, at least, bounded by a
constant.
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller williamdaniel. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $5.97. You're not tied to anything after your purchase.
