📄 http:^^www.cs.wisc.edu^~cs367-2^cs367.html
字号:
Date: Thu, 07 Nov 1996 19:23:52 GMTServer: NCSA/1.5Content-type: text/htmlLast-modified: Thu, 31 Oct 1996 18:30:59 GMTContent-length: 20386<HEAD><TITLE>CS 367 - Lecture 2</TITLE></HEAD><BODY><H1>CS 367-2<br>Introduction to Data Structures<br>Fall 1996</H1><P>Course email address:<!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><A HREF="http://www.cs.wisc.edu/cgi-bin/finger/m?cs367-2"> cs367-2@cs.wisc.edu </A><br>Course home page:<!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><A HREF="http://www.cs.wisc.edu/~cs367-2/cs367.html"> http://www.cs.wisc.edu/~cs367-2/cs367.html</A><br><P>INSTRUCTOR: <a name="yannis"><b>Yannis Ioannidis</b> <br></a>Office: 7357 Computer Sciences<br>Office hours: Tuesday 8:45-9:30 am / Thursday 8:45-9:30 am<br>Office phone: 263-7764<br>Email address:<!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><A HREF="http://www.cs.wisc.edu/cgi-bin/finger/m?yannis"> yannis@cs.wisc.edu </A><br>Home page:<!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><A HREF="http://www.cs.wisc.edu/~yannis/yannis.html"> http://www.cs.wisc.edu/~yannis/yannis.html </A><br><hr><hr><h2>Contents</h2><ul><li> <!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><a href="#news"> News</a><li> <!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><a href="#tas"> Teaching Assistants</a><li> <!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><a href="#lectures"> Lecture Information</a><li> <!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><a href="#cnotes"> The C++ Language</a><li> <!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><a href="#text"> Text</a><li> <!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><a href="#grading"> Grading</a><li> <!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><a href="#exams"> Exams</a><li> <!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><a href="#schedule"> Course Schedule</a><li> <!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><a href="#photo"> Assignment 0</a><li> <!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><a href="#assignments"> Programming Assignments</a><ul><li> <!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><a href="#late"> Late Policy</a><li> <!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><a href="#cheating"> Cheating</a><li> <!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><a href="#help"> Help</a><li> <!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><a href="#criteria"> Program Grading</a><li> <!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><a href="#style"> Style</a><li> <!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><a href="#external"> External Documentation</a><li> <!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><a href="#internal"> Internal Documentation</a></ul><li> <!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><a href="#misc"> Using Unix and Vi</a><li> <!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><a href=#cycle"> The Program Development Cycle </a></ul><hr><a name="news"><h2>News</h2></a><h3>Assignment 3</h3><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><A HREF="http://www.cs.wisc.edu/~cs367-2/assign3/assign3.html">Assignment 3 </A>is now ready.<h3>Midterm Statistics</h3>Some interesting exam statistics for Section 2: <b>max:</b> 98, <b>min:</b> 22,<b>median:</b> 78, <b>mean:</b> 77.92<h3>Old Midterm</h3>A sample <!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><A HREF="http://www.cs.wisc.edu/~cs367-2/oldmdtrm.ps">oldmidterm</A> is now available to help you in your preparation for our ownmidterm.<h3>Assignment 2</h3><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><A HREF="http://www.cs.wisc.edu/~cs367-2/assign2/assign2.html">Assignment 2 </A>is now ready.<h3>Notes on O-notation and Binary Search</h3>The notes on <!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><a href="http://www.cs.wisc.edu/~cs367-2/onot.ps"> O-notation </a>and <!WA27><!WA27><!WA27><!WA27><!WA27><!WA27><!WA27><!WA27><!WA27><!WA27><!WA27><!WA27><!WA27><!WA27><!WA27><!WA27><!WA27><!WA27><!WA27><!WA27><!WA27><!WA27><a href="http://www.cs.wisc.edu/~cs367-2/bin.ps"> Binary Search </a>are now available.If you want to print either one of them, open the <i>File</i>menu from the (<i>Ghostview</i>) window that shows you the document, andchoose the ``Print...'' menu item.<h3>Women In Computer Science</h3>Some female faculty, graduate students, and undergraduates haveformed a group called WICS (Women In Computer Science). Oneof the group's goals is to encourage more women to becomecomputer science majors. So if there are any women in thisclass who would like to talk to someone about majoring incomputer science, or doing graduate studies in computer science,or if there are any women who would like some extra help withtheir classwork, they should see Suzan (a computerscience grad student) during her office hours or email her tomake an appointment.Suzan's e-mail address is: stodder@cs.wisc.eduand her office hours are Tuesday & Thursday 1:30-2:30 in room 1345.<h3>Assignment 1</h3><!WA28><!WA28><!WA28><!WA28><!WA28><!WA28><!WA28><!WA28><!WA28><!WA28><!WA28><!WA28><!WA28><!WA28><!WA28><!WA28><!WA28><!WA28><!WA28><!WA28><!WA28><!WA28><A HREF="http://www.cs.wisc.edu/~cs367-2/assign1/assign1.html">Assignment 1 </A>is now ready.<h3>Out of Town</h3>The first week of classes I will be out of town at the VLDB Conference.Jim Larus will give the lectures for me. I will be in classSeptember 10th.<a name="tas"><h2> Teaching Assistants </h2></a>Both people listed below are teaching assistants (TAs) for the course.They will be grading your homework assigments and will be happy to answerquestions about the assignments, or any other aspect of the course thatis giving you trouble.Note that TAs are not assigned to specific sections.<p><b>Chin Tang Chin</b> <br>Office: 3310 Computer Sciences<br>Office hours: Monday 9:30-10:30am / Tuesday 2:30-3:30pm / Friday 9:30-10:30am<br>Office phone: 262-1721 <br>Email address:<!WA29><!WA29><!WA29><!WA29><!WA29><!WA29><!WA29><!WA29><!WA29><!WA29><!WA29><!WA29><!WA29><!WA29><!WA29><!WA29><!WA29><!WA29><!WA29><!WA29><!WA29><!WA29><A HREF="http://www.cs.wisc.edu/cgi-bin/finger/m?cchin"> cchin@cs.wisc.edu </A><br>Home page:<!WA30><!WA30><!WA30><!WA30><!WA30><!WA30><!WA30><!WA30><!WA30><!WA30><!WA30><!WA30><!WA30><!WA30><!WA30><!WA30><!WA30><!WA30><!WA30><!WA30><!WA30><!WA30><A HREF="http://www.cs.wisc.edu/~cchin/cchin.html"> http://www.cs.wisc.edu/~cchin/cchin.html </A><br><p><b>Wei Zhang</b> <br>Office: 1343 Computer Sciences<br>Office hours: Wednesday 10:00-11:00am / Thursday 9:00-10:00am / Sunday 3:00-4:00pm<br>Office phone: 262-5596 <br>Email address:<!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><!WA31><A HREF="http://www.cs.wisc.edu/cgi-bin/finger?weiz"> weiz@cs.wisc.edu </A><br>Home page:<!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><!WA32><A HREF="http://www.cs.wisc.edu/~weiz/weiz.html"> http://www.cs.wisc.edu/~weiz/weiz.html </A><br><p><a name="lectures"><h2> Lecture Information </h2></a><b>Lecture:</b> 9:30 - 10:45 Tuesday and Thursday<br>1325 Computer Sciences and Statistics<p><a name="cnotes"><h2> The C++ Language </h2></a>CS 367 will be taught using the C++ programminglanguage, and you will be required to do your programming assignmentsin C++.We didn't choose C++ just to make your life more difficult.Most people who become fluent in C++ think it is far superior to C orPascal; the use of C++ is growing tremendously in the field and theodds are that if you ever have to write another program after thiscourse ends, you will be able to write it in C++. (The same statementis not true about Pascal. C is also widely available, but after aninitial startup period you will be more productive in C++ than in C.)If you go on to take more computer science courses, with few exceptionsyou will be required to use C++ in those courses.<a name="text"><h2>Text</h2></a>The text book for this course is<i>Data Abstraction and Problem Solving with C++: Walls and Mirrors </i>by Frank M. Carrano (ISBN # 0-8053-1226-9).This is a well-written text that covers most(but not all) of the material in this course.It also includes a lot about C++, so a separate text for the language is notnecessary.For my lectures I will often (but not always) be following<i> CS 367 Lecture Notes - Fall 1993</i>by David J. DeWitt.These notes are actually considerably more complete that simple lecturenotes, but they are still short of a true text book (there isvery little narrative text, no exercises, etc.)As a recommended additional source, you may want to purchase these notes, whichare available from the DoIT documentation desk near the Dayton Street entranceof the Computer Sciences building (1210 W. Dayton St).<p>If this is the first experience with Unix for you, you will needsome information about activating your account, logging in, creating, editing,and manipulating files, and compiling, running, and debugging programs.The handout<i>CS 1000</i>, available from the DoIT information desk (where the DeWitt notesare available), contains all the key information.You will find it invaluable.See also the <!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><!WA33><a href="#help"> help</a> section below.<p>As I mentioned above, the lectures will often follow the DeWitt notes, althoughI may supplement them with a few handouts during the courseof the semester.Nonetheless,<em>You are responsible for all material covered in lecture!</em>The exams will be based onthe lecture material, reading assignments in the notes, andthe course assignments.<a name="grading"><h2>Grading</h2></a>There will be one or two evening exams during the course of the semester,a final exam and five programming assignments.The exams will determine 50% of the final grade(with approximately equal weight for each one), and the programmingassignments will count for 10% each.<a name="exams"><h2> Exams </h2></a><dl compact><dt> Exam 1<dd> Tuesday, October 22nd, 7:15pm-9:15pm, 1351 Chemistry.<dt> Exam 2<dd> TBA<dt> Final Exam <dd> Wednesday, December 18th, 5:05pm-7:05pm, <i>place TBA</i></dl><a name="schedule"><h2> Course Schedule </h2></a>The following is the list of topics that will be covered in thiscourse. A more detailed scheduled will be provided later.semester.<pre>TOPIC DEWITT'S NOTES WALLS AND MIRRORS===========================================================================Introduction, Administration 1-42 (general familiarity)Basic stuff of C++ lecture #2 101-135, App A, App C---------------------------------------------------------------------------Functions lecture #3 App APointers lecture #4 141-150, App A---------------------------------------------------------------------------Records & dynamic storage lecture #5 141-150, App ALists lecture #6 150-177---------------------------------------------------------------------------Lists lecture #6 150-177Binary Search and O notation 83- 86, 393-405---------------------------------------------------------------------------Advanced Lists lecture #7 177-189Advanced Lists lecture #7 177-189---------------------------------------------------------------------------Stacks lecture #8 249-295Queues lecture #9 307-344---------------------------------------------------------------------------Hashing lecture #10 591-608Hashing lecture #10 591-608---------------------------------------------------------------------------Recursion (Evening Exam) lecture #11 50- 93, 203-238Trees lecture #12 439-468, 501-502---------------------------------------------------------------------------Trees lecture #12 439-468, 501-502Binary Trees - Sort & Search lecture #13 468-500---------------------------------------------------------------------------AVL Trees 587-590AVL Trees 587-590---------------------------------------------------------------------------Graphs lecture #16 620-646Graphs lecture #16 620-646---------------------------------------------------------------------------Graphs lecture #16 620-646Graphs lecture #16 620-646---------------------------------------------------------------------------Sorting lecture #17 405-432THANKSGIVING---------------------------------------------------------------------------Sorting lecture #17 405-432⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -