PROJECTS I) Crypto/Number Theory Factoring Algorithms Break RSA Break DH Secret Sharing with Cards What is magic number needed for Shift, Affine, Poly, etc. What about Matrix Can 20x20 Matrix Cipher be cracked? Private Info Retrieval ------------------------ II) Games (Possible ML angle here) Ramsey Games Grid Games - Square Games Monotonic Subsequene Game players alternate choosing a card from 1,...,n these cards form a sequence winner is the one who places last card causing a seq of length a (OR can do misere version) The cover up game with three or more cards Map coloring game- ML? How to beat kids at their own game- do with three or more colors The cover up game with three or more cards NIM with Cash (would have to be ML project) Penney's Game Boomerang Fractions as either Solitaire or as a game. First problem: x1 = 4/3 x(i+1) = EITHER (your choice) xi + 1/3 OR 1/x_i Truth tellers and liars on a 4x4 grid. If they all say I have exactly one liar adjacent to me how many ways can this happern Truth Tellers and Normals- now thats a game! How to beat kids at their own game- do with three or more colors search in the case of errors- code up both sides, make it a game. Le Her game: Alice gets a card Bob gets a card there is a card on the table. Alice can either SWAP or NOT with Bob. Bob can only decline if he has a king. THEN Bob can swap with card on the table or not. Then reveal cards- high card wins, Bob wins ties. What is opt play. Known- but can generalize. Baccarat- ------------------------------------ III) Gathering Data and Making Conjectures Frob problem for 3 coins, 4 coins, etc. Computer Experiements and see what is known. (Alg not hard part, getting data is.) Test takers Dilemma Sum-Product Bounds Egg drop problem 50-cent problem ------------------------------ IV) Algorihtms Muffins 4.5-coloring a planar graph Fractional colorings of graphs Streaming algorithm for mean, variance, etc. Do a SAT solver and use it to factor or solve other problems -------------------------------- V) Ramsey Theory Can Ramsey Numbers Can VDW Numbers Can Rado Numbers VDW numbers Poly VDW numbers Use LLL. Also- what is PROB that a coloring has property Fractional VDW theorem Frac Poly VDW? --------------------------------- VI) Off-Ramsey Theory Grid coloring: 2-coloring and get 2 L-shapes 2 rectangles * * * * * * -------------------------------- VII) Alg and Gathering data First problem: Show there exists n_1 , ... , n_10 such that n_1 + ... + n_10 = 2011 1/n_1 + ... + 1/n_10 = 1 More generally: given A\in N and m find n_1 + ... + n_m = A 1/n_1 + ... + 1/n_m = 1 ALso- what if the n_i's are distinct? --------------------------- VIII) MISC Q is for Quantum-- Bridge to real quantum. Multiparty Comm Comp- can we do better than n/2 without using hard math? Mini Chaos: f(x) = x^2+c over the reals. take iterations. For what values of c do you get get what limit points.