Pitt Logo SIS Logo

Department of Information Science and Telecommunications

 

INFSCI 0015 - Data Structures and Programming Techniques

(Fall 2001, CRN 20895)


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


INFSCI 0015 Course Materials

Lecture Objectives Readings Slides Examples
Lecture 0
Programming
Introduction to the course. Logistics. Programming and programs. First program. Compilation and errors. K&R2:
Introduction; Chapter 1, Section 1.1
D&D:
Chapter 1, Sections 1.1-1.7, 1.14
Slides Example1
Lecture 1
Data Types
Introduction to data types. Linear programs, printing data, and simple expressions. K&R2:
Chapter 1, Section 1.1
D&D:
Chapter 2, Sections 2.1-2.2
Slides Example1
Example2
Example3
Lecture 2
Variables
Complex expressions, variables, assignment. K&R2:
Chapter 1, Sections 1.2 (skip while)
Chapter 2, Sections 2.1-2.5, 2.7, 2.8, 2.12
D&D:
Chapter 2, Sections 2.4-2.5
Slides Example1
Example2
Lecture 3
Simple Programs
Program design, type conversion, input. After this lecture you should be able to write a program that inputs data, does simple calculations, and prints a result. K&R2:
Chapter 2, Sections 2.1-2.5, 2.7
D&D:
Chapter 2, Sections 2.3; Chapter 3, Sections 3.1-3.2
Slides Example1
Example2
Example3
Lecture 4
Simple Loops
Expressions, their value and side effect; blocks; control flow and flowcharts, simple countdown while loop; increments and decrements; preprocessor: #include and #define K&R2:
Chapter1, Section 1.2, 1.4
Chapter2, Section 2.8
Chapter3, Section 3.1
D&D:
Chapter 3, Sections 3.3, 3.4, 3.12;
Chapter 13, Sections 13.1-13.3
Slides Example1
Example2
Example3
Lecture 5
Tables and Loops
Relational operators (< > <= >= != ==); More assignment operators (+=; -=; *=; /=, %=) Programming patterns. Printing tables with while loop; Counter-controlled and sentinel-controlled loops. Summing up an input. while loop vs. until loop; After this lecture you should get a good understanding of basic loops and be able to write simple programs with counter-controlled and sentinel-controlled loops, in particular, programs that process and print tables K&R2:
Chapter 1, Sections 1.2
Chapter 2, Section 2.6, 2.10, 2.12
Chapter 3, Sections 3.6
D&D:
Chapter 2, Section 2.6;
Chapter 3, Sections 3.7-3.9, 3.11;
Chapter 4, Sections 4.1-4.3, 4.8, 4.11
Slides Example1
Example2
Example3
Example4
Example5
Lecture 6
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. K&R2:
Chapter1, Section 1.5 (Except 1.5.4)
Chapter2, Section 2.2 and 2.3
Chapter3, Section 3.2
D&D:
Chapter 3, Sections 3.5, 3.6, 3.9
Slides Example1
Example2
Example3
Example4
Lecture 7
Nested Ifs and Loops
Else-if and complex conditions. Nested ifs and loops. K&R2:
Chapter1, Section 1.5.6, 1.6
Chapter2, Section 2.6;
Chapter3, Section 3.3
D&D:
Chapter 3, Sections 3.6, 3.10;
Chapter 4, Section 4.10
Slides Example1
Example2
Example3
Lecture 8
Arrays and For Loop
Arrays. Array input and output. For loop. Array processing with for. K&R2:
Chapter1, Section 1.6
Chapter3, Section 3.5
D&D:
Chapter 4, Section 4.4-4.6
Chapter 6, Section 6.1-6.4
Slides Example1
Example2
Example3
Example4
Lecture 9
Array Processing with Loops
Arrays: sum, max, min algorihms. Functions. Array processing with functions. K&R2:
Chapter1, Section 1.7, 1.8
D&D:
Chapter 4, Section 4.6
Chapter 5, Section 5.1-5.5
Slides Example1
Example2
Example3
Example4
Example5
Lecture 10
Character Arrays
Character arrays, strings, processing, initializing, and printing strings. Prameter passing by value and by refernce. K&R2:
Chapter 1, Section 1.8, 1.9
Chapter 2, Sections 3, 4, 7, and 8
Chapter 3, Section 5
D&D:
Chapter 5, Section 5.6-5.8
Chapter 6, Section 6.5
Chapter 8, Section 8.1, 8.2, 8.4
Slides Example1
Example2
Example3
Lecture 11
Searching
Sequential search in non-ordered and ordered list. Binary search. K&R2:
Chapter1, Section 1.8
Chapter 3, Section 3.3
D&D:
Chapter 6, Section 6.8
G&F:
Chapter1, Section 1-4
Chapter 2, Section 2-1 and 2-2
Slides Example1
Example2
Example3
Lecture 12
Nested Loops
Nested loops, bar charts, string search Reading and processing standard input line by line. K&R2:
Chapter 3, Section 3.5, 3.6
Chapter 4, Section 4.1
Slides Example1
Example2
Example3
Lecture 13
Advanced Sorting
Sort Classifications. Insertion Sort. Selection Sort. Bubble Sort. Merging Sorted Files. G&F:
Chapter 11. Read only about the sorts introduced in the classroom
D&D:
Chapter 6, Section 6.9
Slides Example1
Example2
Example3
Lecture 14
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
D&D:
Chapter 7, Sections 7.1-7.8
Ted Jensen:
Pointers and Arrays in C
Stanford CS Ed. Library:
Pointers and Memory
Slides Example1
Example2
Lecture 15
Two-Dimensional Arrays
Two-Dimensional Arrays. Arrays of Pointers. K&R2:
Chapter 5. Sections 5.4 and 5.6-5.9
D&D:
Chapter 6, Section 6.9
Chapter 7, Section 7.9
Slides Example1
Example2
Example3
Example4
Lecture 16
Structures
Structures. Using structures with functions. Pointers to structures. K&R2:
Chapter 6. Sections 6.1 and 6.2
D&D:
Chapter 10, Sections 10.1-10.7
Slides Example1
Example2
Lecture 17
Stacks
Stack. Array implememtation of stacks. G&F:
Chapter 4. Sections 4.1, 4.3 (pp 163-166) and 4.6
Slides
Example1
StackIntAr.h
Lecture 18
Queues
Queue. Operations with queues. Array implememtation of queues. G&F:
Chapter 5. Sections 5.1, 5.3, 5.4 (pp. 230-235)
Slides
Example1
Example2
QueueIntAr.h
Lecture 20
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 21
Linked List Implementation
Implementation of Linked List ADT in C G&F:
Chapter 3. Section 3.8
D&D:
Chapter 12, Sections 12.1-12.4
Slides
Example1
IntLL.h
Lecture 22
Hash Tables
Hash Tables. Hash Table ADT. John Morris: Hash Tables Slides
Example1
IntHT.h
Lecture 23
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
D&D:
Chapter 12, Section 12.5
Slides
Example1
Example2
StackIntLL.h
Lecture 24
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
D&D:
Chapter 5, Sections 5.13-5.15
Slides
Example1
Example2
Example3
StackIntLL.h
Lecture 25
Trees
Basic Tree Concepts. Binary Trees. Binary Tree Traversals. G&F:
Chapter 7 (pp 298-317)
D&D:
Chapter 12, Section 12.7
Slides
 
Lecture 26
Binary Search Trees
Binary Search Trees: traversing, searching, adding nodes, deleting nodes. G&F:
Chapter 8. Section 8.1
Slides
 

Copyright © 2001 Peter Brusilovsky