Cmpt 120 Exam

Method of representing logical relationships between individual data elements.

Coding

Interpreter

Data structure can compute addresses of data items with arithmetic operations. Linked data structures are storing addresses of data items within structure itself.

Yes

Organize Data

Access Data

Manipulate Data

Values stored in sequence and in linear fashion

Values stored in non sequential matter

Values with same type of data stored (arrays)

Values with different types of data grouped (classes)

References, pointers, size, memory locations can be changed during program execution.

Variable remains in the memory throughout the program

List

Tuple

Dictionary

List of values where each value is an element and is numbered started from 0.

[1] in [32,45,23] would be 45.

Are like lists, except values cannot be changed.

Contains an index of keys and definition/value for each key (kind of like ordered pairs).

[]

()

{}

A sequence, an abstract data type, where each element is assigned a number for its position.

Indexing

Slicing

Multiplying

Adding

Checking for membership

(ISMAC)

Each instance of a value is called either an item, entry or element and it is a computer representation of mathematical concept of infinite sequence.

Data structure that stores homogenous values

Methods for creating arrays of fixed types with homogeneous data types

Lists only allow sequential access, array allows random access. Lists are collections of heterogenous elements, arrays are homogeneous.

Yes

Main memory, aka RAM.

It disappears or deletes itself.

In a file.

On secondary storage (hard drives).

Non-volitile

Organized into directories and identified by unique name.

Basic element of data made up of characters

Organization of related fields treated as a unit, row

Collection of similar records, a table

Collection of related data

Space that the OS makes through abstractions of physical properties of its secondary storage devices to define a logical storage unit called a file.

Files are based on its data items and associated operations

Name

Type

Location

Size

Protection

Time, Data, USER ID

open(filename, mode)

Returns name of file

Returns true if file is closed

Return access modef il was opened with

Return false if space explicitly required with print

Returns how many characters (n) you want to read from file

Reads one line from file

Reads all lines from file

Flushes any unwritten information and closes file object

Creates a file

A loop that reads lines

Writes to a file

Frees up any system resources taken by open file.

Abstract Data Type

Mathematical model for certain class of data structure that have similar behaviour.

ADT is more logical, thought of as a picture of the data and the operations to change it.

Data structure is more concrete, where it can be implemented and used within an algorithm.

Programming language primitive whose value refers directly to another value stored elsewhere in the memory using its address.

Array

Linked List

Stack

Queue

Collection of data of same type stored in consecutive memory location

Collection of data of same type, but not stored in consecutive memory

last-in-first-out data structure

first-in-first-out data structure

Linked list that contains nodes which have two fields. Integer value and next node, which points to the next node in the line of nodes.

Linked list that has a second link field beside the next node that points to the previous node in sequence.

A way to represent finite set of data that has a relationship between pairs of elements

Special class of graphs that are used to represent data that has some hierarchical relationship among data elements

Data values at each node are stored form some ordered set, in such a way that in-order traversal of the trees visits nodes in ascending order of stored values

Each node branches into two other nodes.

Data structure which is a type of self-balancing binary search that contains colours for each node.

Tree-based data structure that satisfies the heap property.

Sequence of computer program instructions that perform a specific task.

Inputs of a function

Loads up functions into memory that can be called by program.

Creates a new function where function_name is your own name, and arguments are the inputs required for the function.

Sets a variable to be a value returned from a function

Variable declared within subroutines

Variable declared at the start of a program and can be used within any subroutines

Function that accepts one or more functions as input, returns new function.

A module of code that may be treated as functional unit to accomplish specific sub-task within main program. Often called multiple times.

Great for decomposing complex programming tasks into simpler steps and reducing duplicate code.

Imposes computation overhead and requires standard housekeeping code.

Combination of excess or indirect computation time, memory, bandwidth or other resources that are required to attain a particular goal.

(D)efine Program

(R)equirements

(D)esign

(I)mplementation

(T)est and Debug

(K)ISS

(R)eadability

(I)ndent Style

(M)odularize

(N)o Deviants (confusing, you must not be)

A process of finding and reducing number of bugs

Minimizing inter-modular dependency.

Reproducing bug.

