D1 chapter 1 and 2
Revision mind map on key point and definitions of chapter 1 and 2.
- 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