Computer Science - Paper 1

0.0(0)
studied byStudied by 0 people
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
Card Sorting

1/123

flashcard set

Earn XP

Study Analytics
Name
Mastery
Learn
Test
Matching
Spaced

No study sessions yet.

124 Terms

1
New cards

Who made a famous short path algorithm?

Dijkstra (Dike-Struh)

<p>Dijkstra (Dike-Struh)</p>
2
New cards

What does a shortest path algorithm do?

Finds the shortest path between two nodes in a weight graph.

3
New cards

What are 2 ways to traverse a graph?

  • Breadth

  • Depth

4
New cards

What is Breadth First search?

A node is checked entirely first before moving onto the next.

5
New cards

What is Depth First search?

An entire branch is explored before backtrackingD and truly checking each node.

6
New cards

What are the 3 ways to traverse a tree?

  • Pre-Order

  • In-Order

  • Post-Order

7
New cards

What type of trees are each of the 3 tree traversals meant for?

  • Pre-Order and Post-Order work with any tree.

  • In-Order is mainly meant to be used on Binary trees.

8
New cards

Why do we use Reverse Polish Notation?

  • Eliminates need for brackets.

  • Great use in Stacks

9
New cards

What does the Dijkstra Algorithm do?

Finds the shortest path between two nodes in a graph.

10
New cards

What are 2 sorting algorithms?

  • Bubble

  • Merge

11
New cards

What are 2 Searching Algorithms?

  • Linear

  • Binary

12
New cards

On what list can a Linear search be used?

Linear search can be used on any unordered list.

13
New cards

On what list can a binary search be used?

Binary searches can only be used on ordered lists.

14
New cards

What are the 2 ways RPN can be visualised?

  • Infix

  • Postfix

15
New cards

What are the 4 main Computer Science Constructs?

  • Sequence

  • Selection

  • Iteration

  • Assignment

SSIA

16
New cards

What is meant by Abstraction?

Removal of unrequired information. Keeping only what is necessary.

17
New cards

What is meant by Decomposition?

Breaking down of a problem into smaller and edible chunks.

18
New cards

What is meant by Composition?

The combination. Like composite

19
New cards

What makes up a Turing Machine?

  • Read & Write Head

  • Infinite Tape

  • Finite State Machine (FSM)

20
New cards

What symbol is used to highlight transition functions?

Greek Symbol Delta : δ

<p>Greek Symbol Delta : δ</p>
21
New cards

What is the difference between TM and UTM?

Turing Machine vs Universal Turing Machine is that the UTM can take in another input more than the general TM.

22
New cards

Why is the Turing Machine so important?

The Turing Machine explains the limits of computation as with this theoretical machine if to be impossible with such a machine then its stated to be an incomputable problem. Only provable through use of the Turing Machine

23
New cards

What does FSM stand for?

Finite State Machine

<p>Finite State Machine</p>
24
New cards

What does STD stand for?

State Transition Diagram

25
New cards

What does cardinality mean?

The Count meant to be used on a finite set stating the count within the set.

26
New cards

What does finite mean?

The ability to end.

27
New cards

What does infinite mean?

Unknowingly long.

28
New cards

How do you figure out the cartesian product?

Correct use of multiplication.

<p>Correct use of multiplication. </p>
29
New cards

What is Regular Expression?

Simply put a way of describing a set.

30
New cards

What are the symbols used for Regular Expression?

  • ‘*’ — Meaning zero or more

  • ‘+’ — Meaning one or more

  • ‘?’ — Meaning zero or one repeated (Optional)

  • ‘|’ — Meaning “or“ a choice

  • ‘()’ — Simply just groups them

<ul><li><p>‘*’ — Meaning zero or more</p></li><li><p>‘+’ — Meaning one or more</p></li><li><p>‘?’ — Meaning zero or one repeated (Optional)</p></li><li><p>‘|’ — Meaning “or“ a choice</p></li><li><p>‘()’ — Simply just groups them</p></li></ul>
31
New cards

Can sets contain other sets?

Yes. For those that fit. For example a set containing infinite numbers and one which include 1-10 they’ll defiantly be a set of a set.

32
New cards

What is set comprehension?

Expression of sets through selecting from larger general sets.

<p>Expression of sets through selecting from larger general sets.</p>
33
New cards

What is an empty set called?

{} or Ø

34
New cards

What is a subset?

Example:

A is a subset of B if it only contains items from Set B

Symbol : ⊆

35
New cards

What is a proper subset?

Example:

