Brainscape's Knowledge GenomeTM

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


See full index

2nd Year - 1st Semester > CC4 - chapter 1 and 2 > Flashcards

CC4 - chapter 1 and 2 Flashcards

1
Q

– machine that manipulates data.

A

Computer

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

–Concealing of the implementation details of data object from the outside world

A

Data encapsulation / information hiding

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

– separation between specification of a data object and its implementation

A

Data abstraction

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

– a collection of objects and set of operations that act on those objects

A

Data type

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

– storing and organizing data in a computer so that it can be used efficiently.

A

Data structure

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

– may be organized in many different

A

Data

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

CHARACTERISTICS OF ALGORITHM

A
  • Provides description of elements in terms of data types
  • Defines the relationship among individual
    Elements
  • Valid operations and parameters to be passed
  • Error conditions associated with the operations
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

DATA STRUCTURE OPERATIONS

A
  • traversing
  • searching
  • inserting
  • deleting
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

– accessing each record exactly once so that certain items in the record may be processed.

A

Traversing – retrieving/visiting

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

– finding the location of the record

A

Searching – insert

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

– adding new records to the structure.

A

Inserting – update

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

– removing

A

Deleting – remove

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

– used by os, Compilers, dbms, data communications

A

data structure/+ algorithms

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

– its elements form a sequence
- Array
- Stack – lifo
- Queue – fifo
- Linked list

A

Linear data structure

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

– represent data containing a hierarchical relationship between elements
- Tree & graph

A

Non-linear data structure

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

Quick insertion, very fast access if
Slow search, Slow deletion, index is known, Fixed size

A

Arrays

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

Quicker search than unsorted array. Slow insertion and deletion, Fixed size

A

Ordered Array

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

Provides last-in first-out access Slow access to other items

A

Stack

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

Provides first-in first-out access Slow access to other items

A

Queue

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

Quick insertion and quick deletion Slow search

A

Linked List

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

Quick search, insertion and Deletion algorithm is deletion if tree remains balance complex.

A

Binary Trees

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

Very fast access if key known, Fast Slow deletion, access slow if key not known, inefficient memory usage

A

Hash Table

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

Fast insertion, deletion. Access to Slow access to other items

A

Heap

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

Models real world situation Some algorithms are slow access.

A

Graph

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

Algorithm – finite set of instructions that takes some raw data as input and transforms it in to refined data.

A

Algorithm

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

ALGORITHM STEPS

A
  • input
  • output
  • definiteness
  • finiteness
  • effectiveness
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

– zero or more quantities are externally supplied

A

Input

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

– at least one quantity is produced

A

Output

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

– each instruction is clear and unambiguous

A

Definiteness

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

– algorithm terminates after a fi nite number of steps

A

Finiteness

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

– every instruction must be basic enough to be carried out

A

Effectiveness

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

COMMON TYPES OF ALGORITHM

A
  • searching
  • sorting
  • compression
  • fast Fourier transforms
  • encoding
  • geometric
  • pattern matching
  • parsing
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

– search for a given item in large data collection

A

Searching

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

– arrange data items

A

Sorting

35
Q

Compression – reduce the size of data and program files

A

Compression

36
Q

– designed for digital signal processing

A

Fast fourier transforms

37
Q

– encryption of data

A

Encoding

38
Q

– identification of geometric shapes

A

Geometric

39
Q

– comparing images and shapes

A

Pattern matching

40
Q

– identify different programming constructs

A

Parsing

41
Q

CLASSIFICATION OF ALGORITHM

A
  • iterative
  • divide and conquer
  • greedy
  • back tracking
42
Q

– repeated in loops until the goal is achieved

A

Iterative

43
Q

– fragmented into subproblems which are solved partially

A

Divide and conquer

44
Q

– an immediately available best solution at each step is chosen

A

Greedy

45
Q

– all possible solutions are explored

A

Back tracking

46
Q

EXPRESSING AN ALGORITHM

A
  • natural language
  • graphic representations
  • programming language
47
Q

– must be well defined and unambiguous

A

Natural language

48
Q

– flowcharts

A

Graphic representations

49
Q

– low level implementation must be removed and replaced by natural language

A

Programming language

