CMPS 3120 Algorithm Analysis
Brute Force and Exhaustive Search
- Sorting algorithm: an algorithm that puts elements of a list in a certain order. The most frequently used orders are numerical order and alphabetical order.
- Design a brute-force sorting algorithm.
- String matching: the checking and locating of specific sequences of data of some pattern among raw data or a sequence of tokens.
- Design a brute-force string matching algorithm.
pattern: a string of m characters to
search for
text: a (long) string of n characters to search in
matching: a fully match for all the characters
comparison: compare 2 characters (positive or negative result)
- Depth-first search (DFS) & Breadth-first search (BFS)
- Zachary's karate club
A social network of a karate club was studied by Wayne W. Zachary for a period of three years from 1970 to 1972. The network captures 34 members of a karate club, documenting links between pairs of members who interacted outside the club. During the study a conflict arose between the administrator "John A" and instructor "Mr. Hi" (pseudonyms), which led to the split of the club into two. Half of the members formed a new club around Mr. Hi; members from the other part found a new instructor or gave up karate.
Data Download (Same Data, second data format)
Data Download (Same Data, third data format)
- More examples, and the limitation of brute-force algorithms.