Tugas Besar Implementasi Struktur Data Spell Checking
Spell checking is the process of verifying that a particular word is spelled properly according to some dictionary. Spell checkers are used in many applications, including word processors (such as Microsoft Word), electronic dictionaries, and optical character recognition (OCR) systems that need to turn images of printed text (or even handwriting) into coherent text. Spell checking itself is trivial, requiring only a simple lookup in a dictionary. However, most applications of spell checking also require that the spell checker provide a list of potentially correct spellings (“near matches”) when the word was spelled improperly. For instance, if I type “speling” into an online dictionary, it will provide suggestions of similar words that I may have meant to type, including “spelling”, “spoiling”, “sapling”, and “splendid”. Your task is to implement a spell checker that determines if a given word is spelled correctly based on a dictionary lookup. When the word is not spelled correctly, it will provide a list of similar-sounding words based on your implementation of the edit distance algorithm to find near matches, and ordered based on their edit distance from the string that the user typed.
Fig. 1 gives an overview of the spell-checking process.
Sumber: Dr. Rabie Ramadan. Data Structures and Algorithms. Systems and Computer Engineering Department. Al - Azhar University
Tugas Besar Implementasi Struktur Data Shortest Paths in a Network
Consider a data communication network that must route data packets (email or MP3 files, for example). Such a network consists of routers connected by physical cables or links. A router can act as a source, a destination, or a forwarder of data packets. We can model a network as a graph with each router corresponding to a vertex and the link or physical connection between two routers corresponding to a pair of directed edges between the vertices. A network that follows the OSPF (Open Shortest Path First) protocol routes packets using Dijkstra’s shortest path algorithm. The criteria used to compute the weight corresponding to a link can include the time taken for data transmission, reliability of the link, transmission cost, and available bandwidth. Typically each router has a complete representation of the network graph and associated information available to it. For the purposes of this project, each link has associated with it the transmission time taken for data to get from the vertex at one end to the vertex at the other end. You will compute the best path using the criterion of minimizing the total time taken for data to reach the destination. The shortest time path minimizes the sum of the transmission times of the links along the path. The network topology can change dynamically based on the state of the links and the routers. For example, a link may go down when the corresponding cable is cut, and a vertex may go down when the corresponding router crashes. In addition to these transient changes, changes to a network occur when a link is added or removed. Example Consider a very simplified example of a network at RPI, with vertices at Amos Eaton, Lally, DCC, Troy, Sage, and Folsom. See Figure 1 for an illustration. For this example, the shortest time (or fastest) path from Amos Eaton to DCC is: Amos Eaton–Troy–DCC with a total transmission time of 0.9 milliseconds.
Sumber: Dr. Rabie Ramadan. Data Structures and Algorithms. Systems and Computer Engineering Department . Al - Azhar University
Tugas Besar Implementasi Struktur Data Interpreter LISP
Buatlah sebuah program yang diberi nama LISP-B yang merupakan sebuah interpreter sederhana bahasa LISP-B. Interpreter ini menerima masukan berupa ekspresi-SBin yang diketikkan oleh pemrogram, melakukan interpretasi terhadap ekspresi tersebut, dan menampilkan hasilnya ke layar. LISP-B adalah bahasa mirip LISP, namun hanya mampu menangani ekspresi biner dan uner. Hal ini berbeda dengan bahasa LISP yang menggunakan ekspresi-S yang menangani ekspresi dengan argumen yang dapat bervariasi. Sementera ekspresi-SBin pada LISP-B hanya menangani ekspresi biner atau uner. Konsep-konsep dasar dalam Bahasa LISP dapat dilihat dalam Diktat Kuliah Pemrograman Fungsional Bagian LISP atau sumber-sumber lain, misalnya LISP 1.5 Programmer’s Manual oleh John McCarthy dkk. Interaksi dengan Pengguna Ketika interpreter LISP-B dijalankan, program dikenali dengan munculnya prompt ”>”. Setiap ekspresi yang akan diinterpretasi, harus dituliskan setelah tanda prompt tersebut. Seperti pada LISP biasa, setiap ekspresi dituliskan sebagai list of symbols di antara tanda kurung ( ). Jumlah pasangan kurung buka-kurung tutup dalam suatu ekspresi harus tepat berpasangan satu-satu. Jika tidak, maka ekspresi salah. Program versi awal yang anda buat selalu menangani ekspresi yang bebas dari kesalahan sintaks. Akhir sebuah ekspresi ditandai dengan karakter ”#”. Dengan demikian, bisa terjadi ekspresi kosong, yaitu jika pengguna hanya mengetikkan ”#”. Ekspresi kosong tidak diinterpretasi. Setelah satu ekspresi selesai ditulis dan benar, program akan secara otomatis menginterpretasi ekspresi dan mengeluarkan hasil. Lalu memunculkan kembali tanda prompt. Interpreter LISP-B ditutup jika pengguna mengetikkan perintah (exit)#. Contoh: > (+ 1 2)# 3 > (= 1 2)# T > (+ (+ 1 3) (- 2 1))# 5
Beberapa operasi yang harus bisa dilakukan dalam LISP-B yaitu Ekspresi Aritmatika, Relasional, dan Lojik. Ekspresi dasar aritmatika berlaku hanya terhadap atom yang bernilai numerik (integer maupun real) dan memberikan hasil numerik (integer atau real). Operasi yang mungkin: pemangkatan (exp), penjumlahan (+), pengurangan (-), perkalian (*), pembagian (div dan /), sisa pembagian (mod). Di samping itu juga ada operator minus (-) terhadap suatu nilai numerik yang memberikan hasil nilai numerik tersebut dikalikan -1 dan operator ”se-per” (/) terhadap suatu nilai numerik yang memberikan hasil 1 per nilai numerik bersangkutan. Catatan: Pelajari konsep operasi dasar aritmatika dalam LISP terutama yang terkait dengan tipe integer dan real dan bagaimana hasil operasi terhadap kedua jenis nilai tersebut terhadap operator-operator aritmatika.
Contoh: > (+ 2 (+ 3 4))# 9 > (* (+ 1 2) (+ (- -3 4) 4))# -9 > (- -3)# 3 > (/ -3)# -0.33333 Ekspresi dasar relasional berlaku terhadap atom yang bernilai numerik (integer dan real) atau karakter dan hasilnya adalah boolean. Operasi yang mungkin: kesamaan (=), ketidaksamaan (/=), lebih besar (>), lebih kecil (<), lebih besar atau sama dengan (>=), lebih kecil atau sama dengan (<=). Contoh: > (> 2 5)# F > (<= 4 (+ 3 2))# T Ekspresi dasar lojik berlaku terhadap ekspresi yang bernilai boolean dan hasilnya bernilai boolean. Operasi yang mungkin: negasi (not), dan (and), serta atau (or). Contoh: > (AND (> 1 2) (/= 3 4))# F > (OR T (< 1 2))# T Pada interpreter LISP-B, dibatasi bahwa satu operator hanya memiliki maksimum 2 operan (ekspresi biner atau uner). Operator uner yang dapat ditangani hanyalah negasi (minus dan “se-per” untuk nilai numerik, serta ”NOT” untuk boolean). Sumber: FN, MA dan IL. Algoritma dan Struktur Data. Sekolah Teknik Elektro dan Informatika. Institut Teknologi Bandung
Tugas Besar Implementasi Struktur Data Mini Search Engine
In this project, you will be designing and implementing a mini search engine. The task performed by a search engine is, as the name says, to search through a collection of documents. Given a set of texts and a query, the search engine will locate all documents that contain the keywords in the query. The problem may be therefore reduced to a search problem, which can be efficiently solved with the data structures we have studied in this class. Your task is to design and implement an algorithm that searches a collection of documents. You have the freedom to select the data structures and algorithms that you consider to be more efficient for this task. Of course, you will have to justify your decisions. First, you will process the documents and store their content (i.e. words / tokens) in the data structures that you selected (in information retrieval, this phase is called indexing). Next, for every input query, you will process the query and search its keywords in the documents, using the previously implemented data structures and an algorithm of your choice. (this phase is called retrieval). For each such query, you will have to display the documents that satisfy the query. The queries may contain simple Boolean operators, that is AND and OR, which act in a similar manner with the well known analogous logical operators. For instance, a query: “Keyword1 AND Keyword2” should retrieve all documents that contain both these keywords (elements). “Keyword 1 OR Keyword 2” instead will retrieve documents that contain either one of the two keywords. Consider the following sample documents: Doc1: This is a data structures class. Doc2: Data structures are fun. Doc3: I like this project and survey. Here are the answers to some queries: Query 1: data Doc1, Doc2 Query2: data AND structures Doc1, Doc2 Query 3: like OR survey Doc3 Sumber: -
Tugas Besar Implementasi Struktur Data Snakes and Ladders: The Quickest Way Up
Markov takes out his Snakes and Ladders game and stares at the board, and wonders: If he had absolute control on the die, and could get it to generate any number (in the range 1-6) he desired, what would be the least number of rolls of the die in which he'd be able to reach the destination square (Square Number 100) after having started at the base square (Square Number 1)?
Rules 1. Markov has total control over the die and the face which shows up every time he tosses it. You need to help him figure out the minimum number of moves in which he can reach the target square (100) after starting at the base (Square 1). 2. A die roll which would cause the player to land up at a square greater than 100, goes wasted, and the player remains at his original square. Such as a case when the player is at Square Number 99, rolls the die, and ends up with a 5. 3. If a person reaches a square which is the base of a ladder, (s)he has to climb up that ladder, and he cannot come down on it. If a person reaches a square which has the mouth of the snake, (s)he has to go down the snake and come out through the tail - there is no way to climb down a ladder or to go up through a snake.
Input Format There are 3 lines. 1. The first line contains the number of ladders and snakes, separated by a comma. 2. The second is a list of comma separated pairs indicating the starting and ending squares of the ladders. The first point is the square from which a player can ascend and the second point is his final position. 3. The third is a list of comma separated pairs indicating the starting and ending (mouth and tail) squares of the snakes. the first point is the position of the mouth of the snake and the second one is the tail. Multiple comma separated pairs of snakes and ladders are separated by a single space. Constraints The board is always of the size 10 x 10 1 <= Number of Snakes <= 15 1 <= Number of Ladders <= 15 Squares are always numbered 1 to 100 and the order can be seen in the image above. Output Format Output one integer each on a new line, which is the least number of moves (or rolls of the die) in which the player can reach the target square (Square Number 100) after starting at the base (Square Number 1). This corresponds to the ideal sequence of faces which show up when the die is rolled. Sample Input 3,7 32,62 42,68 12,98 95,13 97,25 93,37 79,27 75,19 49,47 67,17
Sample Output 3
5,8 32,62 44,66 22,58 34,60 2,90 85,7 63,31 87,13 75,11 89,33 57,5 71,15 55,25
3
Explanation For the first test: To traverse the board via the shortest route, the player first rolls the die to get a 5, and ends up at square 6. He then rolls the die to get 6. He ends up at square 12, from where he climbs the ladder to square 98. He then rolls the die to get '2', and ends up at square 100, which is the target square. So, the player required 3 rolls of the die for this shortest and best case scenario. So the answer for the first test is 3. For the second test: Rolls the die to get 1, reaches square 2. Then, climbs the ladder to square 90. Rolls the die to get 4, reaches square 94. Rolls the die to get 6, reaches square 100, which is the target square. So the answer for the second test is also 3. Sumber: Hacker Rank