50
Q
  • Limitation of recursion (only factorials, ackermann, fibonacci, …)?
  • A tool for theorician?
  • Theorem: ‘’any program that can be written using assignment, th
  • E ifelse statement and the while statement can also be written using assignment, if-else and recursion.’’
  • Example: Fibonacci – f(0)=f(1)=1 – f(n) = f(n1)
    + f(n2)
A

Recursive algorithm

51
Q
  • Stated as a function relating the length to the number of steps
  • Is the time and space it uses
A

Complexity

52
Q

2 CRITERIA FOR PERFORMANCE ANALYSIS

A
  • space complexity
  • time complexity
53
Q

– the amount of memory needed by a program to run to completion

A

Space complexity

54
Q

– the amount of computer time needed by a progra m to run to completion

A

Time complexity

55
Q

TWO PHASES IN PERFORMANCE EVALUATION

A
  • performance analysis
  • performance measurement
56
Q

– priori estimate

A

Performance analysis

57
Q

– priori testing fixed

A

Performance measurement

58
Q

part – independent. Memory does not change

A

variable

59
Q

part – dependent. Memory do change

A

asymptotic

60
Q

– helps to compare algorithms worst case running

A

notation

61
Q

– way of solving a problem or calculation in less time by using more storage space (or memory), or by solving a problem in very little space by spending a longtime.

A

Time-space tradeoff

62
Q

– is a finite, ordered sequence of data itemsknown as elements.

A

List

63
Q

– each element has a positionin the list.

A

“ordered”

64
Q

– number of elements currently stored

A

Length of the list

65
Q

T/F:
There are two standard approaches to implementing lists, the arraybased list, and the linked list.

A

true

66
Q

T/F:
- The beginning of the list is called the tail, and the end of the list is called the Head.

A

false (baligtad)

67
Q

– it is a collection of homogenous,
Ordered andfinite set of elements. It is a linear data structure. Its data type can be primitive, composite or other data types.

A

Array

68
Q

– same element type and have the same structure

A

Homogenous

69
Q

– organized in sequence.

A

Ordered

70
Q

– fixed number of elements.

A

Finite

71
Q

ADVANTAGES OF AN ARRAY

A
  • An array uses a single variable to
    Represent a large set of homogenous data collection.
  • An array provides direct access to a storage address for an element.
    Therefore, retrieval of an element is extremely fast.
  • The elements on an array can be
    Manipulated easily using an index. Thus, processing of array is flexible.
  • It is easy to create and initialize an array.
    Arrays are good at implementing iterative algorithms.
  • Multi-dimensional arrays facilitate grouping of data collection into hierarchical structure
72
Q

ACCESSING ARRAY

A
  • index
  • index set
  • lower/upper bound
  • array name/index
    *bracket notation
73
Q

– array the position of an element

A

Index

74
Q

– range of values for the index

A

Index set

75
Q

– smallest and largest value in of index

A

Lower and upper bound

76
Q

– individual elements of an array

A

Array name and array index

77
Q

DISADVANTAGES OF AN ARRAY

A
  • Array size cannot be increased or decreased during runtime.
  • Insertion and deletion operations on arrays are not efficient.
  • For very large data sets, the program may run out of the storage space
78
Q

ARRAY OPERATION

A
  • retrieving
  • adding
  • deleting
  • inserting
  • traversing
79
Q

– -it is also called accessing

A

**Retrieving **

- To retrieve an element we must know the index value

80
Q

– inserts new element in a position specified by the index
- aka assigning

A

Adding

81
Q

– deleting operation removes an existing element with the given index.

A

Deleting

82
Q

– it adds new element in a specified position, without replacing any existing element the position is specified in terms of index value or position relative to an existing element.

A

Inserting

83
Q

– involves accessing and processing an array element exactly once
- aka visiting

A

Traversing

84
Q
  • Two-dimension arrays can be used to store and process strings
  • A string is a sequence of characters
  • In c/c++, a string contains a null terminating character
  • In several applications, we need to store a group of related strings
  • 2-d arrays provide a convenient and
  • Simple mechanism for storing elements
  • Since in 2-d arrays, all rows must have the same number ofharacters, storage space may be wasted if some of the
  • Strings have shorter lengths
A

String arrays

2nd Year - 1st Semester (15 decks)

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