105 - C949 v4 Study Guide.pdf

1. Finiteness in an algorithm

An algorithm must complete in a finite number of steps and not run indefinitely.

2. Definiteness in an algorithm

Each step must be precisely and unambiguously defined.

3. Input characteristic of an algorithm

One or more initial values that feed into the algorithm, taken from a defined domain.

4. Output characteristic of an algorithm

The algorithm must produce at least one result (output) related to the input.

5. Effectiveness in an algorithm

All operations should be basic enough to be performed in finite time with available resources.

6. Generality in an algorithm

The algorithm should solve a broad set of problems (not just a single case).

7. Modularity of an algorithm

Breaking a problem into smaller modules or steps, aiding clarity and organization.

8. Correctness of an algorithm

It must produce the desired output for all valid inputs; logically verified.

9. Maintainability of an algorithm

The structure should be clear so updates can be made with minimal changes.

10. Functionality of an algorithm

It addresses a real-world problem with clear, logical steps.

11. Robustness in an algorithm

The algorithm can handle unexpected or invalid inputs without crashing.

12. User-friendliness of an algorithm

The logic is clear enough to be easily explained to others.

13. Simplicity in an algorithm

A simpler approach is easier to implement, read, and debug.

14. Extensibility in an algorithm

It can be adapted or extended for new needs with minimal refactoring.

15. Brute Force algorithm

Tries all possible solutions exhaustively; simple but can be very inefficient for large inputs.

16. Recursive algorithm

Solves a problem by breaking it into smaller instances of itself until a base case is reached.

17. Encryption algorithm

Transforms data into a secure, unreadable form to ensure confidentiality.

18. Backtracking algorithm

Explores partial solutions, backtracking when a path leads to a dead end (common in puzzles).

19. Searching algorithm

Finds a target item within a collection; e.g., linear search, binary search.

20. Sorting algorithm

Rearranges data into a specified order, e.g., ascending or descending.

21. Hashing algorithm

Converts data into a fixed-size value (hash) for fast lookups in a hash table.

22. Divide and Conquer algorithm

Splits the problem into smaller subproblems, solves them, and combines their solutions.

23. Greedy algorithm

Locally optimal choice at each step, hoping to reach a globally optimal solution.

24. Dynamic Programming algorithm

Saves intermediate results to avoid repeated calculations (overlapping subproblems).

25. Randomized algorithm

Incorporates randomness in its process, often for approximations or probabilistic solutions.

26. Key concepts of recursion

Consist of a Base Case (stops recursion), a Recursive Case (smaller subproblem), and a Call Stack.

27. Factorial as a classic recursive example

n! = n × (n−1)!, with 0! = 1 as the base case.

28. Advantages of recursion

Often more elegant and natural for tree-like or divide-and-conquer problems.

29. Disadvantages of recursion

Can cause extra function-call overhead and potential stack overflows if depth is large.

30. Linear Search definition

Checks each element sequentially until the target is found or the list ends; O(n) time worst case.

31. When to use Linear Search

Useful for small or unsorted datasets, or when simplicity is more important than performance.

32. Binary Search definition

Requires a sorted list; repeatedly halves the search range to find the target in O(log n) time.

33. When to prefer Binary Search

When data is sorted and you need faster lookups (logarithmic vs. linear).

34. Compare worst-case complexity of Linear vs. Binary Search

Linear Search: O(n); Binary Search: O(log n). Binary is faster but requires sorting.

35. Interpolation Search

Estimates the position of the target based on its value; average O(log log n), worst O(n).

36. DFS vs BFS in graphs

DFS goes deep along a path before backtracking; BFS visits neighbors level by level. Both O(V+E).

37. Bubble Sort overview

Repeatedly swaps adjacent elements if out of order; worst/average O(n²), best O(n) if nearly sorted.

38. Selection Sort overview

Finds the minimum and swaps it with the first unsorted position; O(n²) in all cases.

39. Insertion Sort overview

Builds a sorted portion by inserting each new element into its correct spot; O(n²) worst/avg, O(n) best.

40. Merge Sort overview

Divide-and-conquer: split the array, recursively sort halves, then merge; O(n log n) in all cases.

41. Merge Sort complexity

Stable sorting, consistently O(n log n) in best, average, and worst cases.