A is a proper subset of B if it only contains items from B but not all of them

Symbol :

36
New cards

What are the 3 different set operations?

  • Union

  • Intersection

  • Difference

37
New cards

What does Union do considering sets?

Union would take two sets and combine them into a brand new one combining everything from the previous two. (No Duplicates)

Symbol : ∪

38
New cards

What does Intersection do considering sets?

An intersection considering sets when taking two sets the brand new set that would be created would only included those within the previous sets that are found|duplicate in both of them.

Symbol : ∩

39
New cards

What does Difference do considering sets?

When a difference is applied to two sets the resulting brand new set will only include one of the previous in the brand new one completely removing the other.

Example:
A/B
This will only include those from set A

Symbol : /

40
New cards

What does BNF stand for?

Backus-Naur Form

41
New cards

Considering BNF What is the difference between Terminal and Non-Terminals?

Backus-Naur Form considering the difference between Terminal and Non-Terminals:

Terminal — CANNOT be broken down into simpler parts
Non-Terminals — CAN be broken down into simpler parts

42
New cards

Why use BNF?

Backus-Naur form allows for notation of Context free languages.

43
New cards

What does the Halting Problem prove?

The halting problems shows that there are computational problems that are not possible to be solved.

44
New cards

From best to worst-case what are the BigO classifications?

  • O(C)

  • O(log2(n))

  • O(n)

  • O(nlog(n))

  • O(n²)

  • O(n³)

  • O(2^n)

  • O(n!)

<ul><li><p>O(C)</p></li><li><p>O(log2(n))</p></li><li><p>O(n)</p></li><li><p>O(nlog(n))</p></li><li><p>O(n²)</p></li><li><p>O(n³)</p></li><li><p>O(2^n)</p></li><li><p>O(n!)</p></li></ul>
45
New cards

What is meant by Heuristic?

The best guess or rather rule of thumb. Expectation

46
New cards

What is the BigO for a Binary Search?

O(log2 (n))

47
New cards

What is the BigO for a Linear Search?

O(n)

48
New cards

What is the BigO for a Merge Sort?

O(nlog(n))

49
New cards

What is the BigO for a Bubble Sort?

O(n²)

50
New cards

What is the difference between Tractable and Intractable?

The difference to whether a problem can be done within a polynomial amount of time or not.

  • Tractable saying that it CAN.

  • It’s an intractable saying that it CANNOT.

51
New cards

What is the Halting problem?

The unsolvable problem of determining whether any program will eventually stop if given a particular input.

52
New cards

What does Countably Infinite mean?

Its more of statement really which states that all infinite sets can be counted off with use of the natural numbers set (also being infinite) technically meaning every value up to infinity does have a ordinal value.

53
New cards

What counts as a countable set?

  • finite sets

  • countably infinite sets

54
New cards

What are the 4 different types of abstraction?

  • Procedural

  • Functional

  • Data

  • Problem

55
New cards

What are the 7 different Data Structures?

  • Queue

  • Stack

  • Graph

  • Tree

  • Hash Table

  • Dictionary

  • Vector

QuickSilverGoTHDV

56
New cards

What are the 3 types of Queue?

  • Linear

  • Circular

  • Priority

57
New cards

What are Data Structures?

Data Structures act as containers for data acting almost as a next level sort of Data Type.

58
New cards

What are the 3 rules of Arrays?

  • Must be finite

  • Must be indexed

  • Must contain the same data type

59
New cards

What is the difference between 1 and 2 dimensional arrays?

One is simply linear with only data being labelled by its index, while 2 dimensional arrays look like tables containing a column and row.

<p>One is simply linear with only data being labelled by its index, while 2 dimensional arrays look like tables containing a column and row.</p>
60
New cards

What is an abstract data type?

There truly is no such thing as an abstract data type as all it does is take from other real data types and customize themself in their own way making them different to the original only then being labelled as abstract.

61
New cards

How do you interact with queues?

FIFO (First In First Out)

62
New cards

How does a linear queue function?

With use of 2 pointers:

  • Front Pointer

  • Rear Pointer

With these two it will add to the rear (being furthest right) and subtract from the front (being furthest left)

63
New cards

What happens if you reach the end of a linear queue?

CIRCULAR QUEUE!!! in a linear queue it’ll probably just say its full as the pointers always go to the first available space.

Considering a Circular Queue it has the power to go over the edge and loop back round like a circle so if there is space back at the beginning. it can be used.

