Saint Mary’s University
Department of Mathematics and Computing Science
CSC 342.2: Data Structures and Software Engineering II
WINTER 1998-99
Instructor: Dr. Pawan Lingras
Class time: Monday, Wednesday, Friday 12:30-1:20 p.m.
Lab time: Tuesday and Thursday, 11:30 a.m.-12:45 p.m. (Section A)/1:00-2:15 p.m. (Section B)
Brief Description
This is the second part of a two-part introduction to Data Structures and associated algorithms. Students will build on the programming skills developed in CSC 226/227 and CSC 341 (which are pre-requisites for this course) through a systematic study of some of the fundamental computer science concepts. The course will use the basis for evaluating the algorithms, established in CSC 341 to continue the study of various data structures and related operations. The data structures that will be studied in this course include . The operations on these data structures include creation, destruction, insertion, deletions, searching, and sorting. The students will compare the pros and cons of using these data structures. The programming will be done using C++.
Textbook
Topics
Week |
Topics |
Chapter |
1 |
Recursion, recursion trees, time analysis of recursive functions | 1.2.6 |
2 |
Lower bound of
searching and sorting Merge and Quick sorts and their time requirements |
14.4 |
3 |
Hash Tables | 7 |
4 |
Hash Tables (continued) | 7 |
5 |
Binary and other trees | 8 |
6 |
Binary and other trees (continued) | 8 |
7 |
Heap sort | 9 |
8 |
Binary Search Tree | 11 |
9 |
AVL Tree, B-Tree | 11 |
10 |
Graphs | 12 |
11 |
Graphs (continued) | 12 |
12 |
Greedy method, Divide and conquer | 13, 14 |
Each student registered in the course should also be registered for a lab section. There are two 1.5-hour lab-periods every week for each lab section. The lab work is designed to facilitate the programming aspects of the course. Typically first period will be used to introduce a new concept and related programs. Students will try out these programs and will modify them during the next lab period. The lab assignments will usually be related to the class assignment assigned for the upcoming week. They are not designed in advance. Students' needs for information and hands-on-experience will form the basis for the lab assignments. Detailed instructions for the second period (Thursday) of the week will appear on this web site after the first period (Tuesday evening).
Tentative Lab Schedule
Week |
Topics |
Chapter |
1 |
Sorting | 1 |
2 |
Merge sort (Assignment 1) | 14.2 |
3 |
Hash Tables | 7 |
4 |
Hash Tables (Assignment 2) | 7 |
5 |
Binary and other trees | 8 |
6 |
Binary and other trees (Assignment 3) | 8 |
7 |
Midterm review | 9 |
8 |
Binary Search Tree | 11 |
9 |
AVL Tree, B-Tree | 11 |
10 |
Graphs | 12 |
11 |
Graphs (continued) | 12 |
12 |
Final Review | NA |
Evaluation scheme
Method of Evaluation |
Marks |
| In-lab Assignments | 10 |
| Class Assignments | 18 |
| Midterm | 27 |
| Final | 45 |
Total |
100 |
Assignments
Assignment 1 (Due Date: January 15,1999)
Assignment 2 (Due Date: January 29, 1999)
Assignment 3 (Due Date: February 12,1999)
Assignment 4 (Due Date: March 5,1999)
Assignment 5 (Due Date: March 19,1999)
Assignment 6 (Due Date: April 5,1999)
Midterm
The midterm examination will be held on Monday, March 1, 1999. A link to the guide for the midterm will be available here.
Final Examination
The final examination will be scheduled by the Registrar’s office during the examination period from April 8-24, 1999. A link to the guide for the final examination will be available here.