CPSC 217

computer

a device that receives, processes, and represents data

Moore's Law

-States that the complexity for a minimum component has increased at a rate of roughly a factor of 2 per

-year and although there is no reason to believe it will not remain nearly constant for at least 10 years

- Was not a law of nature, but just an observed path of exponential growth

- Held true until 2020, the complexity for minimum component loss doubles every year

computer science

study of computatio and computer technology, hardware, and software. diverse, problem solving interface

software engineering

- Was created by people

- How we develop large software projects

- How we model problems so that many people can work on it at one and ensuring software is working the way its suppose to

artificial intelligence

studies and develops intelligent machines and pieces of software

Difference Engine

→ Dates back to 1847-1849 by Charles Babbage

- The babbage difference engine was first completed in 1991 where a museum took his designs

and tweaked it until it worked

- Used to evaluate 7 degree polynomials to 31 decimal digits

ENIAC (Electronic Numerical Integrator and Computer)

completed in 1946. has about 17468 vacuum tubes

complexity theory

how efficiently can the problem be solved in terms of time and memory space

computability theory

Asking if a problem can be solved with a computer, some things are not (Ex. Halting problem)

top down design

start with the entire problem, break into 3-5 smaller problems, solve problems

algorithm

- A finite sequence of effective (unambiguous and possible to perform) steps that solve a problem

- Expressed in a human-readable form, which is flexible as long as your intended audience understands

it, and more is fine

- Does not have to be words, can be pictures

programming

translating algorithms into a computer language

programming language

allows users to control the behaviour of a computer

levels of abstraction

1. Human Languages → Are the most general and have the highest level of abstract

2. High Level Programming Languages (Ex. Python) are second highest

3. Low Level Programming Languages

4. Machine Language → Are the most specific and have the lowest level of abstract

comments

provide information to someone reading the code

syntax error

identified as code is loaded, no statement executed

runtime error

identified as the program runs, program does not complete successfully

logic error

program runs to completion but generates incorrect results

magic numbers

an unnamed and/or poorly documented numeric constant without obvious meaning

UTF-8

is another encoding scheme for characters, which is compatible with ASCII

ASCII (American Standard Code for Information Interchange)

a code for representing English characters as numbers, with each letter assigned a number from 0 to 127

Boolean logic

the basis for computation in modern computers

Blackbox testing

test program without looking at the source code, functional/behavioural

Whitebox testing

design test cases for the program by looking at its source code, structural

condition coverage

→ Every decision point in the program is executed

- Has a low level of certainty, and runs only once

statement coverage

every statement in the program is executed

path coverage

every possible path through the program is executed

while loops

allow a statement that only appear in the program once to execute several times, executes as long as (while) a condition executes to true

for loops

allow a statement that only appears in the program once to execute several times, executes once for each value in a collection

pre-tested loop

loop condition is tested before the loop executes the first time, runs 0 or more times

post-tested loop

any loop where the condition is not checked until the loop has executed once, runs 1 or more times

infinite loop

a loop that never terminates, this is typically a bug

initialization errors

forget to initialize a value, initialize a variable to the wrong place

termination error

→ Loop runs one times too many or one times too less

- Also known as “off by one error”

- Creates an infinite loop

off by one error

loop body runs one time too many or one time too few

tracing code

examine each statement in sequence, perform whatever tasks the statement requires, recording values of interest (usually requires that the value of each variable is recorded), result of this could be the value of one or more variables or the output generated

nested loops

the body of the loop can contain another loop

break

entire loop ends immediately, execution continues at the first statement after the body

continue

current iteration ends immediately, execution returns to the top of the loop

function

a named set of statements, perform some tasks, may require parameters, or may return values

parameter

allow us to provide data to a function, the name of the parameter variable in the function definition

argument

the value placed in brackets after the function name when the function

named argument

allow users to assign arguments to parameters in any order

global variables

defined outside the function, can be read anywhere in the program after it is assigned a value

scope

determines the portion of a program where a name can be used

preconditions

conditions that must be true before the function executes, if any precondition is not met, the function may not behave correctly

postcondition

Conditions that are guaranteed to be true after the function executes

- If the condition does not make the post-condition true then the function has a bug that needs to be fixed

- ‘Promises’ made by function

- What will be true after the function is called

list

a collection of values

selection sort

while there are still elements in the unsorted list, find the smallest element, remove it, append it to the sorted list

insertion sort

while there are still elements in the unsorted list, remove an element from the unsorted list, find the correct location for that element in the sorted list, insert the element at the correct location

bubble sort

• keeps comparing and swapping numbers next to each other

• It keeps doing it over and over again until everything is in the right numerical order

sorted method

takes an unsorted list, returns a new list sorted into increasing order

sort method

invoked on a list using dot notation, does not require any parameters, modifies the list, sorting it into ascending order

tuples

- When you want to return multiple things from a list

- Is similar to lists, but is more restrictive and cannot change

- Items cannot be assigned individually

- () → empty tuple

- (3,) → length one tuple

- aTuple = (1, “ICT”, 3.14)

dictionary

a collection of values, where each value in the dictionary has a unique identifier associated to it

mutable type

A compound data type whose elements can be assigned new values. (ie, list and dictionaries)

immutable type

A compound data type whose elements can NOT be assigned new values. (ie, float, int, boolean, string)

files

- Variables are temporary → the value is lost when program ends and/or if computer loses power

- Files provide a less volatile form of storage → values are retained after the program ends and are

retained when the computer loses power

text file

encoded using ASCII or Unicode, can be viewed with editors such as Emacs and Notepad, (ie. Python source files, web pages, .txt extension, .csv extension)

binary files

Contain arbitrary sequence of bits which do not perform to ASCII or Unicode characters (ie. images, word processor files, sounds, videos, powerpoint, programs (.exe))

sequential access

start at the beginning of the file (typically used for text files), read data from the file in the order that it occurs (may also be used for a binary file)

escape sequences

Provides a mechanism for placing that controls spacing inside a string

- Begins with a \ (backslash)

- Followed by one character describing the character that should be inserted

- Common escape sequence

command line arguments

values entered by a user when running a program from a command line

exceptions

are thrown when an error occurs, can be caught to recover from te error

database

a structured collection of records organized for ease of search and retrieval

primary key

a unique value associated with each row in a table, typically an integer

foreign key

a primary key value from another table residing in the current table

Recursion

When a function calls itself.

base case

does not make a recursive call, permits function to terminate

recursive case

function calls itself, generally must be a call to a small or simpler version of the problem

Fibonacci numbers

A pattern of numbers. It is found in galaxies, shells, flowers, humans, and other things.

Bloom’s Taxonomy

- Was created by Benjamin Bloom, who is an educator who studied how people think

- Identified 6 levels of competence

Blooms 6 levels of competence

- From least to most competence;

- Knowledge → Recalling something you have heard or read

- Comprehension → Inferring causes, and predicting consequences

- Application → Solving a problem by following a known or established pattern

- Analysis → Identifying bigger patterns, then separating a complex system into pieces, then

finding and identifying the relationship between those pieces

- Synthesis → Using old ideas to create new ideas, then combining several ideas to solve a

problem in a new and unique way (Also generalized from facts)

- Evaluation → Comparing multiple ideas, then identifying strengths and weaknesses of each

What are the Escape Sequences?

- \n → linefeed (newline)

- \t → tab (lining up columns)

- \” → double quotes (string with double questions)

- \\ → backslash