Algorithms and Programs*

• What is a recursion function?

  A function that calls itself, until the base is met.
• What is a validation?

  Ensures the data inputted is reasonable.
• What is a verification?

  Ensures the data is consistent.
• What are examples of verification checks?

  Double entry - enter the data twice and compare to ensure accuracy.

  Proof reading - human will read over the input to manually check.
• What is Big O Notation?

  A notation used to describe the efficiency of an algorithm (Time and Space).
• What is Dijkstra's Algorithm?

  Shortest path algorithm. Each edge must have an associated cost.
• Just learn it.

  
• What is a compression ratio?

  A ratio between the original file and the new compressed file.
• What is compression/decompression time?


  The amount of time it takes to compress or decompress a file.
• What is saving percentage?

  A percentage measure of how much smaller the compressed file is to the original.
• What is a bubble sort?

  Sorting algorithm that compares adjacent sets of data, repeating until the sort is complete.
• What is an insertion sort?

  Sorting algorithm that takes a data item into a temporary variable and clones it into its correct location. Repeats until all data items are in correct order.
• What is a quicksort?


  Select a data item to be a pivot and sort data items either left or right of the pivot into ascending order. Repeat until sorted.
• What is an algorithm?

  A set of instructions which provide a solution to a specific problem.
• Two methods of defining algorithms?

  • Pseudocode
  • Flowcharts
• What is pseudocode?

  A simplified programming language used to plan algorithms.
• What is flowcharts?

  Visual representation of a process or algorithm.
• Benefits of a recursive algorithm?

  Efficiency and simplicity. More elegant than non-recursive algorithms.
• Cons of a recursive algorithm?

  Stack overflow, slower execution time, endless loop, difficult to debug.
• Characteristics of a quick sort:

  • recursive algorithm, means it calls itself until the base is met.
  • has a stopping condition.
• The purpose of Dijkstra's algorithm is to find the shortest path between vertices on a graph. Each path between adjacent vertices is weighted with an intermediate cost.
• What is a binary search?

  Recursive algorithm that halves the amount of searches each iteration. Big O notation of 2Log n.
• When describing data compression?

  • data compression is reducing the amount of memory a file uses.
  • compression ratio is used, compressed file size over original file size.
  • lossy compression reduces file size and data is permanently lost.
  • lossless compression reduces file size and data can be retrieved back.
• An iteration is repeating a set of instructions a set number of times or until a condition is met.
• Factors that affect compression:

  Compression ratio

  Compression/decompression time

  Saving percentage