http://algorithmics.comp.nus.edu.sg/wiki/ 2009-11-23T15:23:58+08:00 http://algorithmics.comp.nus.edu.sg/wiki/ http://algorithmics.comp.nus.edu.sg/wiki/lib/images/favicon.ico text/html 2007-12-29T09:37:34+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/dynamic_heap?rev=1198892254 Important Notes * This is a graded lab. * You have 5 (FIVE) submissions. Make sure that you test your program thoroughly before submitting to CourseMarker. * Note that CourseMarker take your best submission for marking. That is, if your last submission (with comments added) scores less than the previous submission, the previous submission will be used for grading by CourseMarker and LabTAs. If that is the case, the comments added will not be seen by the LabTAs. * Make sure that you add … text/html 2008-01-31T16:18:52+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/lab0?rev=1201767532 Notes * This is a practice lab. * You have 200 submissions for this lab. * You should test your program thoroughly before submitting to CourseMarker. * You should try to practice good programming style by: * Adding in meaningful comments to document your program. * Make sure that you indent the statements to enhance the readability of your program. * Use meaningful identifies. text/html 2008-02-04T23:10:18+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/lab1?rev=1202137818 Special note: This lab is meant for you to practice the various way to read input. Also it lets you practice how to format the output according to the specifications of the question. Description The Association of Amateur Magicians (AAM) organizes a competition every year for aspiring magicians to show off new tricks. The performer of the best trick will be crowned Amateur Magician of the year. text/html 2008-04-10T11:28:30+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/lab10?rev=1207798110 Instructions * This is not a TA graded assignment. (No partial credit will be given if your program do not pass Dynamic tests) * The deadline is 9am on 16/04/2008 (Wednesday). * You have 200 submissions. Make sure that you tested your program fully before attempting to submit to CourseMarker. * Make sure that you practice good programming style. (This will give your 30% of the lab) * Good comments * Good modularity * Good indentation, and * Use meaningful identifie… text/html 2008-04-20T13:56:10+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/lab11a?rev=1208670970 The Singapore Sweep is a nationwide lottery. For each lottery, 3,000,000 tickets are printed with numbers between 1,000,000 and 3,999,999 inclusive. Each ticket costs $3. If your ticket number is drawn, you win the value of the prize. In this question, you are to calculate the NET PROFIT (can be negative) given the numbers of the tickets bought and the winning numbers. text/html 2008-04-20T14:07:11+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/lab11b?rev=1208671631 By definition, logical expression is an expression with boolean operands and logical operations. The value of boolean operand can be either true (represented by 1) or false (represented by 0). The result of a logical expression is also a boolean value. text/html 2008-02-08T13:44:24+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/lab1_analysis?rev=1202449464 Understand the problem The problem description is rather long but make sure you've read it carefully and understood what is required. Typically in such problems, all of the information presented will be useful in one way or another. Getting started It is probably helpful to pick up some playing cards and try out the trick on your own. Getting your hands dirty by playing around with some small examples is a good way to get started on a problem. It will help you to develop a better understandin… text/html 2008-02-09T22:36:34+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/lab2?rev=1202567794 Objective * Learn how to implement a class and use inheritance. * Learn how to implement a linked list. * Learn how to use linked list. Instructions * This is not a TA graded assignment. (No partial credit will be given if your program do not pass Dynamic tests) * The deadline is 9am on 13/02/2008. * You have 200 submissions. Make sure that you tested your program fully before attempting to submit to CourseMarker. * Make sure that you practice good programming style. (This … text/html 2008-04-13T10:22:24+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/lab2_analysis?rev=1208053344 Basics of the Unix FS This task introduced the Unix File System (UFS) and related concepts such as files and directories. A major difference as compared to the file system on Windows is that there is no inherent notion of drives. You can think of the UFS as a logical organization of your files that is independent of the way files are stored physically. text/html 2008-02-22T20:55:57+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/lab3a?rev=1203684957 Instructions * This is a TA-graded lab * You are given 1h 40 min to solve the lab. * This includes 15 min for analysis. * If you have any question, you may raise your hand and the TA will attend to you. * Please note that you will get 50% of the marks if your program cannot compile. * You are reminded that 30% of marks is awarded for programming style. text/html 2008-02-24T00:05:00+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/lab3a_analysis?rev=1203782700 Understanding the problem For this problem, the problem description seems to be needlessly tedious. Thankfully a careful study of the sample input and output provides sufficient information to understand the gist of the problem. Basically, you are given the initial order of the soldiers and a sequence of positions in which the soldiers are called up. When a soldier is called up, he will move to the end of the queue. At the end, you have to output the ids of the soldiers who were called up and … text/html 2008-02-20T19:07:00+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/lab3b?rev=1203505620 Instructions * This is a TA-graded lab * You are given 1h 40 min to solve the lab. * This includes 15 min for analysis. * If you have any question, you may raise your hand and the TA will attend to you. * Please note that you will get 50% of the marks if your program cannot compile. * You are reminded that 30% of marks is awarded for programming style. text/html 2008-02-24T00:07:11+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/lab3b_analysis?rev=1203782831 Understanding the problem Conceptually, this problem involves maintaining a sorted linked list. Each time a new item is inserted, you have to report its position after insertion into the sorted linked list. ListIterator is tricky If you are using the Java LinkedList class, then one way to do the insertion is to make use of the ListIterator to iterate through the list. Note that the get method of the list interface is not suitable for iterating over a linked list. text/html 2008-02-20T19:12:08+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/lab4?rev=1203505928 Instructions * This is not a TA graded assignment. (No partial credit will be given if your program do not pass Dynamic tests) * The deadline is 9am on 27/02/2008. * You have 200 submissions. Make sure that you tested your program fully before attempting to submit to CourseMarker. * Make sure that you practice good programming style. (This will give your 30% of the lab) * Good comments * Good modularity * Good indentation, and * Use meaningful identifies. text/html 2008-03-11T09:42:15+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/lab4_analysis?rev=1205199735 Understanding the problem In this exercise, the task is to check whether a given XML document is valid. Roughly speaking, an XML document is valid if its tags match up properly. Intuitively, it is easier to think in term of matching parenthesis in mathematical expressions. For example, []() is valid while ([)] is not. A tag is a generalized parenthesis which can be identified using a string instead of a single symbol. text/html 2008-03-06T00:39:21+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/lab5?rev=1204735161 Instructions * This is not a TA graded assignment. (No partial credit will be given if your program do not pass Dynamic tests) * The deadline is 9am on 13/03/2008 (Wednesday). * You have 200 submissions. Make sure that you tested your program fully before attempting to submit to CourseMarker. * Make sure that you practice good programming style. (This will give your 30% of the lab) * Good comments * Good modularity * Good indentation, and * Use meaningful identifie… text/html 2008-03-14T10:46:50+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/lab5_analysis?rev=1205462810 Figuring out the right problem to solve An important part of problem solving is modelling the problem, by translating it into a more succinct problem which captures the essence of the problem without all the unnecessary details. In this case, we are given a set of numbers and after that given a series of query scores. For each query score we are to compute its rank, where the rank of a number is its position in descending order. If there are multiple scores of the same value, then their rank … text/html 2008-03-15T23:08:09+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/lab6a?rev=1205593689 Instructions * This is a TA-graded lab * You are given 1h 40 min to solve the lab. * This includes 15 min for analysis. * If you have any question, you may raise your hand and the TA will attend to you. * Please note that you will get 50% of the marks if your program cannot compile. * You are reminded that 30% of marks is awarded for programming style. text/html 2008-04-22T15:22:39+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/lab6a_analysis?rev=1208848959 Initial thoughts There are two kind of events we have to take care of in order to takle this problem * orders from customers * some dish is ready Order from customers should be recorded/stored in some data structure, which should be able to answer queries of the form: for a particular dish X, what is the tag number of the customer to serve the dish to. text/html 2008-03-15T22:03:03+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/lab6b?rev=1205589783 Instructions * This is a TA-graded lab * You are given 1h 40 min to solve the lab. * This includes 15 min for analysis. * If you have any question, you may raise your hand and the TA will attend to you. * Please note that you will get 50% of the marks if your program cannot compile. * You are reminded that 30% of marks is awarded for programming style. text/html 2008-03-22T12:05:51+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/lab7a?rev=1206158751 Instructions * This is a TA-graded lab * You are given 1h 40 min to solve the lab. * This includes 15 min for analysis. * If you have any question, you may raise your hand and the TA will attend to you. * Please note that you will get 50% of the marks if your program cannot compile. * You are reminded that 30% of marks is awarded for programming style. * You are to develop ONLY in Sunfire. You are not allowed to copy any file onto your Windows machine. text/html 2008-04-06T22:29:09+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/lab7a_analysis?rev=1207492149 The original write up and test data for this problem was created by me. This problem was inspired by problem 6.26 from Udi Manber's book Introduction to Algorithms: A creative approach. In retrospect, I feel this problem is not really suitable at this level, although the algorithm is intuitive and easy to implement, understanding why the algorithm works requires a firm understanding of how to show the correctness of greedy algorithms. text/html 2008-03-22T12:10:06+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/lab7b?rev=1206159006 Instructions * This is a TA-graded lab * You are given 1h 40 min to solve the lab. * This includes 15 min for analysis. * If you have any question, you may raise your hand and the TA will attend to you. * Please note that you will get 50% of the marks if your program cannot compile. * You are reminded that 30% of marks is awarded for programming style. * You are to develop FULLY in Sunfire. You are not allowed to copy any file onto your local Windows machine. text/html 2008-03-27T14:12:52+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/lab8?rev=1206598372 Instructions * This is not a TA graded assignment. (No partial credit will be given if your program do not pass Dynamic tests) * The deadline is 9am on 02/04/2008 (Wednesday). * You have 200 submissions. Make sure that you tested your program fully before attempting to submit to CourseMarker. * Make sure that you practice good programming style. (This will give your 30% of the lab) * Good comments * Good modularity * Good indentation, and * Use meaningful identifies. text/html 2008-04-21T19:07:13+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/lab8_analysis?rev=1208776033 Traversals and Trees A traversal is a systematic way to visit all the nodes in a tree. There are three different traversals of a tree, inorder (left-root-right), preorder (root-left-right) and postorder (left-right-root). The prefix (in, pre, post) refers to when the root is visited. text/html 2008-04-06T22:40:59+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/lab9a?rev=1207492859 Instruction * This is a TA-graded lab * You are given 1h 40 min to solve the lab. * This includes 15 min for analysis. * If you have any question, you may raise your hand and the TA will attend to you. * Please note that you will get 50% of the marks if your program cannot compile. * You are reminded that 30% of marks is awarded for programming style. * You are not allowed to copy your files onto Windows. Please develop fully in Sunfire environment. text/html 2008-04-06T22:45:25+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/lab9b?rev=1207493125 Instruction * This is a TA-graded lab * You are given 1h 40 min to solve the lab. * This includes 15 min for analysis. * If you have any question, you may raise your hand and the TA will attend to you. * Please note that you will get 50% of the marks if your program cannot compile. * You are reminded that 30% of marks is awarded for programming style. * You are not allowed to copy your files onto Windows. Please develop fully in Sunfire environment. text/html 2007-12-29T09:37:34+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/pe_solution?rev=1198892254 Is It Complete? (30%) Comments I noticed some students spend a lot of time on Q1 and seems to have neglected Q2 which is actually worth much more marks. Solution 1 The easiest solution I know is just to assign each node a position as if that node is part of a heap. So the root is position 0, left child of root is position 1 and right child of root is position 2 and so on. Then you only need to check that the largest position is equal to number of nodes - 1, i.e. if the nodes were stored in a… text/html 2009-04-02T16:59:50+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/sidebar?rev=1238662790 * Home * Sidebar * Tutorials * Tutorial 1 - Java and Problem Solving * Tutorial 2 - Abstract Data Types * Tutorial 3 - Linked List * Tutorial 4 - Stacks and Queues * Tutorial 5 - Recursion * Tutorial 6 - Analysis of Algorithms * Tutorial 7 - Sorting * Tutorial 8 - Trees * Tutorial 9 - Heaps text/html 2009-04-02T17:00:40+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/start?rev=1238662840 This is an unofficial website for CS1102 created by Melvin. This semester, I'm teaching the following tutorial slots for CS1102Y: * Thursday 2-3 * Thursday 3-4 After each tutorial, please take 5mins to fill in this feedback form. text/html 2009-01-17T15:01:14+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/start_0607_sem1?rev=1232175674 Programs must be written for people to read, and only incidentally for machines to execute. - H. Abelson and G. Sussman Computer Science is a science of abstraction - creating the right model for a problem and devising the appropriate mechanizable techniques to solve it. - A. Aho and J. Ullman Good teaching is more a giving of the right questions than a giving of the right answers. - J. Albers Staff Appointment Name Email Office Lecturer … text/html 2009-01-17T15:01:20+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/start_0708_sem1?rev=1232175680 If you're not failing every now and again, it's a sign you're not doing anything very innovative. - W. Allen In theory, there is no difference between theory and practice, but not in practice. - Anon Think twice, code once. - Anon Staff Appointment Name Email Office Lecturer Dr Tan Sun Teck <tanst@comp.nus.edu.sg> COM1-03-15 6516 2778 Tutor Hugo Willy <dcshw@nus.edu.sg> Tutor Derry Tanti Wijaya <… text/html 2009-01-17T15:03:45+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/start_0708_sem2?rev=1232175825 This is an unofficial website for CS1102 labs created by Melvin. Please note that there is no such thing as a model answer or solution for a programming task. The following are my attempts at analyzing the problem and showing you how to come up with a particular solution. In order not to bore you, I will only highlight the key steps in obtaining the solution. text/html 2007-12-29T09:37:34+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/t1?rev=1198892254 * CHEE BING FOONG * GENG NING * HAI CHIN KIANG * HONG XUCHU KENNETH * LIEW HUI YI SOPHIA * LIM SIEW LIAN JULIANA * LING ZICHENG * LIU SHANGYAN * LOONG PEI HUI * MASITA BTE BAKTI * NAVEEN KUMAR K.V * NEO KEE BENG * ONG YUH SHIN * PUI BEE HONG * SATYA SAYA * SHI YUANNA * TAN E-LYNN * TAN YING ENG * TOH LING LING * WONG AI QI GRACE * ZHOU GUANGHAO text/html 2007-12-29T09:37:34+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/t2?rev=1198892254 * AZHAR BIN MOHAMED YASIN * CHEN HUIWEN * CHENG ZHENGHUI * CHIA SIEW KHOON CHERISA * CHIA YONG KAI * CHNG CHING HUI * CHUA CHENG SOON KELVIN * LEE LINFU * LI QINGYI ESTHER CLAIRE * LIN ZHIJIE * MASNI BINTE HASSAN * MIRA MILIANI * MOHAMED NAHFEES * NGUYEN THI HOAI THUONG * NGUYEN VAN HUONG * ONG WEI YI * SUMAIYA BINTE MOHAMAD ALI * SURIANA BTE SELAMAT * YANG JIANQING text/html 2007-12-29T09:37:34+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/t6?rev=1198892254 * ANG YIN SHER SHARON * CHUNG LIN RUSSELL * KHONG JUN MING MARCUS * KOH CHUN RONG JOHN * LIM PEI YEE * MOHAMED SHAJUDEEN BIN MOHAMED YUSOF * MURNI BINTE MOHAMAD EUSOFF * NIKITA ASTHANA * OEI GRACE YUNITA * SALIHA BINTE ABDUL AZIZ * SIAH KOK SENG SHAUN * XIE JIAHAO * XU SI * ZHUANG YAWEN text/html 2009-02-06T11:19:31+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/tut1?rev=1233890371 Q2a Is the expression “y+++++y” legal in Java? What about “y+++y” or “y++++y” ? The postfix and prefix increment operators are particularly confusing because they modify the value of the variable in addition to returning the value of the variable. Use with caution! text/html 2009-02-06T11:30:12+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/tut2?rev=1233891012 Q1 There seems to be some confusion as to whether “information hiding” and “encapsulation” mean the same thing. There is no definitive answer, but for an accurate survey, you might want to read <http://www.itmweb.com/essay550.htm> In this module, we take the view that encapsulation is about the conceptual idea of grouping data and operations into a single entity. text/html 2009-02-14T13:59:47+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/tut3?rev=1234591187 Q1b/c The mysteryMethod is equivalent to a single pass of the Bubble Sort algorithm, it “bubbles” the largest element to the end of the list. The boolean value returned by the method indicates whether any swaps too place. If there are no swaps, then the list is already sorted and mysteryMethod returns false. text/html 2009-03-19T17:52:02+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/tut4?rev=1237456322 Q2 The solution to this problem makes use of a technique known as depth-first search (DFS), which you will learn under the topic of graphs. See <http://www.cs.rochester.edu/u/kautz/Mazes/search/applet.html> for an applet which shows how DFS finds a path through the maze. text/html 2009-03-19T18:01:02+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/tut5?rev=1237456862 Q2c The divide and conquer solution makes use of a specific property of the minimum of a set of numbers, i.e. `\min(S) = \min(\min(A), \min(B))`, where `S` is a set of numbers and `A \cup B = S` Try to write a proof of this property. text/html 2009-04-17T09:56:26+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/tut5b?rev=1239933386 Power Given two integers n and m, write a recursive algorithm which computes `n^m`. Your algorithm should have a time complexity of `O(\lg m)`. Hint: `n^m = (n^{m/2})^2` if `m` is even Ans: //compute n^m pow(n, m) { if (m = 0) { return 1; } else { l := m/2; r := m - l; n_l := pow(n, l); n_r := n_l; if (n_r = n_l + 1) { n_r := n_r * n } return n_l * n_r; } } text/html 2009-03-19T19:31:20+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/tut6?rev=1237462280 There is a strong connection between analysis of algorithms and counting. The two main basic ideas in counting is the addition rule and multiplication rule. Q1d In this question, the number of times the println statement is executed depends on the value of j. If j is even, the the inner loop executes n - i times, else it executes j times. text/html 2009-04-08T21:28:32+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/tut6b?rev=1239197312 Analysis of iterative algorithms What is the complexity of the following code fragments: for (int i = 1; i <= n; i = i * 2) { System.out.println("*"); } Ans: `O(\lg n)` for (int i = 1; i <= n; i = i + 1) { for (int j = 1; j <= n; j = j * 2) { System.out.println("*"); } } text/html 2009-04-02T16:34:55+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/tut7?rev=1238661295 Q3b It is possible to make quicksort `O(n \lg n)` in the worst case by finding the median in linear time and using it to partition the array, this way the partition set always splits the array into equal halves. However the algorithm for finding the median in linear time is not easy to implement and it is not practical for reasonable datasets. text/html 2009-04-02T16:41:39+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/tut8?rev=1238661699 2b Instead of creating new arrays to represent the inorder and preorder traversal of the subtrees, it is possible to save space by passing a pair of indices instead. Observe that the inorder/preorder traversal of the left and right subtrees are just contiguous segments of the inorder/preorder traversal of the whole tree. Therefore, we can represent the inorder/preorder traversal of the subtrees using a start and end index. text/html 2009-04-24T15:58:37+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/tut8b?rev=1240559917 Number of leaf nodes [CS1102C AY0809 Sem 1] Write a recursive algorithm to count the number of leaf nodes in a binary tree. Ans: int count_leaves(TreeNode u) if (u is empty) return 0 if (u is a leaf node) return 1 else count_leaves(left subtree of u) + count_leaves(right subtree of u) text/html 2009-04-02T16:59:19+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/tut9?rev=1238662759 Q1c Notice that in the first method (insert one-by-one), in the worst case the nodes that are initially inserted at the last level might have to bubble up all the way to the top. There are `O(n/2)` nodes which may need to bubble up `O(\lg n)` levels, hence the complexity is at least `O(n \lg n)`. text/html 2007-12-31T11:31:31+08:00 http://algorithmics.comp.nus.edu.sg/wiki/cs1102/word_ladder_solver?rev=1199071891 Changelog 22/10/06 Corrected mistake in generateNeighbours method, previously did not return list in lexicographical order. Credits to Ruzaika for spotting the mistake. Important Notes * This is a graded lab. * You have 5 (FIVE) submissions. Make sure that you test your program thoroughly before submitting to CourseMarker. * Note that CourseMarker take your best submission for marking. That is, if your last submission (with comments added) scores less than the previous submission, the …