Algorithms

What is an Algorithm

An effective method for solving a class of problems

Can be followed by a human - doesn’t need computer

Resources Required by Algorithms?

Space: how much memory does it take to solve a problem 

Time: how many steps (relative to input size) does it take to solve a problem 

• Performance analysis is actual running time on some computers

• Theoretically: As opposed to actual time

Space Complexity

• The amount of memory required by an algorithm to run to completion

• Some algorithms may be more efficient if data completely loaded into memory

  • Need to look also at system limitations 

  • e.g. Classify 2GB of text in various categories [politics, tourism, sport, natural disasters, etc.] – can I afford to load the entire collection?

• Fixed part: The size required to store certain data/variables, that is independent of the size of the problem: - e.g. name of the data collection - same size for classifying 2GB or 1MB of texts

• Variable part: Space needed by variables, whose size is dependent on the size of the problem: - e.g. actual text - load 2GB of text VS. load 1MB of text

Space vs Time

• Look up table vs recalculation 

• Compressed vs uncompressed data 

• Memoization (can be used to store the results of functional calls to reuse and reduce time complexity. However, increases space complexity)