Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Comp midterm 2 > Exam > Flashcards

Exam Flashcards

1
Q

What is the definition of an algorithm?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

is there any ambiguity in algorithms?

A

no.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

are algorithms guaranteed to produce a result?

A

yes, algorithms are guaranteed to produce a result.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

do algorithms have to stop eventually.

A

yes! they have a finite number of steps..

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What are the two methods to describe algorithms unambiguously?

A

flow charts and pseudo code

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is pseudo code?

A

is describing the steps of an algorithm in plain language.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

define flow chart

A

visual representation of the steps in an algorithm.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

In a flow chart, what does —–> the arrow mean?

A

its called a flow line. it indicates the next operation (the flow of operations) by the connecting symbol.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

In a flow chart, what does the oval/circle mean?

A

it is used to represent the start and end of a flow chart.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

in a flow chart, what does the slanted rectangle mean?

A

it is used for the input and output of operations. such as asking people for their height and name, and calculating the results

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

In a flow chart, what does the rectangle stand for?

A

it is used for any kind of operation and or data manipulation. e.g selected = height, or selected = name.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

In a flow chart, what does the diamond symbol stand for?

A

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?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is runtime?

A

how long does it take to compute the results? how much work is it? how many steps/operations are carried out

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What does N symbolize?

A

it symbolizes problem size.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

what is runtime complexity?

A

described the performance of an algorithm, or how much processing power/time is required to run the algorithm.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

what is problem size?

A

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 well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

how can you tell if something is a linear algorithm?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

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?

A

Linear Algorithm.

because sum = N

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

How do you tell if an algorithm is Linear?

A

runtime complexity = N

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

How does binary search work?

A

if the list is organized, you identify the middle of the list and split it. again and again until you find your result.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What is the binary search complexity?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What is the equation for binary search runtime complexity?

A

logN

logarithm to the base of 2 N

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

what kinds of sorting algorithms are there? (4)

A

binary search
selection sort
bubble sort
and Quicksort.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

selection sort and bubble sort are examples of what type of algorithm?

A

sort algorithm

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

what kind of runtime complexity do selection sort and bubble sort have?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

What is the runtime complexity of Quicksort?

A

Quicksort has a runtime complexity of N x Log N

it is much faster than N^2 (selection sort and bubble sort)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

What is polynomial runtime complexity?

A

they are considered the ‘easy’ algorithms to solve.

polynomial runtime complexities are defined by if N is a main factor in the equation.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

what are Log N, N, N x Log N, and N^2 all examples of?

A

polynomial runtime complexities

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

what is exponential runtime

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

what is the nature of exponential runtime complexities?

A

if the problem size (N) increases by 1, the runtime doubles, triples, quadruples

(the problem size exponentially grows)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

What runtime complexity is 2^N an example of?

A

it is an example of exponential runtime complexity

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

what is the traveling salesman problem (TSP) an example of?

A

exponential runtime complexity

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

What is the equation to figuring out the traveling sales man algorithm?

A

2^N

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

what is the quickest algorithm?

A

Log N (binary search)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

What is the longest algortihm?

A

2^N

Traveling sales man algorithm

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

what is the order from quickest to slowest algorithms.

TSP, Search algorithm, sorting algorithm, linear algorithm

A

1) search
2) linear
3) sorting
4) tsp

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q

what is the order from quickest to slowest formula for algorithms…

N^2
N
log N 
2^N
N log N
A

1) Log N
2) N
3) N log N
4) N^2
5) 2^N

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
38
Q

when is the only time that exponential algorithms make sense?

A

for crypography

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
39
Q

what does programming mean?

A

creating a sequence of instructions for a computer to carry out a task

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
40
Q

what is the difference between an algorithm and a program?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
41
Q

Difference between algorithm and program.

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
42
Q

do algorithms contain bunch of programs…

or

do programs contain a bunch of algorithms?

A

a program typically contains implementations of a couple of algorithms for different tasks bundled together

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
43
Q

what don’t programs have to worry about, that algorithms do…

A
  • insufficient memory
  • limited processor speed
  • invalid or malicious input
  • hardware failure
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
44
Q

what is machine code?

A

a sequence of binary numbers for instructions and data

45
Q

What is assembly language?

A

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

46
Q

What are the benefits of assembly code?

A
  • 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

47
Q

what are the disadvantages of assembly code?

A
  • machine dependency

- an assembly language program running on one CPU must largely be re-written to run on another CPU type

48
Q

