Introduction

This course focuses on standard methods of packaging and storing data (data structures), and building data storage mechanisms that can be reused and re- vised (abstract data types). Emphasis will also be placed on the efficiency of associated algorithms; a problem may be solved by a variety of structures and algorithms, but which is the most efficient solution? The various implementa- tions will develop a familiarity with memory management, including static and dynamic allocation, and pointers.

Calendar

Textbooks

There are no required textbooks. However, we provide the following recom- mended references:

Richard F. Gilberg and Behrouz A. Forouzan Data Structures: a Pseu- docode Approach in C, 2ed. , Course Technology (Thompson), 2005.

K. N. King C Programming: a Modern Approach, 2ed. , W. W. Norton & Com- pany, 2008.

It may be surprising that we recommend textbooks using the C programming language for a course employing C++ for programming. As discussed in section 11, we are using the procedural fragment of C++, which very closely resembles C. Hence, students will be writing what are essentially well-formed C programs, employing only the superior maintenance features of C++.

Lectures

Please attend the section you are registered in, as classroom space is lim- ited and registered students have priority seating. If you miss your regularly- scheduled lecture, you can attempt to make up for the missed material by at- tending replacement lectures in the other section. Be aware that the sections will be kept in rough synchronization; but, there is no guarantee that the other section might not have already covered the material you missed.

Tutorials

Tutorials in a laboratory setting are mandatory and include new material not presented in class. Lectures emphasize the data organization concepts using pseudocode; tutorials focus on how to implement, in C++, the concepts studied in lecture. Material presented in tutorial is examinable.

Students will demonstrate their individual mastery of the programming skills shown in their assignments by completing a lab examination near the end of term. The lab examination will consist of writing a simple program during a tutorial session.

There are five tutorial sections, at differing times of the week:

Most tutorial sections are overbooked (38 students with seating for 33); hence, students with laptops are encouraged to bring them to the first few sessions. Students must attend the section they are registered in.

If you miss a tutorial section, you may try to attend another section during that week; but there is considerable risk you will not be able to find a seat.

Tutorials begin the week of January 10, and conclude with the lab examination during the week of April 4–8.

Dates and Topics

There will be twelve weeks of lecture, ten tutorial weeks, and one lab exami- nation. The approximate order of topics (timing and topics subject to change) are:

Assignments

There will be six assignments in this course, one approximately every two weeks. Assignments shall consist both of questions that require written answers and questions which require you to write computer programs. All computer pro- grams must be written in C++ and must compile using the GNU C++ com- piler (g++) under Linux: the standard will be the tuxworld.usask.ca cluster of machines.

Submission Instructions

Submission instructions will be included with each assignment description. Com- puter files,

• plain text for written answers, MS Word, OpenOffice, or Apple Pages will not be accepted.
• C++ source files for programming questions, including all .h files too.

Due Dates

Assignments will be due Mondays, at 10:00pm.

Evaluation

Examinations

Mid-term Examination

The mid-term examination is intended to provide practice for the final exam, and to provide feedback to students regarding their current performance. It will be held in common with both lecture sections, will be scheduled for 90 minutes over a 2 and one-half hour period; student can select their writing times to meet their schedule:

The mid-term examination is written, closed-book; only bring water, your student card, and writing instruments.

A student who cannot attend the mid-term test for religious reasons or due to a conflict with another class or examination must inform the instructor at least two weeks prior to the test date so that alternative arrangements can be made.

Students who miss the midterm due to illness or family circumstance will be required to contact their instructor by email on the day of the missed exam, and to complete a signed student affadavit, and will discuss the circumstances with their instructor. The instructor, in consultation with the student, will de- termine how the missed work will be compensated for; one potential alternative is transferring the weight of the midterm onto the final examination.

Lab Examination

The lab examination will be held during your last, regularly-scheduled tuto- rial session. You will be given a small-scale programming problem containing variations of the tasks required for assignments. You will have access to your textbooks, notes, and any of your personal course work; but no access to email or other external communication. A sample lab exam is available to assist in preparation.

A student who misses the lab examination due to illness must contact their instructor by email on the day of the missed test explaining the reason for their absence. The student must subsequently provide a signed student affadavit to the course instructor at which time the instructor and the student shall discuss how the missed exam may be made up.

A student who cannot attend the mid-term test for religious reasons must inform the instructor at least two weeks prior to the test date so that alternative arrangements can be made.

Final Examination

The final examination, common to both lecture sections, will be scheduled by central timetabling to occur during the usual final examination interval. It will be three hours long, written, closed-book. Again, bring only water, your student card, and writing instruments.

A student who misses the final examination for any reason, has a conflict with another final examination, or cannot attend the final examination must follow the appropriate procedures outlined in the University of Saskatchewan policy.

Special Accommodations

