CS 242
/ Course Coordinator / Mateen RizkiCourse Title /
Computer Science II
/ Total Credits / 4Catalog Description
Further refinement of the concepts covered in CS 241. 3 hours lecture, 1 hour lab. For CS/CEG majors only. Prerequisite CS 241. Co-requisites: MTH 230.
Textbook
1. Robert Kruse and Alexander Ryba, Data Structures and Program Design in C++, Prentice Hall, 1999.
2. Tony Gaddis, Starting Out with C++ Alternate 2nd Edition, Scott Jones Publisher, 2001.
Language
Microsoft Visual C++ 6.0 Compiler, (available in the library)
Course Goals
The student should learn:
1. How to analyze the time and space complexity of functions and simple programs.
2. Basic abstract data types such as stacks, queues, and trees.
3. The use of recursion as a problem solving technique.
4. Fundamental techniques for searching and sorting data.
The students should be able to apply these concepts and techniques to:
1. Design and implement basic ADTs including stacks, queues, and trees.
2. Analyze the time and space complexity of alternative implementations.
3. Design, implement, and trace recursive programs.
4. Apply search and sorting techniques within various applications.
5. Formulate designs for complex problems, evaluate alternative implementation, and integrate multiple objects to form complete applications.
Prerequisites by Topic
1. Knowledge of object oriented design (OOD) and object oriented programming (OOP).
2. Knowledge of abstract data types (ADT) and the concepts of encapsulation and information hiding
3. The ability to (a) implement objects in C++ and (b) integrate multiple objects to form complete applications.
4. Knowledge of dynamic memory allocation and self-referencing structures
5. Knowledge of calculus I (MTH 229)
Major Topics Covered in the Course
1 Program Design (ADT and OOD) Chapter 1
Reliability and Testing: Handling Exceptions in C++ Chapter 15.1 (Gaddis)
Designing Generic Functions and Classes: Templates Chapter 15.2-4(Gaddis)
2 ADT Development Methodology
Review of ADT List Chapter 6.1-6.2
Using the Standard Template Library (STL) Chapter 15.5 (Gaddis)
3 ADT Stack and Applications Chapter 2, 4.1-4.3
4 ADT Queue and Applications Chapter 3, 4.4-4.6
5 Recursive Programming Chapter 5.1-5.4
6 Search Algorithms Chapter 7.1-7.3
Analysis of Algorithms Chapter 7.4-7.6
7 Sorting Algorithms Chapter 8
Analysis of Sorting Algorithms
8 ADT Table Chapter 9
Applications of Lookup Tables and Hashing
9-10 ADT Binary Tree and Search Trees Chapter 10.1-10.2
Laboratory Projects
There are eight laboratory projects for the course. Each project is designed to explore aspects of the material presented during the previous week. Laboratory exercises typically require students to read existing code, make modifications, perform some simple analysis, or test some newly introduced language construct. Laboratory exercises are worth 20 points. If there is a pre-lab and in-lab component, each part is worth 10 points. The laboratory projects are evaluated based primarily on quality of the solution and accuracy of the results. (20% of the course grade)
Programming Projects
There are four programming projects for the course. The projects are of moderate difficulty. The a good solution to each program requires students to conduct some design process, formulate a set of objects, identify the communications among the objects, combine the objects to form a final solution. Some projects require students to analyze the complexity of their solution and/or write reports describing their results. The projects are evaluated based on the quality of the design, accuracy of the results, documentation. (34% of the course grade)
Estimate CSAB Category Content
Core / Advanced / Core / AdvancedData Structures / 1 / Concepts of PL / 1
Algorithms / 1 / Comp Organization + Architecture
Software Design / 1 / Other
Oral and Written Communications
There are no oral presentations. Students submit source code for their projects along with documentation.We do not claim that documentation constitutes written communications. In at least one project, students perform a system simulation that requires them to perform a series of experiments. A report summarizing the results of these experiments along with a recommendation are required as part of the project.
Social and Ethical Issues
None.
Theoretical Content
Time and space complexity analysis are presented. Students are expected to be able to bound the time/space complexity of their solutions. Students must be able to prove their choice of bounds using algebraic technique or limits.
Problem Analysis
Problems typically require students to identify a several logical objects in the problem and identify the interaction among these objects. The complexity of the problems demands good designs and increase emphasis is placed on the overall quality of the design.
Solution Design
Potential designs for each project are reviewed in class. Design alternatives are presented and discussed in class. The use of basic data structures to solve complex problems is emphasized. Students learn to customize data structures using object-oriented features such as inheritance to simplify the solution of complex problems.