Effective Study Techniques for Exam Success
Starting from learning core factual content to applying knowledge to new problems, connecting knowledge with complex questions, and practicing in exam conditions, this guide provides a step-by-step approach to help you prepare efficiently for exams. The "FACE It" method outlined here ensures a structured revision process to enhance your understanding and retention of key concepts. Utilize the suggested strategies to tackle various types of questions effectively and excel in your examinations.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Synthesizing Number Transformations from Input-Output Examples Rishabh Rishabh Singh and Singh and Sumit Sumit Gulwani Gulwani
Number One of the most commonly used data type Number Formatting Every language has its own format #.00? (C#, Excel), 05.2f (Python, C) End-users
Excel Help-forums upper 45 or 95 upper 45 or 95
Observations from Help-forums Input-Output Examples Specification mechanism Additional inputs for removing ambiguity Excel add-in with same interface
Talk Outline 1. Number Transformation Language 2. Synthesis Algorithm 3. String & Number Language Combination 4. Synthesis Algorithm for Combination 5. Experiments
Generic Framework Expression Language L Expression Language L Expressive and succinct Efficient Data structures for set of expressions Efficient Data structures for set of expressions Version-space algebra GenerateStr GenerateStr All sets of expressions from I-O example Intersect Intersect Intersect two sets of expressions
Format String ? = (?,?,?) ? : minimum number of significant digits ? : maximum number of significant digits ? : number of whitespaces at end
Number Format Exactly 2 decimal places Exactly 2 decimal places 123.4567 123.4567 123.46 123.46 123.4 123.4 123.40 123.40 (? = 2,? = 2,? = 0) .N NET ET : 0.00
Semantics Exactly 2 decimal places Exactly 2 decimal places (? = 2,? = 2,? = 0) 24.589 24.59 24.2 24.20
GenerateStr Interval domains for ?,?,? 123.4567 123.4567 invariant ? ? ? 123.46 123.46 ( ? = [0,2], ? = [2,2], ? = [0,2]) 123.4 123.4 123.40 123.40 ( ? = [2,2], ? = [2, ], ? = [0,0])
Intersect ( ? = [0,2], ? = [2,2], ? = [0,2]) ( ? = [2,2], ? = [2, ], ? = [0,0]) ( ? = [2,2], ? = [2,2], ? = [0,0])
Extension to Integer parts 12.4567 12.4567 012.46 012.46 123.4 123.4 123.40 123.40 Dec(u) ( Int(u), Frac(u)) GenerateStr(Frac(u1), Frac(u2)) GenerateStr(Int(u1)R, Int(u2)R)
Rounding Numbers (?,?,?) ? ? ? zero of interval ? size of interval ? nearest, upper, lower
Round Format Round off to upper 45 Round off to upper 45 11 11 45 45 46 46 95 95 (? = 45,? = 50,? = ) =Min(Roundup(A1/45, 0)*45, Roundup(A1/95,0)*95)
GenerateStr ?1 ?2 Not enough info. to learn precise (?,?,?)
Intersect Intersect((n1,n 1),(n2,n 2)) ? = ? 1 ? ???????? ? 2 ? 1 ? > |?1 ?1,? > |?2 ?2
Intersect Intersect((31,45),(86,95)) ? = 45 ? ????????(95 45)
Intersect Intersect((31,45),(86,95)) ? = 45 ? ???????? 50
Intersect Intersect((31,45),(86,95)) ? = 45 ? 1,2,5,10,25,50
Intersect Intersect((31,45),(86,95)) ? = 45 ? 1,2,5,10,25,50 ? > |45 31 ,? > |95 86
Intersect Intersect((31,45),(86,95)) ? = 45 ? 1,2,5,10,25,50 ? > |14 ,? > |9
Intersect Intersect((31,45),(86,95)) ? = 45 ? 25,50 ? > |14 ,? > |9
GenerateStr 250,000 1,000,000 1,450,000 2,000,000 ? ???????? 1,000,000 Only need to maintain greatest value
Intersect ?1 ???????? ?1 ?2 ???????? ?2 ? ???????? gcd(?1,?2)
Combining String and Number Transformations
Synthesis Algorithm 2004.07.08 7/8/2004 Program P1 to extract 7 in input (P1, 7 -> 7) 1) (-5, -4) 2)(-5, dot -1) 3)(-5, dot 2) 4)(-5, 7) 5)(6, -4) 6) .
Synthesis Algorithm 2004.07.08 7/8/2004 Program P2 to extract 07 in input 1) (dot 1, dot 2) 2)(dot 1, dot -1) 3)(-6, -4) 4)(-6, dot -1) 5)(-6, dot 2) 6) . (P1, 7 -> 7) (P2, 07 -> 7)
GenerateStr 2004.07.08 7/8/2004 (P1, 7 -> 7) (P2, 07 -> 7)
GenerateStr 2004.07.08 7/8/2004 (P3, 8 -> 8) (P4, 08 -> 8)
Constructing the DAG 071/283/425060748 (P1, 7 -> 7) 3 4 2 1 0 (P2, 07 -> 7) 5 6 7 8
Intersection DAG intersection Edge-wise program intersection
Benchmarks 50 benchmark problems Help forums Excel product team
Number of I/O examples 35 30 Number of Benchmarks Number of Benchmarks 25 20 15 10 5 0 1 2 3 Number of Input Number of Input- -Output Examples Output Examples
Performance 3.5 3 Running Time (in seconds) Running Time (in seconds) 2.5 2 1.5 1 0.5 0 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 Benchmarks Benchmarks
Related work String Transformations [Gulwani POPL11] Table Transformations [Singh,Gulwani VLDB12] Spreadsheet Data Manipulation using Examples[Gulwani, Harris, Singh CACM 2012]
Conclusion Number Transformation Language Synthesis algorithm String + Number Transformations Combined Synthesis algorithm
Thanks! CAV Algorithm Designers Software Developers End End- -Users Users Large potential
