CS 163 Section 001: Data Structures

Winter 2005



Prerequisite:  CS162 or consent of instructor


Instructor:                  Sergio Antoy



Office hours:              Tuesday/Thursday 10:30 or By appointment


Text:                           Data Abstraction and Problem Solving with C++, Carrano,

                                    3rd edition

Lecture Notes:           Lecture notes and Powerpoint slides are available for    purchase at Clean Copy


System:                       CS or Odin systems, using g++



All handouts, course outline, and programming assignments can be retrieved from the web at:












If you have a disability and are in need of academic



accommodations, please notify the instructor immediately to arrange needed support





Email is the best way to get questions answered. This term, there is a special email address for you to use for technical questions:



If you have questions, the best approach is to either make use of the office hours listed on this syllabus, send electronic mail to cs16x_help, see the teaching assistant assigned to this class, or make an appointment with the Instructor.


Electronic mail works the best if you have a question that you encounter as you work on the programming assignments. Please be advised that questions should be clearly formulated and it should be clear from the question that you have attempted to solve the problem on your own. Do not, unless explicitly asked by the Instructor, simply email your program and expect a response! Instead, talk about what problems you are encountering and what you have done to make progress.


If you have administrative questions and need to talk directly with the Instructor, send mail to: 


Since I received 100’s of email messages, make sure to put “163 Question” in the subject heading.



Course Description:  

Data abstraction with formal specification. Elementary algorithm analysis. Basic concepts of data and its representation inside a computer. Linear, linked, and orthogonal lists; tree structures. Data structures are implemented as data abstractions. Sorting and searching strategies. Data management.



To acquaint students with structures used in C++ for the storage and manipulation of data.  The concept of data abstraction and the problem of building implementations of abstract data types are emphasized.  Both static and dynamic implementations of major structures are presented and the advantages and disadvantages of each are discussed.  Structures include lists of several types, stacks, queues, trees, binary trees, B-trees and graphs.  Recursion and key transformation (hashing) are examined. Students are encouraged to examine algorithms and to make judgments about the practical and social application of these algorithm concepts to large scale programming projects; the course stresses the importance of quantitative methods in designing software.


Material to be Covered:

• Material to be covered will include data abstraction with formal specification,  elementary algorithm analysis, basic concepts of data and its representation inside a computer, linear linked and orthogonal lists, tree structures, sorting and searching strategies, and data management.



• Course requirements consist of five programming problems and written homework problems. The programming problems provide experience building correct implementations of abstract data types.


• The programs and homework assignments comprise 40% of your grade. Each program is worth 100 points. Each homework is worth 25 points. Therefore, the 4 homeworks that will be assigned are worth the same as a single program.


• 20% of the project grade is based on the program style, comments, and documentation provided with the program, per the STYLE SHEET.


• 20% of the project grade is based on the design write-up provided with the program. The design write-up must be typed and a minimum of 1 page.


• Each student is expected to submit only original work. Software and passwords must be kept confidential.  Any person who violates these will receive a grade of F for the course and a letter will be sent to the head of the CS Department.  Note that the Instructor may ask any student to explain his/her program or homework verbally. Identical programs will be treated as copying even with cosmetic changes.


Late Assignments:

• Each assignment will be due in class on the due date; they will not be accepted late for full credit. Late assignments will be accepted the following class-day with 10 late points deducted. Assignments beyond this will not be accepted unless previously arranged with the instructor. There will be situations where the instructor will change a due date.


• Late assignments will not be accepted after the last day of class – no exceptions! Programs may not be turned in during finals week or after.


• Partial credit will be given for incomplete work. However, 25 points will be automatically deducted for programs that cannot successfully compile and link.


• Notice, assignments are due in not turn them in to the CS department office.


Computing Environment:

Programming assignments must be done on a unix system. You have a choice of using either the CS computers or the ODIN system. No UNIX instruction will be given in class. PSU Computer Services schedules UNIX orientation classes. Students may do their initial development at home on a PC, however, all programming assignments must run on one of PSU’s unix systems and will be graded based on their execution on either the CS machines or ODIN. The excuse but it runs at home on my PC will not be accepted. In fact, it may take some extra time to port an assignment that runs on a PC to ODIN and is not recommended. As such students should plan to spend extra time on those assignments. In addition, make sure that your programs are protected from outside access; unprotected files will be treated as ‘cheating’.


Therefore, follow these instructions to setup your account:


As you login, the first time this term, please type the following to setup your CS163 directory:


      Enter 7 to exit the menu; now you are at the unix prompt


       mkdir cs163

       chmod og-rxw cs163


When you are ready to start working on your program, please work within the cs163 sub-directory. After you login in the future, type the following to get into that directory;

       cd cs163




• See the instructor in advance if you have a midterm conflict; the final is given only at the scheduled time. No take home exams are allowed. All exams are closed book, closed notes.


            Midterm (25%)

            Comprehensive Final (35%)




• 40% of the grade is based on the project and homework scores; 60% of the grade is based on the examinations.


• Minimum Grade Requirements: For  C or better in this class, you must have a grade of 65% or better on the programming assignments and a grade of 65% or better on the examinations.


In additional, grades must be received (above 40%) on each individual assignment, otherwise a failure will result – this means you can’t skip turning in a program, group project, or individual paper.



• Grading will be done near 90% (A-), 80% (B-), and 65% (C). However, exact break points for grades will depend upon the overall class results. For P/NP grade option, a "pass" grade requires an overall class grade of at least a C.



• Students who attend class, turn in any homework, or take any of the examinations will not be given an X in the class for any reason.


• INCOMPLETES will be given only when a minimal amount of work remains to be completed, only for a valid reason and only for a fixed time period. Do not expect an incomplete in this class.


• DROPPING: Students may drop the class at any time. Petitions will be signed without question. However, this is a very time consuming class...much more so than CS162! If you do not think you will have time, please drop immediately.


 • ATTENDANCE is not mandatory. However, you are responsible for anything that transpires during class. Therefore, make sure to get notes from someone (other than the Instructor) when you are unable to attend. However, BORDERLINE GRADE DECISIONS may be influenced by regular class attendance and participation in class discussions. This really can make a difference!