CS50x: Introduction to Computer Science Algorithms Syllabus

Algorithms syllabus — full chapter and topic list

Expand any chapter to see its topics and sub-topics. This is the whole examinable outline for Algorithms in CS50x: Introduction to Computer Science, not a summary of it.

1. 1

   Searching

   2 topics

   • Linear Search
   • Binary Search
2. 2

   Sorting

   3 topics

   • Bubble Sort
   • Selection Sort
   • Merge Sort
3. 3

   Algorithmic Efficiency

   2 topics

   • Asymptotic Notation
   • Running Time Analysis
4. 4

   Recursion

   2 topics

   • Recursive Functions
   • Base Cases

Algorithms flashcards for CS50x: Introduction to Computer Science

23 of 50 cards from the Algorithms deck — real questions with worked answers.

1. What is linear search?

   A search algorithm that checks each element of an array one at a time, from the first to the last, until the target value is found or the end of the array is reached.

2. What is the worst-case running time of linear search on an array of $n$ elements?

   $O(n)$ — in the worst case the target is the last element or absent, so all $n$ elements must be checked.

3. What is the best-case running time of linear search?

   $\Omega(1)$ — in the best case the target is the very first element checked.

4. Does linear search require the array to be sorted?

   No. Linear search works on any array, sorted or unsorted, because it simply inspects every element in order.

5. State the basic procedure (pseudocode idea) of linear search for a target $t$.

   For each element from index $0$ to $n-1$: if the current element equals $t$, return its position (success); if the loop ends without a match, report that $t$ is not present.

6. What is binary search?

   A search algorithm for sorted arrays that repeatedly compares the target to the middle element and discards the half of the array that cannot contain the target, halving the search space each step.

7. What precondition must hold before binary search can be used?

   The array must be sorted. On an unsorted array, discarding half of the elements could throw away the target, giving wrong results.

8. What is the worst-case running time of binary search on $n$ elements?

   $O(\log n)$, because each comparison halves the remaining search space.

9. What is the best-case running time of binary search?

   $\Omega(1)$ — the target might be exactly the middle element on the first comparison.

10. Describe the steps of binary search for a target $t$ in a sorted array.

    1) Look at the middle element. 2) If it equals $t$, done. 3) If $t$ is smaller, repeat the search on the left half; if larger, repeat on the right half. 4) If the remaining range becomes empty, $t$ is not present.

11. After $k$ steps of binary search on $n$ elements, how many elements can remain in the search space?

    At most $\frac{n}{2^{k}}$, since each step halves the search space. The search ends when $\frac{n}{2^{k}} \leq 1$, i.e. after about $\log_{2} n$ steps.

12. Approximately how many comparisons does binary search need in the worst case for an array of $1{,}000{,}000$ elements?

    About $20$, because $2^{20} = 1{,}048{,}576 \geq 10^{6}$, so $\log_{2}(10^{6}) \approx 20$.

13. In the classic phone book example, why is repeatedly tearing the book in half an $O(\log n)$ algorithm?

    Each tear discards half of the remaining pages, so a book of $n$ pages needs only about $\log_{2} n$ tears to narrow down to one page — doubling the book size adds just one extra step.

14. What is bubble sort?

    A sorting algorithm that repeatedly steps through the array, compares adjacent pairs of elements, and swaps them if they are out of order, so larger values "bubble" toward the end on each pass.

15. What is the worst-case running time of bubble sort?

    $O(n^{2})$ — roughly $(n-1)$ passes each doing about $(n-1)$ comparisons, i.e. $(n-1)(n-1) = n^{2} - 2n + 1$ comparisons.

16. What is the best-case running time of bubble sort (with the early-exit optimization)?

    $\Omega(n)$ — if the array is already sorted, one full pass makes no swaps, and the algorithm can stop after that single pass of $n-1$ comparisons.

17. What optimization lets bubble sort terminate early?

    Keep a counter or flag for swaps during a pass; if a complete pass makes zero swaps, the array is already sorted and the algorithm can stop immediately.

18. Describe one full pass of bubble sort.

    Move from index $0$ to $n-2$: compare each element with its right neighbor, and swap the pair if the left element is larger. After the pass, the largest unsorted element has reached its final position at the end.

19. After the first complete pass of bubble sort, what is guaranteed about the array?

    The largest element has "bubbled" to the last position; after $k$ passes, the largest $k$ elements are in their final sorted positions at the end.

20. What is selection sort?

    A sorting algorithm that repeatedly scans the unsorted portion of the array for its smallest element and swaps it into the leftmost unsorted position, growing a sorted region from left to right.

21. What is the worst-case running time of selection sort?

    $O(n^{2})$ — it performs $(n-1) + (n-2) + \cdots + 1 = \frac{n(n-1)}{2}$ comparisons.

22. What is the best-case running time of selection sort, and why?

    $\Omega(n^{2})$ — even on an already sorted array, selection sort must still scan the entire unsorted portion every round to confirm the minimum, so it cannot exit early.

23. Give the formula for the total number of comparisons selection sort makes on $n$ elements.

    $$\sum_{k=1}^{n-1} k = \frac{n(n-1)}{2} = \frac{n^{2}}{2} - \frac{n}{2},$$ which is $O(n^{2})$ after dropping constants and lower-order terms.

See more Algorithms flashcards →

Planning Algorithms for CS50x: Introduction to Computer Science

Algorithms (CS50x: Introduction to Computer Science) FAQ