Course Expectations and Tentative Syllabus
CSC:290 Introduction to Data Structures and Algorithms Fall 2008
Room 200 Olney Hall Time: MWF 10:00-10:50am
Room: 200 Olney Hall Lab Th 2:00-3:45pm
Professor: Dr Michael Redmond
330 Olney Hall (215) 951-1096
http://www.lasalle.edu/~redmond/teach/290
Office Hours: MWF 11-11:50am, R 10:30am-12:30pm, And at other times by appointment
Text:
Lewis J. and Chase J., Java Software Structures, Designing and Using Data Structures, Second Edition 2005, Pearson Addison-Wesley, ISBN: 0-321-24584-9
Course Description:
This course is designed to 1) teach basic data structures including lists, stacks, queues, trees, etc; 2) introduce analysis of simple algorithms; and 3) teach some additional capabilities of Java that are not taught in CSC 280. The course meets MWF with a lab on Thursdays.
We use the Java language as a vehicle for teaching data structures, but it really is more than that. The Java Collections Library provides capabilities for several common data structures. Hence, this raises the level of abstraction. Students can first learn about how the data structure works and can be used, THEN learn about how these could be programmed.
Programming is central to this course. You do not fully understand the concepts until you can use them to solve problems. Hence programming assignments are central to this course. Come to Lab! Come on-time and prepared! Do the assignments! Do them on-time! and Do your own work!
Prerequisite: CSC 280. This class directly builds on that foundation; thorough understanding of material from that class is assumed. For instance, most of Chapter 2 of the text was covered in CSC 280 and will not be covered again in this class.
Grading:
Quizzes 5%
Assignments 30%
Exam 1 15%
Exam 2 15%
Lab Final 10%
Final 20%
Class Participation 5%
Final Grades:
A 92-100 A- 90-91
B+ 88-89 B 82-87 B- 80-81
C+ 78-79 C 72-77 C- 70-71
D+ 68-69 D 60-67 F < 60
Students generally do better if they read the section of the textbook BEFORE it is presented in class, since they are prepared to ask questions. Working end-of-chapter exercises is a good test of your understanding.
Quizzes will be short, 10 minutes or less, with one or a few questions, given at the beginning of class, typically on Fridays. Latecomers to class will not be given extra time to complete the quiz. Lowest quiz score (or one missed quiz) will be dropped.
Assignments will typically be assigned on a Wed., possibly with “pre-lab” preparation work to do, hands-on time in the lab on Thur, and “post-lab” work to do, due the following Wed.
Do your own assignments !!!! Work that is copied or done with somebody (when not assigned to a group) will be punished. If in a group/pair, your group must do its own work. If programs are copied, both students will receive a zero for the assignment. Changing small aspects of a copied program does not make it not a copy. Asking another for help on a step or two in a many-step assignment is acceptable; looking at another person’s program is temptation for cheating; handing in a near duplicate program is cheating
Late Assignments -25% per weekday (NOTE - NOT per CLASS)
UNLESS SPECIFIED OTHERWISE, ASSIGNMENTS ARE DUE AT THE BEGINNING OF CLASS
-10% if handed in after start of class and before I leave for the day.
Makeup exams only by advance arrangements or for documented real emergencies, such as medical problems. Makeup may involve double-counting your final exam.
Lab Final will be held on the last Thursday lab of the semester (Dec 4). It will be a cumulative test involving writing / modifying code in the lab on the computer
The Final Exam is cumulative, though it will focus more on the (previously untested) final part of the course. It will contain the “non-programming” questions – multiple choice, true-false, completion, valid/invalid, following code, etc.
Class participation grade will be assigned based on 1) attendance, 2) in class contribution, and 3) “minute papers” turned in at the end of some classes. These minute papers may vary in content, including reflection, questions, etc from class. More details will be given in class. The formula for calculating class participation is available upon request.
Materials:
It is very highly recommended that you bring a USB drive for storing work. Most assignments will require you to submit your work to Blackboard Course Management System, and the network (I:\) drive provides convenient storage in lab; however, you may want storage you can carry around with you, along with backup capability. You should keep copies of all of your assignments at least until you receive your grade for the assignment (and don’t have any questions about it). Missing or destroyed files are not acceptable excuses for incomplete assignments.
You will need access to Java and the NetBeans development environment outside of class. This is installed on PCs in Olney 200/200A/201. The software can be downloaded for free.
Open Lab Location: Olney 200A is available (small number of computers) irregular hours (most of the day, but not late)
Olney 200 and 201 are occasionally available when not being used for classes.
Wister Building basement lab may or may not have Java and the development environment
Objectives
1. Teach concept of abstract data types and their importance.
2. Demonstrate how abstract data types are implemented in an object-oriented programming language.
3. Reinforce important object-oriented concepts such as inheritance.
4. Introduce analysis of simple algorithms for execution time.
5. Demonstrate advanced Java capabilities including Generics, exception handling and recursion.
6. Introduce many classes in the Java Collections Framework library.
7. Study the set ADT, how to solve problems using sets, and programming techniques that could be used to develop an implementation of sets (both making use of arrays and making use of links (references)).
8. Study the stack ADT, how to solve problems using stacks, the Java Collections stack class, and programming techniques that could be used to develop an implementation of stacks.
9. Study the queue ADT, how to solve problems using queues, the Java Collections queue interface, and programming techniques that could be used to develop an implementation of queues.
10. Study the list ADT, how to solve problems using lists, and programming techniques that could be used to develop an implementation of lists.
11. Study the tree ADT, how to solve problems using trees, and programming techniques that could be used to develop an implementation of trees – in particular, binary search trees.
|
Tentative Course Plan: |
||
|
Date |
Material |
Reading |
|
Aug 25 |
Intro to Class |
|
|
Aug 27 |
Software Engineering / Software Quality / UML |
Chapt 1 |
|
Aug 29 |
Analysis of Algorithms |
Chapt 1 |
|
Sept 1 |
LABOR DAY – NO CLASS , |
|
|
Sept 3 |
References (partial review) |
Chapt 2 |
|
Sept 5 |
Iterator Interface |
Chapt 2 |
|
Sept 8 |
Generic Types |
Chapt 2 |
|
Sept 10 |
Generic Types |
Chapt 2 |
|
Sept 12 |
Error Handling / Exceptions |
Chapt 1 / 2 |
|
Sept 15 |
Exceptions |
Chapt 2 |
|
Sept 17 |
Intro to Collections |
Chapt 3 |
|
Sept 19 |
Sets |
Chapt 3 |
|
Sept 22 |
ArraySets |
Chapt 3 |
|
Sept 24 |
Analysis of Array Sets |
Chapt 3 |
|
Sept 26 |
References as Links |
Chapt 4 |
|
Sept 29 |
TEST 1 |
|
|
Oct 1 |
Linked Lists |
Chapt 4 |
|
Oct 3 |
Linked Sets |
Chapt 4 |
|
Oct 6 |
Linked Sets |
Chapt 4 |
|
Oct 8 |
Analysis of Linked Sets |
Chapt 4 |
|
Oct 10 |
Stacks |
Chapt 6 |
|
Oct 13 |
Using Stacks |
Chapt 6 |
|
Oct 15 |
Implementing Stacks using Links |
Chapt 6 |
|
Oct 17 |
Java Collections Stack |
Chapt 6 |
|
Oct 20 |
FALL BREAK – NO CLASS |
|
|
Oct 22 |
Analysis of Stack Implementations |
Chapt 6 |
|
Oct 24 |
Queues |
Chapt 7 |
|
Oct 27 |
Using Queues |
Chapt 7 |
|
Oct 29 |
Implementing Queues with Links |
Chapt 7 |
|
Oct 31 |
Analysis of Array Implementations |
Chapt 7 |
|
Nov 3 |
TEST 2 |
|
|
Nov 5 |
Recursion |
Chapt 10 |
|
Nov 7 |
Recursion |
Chapt 10 |
|
Nov 10 |
Recursion |
Chapt 10 |
|
Nov 12 |
Trees |
Chapt 12 |
|
Nov 14 |
Tree Traversals |
Chapt 12 |
|
Nov 17 |
Implementing Binary Trees |
Chapt 12 |
|
Nov 19 |
Using Binary Trees |
Chapt 12 |
|
Nov 21 |
Implementing Binary Search Tree with Links |
Chapt 13 |
|
Nov 24 |
Using Binary Search Tree |
Chapt 13 |
|
Nov 26 |
THANKSGIVING BREAK – NO CLASS |
|
|
Nov 28 |
THANKSGIVING BREAK – NO CLASS |
|
|
Dec 1 |
Balanced Binary Search Trees |
Chapt 13 |
|
Dec 3 |
Implementing Binary Search Trees – AVL |
Chapt 13 |
|
Dec 5 |
Implementing Binary Search Trees – AVL |
Chapt 13 |
|
TBD |
Final Exam (Dec 8, 10, or 12) |
|