COMPUTER SCIENCE 101
CHALLENGE EXAM QUESTIONS &
ANSWERS(SCORED A+)
Algorithm - ANSWERa sequence of instructions that solve a problem
psuedocode - ANSWERa simplified programming notation between natural language
and programming language, used in program design
sequential search - ANSWERSearch algorithm where we look at each element in the
list until we find what we are searching or reach end of list. Complexity: best = O(1),
avg/worst = O(n)
binary search - ANSWERused with a sorted list. Look at the middle element and
compare to what we are searching for. If not the middle, repeat with the half of the
list our element will be in. Complexity: best = O(1), avg/worst = O(log n)
selection sort - ANSWERsorting algorithm that searches through list for max/min
value. Place element in correct location and repeat for the rest of list. Complexity:
O(n^2)
Constant time - ANSWERO(1)
Quadratic time - ANSWERO(n^2)
Big O - ANSWERdescribes the performance or complexity of an algorithm as input
grows to infinity
Desirable properties of an algorithm - ANSWER- Easy to use
- elegance
- efficiency
- correctness
Analysis of Algorithms - ANSWERthe study of the efficiency of algorithms
time efficiency - ANSWERthe amount of time an algorithm takes to do its job. There
is often a tradeoff between algorithmic time efficiency and space efficiency
library - ANSWERa collection of useful commands / functions, prewritten algorithms
typically with a shared purpose
abstraction - ANSWERa way to hide/reduce complex details of a problem
computer - ANSWERa device that:
1) takes input
2) processes the input in some way
, 3) produces output
computer science - ANSWERThe study of algorithms. includes:
1) their hardware realization
2) their software realization
3) their formal and mathematical properties
4) their real world application
unsolvable problem - ANSWERa problem in which no generalization algorithmic
solution exists
IDLE - ANSWERintegrated development and learning environment
Ada Lovelace - ANSWERfirst computer programmer
Linus Torvalds - ANSWERperson who started and developed the Linux kernel
positional numbering system - ANSWERnumbering system where value of each digit
depends on the digit itself and the position of the digit in the number
binary - ANSWERbase 2 positional numbering system
bit - ANSWERbinary digit
byte - ANSWERgroup of 8 bits
overflow - ANSWERoccurs when computer tries to represent a number hat exceeds
the maximum value
binary numbers - ANSWERused to store data internally for numerical values, letters,
graphics, etc.
two's complement - ANSWERflips the bits and add 1
sign/magnitude - ANSWERleftmost bit represents sign (0=positive, 1=negative) and
does not contribute to the magnitude of the number.
decimal - ANSWERbase 10 positional numbering system
octal - ANSWERbase 8 positional numbering system (3 bits = 1 octal digit)
hexadecimal - ANSWERbase 16
bias (in context of floating number) - ANSWERfixed value subtracted from exponent
half-precision floating point number - ANSWER16-bit floating point number
assumption - ANSWERthere is always a 1 immediately left of binary point. It is
assumed/removed. We save a bit by not storing the leftmost binary digit
CHALLENGE EXAM QUESTIONS &
ANSWERS(SCORED A+)
Algorithm - ANSWERa sequence of instructions that solve a problem
psuedocode - ANSWERa simplified programming notation between natural language
and programming language, used in program design
sequential search - ANSWERSearch algorithm where we look at each element in the
list until we find what we are searching or reach end of list. Complexity: best = O(1),
avg/worst = O(n)
binary search - ANSWERused with a sorted list. Look at the middle element and
compare to what we are searching for. If not the middle, repeat with the half of the
list our element will be in. Complexity: best = O(1), avg/worst = O(log n)
selection sort - ANSWERsorting algorithm that searches through list for max/min
value. Place element in correct location and repeat for the rest of list. Complexity:
O(n^2)
Constant time - ANSWERO(1)
Quadratic time - ANSWERO(n^2)
Big O - ANSWERdescribes the performance or complexity of an algorithm as input
grows to infinity
Desirable properties of an algorithm - ANSWER- Easy to use
- elegance
- efficiency
- correctness
Analysis of Algorithms - ANSWERthe study of the efficiency of algorithms
time efficiency - ANSWERthe amount of time an algorithm takes to do its job. There
is often a tradeoff between algorithmic time efficiency and space efficiency
library - ANSWERa collection of useful commands / functions, prewritten algorithms
typically with a shared purpose
abstraction - ANSWERa way to hide/reduce complex details of a problem
computer - ANSWERa device that:
1) takes input
2) processes the input in some way
, 3) produces output
computer science - ANSWERThe study of algorithms. includes:
1) their hardware realization
2) their software realization
3) their formal and mathematical properties
4) their real world application
unsolvable problem - ANSWERa problem in which no generalization algorithmic
solution exists
IDLE - ANSWERintegrated development and learning environment
Ada Lovelace - ANSWERfirst computer programmer
Linus Torvalds - ANSWERperson who started and developed the Linux kernel
positional numbering system - ANSWERnumbering system where value of each digit
depends on the digit itself and the position of the digit in the number
binary - ANSWERbase 2 positional numbering system
bit - ANSWERbinary digit
byte - ANSWERgroup of 8 bits
overflow - ANSWERoccurs when computer tries to represent a number hat exceeds
the maximum value
binary numbers - ANSWERused to store data internally for numerical values, letters,
graphics, etc.
two's complement - ANSWERflips the bits and add 1
sign/magnitude - ANSWERleftmost bit represents sign (0=positive, 1=negative) and
does not contribute to the magnitude of the number.
decimal - ANSWERbase 10 positional numbering system
octal - ANSWERbase 8 positional numbering system (3 bits = 1 octal digit)
hexadecimal - ANSWERbase 16
bias (in context of floating number) - ANSWERfixed value subtracted from exponent
half-precision floating point number - ANSWER16-bit floating point number
assumption - ANSWERthere is always a 1 immediately left of binary point. It is
assumed/removed. We save a bit by not storing the leftmost binary digit
