Brainscape's Knowledge GenomeTM

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


See full index

Last Min Paper 1 > hirhs > Flashcards

hirhs Flashcards

1
Q

Application of Breadth First Search

A

Shortest path for an unweighted graph

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

Application of Depth First Search

A

Generating a Maze

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

Application of Pre-Order

A

Copying a tree

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

Application of In-Order

A

Binary Search tree outputting contents in ascending order

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

Application of Post-Order

A

Infix to RPN conversion

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

Time Complexity of Linear Search

A

O(n)

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

Time complexity of Binary Search

A

O(logn)

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

Time complexity of Binary Tree Search

A

O(logn)

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

Time complexity of bubble sort

A

O(n^2)

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

Time complexity of Merge Sort

A

O(nlogn)

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

What is an algorithm

A

A sequence of steps that can be followed to complete a task and that always terminates

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

What is representational abstraction

A
  • A representation arrived at by removing unnecessary details
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is generalisation or catorgerism abstraction

A
  • A grouping by common characterisctics to arrive at a hierarchical relationship of the “is a kind of” type
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is automation

A
  • Putting models into action to solve problems
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

How is automation achieved (4)*

A
  • Creating Algorithms
  • Implementing the algorithms in code
  • Implementing the models in data structures
  • Executing the code
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

RegEx *

A

0 or more repititions

17
Q

RegEx +

A

1 or more repititions

18
Q

RegEx ?

A

0 or 1 repititions

19
Q

What is a regular language

A

A language that can be represented by RegEx

20
Q

Why can BNF represent some languages RegEx cant

A
  • BNF can use recursion to represent languages which RegEx cannot
21
Q

How many permutations for n distinct objects

A

n!

22
Q

What is a tractable problem

A
  • Problems that have polynomial (or less) time solution
23
Q

What is a intractable problem

A
  • Problems that have no polynomial (or less) time solution
24
Q

When are Heuristic Methods used

A
  • When tackling intractable problems
  • Heuristic methods will trade off correctness for speed
25
Q

What is the significance of the halting problem

A
  • Demonstrates that there are some problems that cannot be solved by computers
26
Q

What is the halting problem

A

Given a description of a program , and some input, is it possible to tell, without running the program, whether it will halt with the given input or loop forever, for any program

27
Q

What does a turing machine consist of (4)

A
  • A finite set of states
  • A finite alphabet of symbols
  • An infinite tape with marked off squares
  • A sensing read/write head that can travel along the tape
28
Q

What is the importance of turing machines (2)

A
  • Provide a model of computation
  • Provide a definition of what is computable
29
Q

What would 1 | & , -> mean in a state transition diagram

A

1 is read, write & and move ->

30
Q

When is a program computable

A
  • If and only if it can be computed by a turing machine
31
Q

What is a Universal Turing Machine

A
  • Simulates the behaviour of other Turing Machines when given their transition rules and their input data encoded on its own tape
32
Q

Why can a Universal Turing Machine be considered more powerful than any computer

A

It has a infinite amount of memory tape

33
Q

What is information hiding

A
  • Hiding all details of an object that do not contribute to its essential characterisitcs
34
Q

Convex combination of vectors?

A
  • au+ bv
  • a, b >= 0
  • a + b = 1
35
Q

What is procedural decomposition (3)

A
  • Breaking down a problem into sub problems
  • Each sub problem acomplishes an identifiable task
  • Which might be further subdivided
36
Q

What is Problem abstraction

A
  • Details are removed untill the problem is represented in a way that is possible to solve
37
Q

What is functional abstraction

A
  • Where the particular computation method is hidden

Last Min Paper 1 (1 decks)

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