Pitt Logo SIS Logo

Department of Information Science and Telecommunications

 

INFSCI 0015 - Data Structures and Programming Techniques

(Fall 2000, CRN 20813)


[ Formal Data | Course Tools | Syllabus & Schedule | Course Books | Course Materials | CourseInfo | Links ]


INFSCI 0015 Course Materials

Lecture Objectives Readings (K&R2) Handouts Examples
Lecture 0
Introduction
Introduction to the course. First program. Compilation and errors. Introduction
Chapter 1, Section 1.1
Slides Hello World
Lecture 1
Data Types
Introduction to data types. Linear programs, printing data, and simple expressions. Chapter 1, Section 1.1 Slides Example1
Example2
Example3
Example4
Lecture 2
Variables
Variables, assignment, type conversion, input. After this lecture you should be able to write a program that reads some numbers, does simple calculations, and prints a result. Chapter 1, Sections 1.2 (skip while), 1.4
Chapter 2, Sections 2.1-2.5, 2.7, 2.8
Slides Example1
Example2
Example3
Example4
Lecture 3
while Loop
Relational operators, statement and block, while loop. Simple problems with counter-controlled while loops. Chapter1, Section 1.2, 1.4
Chapter2, Section 2.12
Chapter3, Section 3.1
Slides Example1
Example2
Lecture 4
More Loops
while loop vs. until loop Problems with counter-controlled and input-controlled loops. Chapter 1, Sections 1.2 and 1.4
Chapter 2, Section 2.10
Chapter 3, Sections 3.5, 3.6
Slides Example1
Example2
Example3
Example4
Lecture 5
File Processing
Character data type, character input and output, streams and redurection. File copying and encoding. If-else and if statements. Line, word, and symbol counting. Chapter1, Section 1.5
Chapter2, Section 2.2 and 2.3
Chapter3, Section 3.2 and 3.3
Slides Example1
Example2
Example3
Example4
Example5
Lecture 6
Arrays
Arrays. Array input and output. For loop. Array processing with for. Chapter1, Section 1.6
Chapter3, Section 3.5
Slides Example1
Example2
Example3
Lecture 7
Nested Ifs and Loops
Else-if and complex conditions. Nested ifs and loops. Chapter1, Section 1.5.6, 1.6
Chapter2, Section 2.6
Chapter3, Section 3.3
Slides Example1
Example2
Example3
Example4
Example5
Lecture 8
Array Processing with Loops
Arrays: sum, max, min algorihms. Functions. Array processing with functions. Chapter1, Section 1.7, 1.8
Slides Example1
Example2
Example3
Example4
Example5
Lecture 9
Simple Searching and Sorting
Sequential search in non-ordered and ordered list. Max sorting. Binary search. K&R2:
Chapter1, Section 1.8
Chapter 3, Section 3.3
Gilberg:
Chapter1, Section 1-4
Chapter 2, Section 2-1 and 2-2
Slides Example1
Example2
Example3
Example4
Example5
Example GF2-01
Example GF2-02
Lecture 10
Character Arrays
Character arrays, strings, processing, initializing, and printing strings. Reading and processing standard input line by line. Chapter 1, Section 1.9
Chapter 2, Sections 3,4,7, and 8
Chapter 3, Section 5
Slides Example1
Example2
Example3
Lecture 11
Nested Loops
Nested loops, bar charts, string search Chapter 3, Section 3.5, 3.6
Chapter 4, Section 4.1
Slides Example1
Example2
Lecture 12
Advanced Sorting
Sort Classifications. Insertion Sort. Selection Sort. Bubble Sort. Merging Sorted Files. Gilberg: Chapter 11. Read only about the four sorts introduced in the classroom Slides Example1
Example2
Example3
Lecture 13
Pointers
Memory and variables. Pointers. Operations with pointers. Pointers and functions. Pointers and arrays. Address Arithmetic. Pointers and char arrays. K&R2: Chapter 5. Sections 5.1-5.3 and 5.5 Slides Example1
Example2
Lecture 14
Two-Dimensional Arrays
Two-Dimensional Arrays. Arrays of Pointers. K&R2: Chapter 5. Sections 5.4 and 5.6-5.9 Slides Example1
Example2
Example3
Example4
Lecture 15
Structures
Structures. Using structures with functions. K&R2: Chapter 6. Sections 6.1 and 6.2 Slides Example1
Lecture 16
Stacks
Stack. Array implememtation of stacks. Applications of Stacks. G&F: Chapter 4. Sections 4.1, 4.3 (pp 163-166) and 4.6 Slides StackIntAr.h file
Example 1
Lecture 17
Queues
Queue. Operations with queues. Array implememtation of queues. G&F: Chapter 5. Sections 5.1, 5.3, 5.4 (pp. 230-235) Slides Midterm
Lecture 18
Queues and ADTs
Array Implememtation of Queues. Abstract Data Types. G&F: Chapter 1. Sections 1.2, 1.3; Chapter 5. Section 5.7 Slides Example 1
Example 2
QueueIntAr.h file
Lecture 19
Linear Lists
Linear Lists. Linked Lists. Implementation of Linear Lists with Linked lists G&F: Chapter 3. Sections 3.1, 3.2, 3.3 Slides
Lecture 20
Linked List Implementation
Implementation of Linked List ADT in C G&F: Chapter 3. Section 3.8 Slides Example 1
IntLL.h file
Lecture 21
Stacks Again: Linked-List Implementation
Multiple implementations of ADT. Implementation of stack with linked lists. G&F: Chapter 4. Sections 4.2, 4.3 (pp. 163-166), and 4.5 Slides Example 1
Example 2
StackIntLL.h file
Lecture 22
Recursion
Recursive defintions, Recursive functions. Implementation of recursion. Working with recursive data structures. Towers of Hanoi. G&F: Chapter 6. Sections 6.1-6.3, 6.5, 6.7 Slides Example 1
Example 2
Example 3
Towers of Hanoi from G&F
Lecture 23
Trees
Basic Tree Concepts. Binary Trees. Binary Tree Traversals. G&F: Chapter 7 (pp 298-317) Slides
Lecture 24
Binary Search Trees
Binary Search Trees: traversing, searching, adding nodes, deleting nodes. G&F: Chapter 8. Section 8.1 Slides

Copyright © 2000 Peter Brusilovsky