5008 Jeopardy Season-2

Sorting

100

Sorting algorithm repeatedly selecting the smallest element from the list and moving it to the sorted portion.

Selection (Sort)

200

Time complexity is O(n²), but if array is almost sorted then much faster algorithm.

Insertion (sort)

300

In quick sort, a somewhat arbitrary element in the collection.

Pivot

400

Average case of time complexity in quick sort.

Θ(n log n)

500

In Merge sort, time complexity of divide if you touch O(1) item per level.

O(log₂ n)

Recursion

100

Trivial or easy case where the solution is obvious.

Base case

200

General case of Factorial problem.

N ! = N * (N-1) !

300

A problem very close to the original problem.

Reduce (case)

400

Algorithm design paradigm recursively breaking down a problem into sub-problems until these become simple enough to be solved directly.

Divide and conquer

500

When a function gets called, that context is saved and a new context for the function is pushed on top of the old context.

(System) call stack.

Tree

100

Collection of nodes and arcs.

Graph

200

Tree having 0, 1, or 2 children nodes.

Binary Tree

300

Tree traversal giving sorted data from binary search tree. 

In-order

400

Tree traversal checking the (peer) similar-level nodes first. 

Breadth first

500

Auxiliary data structure to remember what to do next in breadth first implementation.

Queue

Hash

100

4 basic operations on nodes.

CRUD

200

A function that converts a given numeric or alphanumeric key to a small practical integer value

hash function

300

More than one value hash to the same slot in the table or data structure (hash table).

Collision

400

Hash table is an array of linked lists i.e., each index has its own linked list to resolve collision.

Chaining

500

A method of analyzing the costs associated with a data structure that averages the worst operations out over time

Amortized analysis

Compiler

100

Take a stream of characters and break it into a stream of meaningful tokens.

Lexical analysis

200

A pattern that the regular expression engine attempts to match in input text.

Regular expression

300

A computation model that can be used to simulate sequential logic and some computer programs.

Finite state machine (FSM)

400

A set of recursive rules used to generate patterns of strings.

Context Free Grammar (CFG)

500

A metasyntax notation for context-free grammars, often used to describe the syntax of languages used in computing, such as computer programming language.

Backus-Naur Form (BNF)