Department of Information Science and Telecommunications

INFSCI 0015 - Data Structures and Programming Techniques

(Fall 2001, CRN 20895)

INFSCI 0015 Course Materials

Lecture	Objectives	Readings	Slides	Examples	Dissections
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	Dissection3
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	Dissection5 Dissection6
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	Dissection1 Dissection3
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	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 sorts introduced in the classroom D&D: Chapter 6, Section 6.9	Slides	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 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	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 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