COQUITLAM COLLEGE
COURSE NUMBER: CSCI 225-3
TITLE: Data Structures and Programming
DESCRIPTION:
This course will delve into data structures and how they assist us in solving complex problems. Topics include: a) abstract data types (abstraction, encapsulation, information hiding), b) data structures (arrays, lists, stacks, queues, trees, heaps, sets, and hash tables), c) searching and sorting algorithms, d) correctness and efficiency, and e) object-oriented programming. All programming implementations would be done using Java.
PREREQUISITES: CSCI 125
TEXTBOOK:
Starting Out with Java: From Control Structures through Data Structures, 2/E
Tony Gaddis and Godfrey Muganda, Addison-Wesley, 2012
ISBN-10: 0321545869, ISBN-13: 9780321545862
DURATION: 13 weeks, 4 hours/week.
TOPICS:
1. Abstract data type
2. Recursion
3. O Notation
4. Sorting and Searching
5. Generics
6. Linked List
7. Stack
8. Queues
9. Binary Trees, AVL Trees, Priority Queues
10. Hashing
11. Heap
LEARNING OUTCOMES:
1. Define the concept of recursion
2. Describe situations where recursion is needed
3. Analyse, implement, and use recursion
4. Identify the different sorting algorithms
5. Describe the differences among the sorting and searching algorithms
6. Analyse, implement, and use sorting
7. Analyse, implement, and use searching
8. Justify the selected sorting and searching algorithm
9. Assess the appropriateness of the selected sorting algorithm
10. Analyse the complexity of sorting and searching algorithm
11. Give examples of Generic classes
12. Develop customized Generic classes
13. Analyse, implement, and use standard and customized Generic classes
14. Define common type parameter names used in a Generic class
15. Construct Generic classes that implement different sorting and searching algorithms
16. Identify the commonly used Java Collections
17. Discuss the similarities and differences among Lists, Sets, and Maps
18. Analyse, implement, and use collections such as Lists, Sets, and Maps
19. Evaluate the appropriateness of the used collection in a given problem
20. Discuss linked list, double-linked list, circular-linked list, and recursion on linked list
21. Analyse, implement, and use linked list, double-linked list, circular-linked list, and recursion on linked list
22. Evaluate the linked list, double-linked list, circular-linked list, and recursion on linked list solutions
23. Explain stacks and their applications
24. Explain queues and their applications
25. Analyse, implement, and use stacks and queues
26. Explain binary trees and their applications
27. Discuss AVL Trees and priority queues
28. Analyse, implement, and use binary trees, AVL trees, B trees, B+ trees, and priority queues
29. Explain Heap and its applications
30. Analyse, implement, and use heap
31. Define common terms used in Algorithms and Data Structures
32. Cite memory allocation issues
33. Analyse and implement solution for memory allocation issues
34. Demonstrate mathematical literacy in the concepts applicable to Algorithms and Data Structures
EVALUATION:
Classwork / Homework Participation 10%
Quizzes 20%
Midterm Exam 30%
Final Exam 30%
Project 10%
Students must attain an overall passing grade on the weighted average of exams
in the course in order to obtain a clear pass (C or better).