2004 Spring CS 146 Data  

  Structures

  and Algorithms

  Study Guide

 

 

 


 


Prof. Sin-Min Lee

Technical skill is mastery of complexity while creativity is mastery of simplicity.                                                             --------------- - Christopher E. Zeeman

 

What we want is to see the student in pursuit of knowledge, and not knowledge in pursuit of the student.                                     ---------------------George Bernard Shaw

 

Teach the young people how to think, not what to think.

--------------------- Sidney Sugarman

 

 

"You have a point there," said Trurl, "We will have to figure some way around that......The main thing, however, is the algorithm."
"Any child knows that! What's a beast without an algorithm?"

Stanislaw Lem, The Cyberiad

 

 2004  Spring CS 146       Green sheet

 

Course Title: Data structures and Algorithm Design                    Credits: 3

 

Instructor: Prof. Sin-Min Lee Office: MH 212                Tel. No.: (408) 924-5133


Office hours:          Tuesday   12:30 - 13:30 PM, 16:15 - 17:45 PM

                                Thursday 12:30 - 13:30 PM, 16:15 - 17:45 PM

                                                                          

I am also available by appointment. I will have extra office hours before each exam.

 

Email: lee@cs.sjsu.edu  E-mailing is a more efficient way of contacting me outside of office hours

 

Course Description: Introduction to the design and analysis of algorithms. Asymptotic analysis of time complexity. Efficient algorithms for sorting, searching, and selection. Algorithm analysis: worst and average case analysis. Recurrences and asymptotics. Data structures: balanced trees, heaps, hashes, etc. Algorithm design techniques: divide-and-conquer, dynamic programming, greedy algorithms. Algorithms for fundamental graph problems, e.g., depth-first search, breadth-first search, topological sort, shortest paths.

 

Textbook: Mark Allen Weiss, Data Structures and algorithm analysis in Java, Addison Wesley, 1999.

 

Reference books:

1. Sara Baase and Allen Van Gelder, Computer Algorithms, 3rd edition, Addison Wesley, 1999.

2. Berman, Data Structures via C++   ---Objects by evolution, Oxford, 1997.

3. Budd, Data structures in C++ using the standard template library, Addison Wesley 1998.

4. Cormen (ed.), Leiserson, Rivest and Stein, Introduction to Algorithms, 2nd edition, MIT Press, 2001.

5. Ford and Topp, Data Structures with C++, Prentice Hall, 1996

6. Goodrich, Michael T. and Roberto Tamassia.  Data Structures and Algorithms in Java.  J. Wiley & Sons.  7.Langsam, Augenstein and Tenenbaum,Data structures using C and C++,2nd edition,  Prentice Hall, 1990.

8. Main and Savitch, Data structures and other objects using C++, Addison Wesley, 1997.

9. Main, Data Structures and Other Objects Using Java, 2nd edition, Addison Wesley, 2003.

10. Sahni, Data Structures, Algorithms, and Applications in C++, McGraw-Hill ,1998

11. Naps, Thomas L. and Pothering, George J., Introduction to Data Structures and Algorithm Analysis with C++, West Publishing Company, 1995.

12. Walls and Mirrors , Data Abstraction and Problem Solving - - Second Edition

13. Mark Allen Weiss, Algorithms, Data Structures, and Problem Solving with C++, Addison-Wesley Publishing Company, 1996.

14. Sedgewick, Algorithms in C++, Part 1-4 Fundamentals Data Structures, Sorting, Searching, Addison-Wesley, 3rd edition.1998.

 

Prerequisites:  CS 46A and 46B.  Calculus II (Math 031) and Discrete Mathematics (Math 042).  A full chart for all SJSU CS courses can be found here

 

Programming Language:   Mastery of Java equivalent to the material in Professor Cay Horstmann’s Computing Concepts with Java Essentials, now in its third edition.

 

Needed Skills: Teachers and books provide information to students. We do the best job we know how to convey this information; but you, the student, must learn the information and make it a part of your knowledge. Your ability to do this depends on many things but two in particular: motivation and study skills. The student is expected to be familiar with basic concepts of programming in Java and with a variety of mathematical tools for modeling and analyzing discrete structures. In order to tackle these topics, you should already be competent at programming in Java. You should feel confident in your ability to design and implement simple programs using arrays and functions. You should be familiar with some programming environment--either a PC or a Unix system. More specifically, the student should be familiar with programming features such as variables, control flow, iteration, and recursion, and structures such as arrays, records, lists, queues, stacks, trees, and graphs. The student should have some rudimentary understanding of time as a measure of program complexity, of basic ideas of program correctness. The student should be familiar with mathematical areas such as college algebra, calculus including differentiation and integration of basic functions; basic concepts of logic, set theory, and proof construction; counting techniques.

 

Dropping Classes: Tuesday, February 17th  last day to drop or withdraw without a “W” grade.

 

Learning Outcomes: 1. The student will develop a knowledge of intermediate level algorithms and data structures and become proficient in programming advanced data structures  The student will familiar with a number of classical algorithms and data structures that are used frequently in a variety of applications in computer science and mathematics.

