Department of Information Science and Telecommunications

INFSCI 0015 - Data Structures and Programming Techniques

(Fall 2000, CRN 20813)

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