Data Structures and Algorithms

Data Structures and Algorithms I

3 Credits | 300 Level | 50 Contact hours

REQUIRED TEXTBOOKS AND COURSE MATERIALS

1. The primary textbook for this course is Modern Software Development Using Java, Second Edition by
Paul Tymann and G. Michael Schneider. This text is freely available online at
http://www.cs.rit.edu/~ptt/msd/.
2. A secondary (optional) textbook is BIG JAVA Early Objects, Fifth Edition by Cay Horstmann (
http://www.wiley.com/WileyCDA/WileyTitle/productCd-EHEP002512.html )
3. You should own or have access to a good Java reference book. If you don't you might try an online
source such as:
• Java Programming (a wikibook)
• Thinking in Java by Bruce Eckel;
• Introduction to Computer Science using Java by Bradley Kjell; or
• Fred Swartz's topic-based review.
If you find other good online references, let us know!

DESCRIPTION

A continuation of CS 111x, emphasizing modern software development methods. An introduction to the software development life cycle and processes. Topics include requirements analysis, specification, design, implementation, and verification. Emphasizes foundational data structures and program analysis. The course provides a comprehensive look at the Java programming language including object oriented programming, concurrency, inheritance or polymorphism. Additionally, foundational data structures and related algorithms are studied.

LEARNING GOALS

• Students will understand how to write programs in Java, including all basic structures (e.g., ifstatements,
loops, functions), recursion, objects, methods, inheritance / polymorphism, and
exception throwing / handling.
• Students will understand and implement several key data structures, required for a foundational
education in computer science. These data structures include Vectors, Linked Lists, Stacks, Queues,
Binary Search Trees, AVL Trees and Hash Tables.
• Students will understand and be able to implement various sorting methods, including insertion sort,
mergesort, quicksort, etc.
• Students will be able to understand and analyze program analysis using practical approaches (e.g.,
mergesort vs. quicksort) and theoretical approaches. This will include both space and time
complexity analyses.
• Students will gather an abstract, and basic understanding of concurrency and associated issues
(shared resources, etc.). Students will be able to implement simple multi-threaded programs in Java.

OUTLINE

1. Java Review. Basic program structure.
2. Objects and classes. Key data structures.
3. References
4. Class Design.
5. Sorting Collections, Comparators.
6. Abstraction, Interfaces, polymorphism, Inheritance.
7. Java Collections Framework.
8. Sets and Maps.
9. Algorithm Analysis.
10. Sorting. Binary Search.
11. Handling events.
12. Recursion; Divide and Conquer.
13. Data Structures, Trees, Binary Trees, BST.

ASSESSMENT/GRADES

Your final course average will be calculated using the following method:
• Labs and Exercises – 30% Attendance and participation in lab is required.
• Assignments – 20% The exercises will be a combination of programming problems as well as paperand-pencil activities that address the topics studied.
• Exam 1 – 15% Covering the first third of the course.
• Exam 2 – 15% Covering the second third of the course.
• Final Exam – 20% Covering mainly the remainder of the course, with some material from the first
two-thirds