2. Gain experience in making thoughtful programming decisions by examining tradeoffs between size, speed and coding styles.

 3. Obtain an understanding of software engineering on an individual basis through planning, tracking and analyzing your software process. The  more important objective is to learn a number of powerful general techniques that can be used to design and analyze your own algorithms

4. The student will be expected to learn models for asymptotic analysis of algorithms; techniques for searching and sorting.

5. Work on design, coding and testing software and program better using object-oriented programming techniques  throughout the course of the semester

 

 

Teaching Methodology: The course is given through three lecture periods each week. The instructional methods used in conducting the course include: lectures, discussion, and presentation. In this class you will primarily learn by doing. You will prepare for and follow up on lectures by reading relevant portions of the textbooks (especially prior to class). I will augment the information presented in the textbook with my own ideas and other resources. I encourage discussions in class. Do not have conversations while class is going on. Students in the course are expected to complete assigned readings, assignments, and projects. Most of the lectures have reading assignments that you should complete before the lecture. During the lectures, I may ask short essay questions to ascertain the level of understanding of the reading. I encourage collaborative learning but not cheating in class. You may collaborate with your classmates on assignments but you have to do your own work.  Plagiarism is not allowed in this class. My door is wide open during my office hours and I would love to meet you in person.

      Each one of you will deliver a 20—25 minutes presentation in class. The material will be assigned by the instructor. This productive activity could radically alter your future potential . This course, again, will be one of your most time-consuming classes but will also be one of your most rewarding classes. As a program  is completed and correctly executes, most people realize a great deal of satisfaction. You will be expected to demonstrate proficiency in using the different data structures, as well as general programming concepts and knowledge through assignments and examinations. This is a programming intensive course. There are weekly homework assignments and a final presentation report,. Three midterms and a final will test mostly theoretical knowledge.

 

Attendance Policy: Class Meetings: You are required to attend all class meetings. Every class meeting will be important. Regular class attendance is mandatory. Habitual tardiness will not be tolerated.  If you miss a meeting, it is your responsibility to obtain notes from a fellow student. I may cover some material not found in the textbook. Office hours are not meant for individual lectures.  Class participation is the active engagement in questions and answers, taking part in cooperative learning exercises, and contribution of comments in class sessions. Students are expected to read the assigned material, work the assigned exercises prior to class, and to be prepared to discuss them in class. You are expected to be present for every meeting of the course. Be on time to class. Get in your seat, with paper and pencil to work on the warm-up and your homework ready to be submitted.  One or two absences over the course of the semester is no cause for alarm, but more than that has the potential to seriously impact your ability to achieve a decent grade.

 

Examinations: All examinations will be announced at least one week in advance and will cover material discussed in class and the text book. Test material will be drawn from the text book, lecture, assignments and any supplementary material provided by the instructor. Note that asking the student to use the material presented to think beyond what has been laid out, to apply their knowledge, is really what education is all about. Exact details about examinations in this course will be determined by the instructor. Typically there will be three in-class examinations during the semester and a two-hour final examination. Specific details will be made available before the exams are  offered. No makeup tests will be given. If a test must be missed, notify me as soon as possible.
The exam schedules are as follows:

    1st Midterm      February 17, 2004
    2nd Midterm      March 11, 2004
    3rd Midterm      April 6, 2004
    Final Exam for Section (4) is on Monday May 24, 2004 at 12:15 - 14:30  and  Section (6) is on Friday May 21, 2004 at 14:45 - 17:00

 

Grading: Students' competencies with respect to the objectives  of this course will be evaluated by the following  means: assignments, projects, presentation and examinations. Each student will accumulate points for written exercises, exams, the term project, and other assigned homework.

 

(1) Programs      25% Grading        5 programs

Unsubmitted assignments will vary in difficulty and length, but will generally cover the material from the corresponding weeks' lectures. Some will consist of problems from the textbook. Solving more exercise problems in the textbook may be beneficial. Collaboration on homework is encouraged. This means that you may discuss approaches to solving a problem with anyone in the class. On each submitted homework, work together as much as possible (except when specifically prohibited, as on most exams). Homework Policies and Quality Expectations: One way to help understanding each student is looking in their own work. Since this understanding is at the center of the course goals, each student must strive to have a complete understanding of every exercise. Multiple page assignments must be stapled. Homework exercises are due on the assigned due date.

Do not attempt to submit either homework assignments or programs via email.

All program work submissions to the office must include two diskettes and two completed, computerized version  hard copies. Any submission of an assignment supplied on a disk containing a virus detectable by the school’s virus scanning facilities may be deemed to be a non submission. This includes all types of viruses such as the word processing macro types. All materials to be turned in for a given assignment must be placed in a large envelope or folder where the diskette can be stored easily. You are expected to keep a copy of the program and documentation you turn in until you have received your copy back graded. When a program is turned in it MUST execute, with normal termination, on the assigned data set to be considered for grading. They should all include in an envelope with your name on the surface. Programming assignment grading, unless otherwise specified: Structure design/flow charts 20% ,Style 20% Output 20%, Comments 20%, Program and Procedure Def. 20%.

You submission should contain the following:

README file

The README file should be named just that -- "README", in all caps and with no suffix. It should be a plain text (not MS-Word, etc..) file, and it should contain the following information:

Late Turn-In Policy: Assignments will not be accepted after the due date.  I am unforgivingly strict with late assignments. Assignments MUST be handed in on the day due and BEFORE the lecture begins. Late assignments will get an automatic ZERO, no exceptions, no excuses. Proper resource management should allow you to be timely in all your assignments.

(2) Presentation 10%

The student has to deliver a 20—25 minutes presentation which is prepared in Powerpoint. You can prepare the presentation  in the Computer Center  of College of Science. The instructor will provide the material.  You have to print out 32-36 slides in the format of the handout which we distribute in the class. You can go to Kinko or Wolf and make the sufficient quantity of handouts for the whole class. Student who misses the schedule of presentation will contribute $5 for the Last day pizza party Fund!

The marking criteria for the presentations are:

Thoroughness / Content

3  marks

Organization/Timing

2 marks

Clarity: (Appearance / Spelling / Smoothness / Slides etc.)

 4 marks

Response to questions

1 marks

Total

10 marks

 

 

(3) Presentation report       5%

After finish your presentation., you will write a report on the material you cover in class. In your writing, length is not an asset, brevity is. Be brief and clear. Assignment format
Your report should consist of:

1.      A write-up not to exceed ten pages. Please use an 11pt font and 1" margins all around. Try to have figures embedded in the text rather than at the end. Also, try to be efficient about figure selection and organization.

2.      A complete list of references in an acceptable format. By complete I mean that you should list any and all books and articles that in some way directly influence your report. Include references to your lecture notes and class readings as appropriate to support your points.. The reference list must be included in the ten-page limit.

3.      One clean copy of the article(s) you selected, and copies of any other publication that is highly relevant to your report . Unless you specifically ask me to return them, I will keep the copies you submit. The appended articles do not count toward the 7-10 page limit.

The due day of report will be before Tuesday April 27, 2004. Please submit two copies of your report and a high density 3 ½ inch diskette which contains your report and your Powerpoint presentation.  I will keep the diskette and return a graded report to you.

 

 (4) Weekly Quizes   10%

Student Evaluation: A variety of techniques will be used to evaluate student progress. To the extent possible, in-class written exercises (quizzes) will be conducted in addition to a mid-term and final examination. These quizzes will cover material addressed by assigned readings from the text, assigned exercises, and class discussions. Usually  quizzes will be given after 10-15 minutes the lecture begin. There will be no makeup quizzes for any quiz that you might miss. Missing a quiz will result in a grade of zero.

 

(5)  3 Midterm Examinations (3 @ 10%)    30%

An unexcused absence from an examination will result in a grade of zero for that examination. The only valid excuses for missing an examination are prior written approval from the instructor or a documented medical emergency.

 

(6) Final Examination 20%

 

(7) Extra Credit

There may be extra credit items during the semester. These will be announced in class. Included in these maybe one or more of the following: problems solving, bugs in the text, in-class work, web-page design, attendance/participation bonus points. Extra credit only will apply if you are in that class at the time of the extra credit item

(8) Grades will be changed only when a grading error has been made; negotiation is not appropriate. If you think an error has been made, you should submit a written statement; your entire exam or assignment will then be regraded. You must submit an item for regrading within 7 days from when grading of that item is completed.

 

Grading Scale (in points):

100-96             A+             95.99-92       A         91.99-88       A-

87.99-85          B+             84.99-80       B         79.99-77       B-

76.99-74          C+             73.99-72       C         71.99-70       C-

69.99-65          D+             64.99-62       D         61.99-60       D-         Below 60       F

 

Academic Dishonesty ("Cheating") Policies: Cheating on a quiz or on an exam will result in "F" for the course.  Plagarism, cheating on exams or copying assignments will be cause for failure of the course and may result in dismissal from the University.  Students allowing others to copy their own work are guilty of cheating. Cheating, or helping another student to cheat, are considered equal cases of academic dishonesty  Any attempt to copy other people's assignments, destroy other people's data or code  is considered a violation of academic honesty guidelines. Everyone of you should examine the Academic Honesty Guidelines for more details.  Also, the case will be forwarded to the Office of the Dean of Students for appropriate disciplinary action.

 

...even when the individual believes that science contributes to the human ends which

     he has at heart, his belief needs a continual scanning and re-evaluation which is only

     partly possible. For the individual scientist, even the partial appraisal of the liaison

     between the man and the [historical] process requires an imaginative forward glance

     at history which is difficult, exacting, and only limitedly achievable...We must always

     exert the full strength of our imagination.

      -Norbert Wiener, Some Moral and Technical Consequences of Automation,

          Science 131 (1960): 1358.