Look [[here|http://cs.nyu.edu/yap/pub/classes/basic/05f/hw]] for your class homeworks.\n\nSolutions:\n[[Homework 2|sol2.pdf]]\n[[Homework 3|sol3.pdf]]\n[[Homework 4|sol4.pdf]]
9/17/05 - Page created\n10/9/05 - Solutions for homework 2 added\n10/15/05 - Solutions for homework 3 added\n11/18/05 - Solutions for homework 4 added
!!! COURSE ID:\n V22.0310.001, Basic Algorithms, Fall 2005\n\n!!! CLASSES: \n(1) Lecture: Mon and Wed, 11:00--12:15, in WWH 101\n(2) Recitation: Mon, 12:30-1:45, in WWH 101.\n\n!!! TEACHER: \nChee Yap, Office: Warren Weaver Hall, Room 416,\nPhone: (212) 998-3115, Email: yap (at) cs.nyu.edu\n\n!!! TA:\nChris Wu, Office: 715/719 Broadway, Room 704,\nPhone (212) 998-3514, Email: wu (at) cs.nyu.edu\n\n!!! GRADER: \nAnkit Sunil Malpani. His email is ankit.malpani (at) nyu.edu.\n\n!!! OFFICE HOURS: \nChee: Wednesday 4:30--5:30, and by appointment.\nChris: TBA\n\n!!! PREREQUISITE: \nBasic Java programming skills\nData structures course (V22.0102)\n\n!!! TEXTBOOK: \n[[Algorithm Design|http://www.aw-bc.com/info/kleinberg/]] by Jon Kleinberg and Eva Tardos Addison-Wesley (2006)\n\n!!! EXAMS: \nQuizzes: Mon Oct 3 and Mon Nov 28\nMidterm: Wed Oct 12\nFinal Exam: To be confirmed (probably: Mon Dec 19)\n\n!!! HOMEWORK: \n*No late homework. About 6 homeworks (including programming assignments).\n*Non-programming homework must be handed in hardcopy (properly bound). It is due during class hour.\n*All programming homework is to be handed via email to the grader, but cc'ed to me. It is due at 12 midnite of the due date. All the files must come in a single email. If any file is revised, you must resend the entire set in one email again.\n*You are responsible for keeping an extra copy of your submitted homework.\n\n!!! PROGRAMMING: \nA modest amount of Java programming will be required\n\n!!! COURSE ACCOUNT: \nUnix is the official operating system. You are automatically enrolled for a unix account on the machine i4.nyu.edu, which you can access using ssh. If you prefer to use your own machine, and you have a Windows environment, I highly recommend that you install Cygwin on your computer.\n\n!!! GRADE: \nCurved, 40% homework + quizzes, 20% midterm, 40% final.\n\n!!! ACADEMIC INTEGRITY: \nThis must be taken seriously. All handed in assignments must represent your own work. If you use any programs or solutions from sources in the open literature, you should give full attribution. You should never copy work of other students, nor let your work be copied by others. However, we encourage you to discuss problems and material with other students in the class. But all writeup must be your own.
Welcome to the webpage for the Fall '05 Basic Algorithms class.\n\nIf you have suggestions or bug reports, please let me know at wu (at) cs.nyu.edu\n\nThis page is basically a static version of tagglywiki. The page should work with any recent browser. It has been tested on IE, Firefox and Opera for Windows and Safari, Omniweb, Firefox and Camino for OS X.
[[Updates]] [[Welcome]]
| 1 | Sep 12 | Introduction: Representative problems|Chap. 1|\n| 2 | Sep 19 |Algorithmic Analysis |Chap. 2|\n| 3 | Sep 26 |Graphs |Chap. 3|\n| 4 | Oct 3; |Quiz 1 & Graphs (contd) |Chap. 3|\n| 5 |Oct 10 |Greedy Algorithms |Chap. 4; Oct 10 (Columbus day); Midterm (Oct 12)|\n|6 |Oct 17 |Greedy Algorithms (contd) |Chap. 4|\n|7 |Oct 24 |Divide and Conquer |Chap 5|\n|8 |Oct 31 |Divide and Conquer(contd) |Chap 5|\n|9 |Nov 7 |Dynamic Programming |Chap. 6 |\n|10 |Nov 14 |Dynamic Programming (contd) |Chap. 6|\n|11 |Nov 21 |NP Completeness |Chap. 8; Thanksgiving (Nov 24)|\n|12 |Nov 28 |Quiz 2 & NP Completeness (contd) |Chap. 8|\n|13 |Dec 5 |Randomized Algorithms |Chap. 13|\n|14 |Dec 12 |Randomized Algorithms (contd) |Chap. 13; Last class (Dec 14)|\n|15 |Dec 19 |Final Exam | |
! FAQ\n\n\n! Comments\n* Grading is done by the Grader and *not* the TA. Please contact the Grader and not the TA for questions about marking.
[[About the Course]]\n[[Course Mechanics]]\n[[Course Schedule]]\n[[Class Board]]\n[[Homework]]\n[[The Grading Guide]]\n[[Outside Resources]]\n[[FAQ/Comments]]\n\nCreateNewTiddler
THIS SHOULD BE OF NO INTEREST TO STUDENTS...\n \nPlease record grades in an electronic ASCII file.\n\nI need this file in the strict format specified below since I use several programs to process grade files (to compute averages, ranking, sorting, etc).\n\nFeel free to ask me for these programs (written in AWK) if you want.\n\nBasically, each student has a line.\n\nThe grades for each assignment goes into its own column.\n\nTHERE SHOULD BE EXACTLY ONE TAB SEPARATING ANY TWO CONSECUTIVE COLUMNS. \n\nHINT: If necessary, insert space to force the columns to line up (but do not use additional tabs!)\n \nHERE is the typical set of columns. (You can add more columns as the semester progresses):\n\n # GRADE FILE FOR V22.0201, Fall 1997.\n # ======================================================================\n # NO. NAME ID HW1 HW2 MID HW3 FIN \n # (MAXIMUM SCORES) (30) (45) (100) (25) (200)\n # ======================================================================\n 1. Mistry, Ravi 123456789 29 -1 100 22 184 \n 2. Yap, Chee 987654321 8 24 68 25 131\n ...\n ## ======================================================================\n ## COMMENTS:\n ## --Mistry had an valid excuse for missing HW2.\n ## --Yap had a very nice solution to Q2 in HW3 (he used loops!)\n ## ======================================================================\n ## END OF GRADE FILE\n\nREMARKS:\n1) All lines that do not correspond to a student begin with the "#" sign (like a comment).You do not need to obey the TABBING constraint for these lines, obviously. \n2) Use a grade of "-1" to indicate that no assignment was received. E.g., Mistry missed HW2 in the example. Do not use "0"(since this may be an actual grade!).
Unfortunately, we need to discuss this issue which rarely arises.\n\n(A) For the student:\nFirst of all, remember that the university and also our department has clear guidelines about this topic. Please consult these rules. \n\nWhat constitutes cheating? Basically any work you submit with your name on it says "THIS IS MY OWN WORK". Cheating is when this is false. If you partially copied from someone or some source, you must acknowledge this in the assignment. When in doubt, ask me. Note that this is different from DISCUSSING the material with other students in the class: you can freely do this (I encourage this!). But once you start to write up your solution, you are on your own. Abetting cheating is just as serious -- if you knowingly let a friend copy your work, you are also responsible for cheating. \n\n(B) For the Grader: \nI do not expect you to deliberately look out for cheating, but when you get a sense of something unusual, you might want to check more closely. Make a note of the names and discuss with me -- do not confront the students directly.
NOTE: \nAs grader, you should know the general instructions that I give to students on handing in homework. Beware that these instructions may be modified for individual homework or classes!\n\nThere are two basic ways to submit your homework:\n\n(1) Non-programs must be handed in as hardcopies.\n* These are due during class hours.\n* It should be properly bound together (stapled or in an envelop).\n\n(2) Programs must be handed in electronically, in\nONE single email. \n* These are due by midnite of the due date. \n* If you have to re-submit one of the files, please resend the ENTIRE set in one email (so that we can just delete your earlier email).
!PLEASE READ THIS CAREFULLY and always refer to it.\n\nThe most important thing about grading is to be CONSISTENT.\n\nOf course, consistency alone is not sufficient: it has to also agree with the inherent nature of the subject matter. Unfortunately, this is outside the scope of these instructions.\n\nHave a system of assigning points. Make an initial list of items to look out for (key items pertinent to the hw), and distribute points to each item. Often I have already made an initial cut at this.\n\nYou can refine the system as your experience with the assignment grows: do not be afraid to go back and regrade any assignment in hindsight! Hopefully this happens within the first handful of assignments.\n \nHINT: to avoid frequent regrading, allow yourself some discretionary points (say at most 10 percent).\n \n"Get the word out'' -- COMMUNICATE to the students any general rules you have, so that they know what to expect, and how to maximize their\nperformance. If many students have the same mistake, this may be a sign that you may need to communicate to the class. STRONGLY RECOMMENDED: create a webpage for your class.\n\nGive partial credits. If an item gets 4 pts, you might want to give a student 2 pts if he/she got it half-correct, etc. On the other hand, I prefer not go see small fractions (1/2 point is probably OK but not 1/4 point). \n\nFeel free to give individual feedback to students (this may take a lot of effort, but use your judgement). E.g., if you really like a solution, write "Good", "Nice", etc. \n\nThe more specific the comments, the better (e.g., "Your argument here is elegant", "It is a common mistake to forget X'')\n\nYou can note down such information in the grade sheet for my attention.\n\nFeel free to say "I do not understand your solution, please come to explain your answer to me to get full credit".\n\nGive the instructor (me!) feedback: Please keep a note book and jot down information about various points about the hw, and/or about individual solutions. We can discuss them. I am interested to know how individual students are performing. [The extremes of performance, either very weak or very strong ones, are useful to take note of.]\n\n\n! GRADING PROGRAMS\n\nThe rule is: if it does not compile, it gets 0 points.\n\nEvery program must have a brief introduction about:\n (1) its purpose,\n (2) how the program works (what algorithms/data structures, etc)\n (3) how to use it\n\nIn addition, it is sometimes important to: \n (4) describe some important classes/functions/variables\n (5) provide sample data sets\n\nReserve about 10--15% of the points for comments, elegance, etc. Encourage the use of BOTH multiline comments (/*...*/) as well as single line comments (//...)\n\nI normally require that each submission be accompanied by a "Makefile'' with the default target to compile the program. (So we just have to type "make" to compile.) Moreover, it should have another target called "run" or "test" to test the compiled program. (So we can just type "make test" or "make run" to test the program).
* [[Instructions for a TA or Grader]]\n* [[How to Hand in Homework]]\n* [[How to Record Grades]]\n* [[Academic Honesty]]
*[[Java Resources|http://cs.nyu.edu/yap/pub/classes/basic/info/java.html]] : tutorials, programs, etc. \n*[[Make Program|http://cs.nyu.edu/~yap/prog/make/]] : tutorial and info \n*[[Cygwin Resources|http://cs.nyu.edu/~yap/prog/cygwin]] : great free unix environment for your Windows! \n*[[Printing Postscript|http://cs.nyu.edu/yap/pub/classes/info/postscript.html]]\n*General Computing FAQs: [[Unix|http://cs.nyu.edu/yap/pub/classes/basic/info/unix-faqs.html]], [[Windows|http://cs.nyu.edu/yap/pub/classes/basic/info/win-faqs.html]]. \n*The [[Information Technology Services (ITS)|http://cs.nyu.edu/yap/pub/classes/basic/info/its.html]] at NYU provides your basic [[computing needs|http://www.nyu.edu/acf/facstaff.html]] at NYU. Look here for lab sites and hours. \n* Other useful [[links|http://cs.nyu.edu/yap/pub/classes/basic/info/links.html]]. \n*If you have suggestions for this space, please send an email to wu (at) cs.nyu.edu.
The course introduces you to:\n* efficient data structures (e.g., balanced trees),\n* basic computational problems (e.g., shortest paths)\n* important algorithms (e.g., string matching),\n* the mathematical tools for complexity analysis (e.g., recurrences), and\n* general computational paradigms (e.g., divide and conquer) \n\nOur approach is relatively rigorous and mathematical. The pace is not leisurely -- so expect to spend time outside of lectures to keep up with the work. Attendence at lectures and recitations is essential.
Look here for announcements, class discussion and your grades. Login using your NYU NetID, then click this class link.\n\n[[NYU Bboard System|http://classes.nyu.edu/]]
Basic Algorithms
You can SaveChanges if you're using FireFox or InternetExplorer:\n# if you're using Windows XP you might run into ServicePack2Problems\n# right click on [[this link|empty.html]] and select 'Save link as...' or 'Save target as...'\n** do ''not'' try to use the File/Save command in your browser because of SaveUnpredictabilities.\n** choose where to save the file, and what to call it (but keep the .HTML extension)\n# open the newly downloaded file in your browser\n# click the 'options' button on the right to set your username\n# edit, create and delete the tiddlers you want\n** you can change the SpecialTiddlers to change the SiteTitle and MainMenu etc.\n# click the 'save changes' button on the right to save your changes\n# TagglyWiki will make a backup copy of the existing file, and then replace it with the new version\n