CS2 Flashcards
2.1.1 Thinking Abstractly
-Removing of irrelevant information to solve an issue
-Maximizes chances of solving a problem
-Better visualisation of the problem
-Focus on parts of the abstracted model
-Use of subroutines and libraries to seperate code that carries out a specific task
2.1.2 Thinking ahead
-Involves planning the inputs and outputs
-Use of reusable components e.g subroutines
-Knowing what needs to be done/outputted and from what is required/inputs
-Caching: temporarily storing data and instructions
-Allows for faster use by storing data in a faster storage media e.g RAM when a program is in use or secondary storage for web pages
-Caching is complex to implement
-Reusable of components are pieces of code which can be used or called in/from multiple places
-Use of classes, libraries, subroutines
2.1.3 Thinking procedurally
2.1.4 Thinking logically
-Decomposition: breaking a problem down into smaller problems
-Identifying what is required to be done and working sequentially, from the beginning, to achieve it
-Identifying decision points for branching or iteration
-Use of flow charts to design an algorithm
-Allows identification of a point in which decisions are required to determine the conditions and outputs
2.1.5 Thinking concurrently
-Identifying parts of a problem to tackle at one time
-Speeds up achieving a solution to a problem
-Can be difficult to program
-Not all issues can be solves concurrently
2.2.1 Programming techniques
-Sequence: set of program instructions are written one after another
-Executes 1 by 1, in the order placed in the program
-Branching / Selection: programming construct that allows a program to run a sequence of codes based on if the conidition is met (true/false)
-Iteration: section of specified code is repeated through a loop 1 or more times, should a condition be met
-Count-controlled: the program will loop x many times
-Condition-controlled: the program will loop as for as long as a condition is met
-pre-check-cond: condition is checked BEFORE executing (while answer != “comp”)
-post-check-cond: condition is checked AFTER executing (do answer = input until answer == “comp”)
2.2.1 Programming techniques
-Recursion: when a function calls itself, another way of iteration
-Recursive subroutine must have an execute and a base case (a way to exit the recursion)
-Slower, uses more system resources and badly coded can cause stack overflow errors
-Global var: accessible anywhere by anything, declared outside subroutines
-Dangerous, placement matters as it can be unintentionally modified
-Local var: accessible only in the class or subroutine it is declared in
-Modularity: programming with subprograms e.g subroutine
-Allows a team of programmers to work on different modules to complete the program swiftly
-Top-down design is used where the program is continually decomposed until each performs a specific task
-Functions return a value, procedures perform an action and may not return a value
2.2.1 Programming techniques
-Parameter is a variable inserted into a subroutine to be used
-ByVal is where a copy of a variable is passed as the parameter into a subroutine - usually the default
-ByRef is where the address of the variable is passed to the subroutine in which the variable state can be modified
-Integrated develop enviroment contains comprehensive tools for a particular program
-Code editor w/ autocompletion, indentation and syntax highlighting
-Error diagnostics, version control, run-time enviroment to run code and see outputs, translator, variable watch, breakpoints
-OOP is a programming style in which objects are defined to have associated values (attributes) and subroutines (methods) allowing for grouping of relevant data in a subprogram (class)
-Encapsulation: protects attributes by only allowing methods associated with the class to modify attributes in the class i.e via use of “private”
-Inheritence: allows different classes to share the same core code (attributes, method) to child classes which can have more of their own attributes and methods
-Polymorphism: allows subroutines to take objects on in different forms
class Pet
private name
public procedure new(givenName)
name = givenName
endprocedure
public procedure setName(givenName)
name = givenName
endprocedure
public function getName()
return name
endfunction
endclass
myPet = new pet(“Fido”)
myPet.setName(“Spike”)
print(mypet.getName())
2.2.2 Computational methods
-Problem recognition: examine the scenario to recognise the problem to find out how to solve it
-Decomposition, top-down design, abstraction use
-Divide and conquer: method of designing algorithm in which recursion is used to repeatedly divide a task into subtasks of an similar group, this is common is searching, sorting and pathfinding algo
-Backtracking: an algorithmic approach to where partial solutions are incrementally built and if a solution path fails, you return to a previous point of a solution and try another approach
-Essentially trial and error with use of recursion to move from one state of the problem to another
-For each move, consider what the next set of possible moves are
-Only useful for sequential problems
-Datamining: analysis of large amounts of data to provide new information
-Useful way to determine relationships that are not obvious
-Heuristics: a best guess approach to problem solving to reduce computation time
-Balancing time spent between solving a problem and gathering the best solution
-Used when it is unfeasible to analyse multiple possibilities to a solution
-Important to know when a solution path is not as effective so you move to a better path
-Performance modelling: simulating or modelling performance of a system before use
-Use of sample test data for the new algorithm to ensure it responds as intended
-Pipelining: the output of a process is the input of another
-Complex jobs to be divided into pipelines to allow parallel processing
-Can speed up execution however unexpected branches requires the pipes to be flushed
-Visualisation: representation of a scenario using symbols, charts and colours
-Makes a scenario much more easier to read e.g flow charts, class diagram, system diagrams
2.3.1 Algorithm complexities
-Types of complexity: used to classify algorithms according to how their runtime or space requirements grow as input size grows
-TIme: indicates time an algorithm takes to run in relation to size of input
-Computer uses electricity, quicker algorithm will use less
-Space: indicates memory required by an algorithm in relation to size of input
-Computer uses hardware, indication of how good the hardware must be can be analysed
-BigONotation: formal expression of an algorithms complexity
-O(1): Constant time - same amount of time to execute regardless of input e.g accessing array element via index
-O(n): Linear algorithm - time to search increases with number of input e.g looping through an array or linear searching
-O(N^2): Polynomial time - time taken to seach is proportional to the square of the input size e.g bubble sort or insertion sort
-O(2^N): Exponential - time taken to search doubles as the input size increases
-O(logN): time taken to search grows very slowly as data set increases e.g binary, merge and quick sort
2.3.1 Searching algorithms
-Linear: finding an a data piece by checking all elements one by one - O(n)
-Binary: finding a data piece in an ORDERED list by starting at the middle element and determining if the data is higher or lower in the list. The list is then halved and the process repeats until the data element is found - O(log n)
2.3.1 Sorting algorithms
-Bubble: beginning at 1st element, comparing one element to the next and swapping should the higher number be before the right-most element. This happens with the next 2 elements (2nd and 3rd) and repeating the process. When the sort reaches the end, it goes again from element 1 - the pass counter increments. This continues until no more comparisons are needed.
-Least efficient sort
-Time complexity O(n^2)
-Insertion: split the list into 2 parts, sorted and unsorted side. First element is put in sorted list. Sequentially, the elements in the unsorted list moves to the a certain position in the sorted list by comparing it to existing elements in the list. This is more efficient than a bubble sort
-Time complexity: O(n^2)
-Merge: Use of divide and conquer and recursive algorithm. Involves splitting the list into individual elements. Merge and sort pairs of sublist by comparing and determining the order. Repeat this until there is 1 list.
-Time complexity: O(nlogn)
-Quick: Use of divide and conquer. A pivot value is selected and moved to the end of the list. The left-most first larger value is selected. The right-most first smaller value is selected. These two are swapped. This repeats until the right-most smaller value is SMALLER than the left most bigger value.
The current left-most bigger value is swapped with the pivot. The previous pivot is now in its correct location. The process repeats until sorted.
-Fastest sorting algorithm
-Time complexity: O(nlogn)
2.3.1 the hated algorithms
-A* / DIjsttkra
2.3.1 Data structures
-Stacks: LIFO, data is added and removed from the top. Must have a pointer to the top element
-Push(item) - adds item, Pop() - removes item, Peek() - shows top item, IsEmpty() - true or false, IsFull() - true or false.
-Queue: FIFO, data is added and removed in the order it was added. Must have a header and tail pointer
-Enqueue(item) - add item, dequeue() - remove front item, IsEmpty() - true or false, IsFull() - true or false.
-Trees: One root node, with leaf nodes
-Binary: One root node, maximum 2 leaf nodes per node.
-Pre-order: Node is visited before any leaf nodes.
-In-order: Left-most visited then go right from there
-Post-order: Node is visited after all leaf nodes from the left to right have been visited
-Linked-list: dynamic data structure. Each element has a data piece, a header and a pointer
-Breadth-first: Search layer by layer, usually left to right, beginning with root node until all layers have been visited
-Depth-first: Same as post-order. Nodes are visited after all leaf nodes from left to right have been visited