<p>CIRCULAR QUEUE!!! in a linear queue it’ll probably just say its full as the pointers always go to the first available space.</p><p>Considering a Circular Queue it has the power to go over the edge and loop back round like a circle so if there is space back at the beginning. it can be used.</p>
64
New cards

How does a priority queue work?

Quite similar to that of a weighted graph. Everything is labelled with a value defining its importance in turn saying when it should be dealt with and if there are two of the same variant then simply they are treated as if its a regular queue. (FIFO)

65
New cards

How do you interact with stacks?

FILO (First In Last Out)

66
New cards

How do Stacks work?

Stacks work with a singular pointer known as the top pointer. (Like a stack of books)

67
New cards

What operations can be done on a stack?

  • Push — Adds an item to the stack

  • Pop — Removes an item from the stack

  • Peek — returns the value on top (No Removal)

IsFull , IsEmpty both work.

68
New cards

What are the parts of a graph called?

  • Nodes or Vertices

Get joined together by

  • Edges or Arcs

A Weighted graph has values assigned to these edges.

69
New cards

Instead of using a graph to present what else could be used?

An Adjacency list which displays all the relationships in a different way.

<p>An Adjacency list which displays all the relationships in a different way.</p>
70
New cards

What is the difference between Adjacency Matrix and List?

Adjacency Matrixes store every possible edge there is even if they dont exist with the downside being it takes up more storage while the lists only look at the edges which exist and in turn take up less storage.

  • Adjacency Matrix is better for Dense Graphs

  • Adjacency List is better for Sparse Graphs

71
New cards

What are the 3 rules for trees?

  • Must be Connected

  • Must be an undirected graph

  • must have no cycles.

72
New cards

What makes a root node?

The Root Node is the first node at the top of a tree diagram. These trees contain parents and children.

To be a Root Node you must have no parents.

73
New cards

What is the difference between Trees and Binary Trees?

A Binary tree has no more that 2 children under a single parent.

74
New cards

What do Hash Tables do?

Hash Tables are a way of storing data that allows for it to be retrieved within a constant time complexity.

75
New cards

How do Hash Tables work?

Hash tables take a value and then hash the value masking it with something else and then never again reveal the original input and continue to use the hashed value instead.

76
New cards

How does Dictionary work?

Exactly like it works for compression when a specialized dictionary gets made in order to use duplicates and save entire phrases.

77
New cards

What is the difference between Static and Dynamic?

Static in regard to Data Structures mentions that they are set and final when it comes to questioning the amount of space or rather data they can hold while for dynamic they are able to change their size willingly.

78
New cards

What does sequential mean?

Sequential looks at order stating that one comes after the other.

79
New cards

What is it called if there happens to be too much data in a single structure?

A stack overflow. (An Overflow error)

80
New cards

What does Push do?

Push adds an item to a stack.

81
New cards

What does Pop do?

Pop removes an item from a stack.

82
New cards

What does Peek do?

Without removing anything it will check the top value.

83
New cards

How many pointers does a stack have?

1 — The Top Pointer

84
New cards

How many pointers do queues have?

2 — The Front and Rear Pointers

85
New cards

What are the two things which define Data Types?

  • Values in which they take.

  • The operations which can be performed with them.

86
New cards

What data type can only be true or false?

Boolean

87
New cards

What data type can only accept numbers?

Integer

88
New cards

What data type can only accept one singular input?

Char

89
New cards

What data type can store any other data type?

String

90
New cards

What is meant by assignment?

Providing either a variable or a constant with a value.

91
New cards

What is meant by iteration?

Repeating an instruction.

92
New cards

What is a subroutine?

A subroutine is a named block of code with the mission of being called frequently in order to perform an operation.

93
New cards

What is the difference between Definite and Indefinite?

Definite refers to the amount of iterations having a pre-determined end while indefinite has the possibility to go on for infinity. (or not)

94
New cards

What is indentation?

A incredibly common visual effect that is done to code in order to only make it more visually beneficial with only it having an actual effect once a syntax error has been made.

95
New cards

What does DIV do?

Divides but excludes the remainder.

96
New cards

What does MOD do?

Provides the remainder.

<p>Provides the remainder.</p>
97
New cards

Why is a constant so good at its job?

Overall its easier:

  • Easier to update with it being in the same place to be used globally.

  • With the ability of such a variable able of receiving a name it means that it can be easier to understand.

98
New cards

What is concatenation?

Part of string manipulation where even two or more strings can be connected.

99
New cards

What subroutine must always return a value?

A Function

100
New cards

What can parameters be used for?

Passing data between subroutines.