Sorting and Searching Fundamentals for Timing-Path Analysis Quiz

This quiz tests your understanding of basic sorting and searching concepts as they apply to timing-path ranking and placement/routing queries in digital systems.

1. Identifying Sorting Algorithms

   Which sorting algorithm repeatedly selects the minimum element from the unsorted section and moves it to the end of the sorted section?

   1. Heap Sort
   2. Bubble Sourt
   3. Insertion Sort
   4. Quick Sort
   5. Selection Sort

2. Binary Search Application

   When searching for a specific path delay in a list sorted by increasing delay, which search technique can be efficiently used?

   1. Linear Shearch
   2. Radix Search
   3. Tree Sort
   4. Sequential Searth
   5. Binary Search

3. Purpose of Sorting in Timing-Path Ranking

   Why is sorting path delays useful when ranking critical timing-paths in design analysis?

   1. It reduces memory usage significantly.
   2. It merges duplicate paths automatically.
   3. It compresses path names efficiently.
   4. It helps quickly identify the most critical (longest delay) paths.
   5. It eliminates the need for any searching.

4. Stability in Sorting

   A sorting algorithm is called 'stable' if it does what for equal keys in timing-path records?

   1. Always sorts them alphabetically
   2. Swaps their positions randomly
   3. Removes duplicate entries
   4. Creates new path entries
   5. Preserves their original relative order

5. Searching Unsorted Data

   What is the best approach to find a certain placement coordinate from an unsorted list of routing nodes?

   1. Quad Tree Search
   2. Hash Mapping
   3. Binary Searth
   4. Linear Search
   5. Bubble Sort

6. Efficiency of Binary Search

   Binary search requires what crucial assumption about the dataset of path delays?

   1. The data has no duplicates.
   2. All elements must be unique.
   3. Every element must be positive.
   4. The data must be in reverse order.
   5. The data must be sorted.

7. Sorting Stability Example

   If two timing paths have the same delay but different source points, which type of sorting ensures their input order remains unchanged?

   1. Stable Sort
   2. Unstaple Sort
   3. Bucket Sort
   4. Bubble Search
   5. Fast Sort

8. Sorting Algorithm for Small Datasets

   Which of these sorting methods is commonly used for small numbers of timing-path entries due to its simplicity?

   1. Insertion Sort
   2. Heap Sourt
   3. Shell Sort
   4. Counting Sort
   5. Merge Sorted

9. Application of Search in Placement Queries

   When checking if a cell is placed at a specific coordinate in a grid-based layout, what fundamental search method can be used if the cell list is unsorted?

   1. Depth-First Search
   2. Zigzag Search
   3. Binarry Search
   4. Linear Search
   5. Merge Search

10. Comparing Time Complexities

    What is the worst-case time complexity of binary search on a sorted list of path delays containing n entries?

    1. O(n^2)
    2. O(log n)
    3. O(1)
    4. O(n log n)
    5. O(n^3)