Algorithms and Complexity Flashcards

Flashcards covering key concepts from the Algorithms and Complexity lecture, including algorithm definitions, representations, examples, and the basics of space and time complexity.

Algorithm

An effective method for solving a class of problems, represented by a finite list of instructions that terminate and produce the correct output when executed on a valid input.

Algorithm Representations

Computer code, pseudocode, flow charts, and text/sentences.

Sorting algorithms

Used to sort the data in a particular format such as quicksort and mergesort.

Searching algorithms

Used to find a value or record that user requests such as Linear search and binary search.

Graph Algorithms

Used to find solutions to problems such as finding the shortest path between cities, e.g. breadth-first search, Dijkstra’s algorithm, etc.

Space complexity

How much memory it takes to solve a problem.

Time complexity

How many steps (relative to input size) it takes to solve a problem.

Space complexity

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

Fixed Part (Space Complexity)

The size required to store certain data/variables, that is independent of the size of the problem.

Variable Part (Space Complexity)

Space needed by variables, whose size is dependent on the size of the problem.

Optimal Algorithm

Less space in memory and also takes less time to compute the output

The running time

Depends on the size and the organization of the input, optimal operating temperature, number of processor cores