H446 Paper 2 Prep

Match the following 2.1 Elements of computational thinking

• Thinking ahead

• What data will be needed often, we should cache this

• Thinking logically

• Creating a step-by-step solution to the problem.

• Thinking procedurally

• The parts of a problem that can be tackled at the same time.

• Thinking abstractly

• Breaking down a complex problem into smaller, more manageable parts

• Concurrently

• Simplifying a problem by focusing on the important information only.

Match the following 2.2.1 Programming techniques

• Iteration

• Combining data and methods that operate on that data into a single unit, or class

• Recursion

• The mechanism by which one class can get the attributes and methods from another class.

• Inheritance

• A function that calls itself in order to solve a problem.

• Polymorphism

• Repeating a set of instructions a certain number of times or until a condition is met.

• Encapsulation

• The ability to present the same interface for different underlying forms (data types).

Match the following 2.2.2 Computational methods

• Divide and Conquer

• All possible solutions to a problem, building and abandoning paths to determine the solution.

• Simulation

• Breaking a problem into smaller sub-problems, solving each sub-problem

• Data Mining

• A model that can imitate the operation of a real-world process or system over time.

• Simulation

• Creating a model that can imitate the operation of a real-world process or system over time.

• Backtracking

• Process of searching large volumes of data for patterns.

Match the following Performance Modeling questions

• Scalability

• The ability of a system to handle more work or grow larger.

• Throughput

• The amount of work a system can do in a certain amount of time.

• Latency

• The delay before a transfer of data begins following an instruction for its transfer

• Bottleneck

• Testing how well a system performs when many tasks are done at the same time.

• Load Testing

• A part of the system that slows everything else down.

Match the following

• Worst Case

• Notation for running time

• Space Complexity

• Maximum amount of time an algorithm can take to complete

• Time Complexity

• The amount of memory an algorithm uses in relation to the input size

• Best Case

• Minimum amount of time an algorithm can take to complete.

• Big O Notation

• How long an algorithm takes to complete a function

Match the following search algorithms definitions

• Depth-First Search (DFS)

• Explores as far down a branch as possible before backtracking.

• Hash Table Search

• Explores all neighbors at the present depth level before moving on to nodes at the next depth level.

• Linear Search

• Operates by dividing the search interval in half repeatedly; requires a sorted list.

• Binary Search

• Checks each element in a list sequentially until the desired element is found or the list ends.

• Breadth-First Search (BFS)

• Uses a function to directly compute the index of the desired element.

Match the following sorting algorithms definitions

• Bubble Sort

• repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.

• Merge Sort

• picks an element as a pivot and partitions the array around the pivot.

• Insertion Sort

• builds the final sorted array one item at a time, with each new item being inserted into its correct position.

• Selection Sort

• repeatedly selects the smallest (or largest) element from the unsorted portion and moves it to the sorted portion.

• Quick Sort

• divides the array into two halves, recursively sorts them, and then merges the two sorted halves.

Match the following Shortest Path algorithms

• Dijkstra's

• A method to find the shortest path between one place and all other places on a map.

• Heuristic

• A technique used in A* algorithm to estimate the cost from the current node to the goal

• A* (A-star)

• Looks at depth level before moving on to nodes at the next depth level.

• Breadth-First Search (BFS)

• A heuristic (guess) used to improve the efficiency of the search

• Weighted Graphh

• A numerical value representing the cost to traverse that edge.

Match the following data structures

• Stack

• linear data structure where each element points to the next, allowing for efficient insertion and deletion

• Linked List

• collection of elements identified by index, stored in contiguous memory locations.

• Binary Search Tree (BST)

• hierarchical data structure where each node has at most two children

• Array

• linear data structure that follows the Last In, First Out (LIFO) principle.

• Queue

• inear data structure that follows the First In, First Out (FIFO) principle

Match the following Big O Notation

• O(n)

• me it takes grows really fast as the number of items increases

• O(2^n)

• Time it takes grows directly with the number of items.

• O(1)

• Time it takes grows quickly, but not as fast as doubling

• O(log n)

• Takes the same amount of time no matter how many items there are.

• O(n^2)

• Time it takes gets much longer as the number of items doubles