General Concepts

Last updated Sep 14, 2023 Edit

• Compsci
• Theory

• This refers to the memory requirements of a data structure.
• For a static data structure the memory requirements are known in advance and will not change over the lifetime of the program.
• Dynamic data structures, by contrast, have varying memory requirements.
  • This requirement might change between executions of the code
  • But the requirement can also change during a particular execution.
• Mission critical systems frequently forbid the use of dynamic data structures.

• When a program is executed it is allocated a block of memory to run in.
• The memory will be allocated as a multiple of a fixed size:
  • An operating system might allocate memory in 32KB blocks
  • So a program that needs 38KB will be allocated 64KB
• The extra space is described as a heap
• As the memory requirement for dynamic data structures increases, the extra space is allocated from the heap for that program.

• A pointer is simply a variable that can be used to point to something
• A pointer could contain a number that is an index in a list.
  • It is pointing to that position.
• It could contain a number that is:
  • A memory location (perhaps the return address in a stack frame)
  • A position in a file
  • A record in a table
  • A function in a memory
  • An element in a list/array

• When calling a subroutine we can pass it some values.

• We can pass them by value.

  • We gave the subroutine a copy of the variable.
  • The subroutine works on its own copy, the original is left unchanged.

• We can pass them by reference.

  • We give the subroutine a pointer to the variable.
  • The subroutine works on the value in the same memory location as the original value.
  • The memory location will have the most recent value from the subroutine so when control is returned to the calling program it sees the value that subroutine finished with.

• Many programming languages have a data structure called an array.
• An array is a single identifier with many values.
• You reference the specific value by using the identifier and an index.
• For example:
  • myArray[3]
• In an array all elements must be of the same data type.
  • Therefore, they take up the same amount of memory.
  • Which means finding a particular element is easy.
    • address of array + (size of element * index)

• List elements can be any data type

  • This makes them more flexible than arrays

• List elements can be of any size

  • So they can take up different amounts of memory

• Finding a particular element means following links starting from the first item in the list until you find the item you want.

• A linked list does not have to be stored continuously in RAM, whilst an array must be.

• Stacks and queues are special uses for arrays and lists
• Stacks are LIFO
• Queues are FIFO

• Computers can only do one thing at a time.
  • Multiprocessor systems can only do one thing on each processor.
  • Multitasking systems give multiple tasks a small amount of attention.
• Also they cannot keep track of more than one subroutine at a time.
• So we push some data, which we call a stack frame, onto a call stack as each new subroutine is called.
• It is used to restore the state of the computer to what it was before it began executing the subroutine once it has finished.
  • We pop the last stack frame from the call stack
  • The information in the stack frame allows us to restore all the registers.

• Put simply, recursion is when you write a subroutine in terms of itself.
  • That means the subroutine calls itself.
  • The call will be a sub set of the data to be processed or a partially complete result
  • Once the subroutine has been called with a simple enough piece of data it can perform the calculation and the call stack begins to unwind.
• The stack grows in size with recursion, whilst a loop maintains the stack size as it creates a stack frame. Put simply, a loop is iteration, whilst recursion is not.

1
2
3
4
5
6
7
8
9

# Example of recursion

def recursion(n):
	print(n)
	if n > 1:
		recursion(n//2) # On calling this line, we suspend the subroutine and add it to the stack frame
	print(n) # Once n !> 1, we process the stack frame, causing the program to spit out the inverse of what it previously printed.

recursion(1024)

Expected output:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

1024
512
256
128
64
32
16
8
4
2
1
1
2
4
8
16
32
64
128
256
512
1024
>>>

• A graph is a simplified way to represent connection data
• The graph represents physical or logical connections
• A graph is a form of abstraction

• Vertices are the things being connected
• Edges are the connections
• Vertices are occasionally called nodes
• Edges are occasionally called connections

• Adjacency Matrix
  • 
• Adjacency List
  • 

• Edges can be:
  • Weighted
    • Indicates some kind of cost
      • Distance, cost, difficulty etc
  • Directed
    • Shows which way you can travel along an edge
      • One way street, winner in competition etc
• Graphs can be:
  • Unweighted and undirected
  • Weighted
  • Directed
  • Weighted and Directed

• A tree is a special kind of graph

• Trees

  • Have no cycles
  • Are NOT directed
  • Are connected

• Binary trees are a specific kind of tree

• A-level spec requires the ability to construct and traverse a binary tree in 3 ways:

  • Pre-order
  • In-order
  • Post-order

• Different types of traversal get used for different reasons

• Pre-order: Copying a tree. You need to create the parent before you can create its children.

• In-order: Sort the contents.

• Post-order: Deleting a tree. You need to delete the children before you can delete the parent.

• When we represent a tree we usually use a linked list.
• To store a binary tree we need two links for each data item:
  • Left
  • Right

General Concepts