Algorithms and Data Structures

Instructor: Steve Allan

Office: Main 429

Communications: Phone: 797-2587, E-mail: Steve.Allan@usu.edu

Office Hours:  9:30-11:30 MWF.  Additional office hours are available by appointment or when my office door is open.

Prerequisite: CS 1720 or equivalent knowledge. 

If you feel that you are a poor C++ programmer, your chances of succeeding in this class are slim. I would strongly recommend that you take CS1720 instead of this class.  I expect that you know the following material: structs, unions, file operations, classes, friends, overloading operators, inheritance, polymorphism, virtual, exceptions, templates, linked lists, stacks, queues, recursion, and binary trees.  There is so much new material to be learned, you do not have time to learn material that you should have mastered in earlier classes.  Sometimes students like to gamble on success.  The laws of gambling state that the smaller the probability of succeeding, the greater the reward.  Many times the gamble in taking a class (given the time you are willing to spend and the skills you bring to it) has a very low probability of success and a small reward (you may barely pass, but the hours required may cause you to do poorly in other classes). 

Every semester I see many students throwing away time and tuition money by taking classes they can't possibly pass with their skills and/or their commitment.  They go through the motions of taking the course, but don't learn what they need to.  Some students say, "The instructor is so nice. If I come every day and try my best, surely she/he will give me a passing grade.''  It won't happen.  Giving you a passing grade when you haven't earned it is not only unfair to others, but it is no favor to you.  You would go on to struggle in other classes. 

Tutors: Tutors for data structures are available in Main 425 and SER 5.  Please use them whenever possible.  If a tutor is on duty, I expect that you will consult with her/him before you come to see me.  The hours for fall semester are:

MAIN 425:

SER 005

Course Page: All assignments and other information dealing with the course are posted on the course page (www.cs.usu.edu/allan/2200).

Text: Data Structures and Problem Solving Using C++, 2^nd Edition by Mark Weiss.  Addison-Wesley, 2000 (ISBN 0-201-61250-X).   There are many online sites for books.  You might consider Amazon.com, Borders.com, Buy.com, ClassBooks.com, BN.com, BookPool.com, and VarsityBooks.com.

Objectives: The main objectives of this course are: a mastery of data structures, a mastery of refining programming skills, a mastery of developing strategies for the design and evaluation of algorithms, a familiarity of algorithm analysis, a mastery of recursion, a familiarity of sorting algorithms, a familiarity of graphs, a familiarity of trees, a mastery of binary search trees, a mastery of hash tables, a mastery of priority queues, a mastery of splay trees, a mastery of merging priority queues, a familiarity of disjoint set classes, an exposure to dynamic programming, an exposure to greedy algorithms.  Memorization or copying is not learning and will not be encouraged.  Class discussion utilizes discovery learning and will be very different in nature from the step by step, cookbook approach of most texts.  Since you will experience both the text's presentation and the derivation of the ideas in class, you will have the benefit of both teaching techniques. 

Requirements:

Grading:

You may be given an F if either your overall average is below 50%.  Remember, you cannot receive higher than a D+ if you haven't turned in all the programming assignments or don't have over 60% of the possible points on the programming assignments. 

Current scores can be checked on the eagle system.  Special announcements about the class are e-mailed to you, so it is suggested that you check your e-mail daily.

Course Outline:

Regrading: If you feel that a program, written assignment, or exam has been graded incorrectly, submit a concise written summary of your concerns to me.  These requests should be submitted within a week of the return of the assignment or exam.

Tardiness: When you come to class late, every person in the room is distracted by your entrance (including your professor).  You miss important material.  You are saying to your professor, "My time and my schedule are more important than what you have to teach me.''  On the job, if you don't come to work, you will be fired.  If you come late, you will be reprimanded.  Come to class and come on time!  It is good practice for the real world. 

Standards: All work in this class is graded based on the best solution rather than merely solving the problem.  Sometimes students feel it is unfair for a teacher to expect the best when they are just learning, but it is important for a student to strive for the real goal.  On the job, a program that "just works" is almost never adequate.  How can one expect to improve or even recognized quality if it has never been demanded?

Late Work: The most common problem in this class is failure to complete the programs on time. Students are typically optimistic about the amount of time it takes to write a program, and tend to budget their time for the best possible case instead of for the average or worst case.  In addition, when problems do arise, a person tends to think the she/he is the only one with such unforeseen problems and anticipates exceptions will certainly be made.  Once a person gets behind with one program, it is very common to be behind on many programs either because a late finish on one dictates a late start on the next or because the penalty was not sufficient to avoid similar pitfalls.

Late work creates difficulties in grading.  Unless a very strict policy is enforced, chaos reigns.  It is not that I am insensitive to your personal problems, but rather that I must insist that you rise above them. When the instructor grants an extension to one student, it is unfair to the other students who would have benefited from such special treatment.

All programming assignments are due at 11:59:59 p.m. on the date specified. However, each student is entitled to one personal emergency.  Thus, you are allowed to turn in one program up to two days late (48 hours) without penalty (and without explanation). When the personal emergency has been used, late work is accepted (up to two days late) with a penalty of 30% per day.

Code Reuse: For this course, it is almost never appropriate to copy code from the book or another source.  When you graduate, you will often pull code from another source, but at this stage in your development, you need to write it!  I try to make the assignments different from what you can find in books or on the web, but sometimes that makes the assignments harder than I would like.  When I ask you to write code that has been written by thousands of others before you, you still need to write it so you appreciate it, so you learn the lessons contained therein.  You learn next to nothing by copying it from elsewhere. 

