# 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
• 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.
• 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
• 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.
• Different tables
• Records the number of direct links between vertices.
• Distance Matrix
• Records the weight on the edges.
• 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.
• 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