Week 1

Question 1

Solve the following summation:
n
∑ i ?
i=0

Answer 1

n
∑ i = 0 + 1 + 2 … + n = (n(n+1))/2
i=0

Roughly: (1/2)n^2

Question 2

Define an Abstract Data Type (ADT)

Answer 2

The collection of common operations that are accessed through an interface and its characteristics.

Question 3

Name two Data Structures of an integer.

Answer 3

Bit vector

Hexadecimal vector

Question 4

Name all 8 ‘fundamental’ ADTs

Answer 4

Set
Sequence
Map
Stack
Queue
Priority queue
Graph
Tree

Question 5

Define a Set as well as its attributes

Answer 5

A collection of members or elements

Finite or infinite
Orderless
Members are not unique and if appear multiple times called a bag/multiset

Question 6

Define a Sequence/List and it’s attributes

Answer 6

A collection of objects in which insertion order must be maintained.

Multiset with order
Operations include add remove search

Question 7

Define a Stack and it’s attributes

Answer 7

A collection with two defining operations, push pop.

Push adds new element at top of stack
Pop removes element from top of stack

Stack ADT implements Last In First Out. (LIFO)

Question 8

Define a Queue and it’s attributes

Answer 8

A collection with two defining operations, enqueue and dequeue

Enqueue adds new element to back
Dequeue removes element at front

First in First Out

Question 9

Define a Priority Queue and it’s attributes

Answer 9

A collection with the same operations as Queue however an additional priority is associated with each element.

Enqueue add new element to back of queue
Dequeue remove element with the highest priority

Question 10

Define a dictionary/map and it’s attributes

Answer 10

A collection of key pair values

Each key must be unique

Question 11

Define a graph and it’s attributes

Answer 11

A finite set of vertices that are connected via edges representing relationships.

Question 12

Define a tree and it’s attributes

Answer 12

A collection of vertex that is acyclic.

Contains a root at the top and leaves at the bottom

Question 13

Define two data structures that can be used for a list, set or dictionary ADT

Answer 13

Array or Linked List

Array:

• collection of elements stored in a continuous manner
• fast random access
• needs to be resized manually

LinkedList:

• each node stores data and contains a pointer to the next node
• there’s a header pointer at the beginning of the list
• tail pointer that points to the end of the list

Question 14

Define and solve GCD(60,24) using the Euclidean Algorithm

Answer 14

GCD stands for Greatest Common Divisor.

Euclidean Algo = GCD(a,b), a=b(q) + r