COM1029 Data Structures: Algorithm Analysis

• COM1029 is an introductory lecture about Data Structures and Algorithms

Recap

• Algorithm analysis includes measuring time complexity
• Big O Notation, Big Omega Notation and Big Theta Notation are all used

Algorithm Analysis Questions

• O(N) algorithm takes 60 seconds to process an array of size 1000, it takes 120 seconds on an array of size 2000
• O(N^2) algorithm takes 60 seconds to process an array of size 1000, it takes 240 seconds on an array of size 2000
• O(N^3) algorithm takes 1 second on an array of size 1000, it takes 64 seconds on an array of size 4000
• Q2.4) An O(N^6) algorithm takes 2 seconds on an array of size 100, it takes about 2 hours on an array of size 400
• If an algorithm first runs at O(N) and then at O(N^3), the overall efficiency is O(N^3)
• If an algorithm first runs at O(N^2) and then at O(N^3), the overall efficiency is O(N^3)
• The most efficient operation on an array is Insert an Item
• The efficiency of finding the smallest item in an unordered array is O(N)

Data Structures

• Algorithms often work on a large amount of data, which can be organized in many ways
• Choosing a proper representation of data helps to achieve efficiency
• A data structure includes the representation and the operations

Data Collection Management

• Ways to manage collections of data items/objects involve:
  • Adding an item to the collection
  • Finding an item, if it is present
  • Removing an item
  • Iterating through the items
• The most appropriate data structure depends on the desired operations
• When managing a shopping basket, operations include:
  • Add: Putting an item in the basket
  • Remove: Taking an item out of the basket
  • Find: If the basket contains a specific item
  • Iterate: Going through all items, such as when calculating the total price

Basket Implementation

• A basket can be created using an array
• Baskets hold collections of goods
  • These are represented by the array
  • Each entry reserved for one item
• Initial setup requires array capacity and array definition
• Considerations can include:
  • Contents of the basket may vary, this can make the array have unfilled spaces
  • How the unfilled spaces are tracked
  • Can filling be from the front
  • Are repetitions allowed
  • When an item is removed, the position becomes empty
• To add a new item requires consideration of:
  • How to proceed if a basket is full
  • How to proceed if the basket already has the item, including if repetitions are allowed
• If a position to put a new time is known
  • Assigning a[i] = data leads to a complexity of O(1)
• Finding a specific item may require giving their location or reporting if it is there
  • Finding an item has a complexity of O(N)
• Removing involves identifying the item and proceeding according to where items are filled from
• The efficiency of item removal is O(N)
• Overall reflections using arrays include:
  • Arrays implement data sets, these have to be multiset since repeats are allowed
  • Adding an item has an O(1) attribute
  • Finding and removing has an O(n) attribute
  • Iterating has an O(n) attribute
  • If the algorithm involves mainly adding items and iterating over them, the array is good
  • It is possible to do better where the algorithm requires frequent find and remove operations

Data Stacks

• Restrictions on insertion and removal improves the efficiency in applications or algorithms
• Stack Restrictions involve adding and removing of items
• This is known as a standard data structure
• The stack follows:
  • Items are added on top
  • Items are removed from the top
  • This is known as "Last In First Out", (LIFO)
• Stack operations include:
  • An item to be added onto the top (push)
  • The top item to be removed (pop)
  • The top item to be read (top)
  • The top item to be read and removed (topAndPop)
  • Reporting on whether it is empty (isEmpty)
• Stacks have no operations for:
  • Finding elements
  • Removing elements from elsewhere other than the top
• An algorithm that uses a stack is Decimal to binary conversion:
  • Repeatedly divide the number by 2, and push the remainder onto the stack
  • When you reach quotient 0 from the division step, pop the remainders off the stack and print them out – that is your number in binary representation
  • The pop operations give the remainders in reverse order of finding them
  • The remainders can only be 0 and 1, the only allowed binary digits
• An example of turning 6 into binary involves:
  • 6 / 2 = 3 R 0 then push 0 to the top
  • 3 / 2 = 1 R 1 then push 1 to the top
  • 1 / 2 = 0 R 1 then push 1 to the top
  • The binary representation is 110
• Implementing the stack:
  • Use an array
  • The array capacity limits stack capacity
  • The array index indicates the top of the stack
  • In a lecture the index is above the top, in the lab it may point to the topmost item
  • Stacks use any data type
• An empty stack involves indexing one above the top even if the stack is empty
  • The isEmpty operation checks of index is at 0
• When an item V is pushed to the stack
  • The algorithm a[i] = v; i = i+1; is used in constant time O(1)
• With topAndPop
  • algorithm i= i-1; return a[i]; a[i] = ???
  • Operation is O(1)
  • The item does not need to be deleted and physically stays in the array
  • Making Pop operations faster

Stack Summary

• Arrays efficiently implement stacks
• Stack operations such as adding and retrieving elements is constant
• Stacks are suitable in cases where "Last In First Out" buffering is appropriate

Queues

• Stacks use First In First Out, (FIFO)
  • This is a contrast to stacks which use "Last In First Out"
• Queue Operations:
  • An item is inserted to the back (enqueue)
  • The front item is removed (dequeue)
  • The front item is read (getFront)
• Queue Limitations:
  • Has no operations for finding elements
  • Has no operations for removing elements, except for the front one
• Implementing Queue
  • Use an array with capacity limited by the size of the array
  • Includes indexes s for the start of the queue
  • Includes indexes e for the end of the queue
• An empty queue means the start and end index points to the same cell in the array
  • If s=e, the queue is empty, even if the empty space is in the middle of the array
• An enqueue operation involves:
  • Passing the item to be added, with constant time O(1) -A dequeue operation involves:
  • Constant time O(1) de-queuing
  • The 'removed' array elements may require an update, and what that update will be
• The queue is represented by elements s and e
  • With array elements left as 'junk' due to being logically used by the queue
• Array end requires considering can no longer add to the queue
• Wrapping around involves wrapping back to the beginning
  • Then requires overwriting if there are more items than available spaces
• A full or empty queue can lead to an ambiguous setup
  • Therefore, the enqueue/dequeue process should avoid this