====== CSC3270 Advanced Programming Lab ====== ==== Fall 2006 ==== | ^ Lecture I ^ ^ Time | 7:00 pm - 10:00 pm | ^ Venue | SHB 904 | The Golden Rule of CSC3270: No member of the CSC3270 community shall take unfair advantage of any other member of the CSC3270 community. ====== Course Description ====== The course will mainly focus on programming exercises for advanced data structures and algorithms. Topics include dynamic programming, computational geometry, number theory, simulation, combinatorial problems, optimization techniques, graph theory, etc. Prerequisites: CSC1140 and 2100. Corequisite: CSC3160. ====== Personnel ====== | ^ Lecturer ^ Lecturer ^ Tutor ^ Tutor ^ ^ Name | [[ http://www.cse.cuhk.edu.hk/~king |Irwin King]] | Justin Yip | [[ http://www.cse.cuhk.edu.hk/~jkzhu |Jackie Zhu]] | [[ http://www.cse.cuhk.edu.hk/~xpeng |Peng Xiang]] | ^ Email | king AT cse.cuhk.edu.hk | TBD | jkzhu AT cse.cuhk.edu.hk | xpeng AT cse.cuhk.edu.hk | ^ Office | Rm 908 | TBD | Rm101 | Rm1013 | ^ Telephone | 2609 8398 | TBD | 3163 4257 | 2609 8431 | ^ Office Hour(s) | TBD | TBD | TBD | TBD | Note: This class will be taught in English. Homework assignments and examinations will be conducted in English. ====== Syllabus ====== The pdf files are created in Acrobat 6.0. Please obtain the correct version of the [[http://www.adobe.com/prodindex/acrobat/readstep.html#reader | Acrobat Reader]] from Adobe. ^ Week ^ Date ^ Topics ^ Homework & Events \\ [[teaching:csc3270:Guidelines]]\\ [[http://pc89072.cse.cuhk.edu.hk/~csc3270/score.html|Score Board]] ^ Resources ^ | 1 | 11/9 | [[http://www.cse.cuhk.edu.hk/~jkzhu/lec_notes1.pdf|Searching: BFS&DFS]] \\ 1.Introduction \\ 2. Breadth-First Search (BFS) \\ 3. Depth-first search (DFS) \\ 4.Topological sort, etc. | TBD | [[http://en.wikipedia.org/wiki/Breadth-first_search|Breadth-First Search (BFS)]] \\ [[hhttp://en.wikipedia.org/wiki/Depth-first_search|Depth-first search (DFS)]] \\ [[http://en.wikipedia.org/wiki/Topological_sort|Topological sort]] | | 2 | 18/9 | TBD | TBD | | | 3 | 25/9 | TBD | [[http://www.cse.cuhk.edu.hk/~jkzhu/IEPROG2006-C.txt |IEPROG2006-C.txt]] | | | 4 | 2/10 | Public Holiday | TBD | | | 5 | 9/10 | TBD | TBD | | | 6 | 16/10 | TBD | TBD | | | 7 | 23/10 | TBD | [[http://acm.zju.edu.cn/show_problem.php?pid=1790 |1790 - The Geodesic Set Problem]] \\ [[http://acm.zju.edu.cn/show_problem.php?pid=1792 | 1792 - Gap Punishment Alignment Problem]] \\ [[http://www.cse.cuhk.edu.hk/~csc3270/cashiers.pdf | 00005 - Cashiers ]] \\ [[http://acm.uva.es/p/v7/719.html | 719 - Glass Beads ]] \\ [[http://acm.zju.edu.cn/show_problem.php?pid=2221 | 2221 - Taxi Cab Scheme ]] \\ [[http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3013 | 3013 - Overlaying Maps ]] \\ [[http://acm.uva.es/p/v6/607.html | 607 - Scheduling Lectures ]] \\ Due: 23:59, Dec 31, 2006, firmly. \\ The deadline for assg1 is also extended to this time. | | | 8 | 30/10 | Public Holiday | TBD | | | 9 | 6/11 | TBD | TBD | | | 10 | 13/11 | TBD | TBD | | | 11 | 27/11 | TBD | TBD | | | 12 | 4/12 | TBD | TBD | | Notes: - Please submit your homework assignment following the [[teaching:csc3270:Guidelines]]. ====== Examination Schedule ====== | ^ Time ^ Venue ^ Notes ^ ^ Midterm Examination | TBD | TBD | TBD | ^ Final Examination | TBD | TBD | TBD | ====== Grade Assessment Scheme ====== - Attendance, 25% - Homework Assignments and Quizzes, 50% - Mini-contests, 25% Note: The minimum passing grade is to achieve at least 40 out of 100 in the final examination. ====== Programming Requirement ====== Familiarity with the following topics is highly recommended: - Data Structure: data types and structures, lists, queues, stacks, trees, sets, etc. - Algorithm: analysis, design, sorting methods, numerical methods, algorithms on graphs, etc. - Operating System & Programming Environment: Unix systems, C, SQL, and Matlab. ====== Reference Books ====== - [[http://theory.lcs.mit.edu/~clr/|Introduction to Algorithms]], **Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Cliff Stein**, MIT Press. - [[http://www-cs-faculty.stanford.edu/~knuth/taocp.html|The Art of Computer Programming]], **Donald E. Knuth**, Addison-Wesley, 1997. - [[http://www.math.uiuc.edu/~west/igt/|Introduction to Graph Theory]], **Douglas B. West**,Prentice Hall, 2001. - [[http://www.amazon.com/exec/obidos/tg/detail/-/0486414531/103-5037755-0275811?v=glance|Combinatorial Optimization: Networks and Matroids]], **Eugene Lawler**, Dover Publications, 2001. - [[http://maven.smith.edu/~orourke/books/compgeom.html|Computational Geometry in C]], **Joseph O'Rourke**, Cambridge University Press, 1994. ====== Book Sources ====== - **Academic & Professional Book Centre**, 1H Cheong Ming Bldg., 80-86 Argyle St., Kowloon, 2398-2191, 2391-7430 (fax) - **Caves Books (H. K.)**, 4B Ferry St., G/F., Yaumatei, Kowloon, 2780-0987, 2771-2298 - **Man Yuen Book Company**, 45 Parkes street, Jordan Road, Kowloon, Hong Kong, 2366-0594. Not very large, Asian edition books, fair price, wide range, some 10% discount. - **Swindon Book Co. Ltd**, 13-15 Lock Road, Tsim Sha Tsiu, Kowloon, 2366-8001. One of the largest book stores in Hong Kong, exchange rate is not favorable. - **Hongkong Book Centre**, 522-7064. A branch of the Swindon book shop. ====== FAQ ====== * 1. **Q: What happens if a person is caught plagiarizing someone else's work?** A: The CSE department has a very strict guideline on this issue. The guideline is as follows: If a student is found plagiarizing, his/her case will be reported to the Department Discipline Committee. If the case is proven after deliberation, the student will automatically fail the course in which he/she committed plagiarism. The definition of plagiarism includes copying of the whole or parts of written assignments, programming exercises, reports, quiz papers, mid-term examinations. The penalty will apply to both the one who copies the work and the one whose work is being copied, unless the latter can prove his/her work has been copied unwittingly. Furthermore, inclusion of others' works or results without citation in assignments and reports is also regarded as plagiarism with similar penalty to the offender. A student caught plagiarizing during tests or examinations will be reported to the Faculty Office and appropriate disciplinary authorities for further action, in addition to failing the course. [[teaching:csc3270:Guidelines]] ====== Resources ====== - [[http://acm.uva.es/problemset/|On-Line Judge]] - [[http://appsrv.cse.cuhk.edu.hk/~acmprog/web2006/|CSE Programming Team]]