INFSCI 0015 - Data Structures and Programming Techniques

The final exam will be on April 27, from 8:00 AM to 10:00 AM.

Syllabus

Course Description:

Introduces a scientific programming language (e.g., Pascal). Involves the definition, description, and implementation of several information structures such as linked lists, stacks, and queues. (Prerequesite: INFSCI 0010/0011)

Class:

Tuesdays, 9:30 AM - 10:50 AM, IS 404
Thursdays, 9:30 AM - 10:50 AM, IS 404

Instructor:

Stefan Brass (sbrass@sis.pitt.edu)

Address:

University of Pittsburgh
Room 726 SIS Bldg.
135 N. Bellefield Ave.
Pittsburgh, PA 15260

Phone:

(412) 624-9404

Office Hours:

By Appointment.

GSA:

Restiani Andriati (restiani@lis.pitt.edu)
Office Hours: Tuesday, 4-6pm, Room 801, SIS Building.

Textbooks:

Robert L. Kruse: Programming with Data Structures / Pascal Version.
Prentice Hall, 1989, ISBN 0-13-729238-4, ca. $63.00.
[Table of Contents]    [Amason.com Page]
This book is sold out. There are remaining copies in the book center, but the supply is not sufficient. Therefore, the following textbook can be used as an alternative:

Paul Helman, Robert Veroff, Frank M. Carrano:
Intermediate Problem Solving and Data Structures, Walls and Mirrors, 2nd Edition.
Benjamin/Cummings, 1991, ISBN 0-8053-0321-9, ca. 700 pages, ca. $46.95.
[Table of Contens]    [Amazon.com Page]
Note that although I will not follow these textbooks very closely, it is essential for your success in this course that you read one of these books.

If you don't have previous programming experience, I recommend that you buy in addition a Pascal textbook, for instance:
Elliot B. Koffman:
Pascal, 5th Edition.
Addison-Wesley, 1995, ISBN 0-201-52674-3, ca. $44.95.
[Amazon.com Page]
Or alternatively, "Turbo Pascal, 5th Edition Update", by the same author.
[Amazon.com Page]   [Addison Wesley Page]   [Table of Contents]

Preconditions:

This course is for both, students with previous programming experience, and students without knowledge of a programming language. I will introduce Pascal while teaching data structures. In fact, I have been told that this course is also intended as a Pascal programming course. However, the learning curve for participants without previous programming experiences will be quite steep at the beginning.

In addition, you will need some knowledge of basic mathematical notions (sets, functions, etc.).

Goals of this Course:

• Computer Programming
• The programming language Pascal
• Data structures, e.g. lists, trees, hash tables, graphs.
• Algorithms, e.g. for sorting and searching
• Problem specification, Algorithm correctness
• Complexity analysis
• Software engineering (a bit), Programming style

Grading:

40% Homeworks (every week, must be solved individually)
30% Midterm Exam (March 4, "open book")
30% Final Exam (April 27, 8:00, "open book")

Late Submission Policy:

If you have some acceptable excuse, you may submit homework solutions up to one week later. Please contact me as early as possible. I will most probably accept your excuse the first and second time, but then it might get more and more difficult to convince me.

Labs:

Computing and Information Services (CIS) at the University of Pittsburgh

• Lab Locations
• How to get an Account
• Getting Started with Windows 95 / NT 4.0

Turbo Pascal for Windows 1.5

Course Schedule

Tuesday/Thursday, 9:30 AM - 10:50 AM, IS 404

1. January 7: Introduction
   Organisation of this Course, About Computers and Computer Programming, Computer Languages.
2. January 12: Basics of Pascal, Syntax Diagrams
   Steps for Executing a Pascal Program, Lexical Syntax, Syntax Graphs, Built-in Datatypes.
3. January 14: More Pascal
   Built-in Datatypes, Expressions, Statements.
4. January 19: Statements
   Statements.
5. January 21: Procedures, Subrange Types
   Procedures and Functions, Subrange Types, Arrays.
6. January 26: Syntax Diagrams Repetition
   Syntax Diagrams, Arrays.
7. January 28: Two-Dimensional Arrays, Input/Output
   Syntax Diagrams, Two-Dimensional Arrays, read and line ends, Programming Repetition.
8. February 2: Pascal Repetition I
   Pascal as a Pocket Calculator, write/writeln, Datatypes, Variables, Expressions, read/readln.
9. February 4: Pascal Repetition I
   Input, Programming Examples, If Statement, Program Layout.
10. February 9: Pascal Repetition II
    For Statement, While Statement, Programming Examples.
11. February 11: Pascal Repetition III
    While Statement, Advice for Program Development
12. February 16: Pascal Repetition III
    Arrays
13. February 18: Pascal Repetition III
    Arrays
14. February 23: Pascal Repetition IV
    Procedures, Local variables, Block Structure.
15. February 25: Pascal Repetition IV
    Procedures, Call by Value Parameters, Call by Reference Parameters.
16. March 2: Pascal Repetition V
    Typical Errors in Pascal
17. March 4: Midterm Exam
    Exercises can be, e.g., of the following types:
    • Write a Pascal Program for a given application.
    • Given a program, what does it output?
    • Find errors in a given program
    • Find unnecessary statements in a given program
    • Name some identifiers, expressions, statements in a program
    • Draw a syntax diagram for a given language.
    • Draw the operator tree for a given expression.
    • ...
18. March 16: Discussion of Midterm Exam
    Programming Errors in the Exam.
19. March 18: Discussion of Midterm Exam
    Repetition.
20. March 23: Pascal Repetition VI
    Type Declarations, Subrange Types.
21. March 25: Pascal Repetition VI
    Enumerated Types, Record Types.
22. March 30: Stacks
    Data Type Functions, LIFO Principle, Connection to Procedure Calls, Other Applications.
23. April 1: Stacks
    Interface vs. Implementation, Information Hiding, Array Implementation, Reverse Polish Calculator, Sketch of Translation of Expressions into Reverse Polish Notation.
24. April 6: Queues
    Data Type Functions, FIFO Principle, Application: Line Breaking, Different Array Implementations.
25. April 8: Pointers, Dynamic Memory
    Pointer types, new, dispose, possible errors.
26. April 13: Linked Lists
    Linked Lists, Linked List Implementation of Stacks.
27. April 15: Linked Lists
    Linked List Implementation of Queues, Computing the Length of a Linked List, Dictionaries.
28. April 20: Dictionaries, Recursion
    Linked List Implementation of a Dictionary, Recursion.
29. April 22: Binary Search Trees
    Binary Trees, Binary Search Trees, Recursive Insert/Find Functions, Repetition for Final Exam.
30. April 27: Final Exam, 8:00am to 10:00am (IS 404)
    

    Possible exercises are, e.g. (this list will be expanded):

    • A procedure for some task related to arrays and maybe sorting. Try to make sure that you would be able to write now the program for the second exercise in the midterm exam, which was somehow similar. Maybe it would also be a good preparation to write a procedure which checks whether the elements in a given array are in sorted sequence.
    • A procedure for some task related to linked lists. It might be a good preparation to write a procedure for computing the length of a stack in the list representation.
    • Even if there should be two procedures, the total number of lines of Pascal code you have to write will not be above 20.
    • Drawing stacks or queues or other data structures after some operations.
    • Given a small program part and a linked list data structure, how does the data structure look like after the statements in the program are carried out?

Course Materials

Homework Assignments:

1. Homework 1   (First Use of Turbo Pascal, WWW)   Due: January 14
   
2. Homework 2   (Expression Structure, Syntax Graphs, Program: Change in Coins)   Due: January 21   [HTML]
3. Homework 3   (Pascal Errors, Program: Substring Test)   Due: February 18   [HTML]
   
4. Homework 4   (Pascal Errors, Program: Symmetric Matrix, Block Structure)   Due: March 22   [HTML]
   
5. Homework 5   (Program: Word Count)   Due: February 11   [HTML]
6. Homework 6   (Program: Counting Sold Items)   Due: February 18   [HTML]
7. Homework 7   (Program: Word Guessing Game)   Due: February 25   [HTML]
8. Homework 8   (Program: Data Type "time")   Due: April 1   [HTML]
   There is a problem with this homework due to a restriction of Turbo Pascal. Please read this note or download the improved homework sheet.
9. Homework 9   (Program: Application of Stacks)   Due: April 13   [HTML]

Handouts:

• Chapter 2: Basic Pascal (Syntax Diagrams) [January 12]
• Chapter 3: More Pascal (Expressions, Statements) [January 14]
• Chapter 4: Procedures and Functions in Pascal [January 19]
• Chapter 5: Subrange, Enumerated, and Array Types [January 21]
• Chapter 6: Declaration and Type Requirements [January 26]
• Chapter 7: Pascal Repetition, Part 1 [February 2]
• Chapter 8: Pascal Repetition, Part 2 [February 4]
• Chapter 9: Pascal Repetition, Part 3 [February 11/16]
• Chapter 10: Pascal Repetition, Part 4 [February 18]
• Chapter 11: Pascal Repetition, Part 5 [March 2/16]
• Chapter 12: Pascal Repetition, Part 6 [March 18/23/25]
• Chapter 13: Stacks [March 30, April 1]
• Chapter 14: Queues [April 6]
• Chapter 15: Pointers and Linked Lists [April 8/13]
• Chapter 16: Searching, Trees and Recursion [April 15/20/22]

ghostscript can be used for printing Postscript files.

Program Examples

January 12 (Chapter 2: Basic Pascal):

• First Pascal Program: Temperature Conversion   [Standard Pascal]   [Example Run]

January 14 (Chapter 3: Pascal Statements):

• Example for If Statement   [Standard Pascal]   [Example Run]
• For Statement: Temperature Conversion Table   [Standard Pascal]   [Example Run]
• While Statement: Temperature Conversion Table   [Standard Pascal]   [Example Run]
• Repeat Statement: Multiple Temperature Conversions   [Standard Pascal]   [Example Run]
• Case Statement: Menu of Miscellaneous Conversions   [Standard Pascal]   [Example Run]

January 19 (Chapter 4: Functions and Procedures):

• Simple Function Definition   [Standard Pascal]   [Example Run]
• Function Definition with Conditional Statement (max)   [Standard Pascal]   [Example Run]
• Procedure Definition (Temperature Conversion Table)   [Standard Pascal]   [Example Run]
• Procedure Definition with Var Parameter   [Standard Pascal]   [Example Run]
• Block Structure   [Standard Pascal]   [Example Run]
• Constant Definition (Inch to Centimeter)   [Standard Pascal]   [Example Run]

January 21 (Chapter 5: Subrange, Enumerated, and Array Types)

• Day of the Year (Subrange Type)   [Standard Pascal]   [Example Run]
• Palindrome Test (Array)   [Standard Pascal]   [Example Run]

January 26 (Chapter 6: Declaration and Type Requirements)

• Inch to cm (Declaration/Use of Identifiers)   [Standard Pascal]   [Example Run]
• error1 (Local variables)   [Standard Pascal]   [Error Message]
• error2 (Double Declaration)   [Standard Pascal]   [Error Message]
• error3 (Incompatible Types)   [Standard Pascal]   [Error Message]
• error4 (Incompatible Types)   [Standard Pascal]   [Error Message]
• error5 (var parameter)   [Standard Pascal]   [Error Message]

February 2 (Chapter 7: Pascal Repetition, Part 1)

• First Program (Pascal as Pocket Calculator)   [Standard Pascal]   [Example Run]
• Second Program (Using a Variable)   [Standard Pascal]   [Example Run]
• Exercise 1: What does this program output?   [Standard Pascal]   [Example Run]
• First use of read   [Standard Pascal]   [Example Run]
• First use of if statement   [Standard Pascal]   [Example Run]

Information Sources in the Web

In Preparation.

Pascal

• Pascal Programming Course (by Brian Brown and Peter Henry)
• Turbo Pascal Tutorial (Joel Graves and Casey Billett, Grenville Christian College)
• Free Pascal Compiler
• GNU Pascal
• Pascal Page of Borland/INPRISE
• ISO Standards for Pascal (FTP: ISO-7185: Standard Pascal, ISO-10206 Extended Pascal)
• Niklaus Wirth
• Kathleen Jensen / Niklaus Wirth: Pascal - User Manual and Report

Other Books about Data Structures:

In Preparation.

Ellis Horowitz, Sartaj K. Sahni:
Fundamentals of Data Structures in Pascal, Fourth Edition.
Computer Science Press, 609 pages, ISBN 0716782634, ca. $64.00.
[Amazon.com Page]

Mark Allen Weiss:
Data Structures and Algorithm Analysis, 2nd Edition.
Addison Wesley, 1995, 500 pages, ISBN 0-8053-9057-X, ca. $53.75.
[Table of Contents]    [Amazon.com Page]    [Addison Wesley Page]

Other Data Structure Courses in the Web

• ...
• Dan Ventura, Brigham Young University
• ...

Stefan Brass (sbrass@sis.pitt.edu), April 21, 1999

Original URL: http://www2.sis.pitt.edu/~sbrass/ds/   [HTML 3.2 Checked]