Simplify inputs.

6%

Program that directly executes code without converting the language (Python!)

Program that transforms the source code into object code for the computer to understand.

List of commands that can be executed without user interaction

Multi-paradigm

Dynamic

Yes

Free to the public to manipulate code wise.

User friendliness.

Easy to use and learn.

Requires 10 times less code than C++.

Not suited for all problems that are CPU intensive.

100x slower than C++ and takes 10x more space.

Stores programs and data.

Execute steps sequentially.

Produces output from input.

The way hardware components in a computer interact and communicate.

The union of micro and macro architecture.

Model for designing and building computers.

Memory, I/O, ALU, CU.

Stored Program Concept.

Follows Sequential Execution of Instructions.

Macroarchitecture

Central Processing Unit.

ALU and CU.

Performs integer arithmetic and logic operations.

Boolean AND / OR

Master conductor of all operations including reading and interpreting instructions, sequencing the processing of data, responsible for moving data between ALU and memory, and has a instruction set of all possible instructions that it could be asked.

Storage for information.

FALSE.

The faster the memory is, the more expensive and lower it's capacity.

Random Access Memory

Read-Only Memory

Fetch instruction form memory.

Decode instructions.

Execute instructions.

Macro is visible to us, micro is not.

Binary codes.

Transistors

Gates.

Circuits.

0's and 1's.

On/Off switches. They are the heart of high-speed electronic digital computers.

Logical operations made from transistors.

Combinations of gates.

Hiding unnecessary details for some immediate purpose.

10^5

System that can manipulate discrete elements of information.

Analog

Analog computers work in parallel.

Digital computers work fast but do not work in parallel.

Binary Digit (0's and 1's)

8 bits

0

1

10

11

100

Semiconducting materials/elements.

Well order collection of unambiguous and effectively computable operations that, when executed, produces a result and halts in a finite amount of time.

Representation: concrete symbolic encoding of information.

Transformation: the steps used to calculate a specific result.

Grammar, specifies form of a language by describing possible combination of symbols.

Meaning, specifies what is being conveyed by the language.

Set of strings of symbols that may be constrained by rules specific to it.

English or any other spoken language.

Language to describe what we want to program in english. Combination of formal and natural language.

Code written with little attention to the flow of logic. Unstructured and tangled.

(S)equence (normal)

(I)teration (for loops)

(D)ecision (if)

Iterative loops that are used when the # of iterations is known.

Conditional loops that are used when the # of iterations is unknown. More flexible than a For Loop.

Machine -> Assembly -> High Level

Declaritive: What to compute.

Imperative: How to compute.

Logic & Funtional.

Procedural & Object Oriented.

Declarative & Imperative.

High-level programming language where design emphasizes readability, and syntax allows programmers to express concepts in fewer lines of code.

Study of algorithms including their formal mathematical properties, hardware realizations, linguistic realizations and applications.

# of transistors and speed of microprocessors doubles every 18-24 months.

Computer power is rising exponentially.

1940's and machine centred.

GUI (WIMP): Graphic User Interface

CLI: Command Line Interface

HYBRID: GUI + CLI (UNIX)

With precision and accuracy.

Syntax: Incorrect grammar or spelling

Semantic: Incorrect meaning

Logic: Incorrect operation but code still able to run

System in which program are written to find an answer, able to solve any computational problem given enough time and space.

Hypothetical device representation computing machine to help computing scientists understand the limits of mechanical computation.

Used to analyze the general properties of computers.

Device that manipulates symbols on a strip of tape according to table of rules.

Basic computer that uses a fixed set of rules to determine future actions.

Works in parallel to prescribe more than one action for one solution.

Theory that focuses on classifying computational problems according to their inherent difficulty and relating those classes to each other.

The study of the size of a problem.

A task that can be solved by mechanically applied mathematical steps.

A problem for which an algorithm can always answer YES or NO.

Decision problem that increases in time as a polynomial function of the problem size.

Decision problem solvable in time which increases faster than polynomial in n, but once solution is obtained, it can be verified in time polynomial in n (P).

Decision problems in NP, to which all other problems in NP can be reduced in polynomial time.

