CmpE 180-26: Algorithms and Data Structure Design (Fall 2008)

Announcements

• Final grades
• Lab exam 4 scores
• Final exam:
  Time: Dec 17th, Wednesday, 14:45-17:00PM
  Location: CL 226
• Algorithm for updating balance factor
• Midterm grades 2
• Lab exam 3 scores
• Sample solution of Destructor/Copy constructor of BST: [Ameya's][Amulya's]
• Midterm average is: 76.2%.
• Midterm grades posted.
• Lab exam 2 scores
• Lab exam 1 scores

Course Description

Object-oriented data organization and representation as strings, arrays, stacks, queues, dequeues, lists, sets, trees, tables, and graphs. Sorting, searching algorithm design, and performance analysis will be discussed.

The student will learn a variety of fundamental concepts and practices in the areas of software engineering, object-oriented design and programming, data structures, and algorithms. Data structures covered will include: queues, linked lists, trees, graphs and their use. Algorithmic techniques will be studied for recursion, hashing, searching, and sorting. This course includes numerous exercises in C and C++ programming to be performed on a Linux and UNIX compatible systems. Each student should own or have access to a copy of a C/C++ development environment such as Microsoft “Visual C++”, Borland “Turbo C++”, or the Unix-based gcc. Use of a UNIX-based C++ environment is strongly recommended, as all programming exams written for this course must ultimately be developed to work on UNIX-based environments.

Prerequisites

CmpE 101 with a passing grade of CR. The instructor will distribute a sign-up sheet that you must sign to indicate that you are aware of the prerequisite for CmpE180-26. Failure to sign the sheet will result in a grade of F for the course.

You should have the following skills before taking this course:

• ability to use with computers and Unix: logging in, commands, editing, etc.
• ability to program in c++

Textbook

Required textbook:

• ADTs, Data Structures, and Problem Solving with C++, 2nd Edition, by Larry Nyhoff of Calvin College, ISBN: 0-13-140909-3 Upper Saddle River, New Jersey: Prentice-Hall, 2005

Reference texts:

• Lecture notes posted on the course website.
  
• Data Structures and Other Objects Using C++, Main and Savitch, Addison-Wesley Publishing Company, Third edition (2005) ISBN 0-321-19716-X
• Data Structures via C++: Objects by Evolution, A. Michael Berman, Oxford University Press, ISBN 0-19-510843-4
• Data Structures with C++ Using STL (2nd Edition), W. Ford and W. Topp, Prentice-Hall, ISBN 0-13-085580-1
• C++ Plus Data Structures (2nd Edition), N. Dale, D. Teague, Jones and Bartlett Publishers, ISBN 0-7637-1470-4

Syllabus

Resources

• C++ information:
  • C++ FAQ LITE
  • Introduction to Object-Oriented Programming Using C++
  • A good lecture ppt from Dr. Qu
• Platform-independent C++ IDE: Codeblocks. You can compile your source code to executables on different platforms.
• Sharpen your development skills: Topcoder.com

Grading Policy

Grades will be assigned on a curve. Your final grade will be based on assignments, exams, and class participation. These will be weighted as follows.

• The instructor reserves the right to change the percentages listed above by ±5%
• Exams and quizzes must be done individually. Groups of 2 students will be formed to work on homework assignments.
• All the home assignments must be submitted through the Blackboard system.
• No late submission will be accepted unless a written evidence such as a physician's letter is accompanied with the request for late submission.

Description of assignments:

• Class participation: Participation in classroom discussion and other in-class written assignments (surveys).
• Quizzes: Quizzes will be given to students during lectures. Questions may include explanation to terms, comparison between different design, evaluation of data structures, or coding.
• Homework assignments: Homework assignments will be posted every 1-2 weeks. Each homework contains a group of programming tasks. All the homework assignments must be submitted through the Blackboard system.
• Lab Exams:Students will be required to required to write programs based on assigned topics in the Unix lab. Each lab exam takes 2 hours on Fridays. Time slots are assigned at the beginning of the semester. Students are required to sign up for time slots to take the lab exam.
• Exams: There are two written exams: one midterm exam and one final exam. Exams contain multiple choice and paragraphs questions. You may be asked to write pseudo-code or C++ code.

Academic Honesty

Your own commitment to learning, as evidenced by your enrollment at San Jose State University, and the University’s Integrity Policy, require you to be honest in all your academic course work. Faculty members are required to report all infractions to the office of Judicial Affairs. The policy on academic integrity can be found at:

http://sa.sjsu.edu/judicial_affairs/index.html

Things (among many others) you may not do when working with other students (except for team work):

• The term “solution” mentioned below anything (code, design document, description, etc.) you will submit for assignments and exams.
• Work on an assignment together, type in solutions (separately or together) and turn in separate copies.
• Each works on a part of an assignment and turn in separate copies after combining solutions.
• Give any part of your solution (through paper, board writing, email, web posting, reading loud, letting someone else look at your screen, etc.) to other students before the assignment deadline.

Things you may do when working with other students:

• Discuss with other students and leave the discussion with empty hands.
• Share assignment solutions after the assignment deadline in order to compare different techniques used for solving the problems.

Plagiarism

San José State University defines plagiarism as the act of representing the work of another as one's
own without giving appropriate credit, regardless of how that work was obtained, and submitting it to
fulfill academic requirements.
Plagiarism includes:

1.2.1 Knowingly or unknowingly incorporating the ideas, words, sentences, paragraphs, or parts
of, or the specific substance of another's work, without giving appropriate credit, and
representing the product as one's own work;
1.2.2 Representing another’s artistic/scholarly works such as musical compositions, computer programs, photographs, paintings, drawing, sculptures, or similar works as one's own.

Note:

• Copying online content without correct quote is treated as plagiarism in this class.
• Both the person who copies and the person who facilitates the copying will be prosecuted for academic dishonesty.
  

Accommodation for Disabilities

If you need course adaptations or accommodations because of a disability, or if you need special arrangements in case the building must be evacuated, please make an appointment with me as soon as possible, or see me during office hours. Presidential Directive 97-03 requires that students with disabilities requesting accommodations must register with DRC to establish a record of their disability.