Algorithm Design Principles, Explained with Code Examples

UPI Study › Courses › Programming in C › Free lessons › Lesson 1.5 Free with a free account

Algorithm Design Principles

Programming in C · Chapter 1: Programming Fundamentals, Pseudocode, and Program DevelopmentSection 1.5 · lesson 5 of 788 min · free with a free account

← Writing Pseudocode for Program DesignNext lesson: The Program Development Workflow →

Earn 3 college credits for Programming in CRecommended for credit by NCCRS · Computer Science 240 · self-paced · one payment, lifetime access
Enroll in Programming in C · $250 →Download the syllabus (PDF)

In this lesson

Build algorithms from sequence, branching and looping, and compare their growth.

  • Identify sequence, branching and looping in an algorithm
  • Trace a while loop and explain how an infinite loop happens
  • Compare one-by-one search with halving on a sorted list
  • Explain performance as how work grows with the size of the input

Free study notes

Get this lesson's notes by email

The key points and 4 practice questions with answers, in your inbox. One email, free.

One email. Unsubscribe in one click.

Transcript

Everything said in the video, section by section (1,098 words). Read along, or search it.

Opening Claim

Three Moves Behind Every Program

Here's a surprise. Every program ever written, from a pocket calculator to the biggest video game, is built from just three kinds of moves. Do steps in order. Pick one path or another. Repeat something. Learn to spot those three moves, and any plan stops looking like a jumble. Then a second skill: telling a fast plan from a slow one, just by counting.

Definition

Sequence, Branching and Looping

Think about LEGO. A huge castle and a tiny car use the same few kinds of bricks, just arranged differently. An algorithm is a clear, step-by-step plan for solving a problem. And every algorithm is built from three blocks. Sequence: do steps one after another, in order. Branching, also called selection: ask a yes-or-no question, and take one path or the other. Looping, also called repetition: do some steps again and again, while a question keeps answering yes. In nineteen sixty-six, Corrado Böhm and Giuseppe Jacopini proved that any flowchart algorithm can be rebuilt from just these three. They're enough for everything.

Sequence

Same Steps, Different Order

Here's each block as a tiny C program. You don't need every symbol yet. First, sequence: Priya tracks her tokens, top to bottom. She starts with ten. A game of Space Dash costs three. She wins a five-token bonus. Ten take away three is seven, plus five is twelve. Move the printf line up, right after the first line, and it prints ten instead: the game and the bonus haven't happened yet. Same steps, different order, different answer.

Branching

Sixty-Four Tickets Pick a Prize

Branching: at the prize counter, Sam's tickets decide his prize. He has sixty-four. The question in the round brackets after if gets a yes or a no, and only one of the two blocks runs. Sixty-four is fifty or more, so the yes path runs, and the sticker line is skipped. The last line sits after the whole branch, so it runs no matter which path was taken.

Looping

Three Rounds and an Infinite Loop

Looping: a game has three rounds. Instead of writing the same line three times, a while loop asks its question before every trip. Trace it like the computer. Round is one, then two, then three, and each time the answer is yes. After round three, the last step makes round four. Now, is four three or less? No. The loop ends, and game over prints. Forget the step that adds one, and round stays one forever. The answer is always yes, and the game never stops. That's an infinite loop.

Quick Check

Counting Rounds Up to Five

Quick check. In that loop, the question changes to: round less than or equal to five. How many go lines print before game over: three, five, or six? Pause, and decide. Five. Rounds one through five each answer yes. Then round becomes six, six is not five or less, and the loop ends. Three ignores the change. Six would need the question to let six through, and it doesn't.

Combining Blocks

One Turn of Skee-Ball

Real tasks mix all three. Priya plans one turn of Starlight Skee-Ball. First, take one token, and set the score to zero. That's sequence. While balls are left, roll a ball and add its points to the score. That's looping. If the score is bigger than the high score, save it as the new high score. That's branching. Finally, show the score: sequence again. The blocks sit in order like beads on a string, and blocks can also sit inside each other, like a branch inside a loop. When a task feels too big, ask: what happens in order, what depends on a yes-or-no answer, and what repeats? The answers outline your algorithm.

Search Strategies

One by One or Halving

Now the second skill. Two algorithms can both give the right answer, while one takes far longer. How can you tell, without a stopwatch? Sam is hunting for a player's card in the high-score box. I'll just flip through them one by one, he says. Priya points out that the cards are already in order by player number, like words in a dictionary. Open the middle, she says. If the card you want comes later, ignore the whole first half. Then do it again with what's left. With sixteen cards, and the card Sam wants at the very end, one by one takes sixteen looks. Halving keeps sixteen, then eight, four, two, one: five looks. Same card, and less than a third of the looks.

