Department of Information Science and Telecommunications

INFSCI 0015 "Data Structures and Programming Techniques

(Fall 2001, CRN 20895)

Course Objectives

The primary objective of the course is to give BSIS students basic programming knowledge and skills and introduce them to the area of data storage, organization, and manipulation. At the end of this course you will be able to write small meaningful C programs that includes major control structures (such as loop, selection), programming patterns (such as maximum or sequential array processing), data types and data aggregates. You should also be able to distiguish major data structures (such as stacks or lists), consider different implementations of the same data structure from the points of algorithmic and storage efficiency, and pick up a most suitable data structure and implementation for a given task. On the way to that goal we will have to learn a reasonable subset of C language, explore many working examples and write multiple C programs. Learning C language is not the goal of this course. For us C is mainly a tool that will let us to explore data structures in detail. We will only learn as much of C as we will need to work with data structures. Still the amount of material to be learned is rather large and the students who have no previous experience with programming should expect to devote 7-9 hours outside of the class to this course. From another side, those already familiar with C may find the first path of the course too simple.

Assessment and Grading

Components of the Final Grade

Course assessment includes quizzes that will be offered through the course, homework programming assignments, and two exams - midterm and final. The final exam is not cumulative. You final grade has three components: work over the duration of the course, midterm exam grade, and final exam grade. Each of these components will be evaluated separately using 100pt extended Letter Grade scale (0-20 is F range, 20-40 is D range, 40-60 is C range, 60-80 is B range and 80-100 is A range). After that the final grade will be calculated as 40% course + 30% midterm + 30% final.

Grade for the work over the duration of the course is a sum of your assignment grades, quiz grades (we will have a quiz every week, but two lowest quiz grades will be excluded) and activity points. Your progress will be measured as a percentage of the max possible points: (assessment_points + quiz_points + activity_points)/(max_assessment_points + max_quiz_points) * 100%. Using this formula you can always check where you are standing. Score < 50% corresponds to F, 50-62.5 is D range, 62.5-75 is C range, 75-87.5 is B range, and 87.5-100 is A range. The formula to convert this score to 100pt extended Letter Grade scale is (X-37.5)/12.5*20.

Activity Points

You can earn bonus "activity points" for several things such as asking a good question in a discussion forum, providing a helpful answer in a discussion forum, helping during the lecture, attending additional "catch-up" sessions, finding errors in slides and examples. Activity points will be added to your assessment/quiz results.

Submitting and Naming

All assignments has to be submitted in paper form on the due date before or after the lecture has to be in instructor's hands by 4pm on the due date. Submit a printed copy of the program code and a sample output (starting from assignment #3). In addition, the program code of the assignment in ascii form has to be submitted electronically using CourseWeb's dropbox at any time by or on the due date (your submissions are time stamped). Naming conditions for electronic submissions are strict. When submitting via the dropbox, the link to your file should be named programX_Y where X is an assignment number and Y is a problem number within the assignment. You will lose 1/2 point for every misnamed link starting from assignment 3. All submitted work should bear the number of the assignment/quiz and the author's name in printed form inside the header comment. You will lose 1/2 point for every solution that lacks the header comment with this data. By submitting work under your name, you are indicating that you have completed the assignment. This means that you should be able to completely explain every line of code in your program. Failure to be able to account for your coding decisions will be reflected in your grade.

Course Policies

Academic Integrity

You are expected to be fully aware of your responsibility to maintain a high quality of integrity in all of your work. All work must be your own, unless collaboration is specifically and explicitly permitted. Any unauthorized collaboration or copying will at minimum result in no credit for the affected assignment and may be subject to further action under the University Guidelines for Academic Integrity. You are expected to have read and understood these Guidelines. A document discussing these guidelines was included in your orientation materials.

Attendance

Class attendance, while not mandatory, is required if you want to succeed in this course. While most of the material covered by the lectures could be found in course books, for most of the lectures the order of presentation does not match any book exactly. Some material is not sufficiently covered by the book. Finally, all lectures include animated demonstration of examples. If you have missed the lecture, make sure you have a copy of the slides. Spare copies can be picked up from a folder near the instructor's office or printed from the Web.

Late Submissions and Resubmissions

The due date for assignments is strict. For extreme circumstances you have 5 late days to use at your discretion (i.e. you may use them on a single assignment, or distribute them over several assignments). Outside of this limit late assignment will not be considered. You can also improve your submission or fix errors in your submission until due date. Simply upload the new version adding "_v2", "_v3", etc to the name of the link to the program (i.e., program3_1_v2) The rules for submitting an updated version are the same as for late submissions - by or on the due date or use your late days limit. No assignment can be submitted or resubmitted after it was analyzed during the lecture.

Make-ups

If you miss a quiz or and assignment, you will receive a zero. There will be no make-up quizzes, but the instructor will drop the two lowest scores on the quizzes. There are also no make-up assignments since most of the assignments will be analysed in the class on or shortly after the due date. Missed exams can be made up in cases of extreme circumstances.

Office Hours

Office hours are an opportunity for you to clarify details you may have missed in class or to resolve a serious problem you have encountered when working on an assignment. They are not a place to get a "second run" of the lecture if you missed the class or obtain answers on the assignment. If you come to office hours with a problem on the assignment, make sure that you have access to an electronic version of your code.

Special Considerations

If you have a disability for which you are or may be requesting an accommodation, you are encouraged to contact both your instructor and Office of Disability Resources and Services, 216 William Pitt Union, (412) 648-7890 / (412) 383-7355 (TTY) as early as possible in the term. DRS will verify your disability and determine reasonable accommodations for this course.

Course Overview

Introduction
First program, compilation, syntax errors
Variables, data types, and arithmetic expressions
Comparisons, simple conditions, while loop
More Data Types, conversions, constants, for loop
Conditional statement, complex conditions
Embedded while and if
Arrays. Array processing with for
Array as a data aggregate, search in an array.
Array sorting. Analysis of sorting algorithms.
Multi-dimensional arrays
Structures, arrays of structures
Functions, parameter passing
Pointers
Abstract Data Types. Stacks. Stack Implementation with arrays
Queue as an abstract data type. Queue implementation with arrays.
List as an abstract data type
Linked Lists implementation with pointers
Stack implementation with linked lists
Hashtables
Binary trees and Search Trees

Course Schedule

Thursday August 30	Lectures 0 & 1
Thursday September 6	Lectures 2 & 3
Thursday September 13	Lectures 4 & 5
Thursday September 20	Lectures 6 & 7
Thursday September 27	No lectures. Special classroom session
Thursday October 4	Lectures 8 & 9
Thursday October 11	Lectures 10 & 11
Thursday October 18	Lectures 12 & 13
Thursday October 25	Midterm exam
Thursday November 1	Lectures 14 & 15
Thursday November 8	Lectures 16 & 17
Thursday November 15	Lectures 18 & 20
Thursday November 22	No class. Thanksgiving Recess
Thursday November 29	Lectures 21 & 24
Thursday December 6	Lectures 23 & 25
Thursday December 13	Final Exam