CMP 338 - Data Structures And Algorithms I
Fall 2023 Syllabus

Course Information
Course Section Lecture Hours Location
CMP 338 - G401 Mo & We 2:00 pm - 3:40 pm Gillet Hall, Room 231
Contact Information
Instructor: Steven Fulakeza Email: steven.fulakeza(at)lehman.cuny.edu
Phone: NA Office Location: GI 232
Office Hours: Mon and Wed 1:40 pm to 3:40 pm
Instructor Availability: I reply to students' emails regularly but please note that I do not typically check email or Slack messages during late hours on weekdays, and I do not check these at all on the weekends in order to devote time to family, rest, and religious observances. Messages received during these times will receive attention once I am back online.

Course Syllabus Download


Course Description: 4 hours, 3 credits

Abstract characterizations as well as the design and implementation of data structures such as arrays, stacks, queues, linked lists, binary search trees, heaps, hash tables and graphs along with algorithms that make use of such structures including algorithms for sorting, searching, will be studied. Algorithms will be analyzed for their asymptotic behavior in terms of time and space complexity. Implementation issues will be considered and students will write programs that embody these data structures and algorithms.

Prerequisites:

  • CMP 168 - In this course we will do extensive programming in Java. It is assumed that all students are capable of reading and writing object oriented Java code.
  • CMP 232 - In this course we will demonstrate correctness and efficiency of many of the algorithms presented via mathematical arguments and proofs. It is assumed that students are capable of following the logic of such when presented.

Course Objectives:

On successfully completing this course, students should be able to:

  • Improve skills in object-oriented programming
  • Improve understanding of recursive methods
  • Understand a core group of basic data structures as enumerated in topics below
  • Be able to conceptualize many programming issues at a higher level through data structures
  • Know the tradeoffs of each studied data structure so as to employ the appropriate one for a given situation
  • Be able to write parameterized data structures using generics
  • Be able to design algorithms that incorporate data structures for efficient handling of data
  • Be able to code algorithms involving data structures using an object oriented programming language
  • 9. Be able to analyze new data structures and their algorithms for asymptotic behavior
  • 10. Achieve a level of maturity in the subject so that further study of data structures can be pursued independently

For each algorithm, verification of its correctness and analysis of its efficiency will be considered.

Grading Policy:

  • Participation & Challenge Activities From Textbook: 10%
  • Homework Problems: 30%
  • Midterm: 30%
  • Final Exam: 30%

All your assignments: P&C, Homework and Projects are submitted through your zyBooks. All assignments have strict due dates. Late submissions are NEVER accepted. All assignments allow for unlimited attempts to submit via zyBooks prior to the deadline.

For each assignment, the highest earned submission score will be recorded.

The final exam is comprehensive. Since the final exam is comprehensive, if you do better on the final exam than the midterm exam, the final grade can replace the midterm grade. This will be done automatically when your final grade is calculated. This does not include cheating incidents.

Expectations: Students are expected to attend the lecture and participate in the associated lab section. Students are expected to learn the material covered in the lecture, the lab, and the textbook as well as any other assigned reading or exercises. Students are expected to actively participate in the slack communication channel and regularly check for messages or announcements. Students are expected to complete homework as an essential part of the learning experience. Students should review topics from prior courses as needed using old notes and books. All work must be your own.

Honor Code: You are encouraged to discuss the overall design of programs and homework. However, all work must be your own for all programs and homework assignments. Any sources used in the completion of your assignment must be explicitly quoted. You are responsible for knowing and following Lehman's academic integrity code (available from the Undergraduate Bulletin, Graduate Bulletin, Office of Academic Standards and Evaluations, or the Smart Catalog). All incidents of cheating will be reported to the Vice President of Student Affairs.

Communication: We will be communicating with you on a regular basis throughout the semester using Blackboard for this course. You are required to make sure that the email address on Blackboard is your current Lehman email address and you must check it on a regular basis. There will be no acceptable excuse for missing an announcement.

