06191170: Data Structure (Spring-Summer 2010-2011)

Department of Mathematics

Zhejiang University

Announcements    General     Course Goals     Topics     Texts     Grading     

Syllabus      Assignments     Requirements on Assignments      Professional Conduct     Miscellaneous

Announcements

• June 10: 期末考试时间为2011年6月23日星期四上午10:30-12:30，地点紫金港西1-303。
• June 10: 作业FTP将关闭，若有作业需要递交，请email至Mr. Xiaoguang Han (hanxiaoguangcagd@gmail.com).
• June 1: 布置Homework#5, deadline is 9:30a.m., Wed., June 15, 2011.
• June 1: Course21_图的概念与表示
• June 1: Course22_图的遍历与应用
• May 25: Course19_递归
• May 25: Course20_二叉树的应用
• May 18: 布置Project #2, deadline is 9:30a.m., Wed. June 1, 2011.
• May 11: 布置Homework#4, deadline is 9:30a.m., Wed., May 18, 2011.
• April 13: 布置Project#1, deadline is 9:30a.m., Wed., April 27, 2011.
• April 13: 课堂代码（MiniDraw-2）
• April 13: Course14-图像处理编程基础
• April 13: Course13-GUI画图-进阶
• April 11: 考虑到临近春学期期末考试，Homework#3的递交期限往后延 至 9:30a.m., Wed., April 27, 2011. 作业上传至ftp://10.13.91.116的目录\homework_3下
• Mar. 30: 布置Homework#3, deadline is 9:30a.m., Wed., April 6, 2011. 作业上传至ftp://10.13.91.116的目录\homework_3下.
• Mar. 30: 课堂代码，MFC MiniDraw (line, ellipse)
• Mar. 30: 课堂代码，MFC first demo (hello, world!)
• Mar. 30: Course08-链表
• Mar. 30: Course09-双向链表
• Mar. 30: Course10-串
• Mar. 30: Course11-MFC初步
• Mar. 30: Course12-GUI画图
• Mar. 23: 用户调查：“基于画笔的网格分割交互算法测评” （请各位尽量抽空完成，亦可将链接发给他人。谢谢！）
• Mar. 23: 布置Homework#2.5 (optional), deadline is 9:30a.m., Wed., Mar. 30, 2011.作业上传至ftp://10.13.91.116的目录\homework2.5(optional)下.
• Mar. 23: Course07-线性表
• Mar. 23: Course06-数据结构概论
• Mar. 23: Course05-代码编辑效率及技巧
• Mar. 23: Course04_程序的测试
• Mar. 22: Homework#1作业样例
• Mar. 16: 布置Homework#2, deadline is 9:30a.m., Wed., Mar. 23, 2011. 作业上传至ftp://10.13.91.116的目录\homework2下.
• Mar. 16: 课堂代码(动态链表)，注意：代码不完全
• Mar. 16: Course03_编程规范ppt
• Mar. 9:  布置Homework#1, deadline is 9:30a.m., Wed., Mar. 16, 2011. 作业上传至ftp://10.13.91.116的目录\homework1下.
• Mar. 9:  作业上载FTP: ftp://10.13.91.116 的username/password: 均为DS11
• Mar. 9:  Course02_编程入门ppt
• Mar. 9:  课堂代码(namespace的使用)
• Mar. 9:  课堂代码(template Array), 全部C++代码
• Mar. 9:  课堂代码(template Array)
• Mar. 9:  课堂代码(Smart Array)，预留了Max空间的动态数组
• Mar. 2:  更新ID number
• Mar. 2:  课堂代码(Simple Array)，同学们可完成动态数组的其他接口的实现，不必递交
• Feb. 24: Course01_课程介绍ppt
• Feb. 23: Check your ID number.
• Feb. 22: The website is open.

General
　

Course Goals

The goals of this course are to extend and deepen the student's knowledge and understanding of algorithms and data structures and the associated design and analysis techniques. It examines previously studied algorithms and data structures more rigorously and introduces the student to "new" algorithms and data structures. It focuses the student's attention on the design of program structures that are correct, efficient in both time and space utilization, and defined in terms of appropriate abstractions.

Topics
　

