School Coding Project -- 2

LyX Document Page 1 of 2 Arizona State UniversitySER222: Data Structures & Algorithms Lecturer AcuñaRevised 8/15/2019 Determining Optimal Character Memorization Order Summary: In this assignment, you will implement a topological sort algorithm as a way to reorder kanji (漢字; Japanese logographic characters) into an order optimal for memorization. 1 Background In this assignment, you will practice applying your knowledge of graph data structures and algorithms to determine an optimal order to learn logographic characters. Consider the following scenario: as a native speaker of the English language, you wish to learn a language like Chinese (汉语) or Japanese (日本語), which uses a special character set. Unlike the English language, which uses the Roman alphabet to encode phonetics, many east Asian languages use Hanzi derived characters, which are symbols with semantics bound to them (to use the technical term: logographic character). Often times, English speakers learning a language using logographic characters find themselves stumped by the apparently insurmountable problem of memorizing thousands of unique characters. They all look so different and yet so similar - can we hope to tell them apart or write them? 大変な問題!Wouldn't it be nice if we could use our knowledge of algorithms and data structures to somehow address this problem so that English speakers would have a better shot at learning 汉语 or 日本語...? One interesting dependency graph that can be constructed is a “component” graph for Hanzi characters, or Hanzi derived characters (e.g., Kanji). You see, complex characters are often built from simpler characters as components. This sub-structure is very useful! Components not only define a common appearance and stroke order but can indicate phonetics and/or semantics. Furthermore, there are considerably fewer components (hundreds) than actual characters (thousands). (Please note that we use the term component very generally here - it does not map to the traditional notion of a radical.) This sub-structure is particularly useful for people memorizing characters - instead of looking at each character as a monolithic block, one can memorize the individual components, and then reuse that knowledge for more complex characters. The following graph is an example of this for the character 法 ("method"):