Growth

How the Work Grows With the Pile

Sixteen is a small pile. The real difference shows as the pile grows. Priya counted the looks for bigger piles, with a short program. It also counts a third job: if every player high-fives every other player once, how many high-fives happen? Read one column at a time. One by one grows at the same speed as the pile. Ten times the players, ten times the looks. Halving barely grows. Doubling the pile adds just one look, because the first look cuts it right back. Ten thousand cards take only fourteen. Everyone pairs explodes. Each of n players high-fives the n minus one others, counting each twice. So it's n times n minus one, over two. Ten players: forty-five. Ten times the players means about a hundred times the high-fives.

Performance

Halving Needs a Sorted Pile

That's what programmers mean by an algorithm's performance. Not the time on one machine, but how the work grows as the input grows. A plan that's fine for ten players can be hopeless for ten thousand, and you can spot it with nothing more than counting. One warning. Halving needs the pile in order. If the cards are shuffled, the middle card tells you nothing, and you could throw away the right one. For a shuffled pile, one by one is the honest choice.

Quick Check

Halving Four Thousand Cards

Quick check. Halving finds a card among one thousand sorted cards in ten looks. About how many looks for four thousand sorted cards: twelve, twenty, or forty? Pause, and decide. Twelve. Four thousand is two doublings of one thousand, and each doubling adds one look: ten, eleven, twelve. Forty assumes the looks grow as fast as the pile; that's one by one. Twenty doubles the looks, but halving only adds.

Key Takeaways

Three Blocks and Counting Steps

To sum up. Every algorithm is built from sequence, branching, and looping. Every loop needs a step that moves it toward its end, or it never stops. Real plans string the blocks together, and nest them inside each other. And performance is how the work grows with the input: count the steps, and ask what happens when the pile grows.

Think About It

Seven Guesses From One to a Hundred

Something to think about. A friend picks a whole number from one to a hundred. You guess the middle, and they say higher or lower. You never need more than seven guesses. Why seven? And how many would you need for one to a thousand?

About Programming in C at UPI Study

Programming in C (Computer Science 240) is a self-paced online course of 78 video lessons in 11 chapters, from pseudocode and your first program to data types, decisions, loops, functions, arrays, strings, pointers, files, structures, dynamic memory and linked lists. It carries a NCCRS credit recommendation for 3 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →

Compare: C vs C++

Why take it here

Why students take Programming in C with UPI Study

How programs work close to the machineProgramming in C teaches how a program uses memory: variables and data types, control flow, functions, arrays and strings, pointers, files, structures and dynamic memory. C is the base for operating systems, embedded devices and many computer-science courses.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Programming in C carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Algorithm Design Principles

What are the three basic building blocks of an algorithm?
The three building blocks are sequence, branching and looping. Sequence runs steps one after another in order. Branching, also called selection, asks a yes-or-no question and takes one path or the other. Looping, also called repetition, repeats steps while a condition stays true. In 1966, Corrado Böhm and Giuseppe Jacopini showed that any flowchart algorithm can be rebuilt from these three structures.
What causes an infinite loop?
An infinite loop happens when a loop's condition never becomes false. A while loop checks its condition before every pass, so the loop needs a step that moves it toward its end, such as adding one to a counter. If a loop runs while round is three or less and nothing ever changes round, the answer stays yes and the loop never stops.
Why is halving faster than searching items one by one?
Halving is faster because each look throws away half of the remaining items. Searching 16 sorted cards one by one can take 16 looks, but halving takes at most 5, as the pile shrinks from 16 to 8, 4, 2 and 1. Doubling the pile adds only one look, so 10,000 cards need at most 14. Halving works only when the items are in order.
What does algorithm performance mean?
Algorithm performance describes how the amount of work grows as the input grows, not the time on one machine. Counting steps shows it. One-by-one search grows at the same rate as the pile, halving barely grows, and pairing every player with every other grows much faster. With n players, the number of pairs is n times (n minus 1), divided by 2, so 10 players make 45 pairs.

About the Programming in C course

How many college credits is Programming in C?
Programming in C (Computer Science 240) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Programming in C cost and what is included?
$250, paid once, with lifetime access: all 78 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Programming in C take?
It is self-paced with no deadlines. The 78 lessons total about 9 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in Programming in C.

78 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Programming in C →Download the syllabusEvery course with PRO →
Programming in C
3 credits · NCCRSEnroll →