Class notes
CSC 2001F - Data structures Notes
- Institution
- University Of Cape Town (UCT)
This is a comprehensive and detailed note on data structures for CSC 2001F. Quality stuff!! U'll need it!!
[Show more]
Content preview
Modelling Objects in the real world must be modelled as abstract mathematicalentities and basic data types.
Operations How one stores, accesses and manipulates these entities and the
formal meaning of these operations.
Representation How these entities are actually represented in a computer’s memory.
Algorithms Methods used to perform these operations
It’s an abstract/mathematical formalisation about:
o How to store a collection of objects in memory
o Operations that are performed on the data
o Algorithms for those operations
o How time and space efficient those algorithms are
Data storage and operations can be encapsulated by an ADT.
ADT specifies permitted operations as well as guaranteeing time and space.
The user is unconcerned with how it’s implemented.
ADTs are a concept or a convention:
o Not something that directly appears in your code
o Programming language may provide support for ADTs to users
The Dictionary ADT is the most basic and useful of ADTs
Dynamic programming is a method for solving a complex problem by breaking it down into a
collection of sub-problems.
Choice of data structures can make a big difference in speed.
ADTs encapsulate and hide implementation of a data structure, while presenting a clean interface
to other programmers.
Using naïve methods, many sub-problems can be solved only once and used many times over.
, Ordering Put keys into some order so that we know something about how the keys relate to
each other.
Linking Add pointer to each record to find related records quickly.
Pointers let us express relationships between pieces of information.
Pointers of a particular element show the previous and the next element in the list.
Insertion and deletion is easier.
Don’t have to know the size of the data at the start.
Partitioning Divide the records into two or more groups, each group sharing a particular property.
Partitioning usually combines with linking to point to either of the two halves.
Examples:
o Binary space partitioning (BST)
o Bounding volume hierarchies
o Quad-trees
o KD-trees
o Bins. ??
There are many techniques to ensure balance in some form or another.
Binary search guarantees balance b always picking the median.
When using a linked structure, it is not so easy to find the median.
, The running time of an algorithm varies with the input and typically grow with the input size.
Average case is difficult to determine so instead we focus on fining the worst case run time.
How to Measure Running Time?
Method How? Why not?
Experimentally Measure the actual running time of the Actual running time also depends on a
program that implements the algorithm number of other exterior factors that
cannot be accounted for in the test.
The test inputs could not entirely test
the algorithm.
Theoretically By inspecting the pseudo-code, we can Nope. Totes use it actuals.
determine the run time. This uses a high-
level description of the algorithm and
takes in all possible accounts
Running time of any program on a given computer depends on the number of inputs to process:
o Running Time = 𝑇(𝑛) where 𝑛 is the number of data elements.
Linear 𝑇(𝑛) has dominant term 𝑛
Logarithmic 𝑇(𝑛) has dominant term log 2 𝑛
Quadratic 𝑇(𝑛) has dominant term 𝑛2
Cubic 𝑇(𝑛) has dominant term 𝑛3
Run times for small inputs are not very useful:
o We want run time indications for large to extremely large 𝑛.
Algorithmic Analysis must compare functions and emphasise differences for large 𝑛 values.
We use big-O notation to compare function based on their rate of growth.
Properties:
o Dominant term determines the growth rate
o Values of constants are irrelevant
o Small values of 𝑛 are irrelevant.
o Example if 𝑓(𝑛) = 𝑛3 + 100𝑛2 then 𝑂(𝑛 3 ) thus the time complexity is of cubic time
It focuses on the largest term and ignores constants
o The largest term will eventually dominate for large enough 𝑛.
o Constants depend on irrelevant things like clock speed, Operating System, etc.
Definition:
o 𝑇(𝑛) is 𝑂(𝑓(𝑛)) if:
𝑇(𝑛)
lim =𝑐
𝑛→∞ 𝑓(𝑛)
Where 𝑐 is 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 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 anyiamgeorge19. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy this summary for R210,63. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
83750 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy summaries for 14 years now