Department of Information Science and Telecommunications

INFSCI 0015 - Data Structures and Programming Techniques

(Spring 2001, CRN 28006)

INFSCI 0015 Course Materials

Lecture	Objectives	Readings	Handouts	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	Slides	Example1
Lecture 1 Data Types	Introduction to data types. Linear programs, printing data, and simple expressions.	K&R2: Chapter 1, Section 1.1	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	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	Slides	Example1 Example2 Example3
Lecture 4 Simple Loops	Expressions, their value and side effect; blocks; simple while loop; increments and decrements; #define and preprocessor	K&R2: Chapter1, Section 1.2, 1.4 Chapter2, Section 2.8 Chapter3, Section 3.1	Slides	Example1 Example2 Example3
Lecture 5 More Loops	Relational operators (< > <= >= != ==); `while` loop vs. `until` loop; programming patterns; problems with counter-controlled and sentinel-controlled loops.	K&R2: Chapter 1, Sections 1.2 Chapter 2, Section 2.6, 2.10, 2.12 Chapter 3, Sections 3.6	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	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	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	Slides	Solution 3_2 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	Slides	Example1 Example2 Example3 Example4 Example5	Dissection 1 Dissection 3
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	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 G&F: Chapter1, Section 1-4 Chapter 2, Section 2-1 and 2-2	Slides	Meteorologist Example1 Example2 Example3	Dissection3
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	Dissection1 Dissection2 Dissection3
Lecture 13 Advanced Sorting	Sort Classifications. Insertion Sort. Selection Sort. Bubble Sort. Merging Sorted Files.	G&F: Chapter 11. Read only about the four sorts introduced in the classroom	Slides	Partition Array (1) Partition Array (2) Example1 Example2 Example3	Dissection1 Dissection2 Dissection3
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	Slides	Counting Letters (5_2) Example1 Example2	Dissection1 Dissection2
Lecture 15 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 Reversing lines
Lecture 16 Structures	Structures. Using structures with functions. Pointers to structures.	K&R2: Chapter 6. Sections 6.1 and 6.2	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 Midterm Slides	Example1 StackIntAr.h file
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 QueueIntAr.h file
Lecture 19 Stacks, Queues and ADTs	Applications of Stacks and Queues. Abstract Data Types.	G&F: Chapter 1. Sections 1.2, 1.3; Chapter 4. Section 4.6; Chapter 5. Section 5.7	Slides	Example1 Example2 StackIntAr.h file QueueIntAr.h file
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	Slides	Example1 IntLL.h file
Lecture 22 Hash Tables	Hash Tables. Hash Table ADT.	John Morris: Hash Tables	Slides	Example1 IntHT.h file
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	Slides	Example1 Example2 StackIntLL.h file
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	Slides	Example1 Example2 Example3 StackIntLL.h file
Lecture 25 Trees	Basic Tree Concepts. Binary Trees. Binary Tree Traversals.	G&F: Chapter 7 (pp 298-317)	Slides
Lecture 26 Binary Search Trees	Binary Search Trees: traversing, searching, adding nodes, deleting nodes.	G&F: Chapter 8. Section 8.1	Slides