Skip to content
Ameen Abozaid
Englishالعربية
BEG-017

Introductory algorithms

  • 7 Lessons
  • 73 min of reading
  • 4 h practice (estimate)
Start module
On this page 8 topics

Overview

Topics

  • Linear search
  • binary search
  • bubble sort
  • selection sort
  • basic time complexity

Learn first

73 min of reading · 4 h of practice (estimate)

Learning outcomes

  1. Implement linear search and binary search and state when binary search applies.
  2. Implement bubble sort and selection sort and trace them on a small array.
  3. Count the operations of each algorithm for small inputs and compare growth informally.

Lessons

  1. 01What an algorithm is11 min read
  2. 02Linear search9 min read
  3. 03Binary search11 min read
  4. 04Bubble sort10 min read
  5. 05Selection sort10 min read
  6. 06Counting steps: a first look at efficiency11 min read
  7. 07Demo: racing linear and binary search11 min read

Lab and exercises

Lab

BEG-017-LAB1 · Race the algorithms

Outcomes: 1–3 · Time: ~2 h

  1. Implement linearSearch and binarySearch.
  2. Build sorted arrays of 1,000, 100,000, and 10,000,000 elements.
  3. Time both searches (target missing, worst case) with System.nanoTime(); repeat a few times.
  4. Present a results table and write a short explanation of the trend.

Acceptance: correct implementations; written explanation of the trend.

Exercises (assessment: five exercises including tracing a sort by hand)

IDOutcomeTask
BEG-017-EX011Implement linearSearch(int[] a, int target) returning the index or -1.
BEG-017-EX021Trace binary search for 23 in [2, 5, 8, 12, 16, 23, 38]; state when binary search applies.
BEG-017-EX032Trace bubble sort by hand on [5, 1, 4, 2], showing the array after each pass.
BEG-017-EX042Implement selection sort and test it on an empty and a one-element array.
BEG-017-EX053Add a comparison counter to linear search and bubble sort; report counts for n = 10, 20, 40 and describe the growth.
Show solutions
  • EX01 The loop from L02.
  • EX02 low 0, high 6, mid 3 (12 < 23) so low 4; mid 5 (23) found at index 5. It applies only when the data is sorted.
  • EX03 After pass 1: [1, 4, 2, 5]; pass 2: [1, 2, 4, 5]; pass 3: no swaps, sorted.
  • EX04 Code from L05; for empty and one-element input the loops do not run, which is correct.
  • EX05 Linear worst case: 10, 20, 40 (doubles). Bubble: 45, 190, 780 (about four times when n doubles).
  • The informal growth comparison is also in the lab explanation.

Quiz

Outcomes: O1 searching · O2 sorting · O3 counting steps.

A self-check for you: nothing is graded, saved or sent anywhere. Choose an answer, then check it. You can try again as often as you like.

  1. 1Binary search requires the data to be:O1
  2. 2Linear search returns -1 when:O1
  3. 3About how many steps does binary search need for 1,000 sorted items?O1
  4. 4A safer middle calculation is:O1
  5. 5Bubble sort works by:O2
  6. 6After the first bubble-sort pass, the largest value is:O2
  7. 7Selection sort each pass:O2
  8. 8If n doubles, linear search work about:O3
  9. 9If n doubles, bubble sort work about:O3
  10. 10Which grows slowest as n grows?O3

Practical part

Five exercises BEG-017-EX01 to EX05 (including the hand trace of a sort) plus the race lab. Pass: at least four exercises correct, correct implementations, and a written trend explanation.

Common mistakes

Binary search on unsorted data; integer overflow in (low + high) / 2 (mention); off-by-one in loop bounds.

Assessment

5 exercises including tracing a sort by hand.

Career relevance

Formalized in BEG-039; interview staple at Junior level.

Type to search levels, phases, modules and lessons.