Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Data Structures and Algorithms > Week 1 > Flashcards

Week 1 Flashcards

1
Q

What is a Data Structure?

A

The study of Data Structures is about how the data is stored in memory to ensure efficient processing of data

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Definition of a Data Structure

A

*Collection of elements each of which is either a data type or another data structure
*A set of associations or relationships (the structure) involving the collection of elements

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Classification of Data Structures

A
  1. Linear structure (e.g. stack, queue)
  2. Hierarchical structure (e.g. management structure, family tree)
  3. Network or Graph structure (e.g. railway map, computer network)
  4. Set Structure (e.g. students)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

How to choose a right data structure

A

*Analysing the problem
*Determining basic operations needed
*Selecting the data structure

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Brute Force Algorithm

A

Algorithm that considers all the possibilities and selects the best solution
*Advantages: Simple
*Disadvantages: Infeasible

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Divide and Conquer Algorithm

A

Algorithm that works by recursively breaking down a problem into two or more sub-problems of the same or related type. The solutions to the sub-problems are then combined to give a solution to the original problem

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Backtracking Algorithm

A

Algorithm that attempts to complete a search for a solution to a problem by constructing partial solutions, always ensuring that the partial solutions remain consistent with the requirements of the problem. Then, it attmepts to extend a partial solution towards completion, but when an inconsistency with the requirements of the problems occurs, the algorithm backtracks by removing the most recently constructed part of the solution and trying another possibility

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Greedy Algorithms

A

In a Greedy Algorithm a decision is made at each stage that appears to be good but no consideration is given to future consequences of this decision

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Abstract Data Type (ADT)

A

A collection of data associated subprograms/ methods stored as a single module

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Datas in Abstract Data Type (ADT)

A

*Cannot be accessed directly
*Can only be accessed indirectly via one of the methods associated with the data

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is in Abstract Data Type (ADT)

A

*The data structure
*Statements to access the data structure
*Statements to modify the data structure

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Difference between ADT and Data structure

A

ADT | Data Structure
High level description | Concrete description
Concerned with what it can do | Concerned with how a task is done
Implementation independent | Implementation dependent

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is a stack ?

A

A stack is a collection of objects organised such that only the most recently inserted object can be removed at any time | is a linear data structure with the property that only the top element of the stack is accessible

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Methods that Stack ADT must support

A

*Push (Add an element to the top of the stack)
*Pop(Remove an element from the top of the stack)
*Peek(Examine element at the top of the stack)
*Length(Give the size of the stack)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Implementation of a Stack - Using an Array

A

The stack of elements will be stored in an array S of size N
An additional integer variable TOP will be required to give the index of the last element in the array S

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Operations for Using an Array

A
  1. Push: The element is added to the top of the stack. TOP is incremented by one. If the stack was full an error occurs
  2. Pop: The required element is at the top of the stack. The element is removed. TOP is decremented by one. If the stack was empty an error occurs
  3. Peek: The required element is at the top of the stack. TOP is unchanged. If the stack was empty an error occurs
17
Q

Application - Queue Abstract Data type (What is a queue?)

A

A queue is a collection of objects organised such that the object that has been stored in the queue the longest is the next one removed | is a linear data structure with the property that elements are inserted at one end of the linear data structure (called TAIL) and removed from the other end of the linear data structure (called HEAD) of the queue

18
Q

Methods that Queue ADT must support

A

*Enqueue (Add an element to the tail of the queue)
*Dequeue(Remove element from the head of the queue)

19
Q

The objective of using Big-O Notation

A

Represent the general efficiency of an algorithm

20
Q

O(1)

A

The running time of the program is CONSTANT irrespective of the value of N |
The running time is NOT DEPENDENT on the value of N

21
Q

O(N)

A

The running of the program is LINEAR
|
The running time is DEPENDENT on the value of N

22
Q

O(N^2)

A

The running time of the program is QUADRATIC

23
Q

O(N^3)

A

The running time of the program is cubic

24
Q

O(log N)

A

The running time of the program is LOGARITHMIC

25
Q

O(N log N)

A

The running time of the program is N log N

26
Q

O(2^N)

A

The running time of the program is EXPONENTIAL

Data Structures and Algorithms (6 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions