CSCI203 = Algorithms & Data Structures

What are the different tyoes of standard algorithms?

• Finding the Maximum

• Finding the Minimum

• Linear Search

• Binary Search

• Binary Search with test for termination

What are the different ways to compare algorithms or find the best algorithm to use?

• Fastest?

• Smallest?

• Most general?

• Easiest to understand?

How do we compare the speed of algorithms?

• Every operation takes time

• More operations = more time = slower algorithms

• Fewer operations = faster algorithm

• More operations = slower algorithm

What is Problem Size in algorithms?

• n = how many items the problem contains (number of items)

e.g.

• Sort 10 numbers is n = 10

• Sort 100 numbers is n = 100

What is Algorithm Complexity?

• Describes how the number of operations grow as the problem size (n) increases

• Measures the algorithm’s rate of growth not the exact running time

e.g.

• Small increase in work = better algorithm

• Large increase in work = less efficient

What are Complexity classes of algorithms and their types?

• Groups of algorithms that have approximately the same rate of growth as the problem size (n) increases

Types:

• Constant (1) = problem is independent of n

• Logarithmic (log n) = as n grows, the number of iterations to find the item grows slowly

• Linear (n) = as n grows, number of iterations grows at the same rate

• Linearathmic (nlog n) = time proportional to n

• Quadratic (n²) = number of iterations grows n * n

• Exponential (2^n)

• Factorial (n!)

What are Arrays?

• Fixed number of data items of the same type

• Directly accessible via an index value

• Can have more than one index (multidimensional)

• Initialising one takes n operations for an array of n elements

• Records may appear as an element

What are Lists?

• Collection of items arranged in some order

• Can’t be directlya accessed via an index

• Nodes (items) are recorded containing data and a pointer to the next node

• May also have a pointer to the previous

• Special pointers head and tail (for doubly linked lists) are maintained to point to the first and last elements

What are Stacks?

• Holds multiple elements of a single type

• Removed in reverse order of isnertion (Last In, First out)

• Implemented with an array and integer counter to indicate the current number of elements

What are Queues?

• Holds multiple elements of a single type

• Removed int he order in which they were inserted (First In, First Out)

• Can be implemented with an array and two integer counter to indicate the current start and next insertion positions

What are Records?

• Fixed number of items

• Elements may be of differing types and are named

• Array may appear as a field

• Addressed by a pointer

• Fields are accessible via the field name

What is a Compact String Storage?

• A way to store many strings of different lengths while using memory efficiently

Goals

• Uses the minimum amount of storage

• Allow fast access to any string

• Avoid the overhead of dynamic memory allocation

What is a String Pool?

• A collection of data structures used to efficiently store a large number of strings of different lengths (variable-length strings)

• Stores many strings efficiently

• Different implementations have small differences but are about equally efficient