Paper 2 Flashcards
Features of good algorithm
-Allow invalid input
-Terminates
-clear steps
-execute correctly and efficiently
All types of complexities O() best to worst
-constant
-Logarithmic
-linear
-quadratic
-Polynomial
-Exponential
-Factorial
Define time complexity/How to reduce time complexity
-How execution time scales with size of input
-use divide and conquer
Define space complexity/ how to improve
-How amount of memory space scales with size of input
-Update variables on original data don’t create copies
Space-Run on cheaper Ram
Time-less power used / more tasks in a period of time
Depth First Traversal
Uses stack / visited list
-Go as down as possible before backtracking
-Start popping to backtrack and search for neighbors
If stack is empty stop
Breadth Firtst Traversal
-use queue
- explore all the neighbors
Graph/Tree Difference and Similarity
Graph: edges and vertices and weights
Tree:hierarchy / root /leaf/edges/branches
Trees don’t have cycles
Trees are not weighted
Advantage/Disadvante of DFS
+= stack uses less memory/ quick to find deeper parts
-= DFS may not find shortest path all the time
-= May get stuck in infinite loop
Give some features of IDE and definition of IDE
Set of tools to help develop/debug code
Watch Window
Stepping
Breakpoint
Code Editor stuff like highlighting auto completion/ auto indent
Debugging Tools
What is concurrent processing/ how to implement it
Multiple processes happening at the same time
Break into threads-> multi threading
Concurrent vs Parallel
Possible problems with Concurrent Processes
Simultaneous access to variables may cause inconsistencies/use record locking
Not everything is parallelisable. Sometimes if output of one thing depends on next .
Also x processors don’t mean 1/x time
How do you read from a file and write it to other
file1=openRead(“1.txt”)
file2=openWrite(“2.txt”)
while NOT file1.endOfFile()
a=file1.readLine()
file2.writeLine(a)
file1.close()
file2.close()
How do you find length of string and find the character of index 2
1)string.length
2)string.substring(2,1)
substring(startindex,numofchar)
What is casting?
int(“3”)
Or
float(“3.14”)
Computational Methods
-Problem Recognition
-Backtracking
-Heuristics
-Performance Modelling
-Pipelining
-Visualisation
Computable Problems
Intractable-practical to solve
1)Clearly defined problem
2)every instance of problem can be solved in finite number of steps
Advantages of Decomposition
Breaking into sub problems allows:
-speed up and simplify
-split between programmers
-problem easier to manage and easy to modify
-easy to test/debug individual parts
-Modular programming
DFS(post-order) for a tree
1)Go left as much as possible
2)If no more left child, go right
3)When no more child nodes, backtrack to root node to check for further nodes.
Symbols and labels are used / example of abstraction
Advantage Disadvantage of Abstraction
+reduce time and resources -> less computational resources cheaper
+focus on core aspects don’t get distracted with details
+too much abstraction can make game simple and boring
Advantages of OOP over Procedural
code reusability, data encapsulation, and improved code maintenance and modularity
Encapsulation and Advantages
Daha hiding setters/getters. Protects the data from being unintentionally changed by other subroutines
Advantage/ Disadvantage of Linked Lists
Easy to add delete
Hard to search