Some students, especially those with disabilities, may be entitled to special ac- commodations, primarily for assignment deadlines, and examination times and circumstances. In keeping with Disabled Student Services policy, all students claiming special accommodations

• must verify their study plans with the DSS office to ensure that assignment accommodations occur as an unusual situation, not as the norm;
• schedule, in the first two weeks of class, a face-to-face meeting to inform the instructors of their situation and deliver their DSS Letter to Professors;
• provide adequate and advance notice to their instructor of the need for special accommodations,
• understand that late assignment submissions will not be accepted if solu- tions have been posted.

Three Success Criteria

Please note that three important criteria are required to successfully complete this course:

• You must write and pass the final examination – this is College of Arts and Science policy,
• You must achieve a passing average (50% or greater) overall on the as- signments,
• You must complete the required coursework, including
  • the assignments,
  • the midterm examination,
  • the lab examination, and
  • the final examination.

Furthermore, the following University policies must be adhered to:

1. All students must be properly registered in order to attend lectures and receive credit for this course.
2. Failure to write the final examination will result in a failure of the course.
3. Failure to complete required course work will result in a failure of the course. For the purposes of this course, the course work includes all as- signments, the midterm examination, the lab examination, and the final examination. An official statement about coursework:
   • When a student has not completed the required course work, which includes any assignment or examination including the final exam- ination, by the time of submission of the final grades, they may be granted an extension to permit completion of an assignment, or granted a deferred examination in the case of absence from a final examination. Extensions for the completion of assignments must be approved by the Department Head, or Dean in non- departmentalized Colleges, and may exceed thirty days only in unusual circumstances. The student must apply to the instructor for such an extension and furnish satisfactory reasons for the deficiency. Deferred final exami- nations are granted as per College policy.
   • In the interim, the instructor will submit a computed percentile grade for the class which factors in the incomplete coursework as a zero, along with a grade comment of INF (Incomplete Failure) if a failing grade. In the case where the instructor has indicated in the course outline that failure to complete the required coursework will result in failure in the course, and the student has a computed passing percentile grade, a final grade of 49% will be submitted along with a grade comment of INF (Incomplete Failure).
   • If an extension is granted and the required assignment is submitted within the allotted time, or if a deferred examination is granted and written in the case of absence from the final examination, the in- structor will submit a revised computed final percentage grade. The grade change will replace the previous grade and any grade comment of INF (Incomplete Failure) will be removed.
4. All students must accept and adhere to the Computer Science departmen- tal academic honesty policy.

Grading Scheme

Intangibles may count in the determination of your grade. Regular attendance and productive classroom participation may slightly ameliorate some weaknesses elsewhere; the converse is also true.

Late Assignment Policy

Late submissions will not be accepted.

Extensions

Extensions on assignments will be granted only by the course instructor. As a general rule, individual requests for extensions on medical or compassionate grounds will only be considered if made prior to the due date of the assign- ment. All extension requests will require suitable documentation. Students with disabilities should review the discussion above.

Grading Appeals

Assignments will typically be marked by the TA in your tutorial section, al- though some questions may graded by other TAs. Hence, if you feel that an assignment grade is inaccurate, please consult your TA first. They are instructed to review your entire assignment, not just any portion you select. Therefore, if you appeal your grade, the entire piece of work will be re-graded. If you are still unsatisfied, please appeal to your instructor, who will follow the same full review process.

If you are concerned about consistency of grading, i.e. your mark differs from your friend’s mark, and wish to appeal on that basis, then you and your friend must submit both assignments for re-grading: none, one, or both assignments might have grades altered up or down. If both assignments to be reviewed are from a single tutorial section, begin the review by approaching that section’s TA. If the assignments are from different tutorial sections, or if you disagree with the results of the TA’s review, please appeal to one of the instructors.

Grading Standards

To understand the grading standards, students are directed to the University Grading System. Part of this reproduced below, for completeness.

>90 Exceptional A superior performance with consistent strong evidence of

• a comprehensive, incisive grasp of the subject matter;
• an ability to make insightful critical evaluation of the material given;
• an exceptional capacity for original, creative and/or logical thinking;
• an excellent ability to organize, to analyze, to synthesize, to integrate ideas, and to express thoughts fluently.

80–89 Excellent An excellent performance with strong evidence of

• a comprehensive grasp of the subject matter;
• an ability to make sound critical evaluation of the material given;
• a very good capacity for original, creative and/or logical thinking;
• an excellent ability to organize, to analyze, to synthesize, to integrate ideas, and to express thoughts fluently.

70–79 Good A good performance with evidence of

• a substantial knowledge of the subject matter;
• a good understanding of the relevant issues and a good familiarity with the relevant literature and techniques;
• some capacity for original, creative and/or logical thinking;
• a good ability to organize, to analyze and to examine the subject material in a critical and constructive manner.

60–69 Satisfactory A generally satisfactory and intellectually adequate per- formance with evidence of