In English, if you are to write a paper, you are not allowed to find a good one on the web and turn it in.  In CS, it is a little different, because you are encouraged not to reinvent the wheel.  However, in this class, I want you to "invent the wheel.''  If you don't know how the wheel was build, you can't improve upon it.  Learning must be done in layers.  I can't teach you how to code exotic programs unless you have done the simpler things.  Writing the simpler things yourself - independently of the book - is necessary to form the correct foundation for what you need for later algorithms. 

In any course, you should never use someone else's product without clearly stating where it came from.  To use someone else's creation without giving them credit is cheating.  Here's the approach I would try.   Study the book.  When an assignment is given, try to do it without looking at anything.  If you can't, study the book again - but before you start coding, shut the book.  Then, you know that you have retained the most critical parts of the design. 

Preparation: Preparation is necessary for learning.  For this class, preparation includes attending class regularly (90% of the time), coming on time, remaining focused until class is dismissed, asking timely questions, trying problems at your seats when directed to do so, answering questions when called upon, completing homework questions, paying attention during lecture, and reading appropriate material before coming to class. 

Because you learn more if you are involved in class discussion, I often ask for class response to a question.  However, do not feel that you need to answer every question.  I would like to hear from everyone in the class not the same two or three people every time.  To facilitate hearing from everyone, the "three strikes rule" is implemented.  After you have verbalized an answer three times in a class period, you are not allowed to answer any more questions that period.  If your answer is so wonderful that you will die if it isn't expressed, tell your neighbor and let her/him share it.  Along the same line, make sure the questions you ask are appropriate for the entire class.  If you had a bizarre occurrence on your home computer, are wondering what you will miss when you travel to Alaska on Wednesday, or want to know how to use some advanced feature of the language, ask me after class.  I don't want to spend class time on questions that are of interest to only a few or intimidate others by answering questions they are not ready for. 

Cheating: Although you may collaborate on problem solving, each person must write, debug, and test his/her own work.  Some students feel that if they worked with the other person for a long period of time (as opposed to just copying another's work without any personal effort), they haven't cheated.  That is not true.  Note, you don't have to feel guilty for what you have done to have it be cheating. There are degrees of cheating.  Copying another person's code (with or without their knowledge) is cheating.  However, if another person helps you so much that the result isn't your work, then it is still cheating, regardless of how many hours you spent in the process.  Some think that because the course is demanding, it gives them license to cheat.  Nope!  Cheating is cheating.  There is no set of circumstances that justifies it. 

Submitting projects which include part or all of code/text that is obtained from sources such as a text book or a site on the Internet, without properly acknowledging the source(s) of the code/text in your submission is considered cheating.  In most cases, such "borrowing'' is not permitted, with or without proper acknowledgement.  In case of doubt, talk to me about your intention to include such code before using it. 

I do not recommend designing the code with others because it is difficult to pull yourself away from the group and do your own work.  For every problem you encounter, you want to know how others in your group solved that problem.  Copying code from the text or other sources (including tutors and consultants) is not allowed unless specifically indicated.  Do not allow someone else to write the code for you no matter how helpful it would be.  Cheating will be dealt with severely.  The penalty given is worse than not having done the assignment, written the program, or taken the exam (i.e., the least penalty possible is negative points).  When cheating occurs, a letter to that effect is placed in your file and a copy is sent to the dean's office.  Some excuse their cheating by saying "I was under so much pressure and just ran out of time.''  This is like saying, "I am honest until it is inconvenient.''  Cheating is not tolerated. 

Flagrant cheating involves turning in another's work as your own (even if that work was done by a tutor).  However, there are many other forms for dishonesty that are also considered cheating. Allowing others to copy from your work is considered cheating, and both of you will be penalized. Do not put your friends in an awkward position by asking them to help you cheat. If there are any questions, please refer to the departmental cheating policy.

Incompletes: According to university policy, incompletes are not to be given for poor performance. There will be no incompletes given except for conditions beyond the student's control. Such conditions have to have written documentation.  The term "conditions beyond the student's control" includes (1) incapacitating illnesses that prevent a student from attending  classes for a period of at least two weeks; (2) a death in the immediate family; (3) financial responsibilities requiring a student to alter course schedule to secure employment; (4) change in work schedule as required by an employer; or (5) other emergencies of this nature.  When an incomplete is given, it is anticipated that the remaining work will be finished within two or three weeks. If the course must be retaken to make up the work, an incomplete is not appropriate.  There are provisions in case of emergency to permit a student to withdraw (grade of W) from a course after the regular drop period when it is not feasible to give an I.

ADA Statement: If a student has a disability that will likely require some accommodation by the instructor, the student must contact the instructor and document the disability through the Disability Resource Center, preferably during the first week of the course.  Any requests for special considerations relating to attendance, pedagogy, taking of examinations, etc., must be discussed with and approved by the instructor.  In cooperation with the Disability Resource Center, course materials, can be provided in alternative formats - large print, audio, diskette or Braille.

Class Fees: Associated with this class is a fee of $25.  The monies from this fee are used to maintain lab facilities for the class, purchase software and licenses, and supervise the lab.  In some cases, students may have their own computing equipment, and thus feel that they do not need to use the lab.  However, the lab must be maintained regardless of  and individual's use of it, and thus the fee is charged to all registered for the class.  If you have questions or concerns about the fee, please see the department head.

Late Adds: The last day to add this class is September 20^th. Attending this class beyond that date without being officially registered will not be approved by the Dean's Office.  Students must be officially registered for this class.  No assignments or tests of any kind will be graded for students whose names do not appear on the class list.

Drop Date: The last day to drop classes is 

Last modified: October 05, 2005