42. Quicksort overview

Partitions around a pivot and recursively sorts each side; average O(n log n), worst O(n²).

43. Why pivot selection is critical in Quicksort

A poor pivot leads to unbalanced partitions and worst-case O(n²) performance.

44. Heap Sort overview

Builds a heap, repeatedly removes the root (max or min), and re-heapifies; O(n log n), in-place, not stable.

45. Counting Sort overview

Counts occurrences of each distinct value (within a limited range); O(n + k).

46. Radix Sort overview

Sorts digit by digit (or character by character) using another stable sort; O(n·k).

47. Bucket Sort overview

Distributes elements into buckets, sorts each bucket individually; average O(n + k), worst O(n²).

48. Shell Sort overview

A generalized insertion sort using a gap sequence; typical average ~O(n^(3/2)), depends on gap choice.

49. Definition of Big O notation

Describes the upper bound of an algorithm’s time (or space) complexity as input size grows.

50. List of common Big O complexities

O(1), O(log n), O(n), O(n log n), O(n²), O(2^n), O(n!).

51. Big O simplification rules

Ignore constants, keep the dominant term, treat different log bases as the same, etc.

52. Best, Worst, Average case definitions

Best: minimal operations, Worst: maximal operations, Average: typical scenario (often used).

53. Data Type vs Data Structure

Data Type: defines kind of data (e.g., int); Data Structure: organizes data (e.g., arrays, linked lists).

54. Abstract Data Type (ADT)

A model specifying operations and behavior, not implementation details.

55. Enumeration (enum)

A type with a fixed set of named constants; enhances readability and type safety.

56. Array basics

A contiguous block of memory for homogeneous elements; O(1) index access, O(n) inserts in the middle.

57. Typical array operations

Access O(1), linear search O(n), insertion/deletion at end O(1) amortized (dynamic array), at index O(n).

58. Linked List basics

Nodes linked by pointers; dynamic size, O(n) to access by index, easy insertion/deletion at head.

59. Linked List operation complexities

Access O(n), insert at head O(1), insert at tail O(n) unless tail pointer is maintained.

60. Stack ADT definition

LIFO structure with push() and pop() in O(1) average time.

61. Where stacks are used

Function call stack, undo mechanisms, backtracking, depth-first search.

62. Queue ADT definition

FIFO structure with enqueue() and dequeue() in O(1) average time.

63. Queue use cases

Used in scheduling, breadth-first search, buffering (e.g., printer queues).

64. Deque definition

Double-ended queue allowing insertion/removal at both front and rear in O(1).

65. Deque use cases

Useful for sliding window problems, scheduling, or any scenario needing both ends accessible.

66. Bag (multiset) definition

A collection that allows duplicates; used for counting occurrences (e.g. word counts).

67. Hash Table definition

Maps keys to indices via a hash function; average O(1) for insert, search, delete.

68. Properties of a good hash function

Deterministic, uniform distribution of keys, and quick to compute.

69. Collision handling in hash tables

Chaining (linked lists in buckets) or open addressing (linear/quadratic probing, double hashing).

70. Tree data structure

Hierarchical structure with nodes (root, children, leaves); can be binary, n-ary, etc.

71. Forms of binary trees

Full (0 or 2 children), Complete (filled levels left to right), Perfect (all leaves same level), Balanced (height difference ≤ 1).

72. Binary Search Tree (BST) property

Left subtree < node < right subtree; in-order traversal is sorted.

73. BST operations

Insert, search, delete in average O(log n); can degrade if not balanced.

74. Tree traversal types

Pre-order (NLR), In-order (LNR), Post-order (LRN), Level-order (BFS by levels).

75. AVL Tree definition

A self-balancing BST that keeps subtree heights within 1; uses rotations if unbalanced.

76. Red-Black Tree definition

A BST with nodes colored red or black to maintain balanced height; O(log n) operations.

77. B-Tree definition

A self-balancing tree with multiple children per node, often used in databases and filesystems.

78. Heap data structure

A complete binary tree satisfying heap property (max-heap or min-heap).

79. Core heap operations

Insert O(log n), remove-root O(log n), peek O(1), heapify O(n).

80. Indexes of children in a binary heap

For node at index i: left child = 2i+1, right child = 2i+2 (0-based indexing).