• an acceptable basic grasp of the subject material;
• a fair understanding of the relevant issues;
• a general familiarity with the relevant literature and techniques;
• an ability to develop solutions to moderately difficult problems re- lated to the subject material;
• a moderate ability to examine the material in a critical and analytical manner.

50–59 Minimal Pass A barely acceptable performance with evidence of

• a familiarity with the subject material;
• some evidence that analytical skills have been developed; some un- derstanding of relevant issues;
• some familiarity with the relevant literature and techniques;
• attempts to solve moderately difficult problems related to the subject material and to examine the material in a critical and analytical manner which are only partially successful.

<50 Failure An unacceptable performance.

Communication

Course Website

The course website is on the Department Moodle site, under CMPT 115.

Course announcements regarding assignments and examinations, as well as lists of frequently-asked questions and other information will be communicated to the class members via this website. Each student is responsible for reading this website regularly.

Office Hours

Instructor office hours are

If these times do not suit, please contact the instructor to schedule a specific appointment. Teaching assistants in the Spinks help centre may offer tutorial assistance, according to that centre’s schedule.

Student Discussion

The department provides facilities for students to discuss coursework, via the Moodle course website. Note that the instructors and TAs will often be available on this system. Also, note that this system is archived and reviewed (even for anonymous use) to ensure that academic misconduct does not occur. As a general rule, pseudo-code and abstract discussions are fair, anytime actual code or written solutions are mentioned, the line has been crossed into misconduct. Note that permitting others to use your work constituted academic misconduct also; so, keep your code safe.

Students are warned that the department employs the MOSS system to detect code copying. Effectively, the work required to defeat MOSS exceeds the work involved in the assigments by an order of magnitude (or more).

Academic Honesty

Note that the University of Saskatchewan has adopted a new Academic Mis- conduct policy. Students are obligated to inform themselves of this policy; as an example, this paragraph suffices to ensure that a student reasonably ought to have known better.

Students are expected to be academically honest in all of their scholarly work, including course assignments and examinations. Academic honesty is defined and described in the Department of Computer Science Statement on Academic Honesty and the University of Saskatchewan Academic Honesty Website.

Declaration of Academic Honesty

All students will be asked to make a Declaration of Academic Honesty.

Students using the Moodle system to submit an assignment for the first time will be prompted with a declaration of academic honesty. After reading the declaration, you will be presented with three options: “Agree”, “Disagree”, or “Decide Later”. If you choose “Decide Later” you will be prompted again the next time you log into the Moodle system. Agreement or disagreement applies to all CMPT courses in which you are registered.

For classes that do not use the Moodle system, each student may be re- quested to submit an Online Declaration of Academic Honesty.

A Note on our Implementation Language

All implementation will be done in the procedural fragment of C++. In most respects, this is identical to ansi C, but with superior programmability:

• constant values – rather than #define – yielding equivalent performance without sacrificing debugging capabilities,
• a boolean type – rather than encoding false and true as zero and non- zero respectively – yielding fewer logic and syntax errors,
• file-scoped static variables – rather than global scope – yielding fewer unanticipated name clashes,
• inline functions – rather than #define macros – yielding equivalent per- formance without unexpected redundant side-effects,
• reference & types – rather than pointers (where possible) – yielding the same space and execution efficiency while eliminating many bugs related to needless reference (&) and dereference (*) operators
• nested scoping of variables – rather than omnibus declarations at the top of each function – resulting in better variable naming, and
• well-typed, higher-level memory management operations, new and delete – rather than untyped, byte-oriented operations malloc, calloc, realloc, and free – yielding better compile-time error checking.
• full-line comments, introduced by // and extending to the end of the line – rather than C-style comments delimited by /* and */ – yielding easier debugging by avoiding unexpected nesting of comments.

Use of object-oriented features of C++, including cin, <<, cout, >>, will be be penalized with a 25% reduction of the total mark, unless explicitly stated to be allowed.

Staff

Instructor (MWF): Ian McQuillan
email mcquillan@cs.usask.ca
web http://www.cs.usask.ca/faculty/mcquillan
office Spinks 423

Instructor (TR): Chris Dutchyn
email mailto:dutchyn@cs.usask.ca
web http://www.cs.usask.ca/faculty/cjd032
office Thorvaldson 286.10

TA (Mon.): Teresa Hume
email mailto:tch562@mail.usask.ca

TA (Tues.): Steven Indzeoski
email mailto:sji969@mail.usask.ca

TA (Wed.): Muhammad Asaduzzaman
email mailto:mua237@mail.usask.ca

TA (Thurs.): Scott Johnston
email mailto:gsj601@mail.usask.ca

TA (Fri.): Marli Rauert
email mailto:mrr628@mail.usask.ca

Additional Marking Minhaz Zibran
email mailto:mfz946@mail.usask.ca