A program where there exists no algorithm for its solution.

Problem of determining whether a program will finish running or continue to run forever. Self referential.

A structure where every node branches into two descendant nodes and number of nodes expands/grows in complexity exponentially with depth.

Relative representation of the complexity of an algorithm.

It tells you how fast a function grows or declines.

Determination of the amount of resources needed for execution.

Resources = time + storage

Amount of time or steps it takes to fully compute an algorithm.

Amount of space or memory needed to process the algorithm.

Best, Worst, Average.

Measures the time complexity of different inputs of the same size.

Solving a problem for best input of size n with least number of steps.

Solving a problem for worst input in most number of steps.

Solving a problem with average input, uniform distribution of all inputs of size.

Algorithm that has at most worst-case polynomial time complexity.

Algorithm that cannot be solved at all. No worst-case polynomial time complexity.

Linear

Quadratic

Logarithmic

Exponential

O(n)

Looking at how a problem changes if it is done for more elements.

O(n^2)

Problem that takes four times as long to solve when size of problem doubles.

O(logx(n))

Problem that halves its space with every step until solution is achieved. Binary searches.

O(b^n)

Problem where running time increases exponentially with one step increase in input.

An algorithm to loop up a particular value in a list or data structure. Find a value and determine position.

Linear search

Binary search

Ternary search

Search that halves the list until a value is found.

Divide & Conquer style!

Binary because it always halves.

Used to find minimum or maximum of an increasing/decreasing function and determines whether the min/max is in the first third or last third, and repeats same procedure with remaining two-thirds.

Divide and Conquer.

An algorithm to put elements of a list in a certain order, where output is either in nondecreasing order or is a permutation.

Simple sort.

Efficient sort.

Bubble sort.

Insertion sort and selection sort. Both of which is efficient if used on small data.

An element in the list is compared with all elements before it until it is not greater than the element after it.

Practical general sorting algorithms based on algorithm with average complexity, including heap sort, merge sort and quick sort.

Swapping adjacent element pairs only from multiple passes through the list until sorted.

Yes. Less comparisons and good performance on almost-sorted data.

Recursive or Iterative.

Logical or Procedural.

Serial or Parallel.

Deterministic or Non-Deterministic.

Calls itself repeatedly until a certain condition is met.

Use of repetitive constructs like loops.

Top-Down style of logic where a logic component expresses the axioms which may be used in computation and a control component determines the way in which deduction is applied to the axioms.

Algorithms that execute one instruction at a time.

Several instructions at once.

Predefined process on how to solve a problem.

Guesses of best solutions at each step through heuristics.

Design paradigm that works by dividing problem into sub problems. Conquers each sub problem recursively and combines results.

Optimization technique used to primarily speed up computer programs by keeping results of expensive function calls and returning the cached result when same inputs occur again.

Solving problems with overlapping sub-problems

Data structure used to implement an associative array and can map keys to values.

Same to dynamic, except algorithm does not require a solution at each stage for every sub-problem.

A method to achieve the best outcome in a mathematical model, whose requirements are represented by linear relationships.

Solving a problem by transforming it into another proble by simplest transformation.

Used to model problems

Random choices are made to solve problems

Experience-based techniques for problem solving. Comes up with a solution that may not be accurate by arbitrary guesses.

Facts or figures that relay something specific but are not organized in any way.

Set of rules that assigns a property to the elements of a computer program.

A classification scheme that identifies various types of data.

Possible value for the type.

Operations that can be done on that type of value.

Meaning of the data.

The way values of that type can be stored.

Characters, integers, real numbers, booleans, alphanumerics.

Data type built upon simpler data types. Arrays.

A way to describe how a program is storing information given. Invisible to us programmers.

Data structure decides how complex data types are stored.

Numerical and Logical data that are processed through ALU circuits.

Constant is an immediate value found in an expression.

Variable is a memory location containing some known/unknown value.

Giving or assigning value in memory or object to a data type.

Computers cannot tell the difference between two values/objects. Typing conveys meaning to the programmable hardware to form a symbolic system.

Process of verifying and enforcing constraints of types, implemented at either compile-time or run time. Dynamic is used by Python.