What is a high level language?

A

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.

49
Q

What are the advantages of high level language?

A
  • 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
50
Q

How can a high level language be translated into different CPU’s? (2 steps)

A

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)

51
Q

What is a compiler?

A

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.

52
Q

What is a Syntax error?

A

check for spelling, missing brackets, invalid characters

e. g.
correct: I like computers

Synax error: I Luke computers / I computers like / I @#@# computers

53
Q

what are the kind of errors that compilers usually cannot detect
?

A

semantic errors / logic errors

54
Q

what is a semantic error/logic error

A

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

55
Q

what is a program error called?

A

bugs

56
Q

what does debugging mean?

A

finding and removing an error.

57
Q

what is a software library?

A

code that is intended for reuse is provided in software libraries

when programmers write pieces of software that others can reuse.

58
Q

What is ‘interface’

A

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

59
Q

What is API? (Application Programming Interfaces)

A

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.

60
Q

What is SDK (Software Developing Kit)

A

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.

61
Q

what is copyright?

A

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”

62
Q

What is software licensing?

A

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
63
Q

What is Canadian copyright for educational services?

A

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.

64
Q

What is open source?

A

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

65
Q

What is closed source

A

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.

66
Q

what is software testing?

A

actively checking where the actual results match the expected results in software.

67
Q

what is an operating system?

A

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

68
Q

what are the main responsibilities of an operating system?

A

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)

69
Q

What are the major operating systems?

A
  • Unix
  • DOS (disk operating system
  • Mac OS (apple)
  • Windows (microsoft)
  • Linux (open source)
  • Android (google)
70
Q

What is the most common OS for cell devices?

A

android (controlled by google)

71
Q

what is the most common OS for desktop/laptops?

A

Windows (controlled by microsoft)

72
Q

What is process scheduling?

A

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.

73
Q

how many processes can run on a CPU core at a time?

A

only one process can use a CPU core at a time.

74
Q

What is RAM allocation?

A

OS decides how much RAM will be allocated to each process.

> > process needs to ask the OS for permission to use more memory

75
Q

what is memory swapping?

A

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

76
Q

What is memory protection?

A

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

77
Q

what is management of storage responsible for?

A

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

78
Q

what is the difference between physical and logical storage?

A

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.

79
Q

what is a block?

A

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.

80
Q

what is a path?

A

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.

81
Q

what is a device driver?

A

device drivers communicate with a particular piece of hardware. e.g. a printer, graphics card, ect.

82
Q

what is kernel?

A

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.

83
Q

what is a system call?

A

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.

84
Q

What is ROM (read only memory)

A

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

85
Q

what is firmware?

A

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

86
Q

what is virtual machine?

A

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

87
Q

layered software achitecture:

A 
applications
-
Libraries
-
\::Operating system::
System calls 
Operating System: Kernel 
Device Drivers
-
Hardware / device
88
Q

what is the purpose of Javascript?

A

to allow web browsers to achieve dynamic effects on web pages

89
Q

does javascript run on top of a website?

A

Javascript usually runs onto of a website (HTML) inside a web browser

90
Q

what does HTML stand for?

A

Hypertext Markup Language Document

91
Q

How does Javascript work?

A

javascript programs are also called script.. because they are written in between ….

92
Q

what is a html tag

?

A

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.;

93
Q

what is HTML? (hypertext markup language)

A

its the standard markup language for documents designed to be displayed in a web browser.

94
Q

Is Javascript meant for widespread use?

A

Yes! you can use javascript in almost any webbroswer regardless of operating system

95
Q

what are the advantages of javascript?

A

you can use in any web browser

its easy to write and test.

most webpages contain javascript

96
Q

Javascript is usually embedded in HTML code in between … tags.

A

that’s all.

97
Q

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

A

just some basics of javascript

98
Q

what are the javascript functions?

A

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.
99
Q

what are the javascript variables?

A
  • 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
100
Q

Repeating instruction: Loop in Javascript

A

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.

101
Q

alternative execution paths in java script

A

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.

102
Q

conditional jumps in java

A

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

103
Q

interactions between javascript and HTML

A

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

104
Q

What is HTML

A

any web page that you load and view in a web browser is an HTML document

105
Q

what are HTML tags?

A

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

106
Q

How Java and HTML work on a webpage.

A

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’

107
Q

Javascript is typically used on a website to add…..

A

interactivity on the website

108
Q

the purpose of variables is to…..

A

store data items

Comp midterm 2 (1 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions