Montgomery County Community College
Spring 2005
CIS 112 – SC,YO
Computer Science III: Data Structures & Algorithms
3-2-2
TIME: Tuesday Evenings, 6:00 PM - 9:50 PM (Two 5 minute breaks)
CLASS FORMAT: Lecture and discussion Room: SCIC 205 Time: 6:00 PM - 7:55 PM
Computer Lab Room: SCIC 106 Time: 8:00 PM - 9:50 PM
(Section YO is an on line class).
|
INSTRUCTOR: Robert Moyer |
E-MAIL: rmoyer@mc3.edu |
|
PHONE: (484) 865-5688 (day) (610) 584-4730 (evenings) |
Faculty Home Page: faculty.mc3.edu/rmoyer/ |
|
OFFICE HOURS/LOCATION: by appointment |
|
CATALOG DESCRIPTION
Building on the concepts learned in CIS 111B, the fundamental concepts of data structures and algorithms are explored. This course will apply software engineering techniques to the design and implementation of programs that manipulate complex data structures. Effective software engineering methods are stressed as well as developing good programming style. A high-level compiler language such as Java or C++ will be used. This is the third course for computer majors.
PREREQUISITES: CIS 111B with a “C” or better, or equivalent object-oriented programming experience.
LEARNING GOALS
1. Demonstrate the application of fundamental data structures including stacks, queues, linked lists, hash tables and trees.
2. Practice basic principles of software engineering for designing and implementing programs with emphasis on algorithm analysis and top-down design using good programming style, and documentation.
3. Design programs that demonstrate understanding of fundamental computing algorithms such as binary search trees, depth-first traversals and breadth-first traversals.
4. Demonstrate fundamental algorithmic strategies such as brute-force, divide and conquer, backtracking, branch-and-bound and pattern matching.
5. Use software validation and debugging methods including plan test creation and test case generation.
6. Develop a foundation for further studies in computer science.
Required Text and Other Materials
Data Structures and Abstractions with Java
Frank M. Carrano and Walter Savitch,
Prentice Hall
|
|
The Companion Website provides the following: PowerPoint Slides: Available for download either by chapter or as one zipped archive for all chapters. Figures: Available for download either by chapter or as one zipped archive for all chapters. Available online: Errata for Data Structures and Abstractions with Java |
Student should have removable storage devices (diskettes, flash memory, etc) for transporting programming assignments.
Grading (Criteria and Methods of Evaluation)
Final grade for the course will consist of the average of the following five grading instruments. Each component will receive a letter grade (A+,A,A-,B+,B,B-, etc.). Quiz and Exam scores will be graded based on percentage. (e.g. Total Points Earned/Total Possible Points). Programming assignments will be graded on correctness, completeness and style. Programs will be weighted by complexity, to be determined when the assignments are given. The letter grades will then be used to calculate the final grade for the course. (e.g sum of (grade * percent) )
|
Weekly Quizzes |
20% of final grade |
Total points, normalized to 100 and adjusted for attendance |
|
|
Lab Exercises |
20% of final grade |
Simple lab exercises to be done in the lab portion of class. Labs and schedule TBD. These are scheduled Closed labs. Note: some lab time will be Open lab and may be used for any programming assignments. |
|
|
Semester Project |
15% of final grade |
A Major Programming Assignment. |
|
|
Program assignments |
20% of final grade |
Approximately 7 programs to be writtten by the student as Homework. Possible topics may include: 1. Performance of Algorithms 2. Memory allocation, Static vs. Dynamic 3. Classic problems involving Stack, Queues, or Lists 4. Classic problems solved with recursion. 5. Exploring various non-linear structures such as trees. |
|
|
Final Exam |
25 % of final |
(see format below) |
|
|
Grade |
Points |
+ |
- |
|
A |
4.0 |
4.25 |
3.75 |
|
B |
3.0 |
3.25 |
2.75 |
|
C |
2.0 |
2.25 |
1.75 |
|
D |
1.0 |
1.25 |
0.75 |
|
F |
0.0 |
na |
na |
<>
For example:
Quiz grade of A+ would be 4.25 * .20 =
0.850
Lab grade of B- would be 2.75 * .20
= 0.550
Project grade of B+ would be 3.25 * .15 = 0.475
Program grade of B would be 3.0 * .20 = 0.60
Final Exam grade A- would be 3.75 * .25= 0.5625
For a total of 3.05 for a course grade of B (>=2.5 and < 3.5)
A = >=3.5 points
B = >=2.5 and < 3.5
C = >=1.5 and < 2.5
D = >= 0.5 and < 1.5
F = <0.5
Final exams will be approximately 60% short definitions, fill-in blanks, matching and true/false questions. Quizzes will given each class period. Questions on the quizzes will most likely reappear on the examination with minor editing. Quizzes, therefore, provide the student with an excellent study aid for the exam. They should not be missed. If you miss a quiz, you may get a copy to study from, but NO MAKE-UP QUIZZES WILL BE GIVEN. Quizzes will take only a few minutes of each class period. They will be based on the previous week's reading assignment and class discussions.
The final 40% of the exams will be short program stubs and/or discussions on the concepts of data abstractions, algorithms, and data structures.
Programming assignments will be given throughout the semester to give the student a working knowledge of problem solving using various data abstractions and structures. Students should keep current with assignments. Assignments due dates will be stated when the assignment is given. The maximum grade obtainable on a late assignment will be one (1) letter grade lower for each week an assignment is late. There will be approximately 7 programming assignments during the semester.
Attendance Policy (absence and lateness)
Attendance is expected at all lecture sessions. Computer lab time is for the benefit of the student. Students should attend all labs sessions where they will have access to the Instructor, question and answer time on assignments, and lab exercises reinforcing material covered during lecture. Some lab time will be free time used to work on class assignments. However, assignments may be done on any computer the student has access to, including the Learning Resource Center.
Missed Work/Test Make-Up Policy
Assignments are due as scheduled. Final exams should be taken as scheduled. (Make-ups and extensions are by prior arraignment only). Quizzes and late assigments a noted above in the grading section.
Withdrawal Policy
Students may withdraw from the class according to the College Guidelines. Special consideration may be given on an individual basis.
Students who are in otherwise good standing in the course, may be given the grade of INCOMPLETE, provided that any conditions outlined by the college are met. Good standing means evidence of progress toward all assignments can be demonstrated and a reasonable plan for completion provided. In the case of a missed Final Exam, an UNAVOIDABLE and documented reason for missing the exam is required. In no case will workload from concurrent course work be considered as a reason for granting INCOMPLETE status.
A student may change from Grade to Audit status at any time, again within the rules of the college.
Student Academic Code of Ethics
"In the pursuit of knowledge and scholarship, all members of the academic community at MCCC must maintain a constant commitment to academic integrity. the College provides an environment that fosters critical thinking and judgment, and in order to safeguard the integrity of the institution, students are expected to follow the policies of the College and the faculty. To fulfill their part of that commitment, students must adhere to an academic code of ethics by refraining from participation in acts of academic dishonesty. By attending MCCC, students accept this Student Academic Code of Ethics and agree to the following:
· Students must do all of their own work.
· Students must not cheat.
· Students must not help others to cheat.
Students who are unclear about the validity of an academic procedure they are
about to undertake should ask their instructor for guidance beforehand. Violations
of this code of ethics will result in sanctions, including possible dismissal
from College." (See complete Student Code of Ethics in the catalog,
Student Handbook Calandar, or on line at http://www.mc3.edu/gen/polpro/st_acad_code_of_ethics.html)
Please note:
Students may consult each other when solving programming exercises. Work turned
in for grade, must show sufficient understanding of the problem and original
effort on the part of the student. Copies of other students programs will not
be accepted for credit and will be considered in voilation of the above code of
ethics.<>
Students with Disabilities Policy:
“Students with disabilities may be eligible for accommodations in this course. Contact the Director of Services for Students with Disabilities in the Counseling Center, College Hall, at (215) 641-6575/6577 for more information. At West Campus, contact the Director of Student Affairs, (610) 718-1839.”
Other:
Homework for this class can be expected to be from 5 to 15 hours per week.
Students are expected to have any reading assignments complete before the class
in which they will be discussed.
You should have access to the JAVA SDK from Sun. http://java.sun.com/j2se/
Java Technology
Java 2 Platform,
Standard Edition (J2SE)
Since Java runs on most platforms, feel free to use your favorite. I have JDKs running on Windows, Linux, and Mac. Lab PCs use Windows XP.
Weekly Assignments
(may be subject to minor changes)
The online class weeks start on Wednesday of each week and end on Tuesday the following week. You may read all the material anytime, but must have completed that weeks material by the date below. Week #1 would run from 19-Jan-05 to 25-Jan-05 the night of the inclass lecture.
Online students are welcome to attend the inclass meetings anytime.
|
Class/Week # |
Class Date |
Chapter(s)Discussed |
Topic(s) |
|
1 |
25-Jan-05 |
1,2,3 |
Java Classes, Creating and Designing Classes |
|
2 |
1-Feb-05 |
4,5,6 |
Lists and List Implementations (Arrays and Linked Data) |
|
3 |
8-Feb-05 |
7,8 |
Lists (cont.), Iterators and Java's Iterators |
|
4 |
15-Feb-05 |
9,10 |
Efficiency of Algorithms and Recursion |
|
5 |
22-Feb-05 |
11,12,13 |
Sorting, Basic and Advanced Method, Sorted Listed |
|
6 |
1-Mar-05 |
14,15 |
Inheritance and Lists, Mutable, Immutable and Cloneable |
|
7 |
8-Feb-05 |
16,17,18 |
Searching and Dictionaries |
|
8 |
22-Mar-05 |
19 |
Hashing as a Dictionary Implementation, Semester Project |
|
9 |
29-Mar-05 |
20,21 |
Stacks and Stack Implementations |
|
10 |
5-Apr-05 |
22,23 |
Queues, Deque, and Priority Queues and Implementations |
|
11 |
12-Apr-05 |
24,25 |
Trees and Tree Implementations |
|
12 |
19-Apr-05 |
26,27 |
Binary Tree Search and Heap Implementations |
|
13 |
26-Apr-05 |
28 |
Balanced Search Trees |
|
14 |
3-May-05 |
29,30 |
Graph and Graph Implementations |
|
15 |
10-May-05 |
|
Final Exam |
This file was created by Robert Moyer on 01/14/05.