Introduction Flashcards
What are variables?
A way to hold data.
What are data types?
A set of data with predefined values. Examples of data types are: integer, floating point, unit number, character, string, etc.
At the top level, there are two types of data types. Describe them.
- System-defined data types => Data types that are defined by system are called primitive data types. The primitive data types provided by many programming languages are: int, float, char, double, bool, etc. The number of bits allocated for each primitive data type depends on the programming languages, the compiler and the operating system. For the same primitive data type, different languages may use different sizes. Depending on the size of the data types, the total available values (domain) will also change.
- User defined data types => If the system-defined data types are not enough, then most programming languages allow the users to define their own data types.
What are data structures?
Data structure is a particular way of storing and
organizing data in a computer so that it can be used efficiently. General data structure types include arrays, files, linked
lists, stacks, queues, trees, graphs and so on.
Data structures are classified into two types:
Linear and non-linear data structures.
Explain linear data structures.
Elements are accessed in a sequential order but it is not
compulsory to store all elements sequentially. Examples: Linked Lists, Stacks and
Queues.
Explain non-linear data structures.
Elements of this data structure are stored/accessed in a
non-linear order. Examples: Trees and graphs
To simplify the process of solving problems, we combine the data structures with their operations and we call this ________ .
Abstract Data Types (ADTs).
An ADT consists of two parts. What are they?
I. Declaration of data
II. Declaration of operations
What is an algorithm?
An algorithm is the step-by-step unambiguous instructions to solve a given problem.
What are the two main criteria for judging the merits of
algorithms?
correctness and efficiency.
Why the analysis of algorithms?
Algorithm analysis helps us to determine which algorithm is
most efficient in terms of time and space consumed.
What is running time analysis?
It is the process of determining how processing time increases as the size of the problem (input
size) increases.
The following are the common types of inputs:
- Size of an array
- Polynomial degree
- Number of elements in a matrix
- Number of bits in the binary representation of the input
- Vertices and edges in a graph
What is rate of growth?
The rate at which the running time increases as a function of input.
Name a few commonly used rates of growth.
O(1) - Constant => Adding an element to the front of a linked list
O(log n) - Logarithmic => Finding an element in a sorted array
O(n) - Linear => Finding an element in an unsorted array
O(n log n) - Linear Logarithmic => Sorting n items by ‘divide and conquer’
O(n^2) - Quadratic => Shortest path between two nodes in a graph
O(n^3) - Cubic => Matrix multiplication
O(2^n) - Exponential => The Towers of Hanoi problem
