Exam Flashcards
What is the definition of an algorithm?
sequence of ordered and precisely described steps to achieve a result/solve a problem.
-each step is expressed in terms of basic operations who’s meaning is completely specified
is there any ambiguity in algorithms?
no.
are algorithms guaranteed to produce a result?
yes, algorithms are guaranteed to produce a result.
do algorithms have to stop eventually.
yes! they have a finite number of steps..
What are the two methods to describe algorithms unambiguously?
flow charts and pseudo code
What is pseudo code?
is describing the steps of an algorithm in plain language.
define flow chart
visual representation of the steps in an algorithm.
In a flow chart, what does —–> the arrow mean?
its called a flow line. it indicates the next operation (the flow of operations) by the connecting symbol.
In a flow chart, what does the oval/circle mean?
it is used to represent the start and end of a flow chart.
in a flow chart, what does the slanted rectangle mean?
it is used for the input and output of operations. such as asking people for their height and name, and calculating the results
In a flow chart, what does the rectangle stand for?
it is used for any kind of operation and or data manipulation. e.g selected = height, or selected = name.
In a flow chart, what does the diamond symbol stand for?
it represents a conditional operation that determines which of the two paths the program will take. e.g. has every person in the room been asked yet?
What is runtime?
how long does it take to compute the results? how much work is it? how many steps/operations are carried out
What does N symbolize?
it symbolizes problem size.
what is runtime complexity?
described the performance of an algorithm, or how much processing power/time is required to run the algorithm.
what is problem size?
the number of elements of the input is the problem size… e.g. how many people are in the room to find the problem size for the tallest person algorithm
how can you tell if something is a linear algorithm?
if the runtime complexity = N (problem size)
this is because the number of steps in an algorithm will increase linearly with the problem size (N)
if N=80, then runtime will be 80
if the pseudo code is:
set sum to 0
for each height on the list add height to sum
set average sum to N
what type of algorithm is this describing?
Linear Algorithm.
because sum = N
How do you tell if an algorithm is Linear?
runtime complexity = N
How does binary search work?
if the list is organized, you identify the middle of the list and split it. again and again until you find your result.
What is the binary search complexity?
with every split necessary, the size of N doubles.
if there is 1 split, the problem size is 2.
if there is 2 splits, the problem size is 4.
if there are 3 splits the problem size is 8
if N increases (the number of splits) then the runtime increases not as much
What is the equation for binary search runtime complexity?
logN
logarithm to the base of 2 N
what kinds of sorting algorithms are there? (4)
binary search
selection sort
bubble sort
and Quicksort.
selection sort and bubble sort are examples of what type of algorithm?
sort algorithm
what kind of runtime complexity do selection sort and bubble sort have?
N (problem size) to the power of 2.
N^2
e.g. if N=20 then the runtime will be 400.
this makes it a very slow algorithm. the graph looks very spiked. like its pointing straight up with a little bit of a slope
What is the runtime complexity of Quicksort?
Quicksort has a runtime complexity of N x Log N
it is much faster than N^2 (selection sort and bubble sort)
What is polynomial runtime complexity?
they are considered the ‘easy’ algorithms to solve.
polynomial runtime complexities are defined by if N is a main factor in the equation.
what are Log N, N, N x Log N, and N^2 all examples of?
polynomial runtime complexities
what is exponential runtime
these are considered ‘hard’ algorithms to solve.
exponential runtimes are defined if N exists only in the power of something in an equation. E.g.. 2^N
what is the nature of exponential runtime complexities?
if the problem size (N) increases by 1, the runtime doubles, triples, quadruples
(the problem size exponentially grows)
What runtime complexity is 2^N an example of?
it is an example of exponential runtime complexity
what is the traveling salesman problem (TSP) an example of?
exponential runtime complexity
What is the equation to figuring out the traveling sales man algorithm?
2^N
what is the quickest algorithm?
Log N (binary search)
What is the longest algortihm?
2^N
Traveling sales man algorithm
what is the order from quickest to slowest algorithms.
TSP, Search algorithm, sorting algorithm, linear algorithm
1) search
2) linear
3) sorting
4) tsp
what is the order from quickest to slowest formula for algorithms…
N^2 N log N 2^N N log N
1) Log N
2) N
3) N log N
4) N^2
5) 2^N
when is the only time that exponential algorithms make sense?
for crypography
what does programming mean?
creating a sequence of instructions for a computer to carry out a task
what is the difference between an algorithm and a program?
an algorithm is an abstract or idealized process.
it might ignore the details, e.g. invalid user input, hardware failure, ect..
a program is like an algorithm (they are both a sequence of detailed instructions)
but…..
a program is more detailed than an algorithm, it implements the algorithm.
Difference between algorithm and program.
an algorithm is the steps that need to be followed in order to solve a problem.
a program is an instruction set for a specific type of machine for the algorithm to function
do algorithms contain bunch of programs…
or
do programs contain a bunch of algorithms?
a program typically contains implementations of a couple of algorithms for different tasks bundled together
what don’t programs have to worry about, that algorithms do…
- insufficient memory
- limited processor speed
- invalid or malicious input
- hardware failure
what is machine code?
a sequence of binary numbers for instructions and data
What is assembly language?
allows programers to use meaningful words instead of binary numbers for instructions and memory locations.
e.g. print. or store… like you might see in the toy computer
What are the benefits of assembly code?
- easier to use than binary code
- the assembler automates some of the ‘clerical tasks’ e.g. keeps records where the data is stored in the memory
what are the disadvantages of assembly code?
- machine dependency
- an assembly language program running on one CPU must largely be re-written to run on another CPU type
What is a high level language?
high level languages were developed to make it easier to create programs, usually for a specific purpose.
e.g. learning how to program, business taks, web applications… ect.
What are the advantages of high level language?
- they provide instructions that are more powerful than assembly language code, and are closer to the way people think
- learning how to write programs is easier and faster
- software can be created in shorter time
- its easier to detect some program errors
- programs are independent of CPU architecture
How can a high level language be translated into different CPU’s? (2 steps)
yes! using a compiler and an assembler.
1) the compiler converts a program into the CPU specific assembly language instructions
2) an assembler converts the assembly language instructions into machine code. (binary instructions)
What is a compiler?
a compiler converts a program that is written in a high level language into a CPU specific assembly language.
a.k.a. it is a computer program that translates one computer code written in one language into another language.
What is a Syntax error?
check for spelling, missing brackets, invalid characters
e. g.
correct: I like computers
Synax error: I Luke computers / I computers like / I @#@# computers
what are the kind of errors that compilers usually cannot detect
?
semantic errors / logic errors
what is a semantic error/logic error
errors that cannot check for grammar. which dictates a specific meaning.
e. g.
correct: let’s eat, grandpa!
semantic error: Let’s eat grandpa!
the two sentences convey 2 different meanings. the syntax error cannot detect the comma, which changes the meaning of the phrase
what is a program error called?
bugs
what does debugging mean?
finding and removing an error.
what is a software library?
code that is intended for reuse is provided in software libraries
when programmers write pieces of software that others can reuse.
What is ‘interface’
software libraries offer their benefits to the outside world via Interfaces.
interfaces act as the medium between software libraries and customers who want to use the software.
interfaces communicate with the deeper layers of the program to retrieve the software that the customer wants to use
What is API? (Application Programming Interfaces)
some software libraries are intended to help creating applications in a specific areas
software that intermediary that allows two applications to talk to each other.
is a connection between computers or between computer programs.
e.g. google maps API: enables programmers to add maps to their own applications.
What is SDK (Software Developing Kit)
is a collection of programs providing everything to create an application of a specific type.
e.g. android software development kits allow people to create android apps.
what is copyright?
Software is protected by copyright
a type of intellectual property that gives its owner the exclusive right to make copies of a creative network, usually for a limited time.
“creators have the right to exploit their work for a limited amount of time”
What is software licensing?
software producers sell licenses to grant customers permission to use a software
licenses can be limited for a specific period of time
- you do not own the software
- typically you are allowed to use one copy on one computer
What is Canadian copyright for educational services?
educational institutes, teachers, and students may save, download and share publicly available internet materials.
you can do this for material that doesn’t have any technological protection (material you don’t have to put in a password for)
you are required to cite the source of the material.
What is open source?
source code that is publicly available - everyone can view it and even modify it.
its use is royalty free – no license fee, but there are still licenses.
software under the GPL (general public license) is free to be used by anybody.
examples: linux, android, firefox
What is closed source
closed source code is software that has encrypted source code.
the user can’t copy, modify, or delete parts of it.
source code is usually treated like a trade secret.
software is usually delivered in a compiled format.
its infeasible to retranslate object to source code.
what is software testing?
actively checking where the actual results match the expected results in software.
what is an operating system?
is system software that manages computer hardware, software resources, and provides common services for computer programs.
we need the OS to manage resources and coordinate applications.
OS provides services for applications. E.g. storage of data in files.
e.g. microsoft windows, linux, Mac OS
what are the main responsibilities of an operating system?
1) controls and allocates the resources of a computer.. controls how much CPU time each application gets
2) manages and allocates RAM to applications
3) manges information on storage devices
4) manages and coordinates the activities of peripheral devices connected to the computer (microphone, speaker)
What are the major operating systems?
- Unix
- DOS (disk operating system
- Mac OS (apple)
- Windows (microsoft)
- Linux (open source)
- Android (google)
What is the most common OS for cell devices?
android (controlled by google)
what is the most common OS for desktop/laptops?
Windows (controlled by microsoft)
What is process scheduling?
The operating system decides which process (program being executed) gets to run (on which core) and for how long.
OS can prioritize (increase CPU time) or suspend a process
decides which part of a process gets to run at a specific time.
how many processes can run on a CPU core at a time?
only one process can use a CPU core at a time.
What is RAM allocation?
OS decides how much RAM will be allocated to each process.
> > process needs to ask the OS for permission to use more memory
what is memory swapping?
When the OS moves memory that is used by a process out to a disk temporarily if RAM is needed for the next process to run.
memory swapping slows down the execution of a process significantly because the disk is much slower than RAM
What is memory protection?
The OS makes sure that a process doesn’t overwrite or read (spy on) the RAM being used by another process.
memory protection keeps the process from interfering with each other.
OS shows each process only those RAM segments that are assigned to this process
what is management of storage responsible for?
the management of information stored on disks…
its responsible for:
1) how files are physical stored on disks
2) how files are organized logically
3) how permissions to access files are organized
what is the difference between physical and logical storage?
physical storage is where the files are physically sorted on the disks. which platter/secor/track of a hard disk is used
logical storage is how the files are organized logically…. the names of folders and subfolders.
what is a block?
any data on drives is stored as blocks.
a block may only be partly used but never contain more than one file.
blocks contains either 512, 1024, 2048, 4096, or 8192 bytes
blocks are used in the physical organization of storage management
the OS keeps records of all blocks being used by a file.
what is a path?
logical organization is based on a folder hierarchy.
the folder hierarchy follows a tree structure
the location of a file in this tree stucture is called a PATH.
what is a device driver?
device drivers communicate with a particular piece of hardware. e.g. a printer, graphics card, ect.
what is kernel?
kernel is the primary interface between the hardware and process of a computer
kernel is apart of the operating system that has control over everything.
its one of the first programs loaded after startup. it handles the rest of startup swell as memory.
what is a system call?
the computer requests a service from the kernel of the operating system.
its the fundamental interface between an application and the kernel.
layers of the OS request services. these services are called call services. other layers provide them via the defined interface.
What is ROM (read only memory)
is a type of electronic storage that comes built into a device.
its non-volatile memory used in computers and other devices.
permanently stores data on personal computers and other electronic devices
what is firmware?
firmware is installed on a small memory chip in a hardware device.
firmware is a small piece of software that makes hardware work as its manufacturer intended it to.
firmware refers to software that has been permanently installed in a machine
what is virtual machine?
allows you to run multiple operating systems on one machine.
allows you to run multiple OS simultaneously on a virtual machine.
is a compute resource that uses software instead of a physical computer to run programs and deploy apps.
they allow you to run an operating system in an app window on your desktop that behaves like a full, separate computer
layered software achitecture:
applications - Libraries - \::Operating system:: System calls Operating System: Kernel Device Drivers - Hardware / device
what is the purpose of Javascript?
to allow web browsers to achieve dynamic effects on web pages
does javascript run on top of a website?
Javascript usually runs onto of a website (HTML) inside a web browser
what does HTML stand for?
Hypertext Markup Language Document
How does Javascript work?
javascript programs are also called script.. because they are written in between ….
what is a html tag
?
a set of characteristics constituting a formatted command for a webpage.
html tags are the hidden keywords within a webpage that define how your web browser must format and display the content.;
what is HTML? (hypertext markup language)
its the standard markup language for documents designed to be displayed in a web browser.
Is Javascript meant for widespread use?
Yes! you can use javascript in almost any webbroswer regardless of operating system
what are the advantages of javascript?
you can use in any web browser
its easy to write and test.
most webpages contain javascript
Javascript is usually embedded in HTML code in between … tags.
that’s all.
lots of Javascript libraries (collections of re-usable scripts) are built in and provide features for us to re-use in our programs.
e.g. alert () to display a short message in box
just some basics of javascript
what are the javascript functions?
prompt ()
alert ()
are functions.
functions may have parameters
functions may have a return value
prompt () is a javascript function
a function is a block of code that is designed to perform a particular task. A javascript function is executed when “something” invokes it (calls it)
- alert () is a function => note: brackets after the name
- we use (a.k.a. “call” a function to let it do something for us
- funtions may require several input values. these are called parameters
online alert () functions often return (calculate and pass back) a result to the statement that called the function. -return values are often stored in variables for later use.
what are the javascript variables?
- javascript uses variables to store data items (like a container)
- variables are declared (and introduced) prior to their use. e.g. var text … declares a variable with the name ‘text’
-a variable can store different types of information, e.g. a sequence of characters (called a string) or a number. var text = hey whassup
Repeating instruction: Loop in Javascript
e.g. the while loop.
in many situations, we want a program to repeat a sequence of instructions, typically with some variation every time.
if we repeatedly execute a particular sequence of instructions, we call this a loop or iteration
this execution continues as long as the certain condition is true.
repeat instructions inside of { } brackets while the condition is true.
alternative execution paths in java script
a common instruction for decision making in javascript is the IF ELSE
if
else
the ‘else’ branch is optional
both ‘if’ and ‘else’ include multiple instructions.
conditional jumps in java
sometimes IF can just be used.
execute the instructions made inside the
{ } after the ‘if’ instruction only if the condition is true.
this can put you in a loop
interactions between javascript and HTML
the real power of javascript, emerges from the combination of Javascript and HTML
once the browser is fully loaded on an HTML page, javascript code may start to run.
Javascript code can manipulate parts of the HTML document
What is HTML
any web page that you load and view in a web browser is an HTML document
what are HTML tags?
items inside the < > are called HTML tags.
a characteristic feature of HTML documents is that all its parts are enclosed with a pair of tags.
page content
document head goes here
How Java and HTML work on a webpage.
anything in the code that is < > is html
anything on the webpage that looks like onClick=onclick() is javascript.
or that looks like ‘var’ or ‘function’
Javascript is typically used on a website to add…..
interactivity on the website
the purpose of variables is to…..
store data items
