CompSci Unit 5 - Algorithms

0.0(0)
Studied by 0 people
linked notesView linked note
call kaiCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/16

encourage image

There's no tags or description

Looks like no tags are added yet.

Last updated 5:22 AM on 3/14/25
Name
Mastery
Learn
Test
Matching
Spaced
Call with Kai

No analytics yet

Send a link to your students to track their progress

17 Terms

1
New cards
What is an algorithm?
A finite set of instructions to accomplish a task.
2
New cards
What are the three main components of algorithms?
Sequencing, selection, and iteration.
3
New cards
What is a decidable problem?
A decision problem for which an algorithm can be written to produce a correct output for all inputs/instances.
4
New cards
What is an undecidable problem?
A problem for which no algorithm can be constructed that is always capable of providing a correct yes/no answer.
5
New cards
What is a linear (sequential) search?
A search method that checks each element of a list in order until the desired value is found or all elements are checked.
6
New cards
How does a binary search work?
It checks the middle value, eliminates half the values, and chooses a new middle until the correct number is found; only works on sorted data.
7
New cards
What is selection sort?
An algorithm that selects what should be at each index and swaps it with the current value, repeating for each index until sorted.
8
New cards
What is insertion sort?
An algorithm that compares each value with the one immediately before it and shifts it left until it is in the correct location.
9
New cards
What is efficiency in the context of algorithms?
A measure of how many steps are needed to complete an algorithm in the worst-case scenario.
10
New cards
What does linear efficiency indicate?
An algorithm that runs n times for a given list size n, indicating linear time performance.
11
New cards
What is the worst-case efficiency for insertion and selection sort?
Runs a maximum of (n^2 - n)/2 times, indicating polynomial time (n^2), which is often unreasonable.
12
New cards
What is exponential efficiency?

An algorithm where the list size n has 2^n subsets, indicating exponential time performance. runs in an unreasonable time

13
New cards
What is a brute force algorithm?
An algorithm that calculates the distance of every possible route to identify the shortest one.
14
New cards
What is a decision problem in algorithms?
A problem that has a yes/no answer.
15
New cards
What is an optimization problem?
A problem with the goal of finding the best solution.
16
New cards
What is a heuristic in algorithms?
An algorithm used that is good enough and runs in a reasonable time.
17
New cards
When is an algorithm considered undecidable or impractical?
When it is impossible (undecidable) or requires unreasonable time (impractical).