progweek4

Question 1

A tree can be defined as :

Answer 1

a non-linear
data structure, in which the
information is ordered hierarchically
and interconnected.
It consists of a collection of nodes
(vertices) (storing the value(s))
connected by edges (connections)

Question 2

Path:

Answer 2

a group of sequential edges; let p and c be two nodes such
that there is an edge from p to c. Then we say that p is a parent of
c and that c is one of the children of p.

Question 3

Root:

Answer 3

the only node with no parent.

Question 4

Leaf:

Answer 4

a node with no children.

Question 5

Height (of a node):

Answer 5

number of edges between the root and the
farthest leaf. The height of a tree is the length of the longest path to
a leaf.

Question 6

Depth:

Answer 6

the number of edges from a node to the root.

Question 7

a tree we see daily:

Answer 7

Unix file system

Question 8

we focus on: _ trees.

Answer 8

binary

Question 9

Why are binary trees (BTs) so important?

Answer 9

1. Efficient searching and sorting:

BTs allow for fast searching, insertions and deletion of items.

2. Hierarchical data representation:

they are used to represent structures were hierarchical order is crucial. For example in file systems, HTML, etc.

3.Elegant algorithm design:

many algorithms are based or use BTs as part of their implementation.

Question 10

Why and when are trees useful?

Answer 10

Computer Science:
Often used to give a hierarchical structure to data, e.g., file systems,

Modelling:
Hierarchical clustering of data (Statistics! Machine Learning!)

Linguistics:
To represent the syntactic structure of sentences in a language

Question 11

full BT:

Answer 11

Every node has either
0 or two children.

Question 12

perfect BT

Answer 12

All the nodes have
two children, and leafs
are at the same level.

Question 13

complete BT

Answer 13

All the levels (expect
the last one) should
be full.

Question 14

Degenerate BT

Answer 14

Every node has only one
child, either in the left or
right.

Question 15

balanced BT

Answer 15

Heights of the left subtree
and right subtree defer by
zero or, at most, one.

Question 16

In a binary search tree (BST), all the
elements from the nodes are ordered following a specific order.
The left node must be _ than
its parent node, and the value in the
right node must be _ than the
parent node.

Answer 16

smaller

greater

Question 17

Some key operations on BSTs are:

Answer 17

Searching.
Insertion.
Deletion.
Traversal.

Question 18

The idea of Object Oriented Programming is

Answer 18

that data is what should
guide software development and that the language should support data
abstraction.

Question 19

Classes:

Answer 19

Provide a description of a type of object (essentially
improved ADTs).

Question 20

Objects:

Answer 20

Are instances of classes.

Question 21

Class attributes:

Answer 21

attributed shared by all instances of the class, e.g.,
the number of students currently in the system.

Question 22

Instance attributes:

Answer 22

attributes that are proper of the instances of
the class, e.g., the name and ID of a student.

Question 23

Class (static) Methods:

Answer 23

functionalities that belong to the class,
e.g., a method that prints the number of students currently in the
system

Question 24

Instance Methods:

Answer 24

functionalities that belong to the instance, e.g.,
a method that allows to change the name of a specific student.

Question 25

Constructor:

Answer 25

Is a method that allows to create an object of the class. Space is created and attributes initialized. Most OOP programming languages require that classes have a constructor.

Question 26

Destructor:

Answer 26

Is a method that destroys (frees) the object. In
particular it frees the memory allocated for the object.

Question 27

python’s Paradigm:

Answer 27

Object Oriented imperative

Question 28

python’s Type system:

Answer 28

Untyped (aka dynamically typed) this removes the
distinction between declaration and initialization, variables are
declared when they are initialized

Question 29

python’s Parameter passing:

Answer 29

Officially called “pass-by-assignment”, but it’s
essentially call-by-value. Objects are references (pointers) so can in principle be changed (see below Immutability).

Question 30

python’s Scoping:

Answer 30

the scoping rule is static (non-local names are searched where the function was declared). Blocks are as in C with the exception that body of if/while/for are not blocks (variable declared inside a while exist after). Moreover nested function declaration is allowed.

Question 31

Memory:

Answer 31

Managed by runtime support (object are deallocated
automatically). Still techniques can be used to make programs more efficient.

Question 32

Mutable type:

Answer 32

The operations can directly change the values of the type, e.g., when adding an element to the list you actually modify the list.

Question 33

Immutable type:

Answer 33

The operations cannot modify the values of the type and have to return a new structure with the correct value.

Question 34

immutable in python:

Answer 34

Integers
Float
Strings
Boolean
Tuples

Question 35

Mutable in python:

Answer 35

Lists
Dictionaries
Sets

Question 36

In Python everything is _ and variables are actually _.

Answer 36

an object

references to that object

Question 37

if the type of the parameter is mutable:

Answer 37

then the function will
actually be able to change the value of the parameter (same as
passing an array in C).

Question 38

if the type of the parameter is immutable:

Answer 38

then the function will
not be able to change the value of the parameter (same as passing an
integer in C).

Note though that if an immutable type contains a value
of a mutable type then the function can change that value, e.g.,
consider passing a pair of lists p = ([0], [1]) and performing
p[0][0] = 32.

Question 39

You can use the dot notation to _

Answer 39

invoke methods

Question 40

Encapsulation, i.e.,

Answer 40

the process of hiding information from the user, is a key feature of OOP.

Question 41

Private names (names that can only be accessed within the class) can be
declared using _

Answer 41

a double underscore

Question 42

Another characteristic features of OOP is that classes can often be
organised _

Answer 42

in a hierarchy.

Question 43

The idea is that classes that are higher in the hierarchy are more _
than those that appear in the the lower levels.

Answer 43

abstract

Question 44

In Python, every class is automatically a _

Answer 44

subclass of the class object.

Question 45

When a method is overridden, _

Answer 45

the version in the subclass will be used instead of the one in the superclass, even when the method is called on an instance of the subclass.

This is useful when the subclass needs to perform a specific behavior different from the superclass, but still wants to use the same method name for consistency and readability.

Question 46

Abstract Iteration :

Answer 46

(Specification on Iteration): Iterators and
Generators

Question 47

Polymorphism (give small def): (via what)

Answer 47

parametrization on types

Via names overloading
Via sub-typing
Via generics/templates
Via variables of type type (universal poly.)