This course provides a comprehensive introduction to data structures and algorithms, including their design, analysis, and implementation. Topics include:
    ·Analysis tools: running time, pseudo-code, algorithm analysis, asymptotic notations
    ·Stacks, queues, linked lists, deques
    ·Vectors, lists, sequences
    ·Trees: basic algorithms on trees, binary trees, representing trees
    ·Priority queues, heaps
    ·Dictionaries: log files, hash tables, ordered dictionary ADT, look-up tables, skip lists
    ·Search trees: binary search trees, AVL trees, multi-way search trees, (2,4) trees, red-black trees
    ·Sorting, sets, and selection
    ·Graphs: traversal, directed graphs, weighted graphs, minimum spanning trees

Texts
　

Required textbook:
            C/C++与数据结构，王立柱著，清华大学出版社, 第3版 （上下册）.

Optional textbook:
            Data Structures, Algorithms, and Applications in C++, Sartaj Sahni, McGraw-Hill. （数据结构算法与应用——C++语言描述，机械工业出版社.）
            Data Abstraction and Problem Solving with C++: Walls and Mirrors by Frank Carrano, fourth edition, Addison Wesley.
            Any good introductory book on C++ programming.

Readings:
            Various journal, conference, or WWW materials as appropriate.
　

Grading

Credit toward the semester grade will be allocated to each of the components as indicated in the following table.

Note: Final examination will be in-class, closed-book. More information will be provided prior to it.

Note: Here you can view or download the notes that we use in class. DO NOT depend solely on these notes as many details are missing. You should read the textbook and take notes in class.

• Course01_课程介绍
• Course02_编程入门
• Course03_编程规范
• Course04_程序的测试
• Course05-代码编辑效率及技巧
• Course06-数据结构概论
• Course07-线性表
• Course08-链表
• Course09-双向链表
• Course10-串
• Course11-MFC初步
• Course12-GUI画图
• Course13-GUI画图-进阶
• Course14-图像处理编程基础
• Course15-树的概念
• Course16-二叉树
• Course17_二叉树的遍历
• Course18_树
• Course19_递归
• Course20_二叉树的应用
• Course21_图的概念与表示
• Course22_图的遍历与应用
• Course23_排序
• Course24_查找
• Course25_广义表

Applets

• Java Applets by R. Mukundan
• Sorting algorithms (app1 (with recursive mergesort), app2 (with iterative mergesort))
• Radix sort applet
• Heap sort applet [ click (1) start, (2) no, (3) ok, and (4) start]
• Binary tree
• AVL animation
• B+ tree animation
• Hash applet
• Depth-first search
• Breadth-first search
• Many other applets

Homework

• Homework#1, deadline is 9:30a.m., Wed., Mar. 16, 2011.
• Homework#2, deadline is 9:30a.m., Wed., Mar. 23, 2011.
• Homework#2.5 (optional), deadline is 9:30a.m., Wed., Mar. 30, 2011.
• Homework#3, deadline is 9:30a.m., Wed., April 27, 2011.
• Homework#4, deadline is 9:30a.m., Wed., May 18, 2011.
• Homework#5, deadline is 9:30a.m., Wed., June 15, 2011.

Projects (Project requirement)

• Project#1, deadline is 9:30a.m., Wed., April 27, 2011. 
• Project#2, deadline is 9:30a.m., Wed. June 1, 2011.

Note: Please zip your submission stuffs of the assignment into one single file either using WinZip or WinRAR. Name the file name as "ID_Name_Homework1.zip" or "ID_Name_Project1" where ID is your unique ID number in the class. For Example, my submission file name might be "007_张三_Homework1.zip".

Requirements on Assignments
　

Requirements

• All students are expected to study the relevant portions of the textbook and handouts in conjunction with our class discussions (i.e., before coming to class). Explicit reading assignments will not always be given.
• All programming for this course will be done in C++ according to the coding styles. We will compile and test programs on MS Visual C++ Version 6.0 under Windows XP. It is the responsibility of the student to submit a program that will successfully compile and execute on the specified platform.

Assignment Submission

• All students are expected to complete their homework assignments by their due dates.
  All assignments are due prior to 11:59:59 PM Wednesday night every week.
• Submission stuffs
  Your ID number, your name, the assignment number or name, source codes, related document
