COURSE DESCRIPTION
An extension of programming methodology for data storage and manipulation of complex data sets. Topics include: programming and applications of data structures; stacks, queues, lists, binary trees, heaps, priority queues, balanced trees and graphs. Recursive programming is heavily used. Fundamental sorting and searching algorithms are examined along with informal efficiency comparisons.
COURSE GOALS
- To provide students with additional programming experience using an object-oriented language, with emphasis on larger-scale programs that require the use of sophisticated data structures.
- To enhance student understanding of abstract data types, pointers, recursion, and algorithmic design.
- To introduce students to the importance of time and memory efficiency in algorithm design.
COURSE TOPICS
- Software Design: Specifications; memory and execution time efficiency; introduction to Big Oh notation; abstract data types and examples; review of object-oriented techniques.
- Linked Lists: Singly-linked lists; implementation; inserting and removing data; variations: doubly-linked lists, circularly-linked lists; comparison of arrays and linked lists to store general lists.
- Stacks and Queues: Basic operations of a stack; implementation using an array and a linked list; various stack applications (evaluating postfix, conversion of infix to postfix, etc.). Basic operations of a queue; implementation using an array and a linked list; queue applications (Josephus problem, simulations, Jai Alai).
- Recursion: Recursion and activation records, backtracking, introduction to dynamic programming, tail recursion.
- Binary Trees: Terminology; implementation of trees using nodes; Binary search trees: insertion and removal of data; Tree traversals. Heaps; implementation using arrays; use of a heap as a priority queue.
- Balanced Trees: B-trees; 2-3-trees; 2-3-4-trees; red-black trees; AVL trees; splay trees; examples.
- Searching: Sequential and binary search algorithms; hashing and hash tables; time analysis.
- Sorting: Quadratic sorting algorithms; divide and conquer sorts (quick sort and merge sort); heap sort, time analysis.
- Introduction to Graphs: Terminology; implementations using arrays and linked nodes; graph traversals.
REGISTRATION
CSE 114 (Computer Science I) is the prerequisite for this course. If you meet the course prerequisities but have been unable to register for the course, please see the professor the first day of class.
INSTRUCTOR
Richard McKenna
Lecturer
Computer Science 1436
Office Hours: MF 10:30 am - 12:30 pm and by appointment
TEACHING ASSISTANTS' OFFICE HOURS in CS 2110
Bharat Jain
Tuesdays, 5pm - 7pm & Wednesdays, 10am - 12pm
Kiwon Yun
Tuesdays & Thursdays, 2pm - 4pm
Reza Basseda
Tuesdays & Wednesdays, 12pm - 2pm
Ritwik Banerjee
Wednesdays, 2pm - 5pm & Fridays, 4pm - 5pm
Sing Yi Kong
Mondays & Fridays, 2:20pm - 3:50pm
Xiang Gao
Tuesdays, 10am - 12pm
LECTURE
Tuesdays & Thursdays
12:50 pm - 2:10 pm
Light Engineering 102
RECITATIONS
Section R01: (TA TBD)
Monday 12:50 pm - 1:45 pm
Chemistry 128
Section R02: (Xiang)
Friday 12:50 pm - 1:45 pm
Chemistry 123
Section R03: (Reza)
Monday 2:20 pm - 3:15 pm
Chemistry 123
Section R04: (Sing Yi)
Friday 10:40 am - 11:35 pm
MELVILLE LBR E4310
TEXTBOOK
Data Structures & Other Objects Using Java (3rd Edition)
by Michael Main
Published by Addison Wesley, 2005,
ISBN 0321375254
COURSE COMPONENTS
- Recitations - During recitation, you will be given problems to solve in groups. Your group will be responsible for coming up with solutions. You may be asked to explain your work to the rest of the class. Participation in your assigned group is essential to receive credit.
- 6 Programming Assignments - There will be 6 programming assignments which must be submitted electronically by the announced due date and time. All code must compile. Code that does not compile will not be graded. Assignments will be graded based on program performance and documentation. You may not submit any programming assignment late. Late programming work will not be graded. All program code that is submitted electronically must have the following information listed clearly in documentation (comments in your program code) at the beginning of each file:
- Your name
- Your SOLAR ID#
- The programming assignment number
- The course (CSE214)
- Your recitation number and TAs Name
- 3 Coding Exams - Coding Exams will test each student's ability to program using data structures in the Java programming language. These exams will be given in the Translab and in each exam, students will have 3 hours to complete 6 programming exercises on the computers there. Programs will be graded purely based on functionality. Programs that do not compile will receive no credit.
- Final Exam - The final exam will be a written, cumulative exam on all materials covered during the semester. This includes class lecture topics, homework assignments, and recitation materials. It will be given during the University's prescribed final exam time.
GRADING BREAKDOWN
| Recitation Exercises | 5 % | |
| 6 Programming Assignments | 30 % | (5% each) |
| 3 Coding Exams | 45 % | (15% each) |
| Final Exam | 20 % | |
| 100 % |
PROGRAMMING ASSIGNMENT PLATFORMS
This course will use the Java programming language for all 6 assignments. The Java programming environment for this semester will be the Open Source eclipse IDE, which includes a very useful debugger. Go to the eclipse download page to get your own free copy. eclipse will also be available to you in the SINC Site Labs.
Although you might have access to other Java programming environments installed on your PC or elsewhere, you are strongly encouraged to use the officially sanctioned programming environment for this course because it is the one that will be available in the room where the programming exam will be.
ACADEMIC DISHONESTY
Read This! You may discuss the assignments in this course with anyone you like, however each student's submission must be his or her own work, and only his or her own work. Any evidence that a submission has been copied, shared, or transmitted in any way between students, or has been downloaded from the Internet, or has been written by others in previous semesters will be regarded as evidence of academic dishonesty. Additionally, any evidence of sharing of information or using unauthorized information during an examination will also be regarded as evidence of academic dishonesty.
The College of Engineering and Applied Sciences regards academic dishonesty as a very serious matter, and provides for substantial penalties in such cases, such as receiving an `F' grade, or expulsion from the University. For more information, obtain a copy of the CEAS guidelines on academic dishonesty from the CEAS office.
Be advised that any evidence of academic dishonesty will be treated with utmost seriousness. Those involved will be prosecuted to the fullest extent permitted by the University and College laws. If you have a situation that may tempt you into doing something academically dishonest, resist the urge and speak with your instructor during office hours for help.
SPECIAL ASSISTANCE
If you have a physical, psychological, medical or learning disability that may impact on your ability to carry out assigned course work, I would urge that you contact the staff in the Disabled Student Services office (DSS) in the ECC building (where the Computer Store used to be), 632-6748v/tdD. DSS will review your concerns and determine with you what accommodations are necessary and appropriate. All information and documentation of disability are confidential.
If you need general computer help, you can use the Computer Science Help Desk. Services offered include setting up an account on a department server, using Windows NT, using a browser, and connecting to the campus network. The Help Desk office is located in the SBCS Office - Room 2110.
Web page created and maintained
by Richard McKenna