Brainscape's Knowledge GenomeTM

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


See full index

Computer Science Ongoing Flashcards > Set 8 > Flashcards

Set 8 Flashcards

Need to add time complexity cards. card 36 needs updating

You may prefer our related Brainscape-certified flashcards:
Biology 101 flashcards
1
Q

Why is space complexity important to consider when analysing binary tree search?

A

Because the algorithm is recursive, it places a demand on the call stack

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

Merge sort complexity

A

O(n log n)

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

Give two reasons why smaller time complexity is better

A
  • A quicker program could solve more of the same problem or run more programs in the same time period
  • Computers consume electricity to run…
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Give two reasons why is smaller space complexity better

A
  • A program that uses less memory could run off cheaper hardware (as less RAM is needed)
  • Or a greater number of different algorithms can run on the same hardware simultaneously
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is the purpose of Dijkstras algorithm?
Can the graph be directed/weighted?

A
  • Calculates the shortest path between a node and all other nodes in a graph
  • Graph may be directed or undirected
  • Graph must be weighted
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What approach does merge sort take to sort a list?

A

Divide and conquer

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

What is bubble sort’s time complexity? Why?

A

O(n^2). Since it involves a for loop within a for loop. You need to do n passes of the list/array, and each pass involves swapping all the way down the list.

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

Hierarchy of complexities (polynomial, logarithmic, constant, exponential, linear)

A

constant < logarithmic < linear < polynomial < exponential

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

What is a first class object?

A

First class objects are objects which may:
- R - be returned in function calls
- A - be assigned as arguments
- V - be assigned to a variable
- E - appear in expressions

Functions are first-class objects in functional programming languages

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

What does function application mean?

A

Applying a function to its arguments

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

What does partial function application mean?

A

Parțial function application means only applying a function to some of its arguments. The result is a function.

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

What is the purpose of a domain name?

A
  • A domain name identifies an organisation or individual on the internet.
  • They use alphanumeric characters which make them easier for humans to remember than IP addresses
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is the purpose of a domain name server?

A

To translate a fully qualified domain name into its corresponding IP address

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

What is the domain name system?

A
  • The domain name system is a distributed database of mappings from FQDNs to their corresponding IP addresses
  • DNS servers are organised into a hierarchy
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What happens is a domain name server cannot resolve a lookup?

A

The query will be passed to another DNS server

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

Who manages top level domains?

A
  • An (internet) registry
  • Each TLD may have restrictions as to who can use it
17
Q

What is the main responsibility of an internet registry?

A

To maintain a definitive register of who owns a specific domain.

18
Q

Give two examples of top level domains

A

.uk .org

19
Q

What is meant by baud rate?

A

The maximum number of signal changes in a medium per second

20
Q

What is meant by bit rate?

A

The number of bits transmitted over a medium per second

21
Q

Bit rate equation

A

bit rate of channel = (baud rate) x (number of bits per signal change)

22
Q

What is Serial Data Transmission?

A

Bits are sent one after the other over a single wire from source to destination

23
Q

What is Parallel Data transmission?

A
  • Multiple bits are sent simultaneously over multiple wires from source to destination
  • Each bit is sent down a different wire
24
Q

Give two problems with Parallel Data transmission

A
  • Unreliable because of skew
  • Parallel wires also suffer from crosstalk
25
Q

What is skew?

A

As each wire has slightly different properties, there is a possibility bits could travel different speeds over each of the wires and arrive at different times, meaning the signals might overlap

26
Q

What is cross-talk?

A

Interference between different lines, which causes data corruption

27
Q

Give three advantages of serial over parallel transmission

A
  1. Serial transmission doesn’t suffer from skew or cross-talk
  2. Serial is reliable over much longer distances
  3. Serial transmissions tends to be cheaper, as there is much less complexity and the physical size of cables is smaller
28
Q

What is bandwidth? What unit is it measured in?

A
  • A measure of the maximum capacity of a communication channel
  • It is directly proportional to bit rate
  • Measured in bits per second
29
Q

What is latency?

A

A time delay before some component in a computer system responds to an instruction

30
Q

What is synchronous transmission?

A
  • Data is transferred at regular intervals, synchronised by a clock signal
  • Receiver and transmitter clocks are synchronised
31
Q

What is asynchronous transmission?

A
  • Receiver and transmitter clocks only need to be synchronised for the duration of data transmission
  • Blocks of data are sent as soon as they are ready
32
Q

How are start and stop bits used in asynchronous transmission?

A
  • Start bit is sent to synchronise the clock in the receiver to the transmitter clock
  • Stop bit allows the receiver time to process the current block of data before another is sent
  • Stop bit is opposite to start bit to allows the next start bit to be recognised
33
Q

What is a worm?

A

A piece of malicious software that can self-replicate between computers, either within a network (such as the Internet) or by a user downloading and running and malicious files.

Unlike viruses, worms are complete programs - they do not require a host program to cause damage.

34
Q

What is a virus?

A
  • A virus is a small program of self-replicating software that is attached to other program or files
  • Viruses require a host file in which to reside
35
Q

What is a trojan?

A
  • A type of malware that is disguised as a legitimate benign file that users can be tricked into opening
  • They can delete and modify data and allow more malware in once they are opened
36
Q

Give five ways to prevent malware

A
  1. Improving code quality
  2. Monitoring
  3. Protection (e.g. up to date antivirus programs)

Computer Science Ongoing Flashcards (10 decks)

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