Are you a second-year Computer Science student at the University of Cape Town looking for a comprehensive study aid to excel in your practicals, tests, and exams? Look no further! These meticulously crafted digital lecture notes cover data structures.
BEN FROST
GOAT NOTES: DATA STRUCTURES (CSC2001F)
Analysis of Algorithms:
Empirical Analysis:
Running implementations of multiple different algorithms and seeing
which one is fastest.
- Algorithms have to be implemented before any insight on their
speed can be gained.
- Should actual, random or adversarial data be used for testing?
- Scaling of testing can be impractical.
- Important to identify which parts of programs influence speed
most.
Algorithm Analysis:
Carrying out mathematical analysis on algorithms while they are
still abstract.
- Algorithms do not need to be implemented before any insight on
their speed can be gained.
- Enables performance predictions to be made before any code needs
to be implemented or run.
- Important to consider factors such as resource usage including
hardware availability and the chosen programming language.
- Abstract operations need to be identified and counted.
Asymptotic Analysis ~ Determining the bounds on resources needed as
the size of data needing to be processed increases.
Time-Complexity Analysis ~ The consideration of Best, Average &
Worst cases.
N ~ The primary parameter affecting run-time. (typically represents
input data size)
Use some basic operation to create an operation(y) = input(N) data
function: f(N)
When considering functions only consider the N term of the highest
order.
Asymptotic Analysis:
Big-O Notation is a type of asymptotic analysis in which f(N) is
bounded by a multiple of g(N), for N of the highest order.
f(N) is O(g(N)) if g(N) grows as fast or faster than f(N)
1
, BEN FROST
Formal Definition: f(N) is O(g(N)) if there exists a positive real
number M and a real number NO such that:
|f(N)| <= M x g(N) for all N>=NO
Big-O Examples:
Algorithm Trade-Offs:
Time-Space ~ Using additional memory to make operations faster.
~ Using slower operations to reduce memory requirements.
Time-Time ~ Insertion Time vs Search Time
Data Structures:
Intro to Data Structures:
2
, BEN FROST
A data structure is an efficient mechanism to store data and
provide access operations.
- Can be in-memory or on-disk.
- In-memory is faster.
- On-disk is larger & non-volatile.
Maps ~ An abstract data type of items with keys and values that
support two main operations; the insertion of a new item with a
specified key and the search and return of an item with a specified
key. (aka symbol table, dictionary, or associative array)
Array:
- Indices = Integer Keys
- Insert, Search, Remove in constant time.
- Select and Sort in Linear Time. Worst case; iterate
through whole array, N.
Singly Linked List:
- Node = Value & Key
- Search in linear time. Worst case; N. Avg. Case; N/2.
- Search + insert in linear time. Worst case; N. Avg.
Case; N.
Doubly Linked List:
Map Data Structures & Time Complexity:
3
, BEN FROST
Recursion in Data Structures:
Recursive Algorithm ~ Solves a problem by solving one or more
smaller instances of the same problem.
Recursive Method ~ A method that calls itself and has a base case
to end its recursion. Any returned value is stored in the method’s
continuous “stack”.
Any recursive method can generally be converted into an iterative
one and vice versa.
Examples:
Addition of Integers 1 to n:
public int sum(int n) {
Stack when n = 4:
// Base Case:
if (n == 0) R1: 4 + sum(3)
{ R2: 4 + 3 + sum(2)
return 0; R3: 4 + 3 + 2 + sum(1)
} R4: 4 + 3 + 2 + 1 + sum(0)
else R5: 4 + 3 + 2 + 1 + 0
{
// Recursive Call: RESULT = 10
return n + sum(n-1);
}
}
Printing out an Integer Array:
public void print(int start, int stop) {
// Base Case:
4
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 EFT, 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 this summary from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller benfro764. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy this summary for R50,00. You're not tied to anything after your purchase.
