Summary: Algorithms And Data Structures

Read the summary and the most important questions on Algorithms And Data Structures

• 1 Introductie

• 1.2 Fundamentals of Algorithmic Problem Solving

  This is a preview. There are 3 more flashcards available for chapter 1.2
  Show more cards here

• Algorithm design technique

  A general approach to solving problems algorithmically that is applicable to a variety of problems from different areas of computing.

• 3 Complexity and State Spaces

• 3.2 2.2 Asymptotic Notations and Basis efficiency classes

  This is a preview. There are 2 more flashcards available for chapter 3.2
  Show more cards here

• O(g(n))

  Is the set of al functions with a lower or same order of growth as g(n)

• 4 State space and brute force

  This is a preview. There are 1 more flashcards available for chapter 4
  Show more cards here

• 4.2 3.2 Sequential search and brute force string matching

  This is a preview. There are 1 more flashcards available for chapter 4.2
  Show more cards here

• Brute force string matching

  Align the pattern against the first m characters of the text and start matching the corresponding pairs of characters from left to right until either all the m pairs of the characters match or a mismatching pair is encountered

• 5 Exhaustive search

• 5.1 3.4 Exhaustive search

  This is a preview. There are 5 more flashcards available for chapter 5.1
  Show more cards here

• Traveling salesman problem

  Find the shortest tour through a given set of n cities that visits each city exactly once before returning to the city where it started.

• Exhaustive search approach Knapsack

  Leads to generating all the subsets of the set of n given items, computing the total weigth of each subset in order to identify feasible subsets, and finding a subset of the largest value among them.

• 5.2 3.5 Depth-first-search and Breadth first search

  This is a preview. There are 1 more flashcards available for chapter 5.2
  Show more cards here

• Depth first search (DFS)

  Starts a graph's traversal at an arbitrary vertex by marking  it as visited. On each iteration, the algorithm proceeds to an unvisited vertex that is adjacent to the one it is currently in. This process continues until a dead end -a vertex with no adjacent unvisited vertices- in encountered. At a dead end, the algorithm backs up one edge to the vertex it came from and tries to continue visiting unvisited vertices from there.

• DFS and BFS forest

  The starting vertex of the traversal serves as the root of the first tree in such a forest. Whenever a new unvisited vertex is reached for the first time, it is attached as a child to the vertex from witch it is being reached. Such an edge is called a tree edge because the set of all such edges forms a forest. With an BFS if an edge leading to a previously visited vertex other than its immediate predecessor is encountered, the edge is noted as a cross edge.

• 6 Backtracking

• 6.1 12.1 Backtracking

  This is a preview. There are 6 more flashcards available for chapter 6.1
  Show more cards here

• State space tree

  Its root represents an initial state before the search for a solution begins. The nodes of the first leven in the tree represent the choices made for the first component of a solution, the nodes of the second level represent the choices for the second component, and so on.

• 7 Divide and Conquer

  This is a preview. There are 1 more flashcards available for chapter 7
  Show more cards here

• 7.5 5.5 The closest pair

• Closest pair problem

  We can divide the points into two subsets pl and pr respectively, by drawing a vertical line through the median m of their x coordinates. Then we can solve the closest pair problem recursively for subsets Pl en Pr. Note that d is not necessarily the smallest distance between all the point pairs because points of a closer pair can lie on the opposite site of the separating line. Therefore as a step combining the solutions to the smaller subproblems, we need to examine such points.

• 7.8 4.4 Decrease by a constant factor

  This is a preview. There are 1 more flashcards available for chapter 7.8
  Show more cards here

• Fake coin problem

  Among n identical-looking coins, one is fake. With a balance scale, we can compare any two sets of coins. That is, by tipping to the left, to the right, or staying even, the balance scale will tell whether the sets weigh the same or which of the sets is heavier than the other but not how much.