Algorithms
Common Prolem solving techniques:
#1 Devide and Conquer
#2 Recursion and dynamic programming
#3 Case analysis
#4 Generalization
#5 Data Structures
..... any many more.
Problems:
#1 Design an efficient algorithm for determining if there exist a pair of indices i, j (not necessarily distinct) such that A[i] + A[j] = S.
#2 You are required to write a method that takes two text documents: an anonymous letter L and text from a magazineM. Your method is to return true if L can be written using M and false otherwise. (If a letter appears k times in L, it must appear at least k times in M.)
#3 PAIRING USERS BY ATTRIBUTES
Common Prolem solving techniques:
#1 Devide and Conquer
#2 Recursion and dynamic programming
#3 Case analysis
#4 Generalization
#5 Data Structures
..... any many more.
Problems:
#1 Design an efficient algorithm for determining if there exist a pair of indices i, j (not necessarily distinct) such that A[i] + A[j] = S.
#2 You are required to write a method that takes two text documents: an anonymous letter L and text from a magazineM. Your method is to return true if L can be written using M and false otherwise. (If a letter appears k times in L, it must appear at least k times in M.)
#3 PAIRING USERS BY ATTRIBUTES
You are building a social networking site where each user specifies a set of attributes. You would like to pair each user with another unpaired user that specified exactly the same set of attributes.
Specifically, you are given a sequence of users where each user has a unique
key, say a 32-bit integer and a set of attributes specified as a set of strings. As
soon as you read a user, you should pair it with another previously read user with
identical attributes who is currently unpaired, if such a user exists. If the user
cannot be paired, you should keep him in the unpaired set.
Problem 1.11: How would you implement this matching process efficiently? How
would you implement it if we allow an approximate match of attributes as well?
Comments