cs paper 1 - past paper questions Flashcards
(25 cards)
Recursive Subroutine?
a subroutine that calls itself
Heuristic Technique?
employs a method of finding a solution that might not be best ( an estimate for an intractable problem)
difference between static and dynamic data structures?
- Static storage size can be determined before program is run / dynamic can grow and shrink during execution.
- Static can waste storage space / dynamic only takes up amount of storage space needed for data
- Dynamic requires pointers to next item / static does not need pointers
Why RPN used
-simpler for machine to evaluate
- Do not need brackets to show correct order of evaluation
Components of Stack frame
local variables, return address
why use adjacency list?
-when there’s fewer edges between vertices
-when edges rarely change
why use adjacency metric
- Many edges between vertices
- Edges frequently change
Halting Problem
- determining if a program will halt
- without running the program
Why can a TM not be used to solve halting problem
- it is non-computable
-TM can only solve computable problems
components of TM
-finite set of states
- read-write head
-set of transition rules
The Universal TM
- computes any computable sequence
- Instructions for TM stores on tape
- acts as an interpreter
Why is Universal TM powerful?
- infinite amount of memory
how to ‘solve’ an intractable problem
- use of heuristic algorithm
- makes an estimate based on experience
representational abstraction?
- remove unnecessary details
abstraction by generalisation
- grouping by common characteristics
intractable problem
- problem can be solved
- but in exponential time complexity or worse
dynamic data structures +/- compared to static
+no wasted memory
+ resources only allocated if needed
- additional memory needed for pointers
- can result in memory leak
Binary tree
- rooted tree
- where each node has at most 2 child nodes
Base case for recursive subroutines
- circumstances when recursive subroutine does not call itself
procedural decomposition
-breaking problem into smaller sub-problems
-each solves an identifiable task
- each of which might be further subdivided
steps to add record in hash table
- Hash algorithm applied
- to key value
- result is location in table where record should be stored
- if location not empty
- use next free location
tractable problem
- polynomial or better time complexity
Constant time complexity
- as size of input increases, amount of time taken remains the same
Cardinality
- number of elements in a set
