# D1 chapter 1 and 2

Revision mind map on key point and definitions of chapter 1 and 2.

HideShow resource information

- Created by: O'nika
- Created on: 16-05-13 14:49

View mindmap

- D1 revision
- Chapter 1
- Binary Search
- Used to search an ordered list for an item.
- Select the middle item in the list. IF=f the target is the middle item then stop.
- It the target is before the middle item get rid of the second half of the list and vice versa.
- Repeat this unitl you have found the target or when you have searched the whole list.

- It the target is before the middle item get rid of the second half of the list and vice versa.

- Quick Sort
- Chosse a pivot and create sublists untill all data is in order.
- Used to order lists.

- Bubble Sort
- Compare items next to each other in the list and swap when in the wrong order. Move through the list comparing and swapping untill the list is in order.
- Used to order lists

- Bin Packing
- Doesn't always give optimal solution.
- 3 different algorithms
- First-fit
- First-fit decreasing
- Full-bin packing

- Binary Search
- Chapter 2
- Different Graphs
- Bipartite Graph
- Has 2 sets of nodes ,x and y. Nodes in x can only join with nodes in y.

- Path
- A finite Sequence of edges, where the end vertex of on edge is the start vertex of the next edge.

- Connected Graph
- A graph with a path between all the veritices.

- Simple Graph
- Graph with no loops and no more than one edge connceting 2 vertices.

- Tree
- A connected graph with no cycles

- Isomorphic Graphs
- They show the same information but look different.

- Cycle
- A closed path, where the start vertex is the end vertex.

- Bipartite Graph
- Different tables
- Adjacency Matrix
- Records the number of direct links between vertices.

- Distance Matrix
- Records the weight on the edges.

- Adjacency Matrix

- Different Graphs

- Chapter 1
- Chapter 1
- Binary Search
- Used to search an ordered list for an item.
- Select the middle item in the list. IF=f the target is the middle item then stop.
- It the target is before the middle item get rid of the second half of the list and vice versa.
- Repeat this unitl you have found the target or when you have searched the whole list.

- It the target is before the middle item get rid of the second half of the list and vice versa.

- Quick Sort
- Chosse a pivot and create sublists untill all data is in order.
- Used to order lists.

- Bubble Sort
- Compare items next to each other in the list and swap when in the wrong order. Move through the list comparing and swapping untill the list is in order.
- Used to order lists

- Bin Packing
- Doesn't always give optimal solution.
- 3 different algorithms
- First-fit
- First-fit decreasing
- Full-bin packing

- Binary Search

## Comments

No comments have yet been made