• Grading of programming assignments will be based on the following criteria:
  1. Correctness of program.
  2. Output from program that adequately demonstrates correctness.
  3. Documentation, internal and external, included as appropriate according to the Computer Program Documentation Standards.
  4. Efficient use of algorithms and appropriate data structures.
  5. Stress - program must function correctly under all and/or extreme and unusual combinations of input.
  6. Creativity - credit for innovation in interface, implementation, style, etc.
• Submission approach
  Please submit your assignment stuffs via my FTP not via email.
• Late Work
  No late work will be accepted. If you know you will miss a test due to an excused absence, you must contact me ahead of time to schedule a make-up session.
• Late programming assignments follow the following rules:
  25% deduction for 1-day late
  50% deduction for 2-day late
  Not accepted after being 2-day late
  Regarding your marks, contact the grading TA within two weeks after the assignment is handed back. After this two-week period, your assignment stays as it is graded.

What constitutes Creativity ?

Creativity is any substantial improvement beyond the basic solution - it can be applied to any part of the project. For example, the following are relevant in most cases :

• User Interaction
      ̶  It would be nice to present the user with options to either test the program using internal tests or an interactive interface
      ̶  Work around limitations in the program. For example, if the program asks for lines of input and quits when it sees "X", invent a special syntax (called an escape sequence) to allow the user to type in "X" without the program exiting. Hypothetically, if the user enters $X the program interprets it as X, if the user enters $$ the program interprets it as $ and if the user enters X the program exits.
• Visualization
      ̶  A representation of how data is actually being stored in the data structure, by specific position and value (this would even help greatly with debugging) - this could be accomplished with specialized data access routines for output formatting
• Testing
      ̶  Simulating real-world conditions for input by making some assumptions about the distribution of operations performed and the rate of operations, then simulating using random number generators
      ̶  Intensively testing creation, usage and destruction of the data structure to prove there are no memory leaks
      ̶  Exhaustive automatic testing - go through many (or every) possible scenarios for the data structure (up to some time limit). For example, assign "add" and "remove" to a binary variable - then generate all possible strings of operations - test the structure for each case, and test the results automatically in your main program to make sure they are what was expected.
      ̶  Develop a syntax for file-based testing and use this as an option - eg. "enter X" and "retrieve"
• Efficiency
       ̶  Minimize the number of allocations of memory blocks by reusing deleted blocks
  Ask yourself these questions ...
      ̶  How can I make the interface more natural ?
      ̶  How can I make the program run faster ?
      ̶  How can I use less memory/disk space ?
      ̶  Have I thoroughly tested my program ? Will my program survive real-world tests ? Will my program survive worst-case scenario tests ?

Professional Conduct

As a student in our class, you are expected to conduct yourself in a professional manner.

Limited Collaboration Policy. Unless otherwise indicated, any homework assignment or programming exercise given in this class will be an individual assignment. The work you submit is to reflect the knowledge, understanding, and skill that you have attained as an individual. However, the instructor does want to encourage the development of a community of scholars who are actively engaged in discussion of the ideas related to this course. With this in mind, you are allowed to discuss solutions of the homework and programming problems with other students if done so according to the following guidelines:

• You may discuss ideas for homework and programming assignments with your classmates. However, you cannot collaborate on writing the solution or the program code. That is, you can talk about the problems and ideas for solving them, but you cannot write things down with anyone else. You are, of course, prohibited from copying or seeing another student's written solution, and you are not allowed to show your work to anyone else.
• You should accept help with care. If you work too closely with another student, you might mislead yourself into believing that you understand the concepts and techniques better than you actually do. Don't forget that the instructor has office hours and can probably give you hints or suggestions to get you started.
• You should give help with care. Do not help anyone too much. When you have solved a problem, it is tempting to just tell other students how you solved it. Instead, try to allow them to come to the solution on their own. Maybe give them a hint to help them get "over a hump." Remember that helping someone too much will hurt them in the long term if they can't work through problems on the exams by themselves. So avoid the temptation to do so. If you can't help other students without giving away the whole solution, direct them to see the instructor (who may or may not have a way to "edge" them toward the solution).
• You are not obligated to help anyone. If you feel uncomfortable helping another student for any reason, please direct them to see the instructor.

Miscellaneous

Professionals

• C++ coding styles
• Computer Program Documentation Standards

Online C++ resources

• nC++ language tutotial
• C++ online tutorial
• Programming in C++
• C++ tutorials
• Thinking in C++ (a good on-line C++ textbook)

Useful coding related sites on the internet