Homework: Participation Activities via the online textbook zyBooks will be assigned for every topic covered in class. Completion of these activities is expected by the specified due date.
Programming assignments are due most weeks. Assignments will be submitted via your zyBooks textbook. These programming problems reinforce concepts covered in class. To receive full credit for a program, it must be completed by the specified due date and the program must perform correctly. You will be allowed to submit your solution multiple times; the submission with the highest grade will count as your grade. All homework assignments have a deadline, No late homework will be accepted.
Late submissions are NOT accepted.
Unlimited attempts to submit via zyBooks are permitted prior to the deadline.
The submission with the highest grade will count as your grade for the assignment.
ONLY submissions via zyBooks will be accepted and scored via the automated test cases.

Materials and Resources:

Textbook: Zybook code: CCUNYCMP338FulakezaFall2023

Suggested Additional Textbooks:

  • Data Abstraction and Problem Solving with Java: Walls and Mirrors by Frank M. Carrano and Janet J. Prichard (3rd Edition) ISBN 978-0-13-212230-6.
  • Data Structures & Algorithms by Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser (6th Edition) ISBN 978-1-118-77133-4.
  • Data Structures and Algorithms in Java, 6th Edition Wiley ISBN: 978-1-118-77133-4

Technology:

Access to personal computers with Eclipse IDE, JDK 8

Tutoring:

Departmental tutoring is available in the Math Computer Science Learning Center, Gillet Hall, Room 222.
site: mcslclehman.wordpress.com email: mcs.learningcenter@lehman.cuny.edu

Computer Access:

Part of this course will use university computer laboratories. These machines are for work related to this course only and a code of conduct applies to computer use in the department and on-campus. Misusing university computers could result in losing your computer access for the rest of the term, making it exceedingly difficult to complete this course.

Accommodating Disabilities:

Lehman College is committed to providing access to all programs and curricula to all students. Students with disabilities who may need classroom accommodations are encouraged to register with the Office of Student Disability Services. For more info, please contact the Office of Student Disability Services, Shuster Hall, Room 238, phone number, 718-960-8441.

Additional Online Resources:


Topics

Intro Topics:

  • Abstract Data Types (ADTs) - Specification and Implementation
  • Asymptotic Analysis and Notation: “Big-O”
  • Sorting: Merge Sort, Quick Sort, Radix Sort

Linked Lists:

  • A simple List ADT
  • Implementing a List using Linked Nodes
  • Implementing a List using an Array
  • Implementation Issues
  • The use of dummy nodes

Stacks:

  • The Stack ADT
  • Array Implementations: Fixed size and resizable.
  • Reference Based Implementation
  • Comparisons of efficiency for Array and Linked List implementations
  • Application: Evaluation of Algebraic Expressions

Queues:

  • The Queue ADT
  • Circular Array Implementation
  • Reference Based Implementation
  • Comparing Implementations: Fixed size, resizable

Binary Search Trees:

  • Definitions and Properties for Binary Tree and Binary Search Tree
  • Implementing Binary Trees using Linked Nodes
  • Implementing Binary Trees using Arrays
  • Full, Complete, Balanced Binary Trees
  • Preorder, Inorder, Postorder tree traversal
  • Using a BST to Implement Treesort
  • Additional methods for manipulating Binary Tree Data
  • Using the definitions to determine correctness of Binary Tree Algorithms

Heaps

  • Definitions of Max-Heaps and Min-Heaps
  • Implementing a Heap
  • Using a Heap to Implement Heapsort

Graphs:

  • Graph ADT and Definitions
  • Data Structures and Implementation issues for Graphs
  • Graph Traversal: Breadth First and Depth First Traversal (BFS), (DFS)
  • Greedy Algorithms
  • Shortest Path: Dijkstra’s Algorithm

Tentative Schedule:

Week Day Date Topic Reading Materials P&C Due Dates HW

If you will be using your personal computer, please install JDK and Eclipse.


Java Development Kit(JDK) Download and Installation:

Click here for Java SE Development Kit 8 Downloads
Download Java SE Development Kit 8. Open the downloaded file and follow the installation instructions


Eclipse Download:

Click here for Eclipse Download
Download Eclipse. Open the downloaded file and follow the installation instructions