Fall Term 2015 COSC 160 Data Structures Instructor : Professor Bala Kalyanasundaram TA : Office : St. Marys Rm 329 Office : Office hrs : Mon & Wed Hours : 11 - 12:30 p.m. (or whenever I am free) Phone : 687-2709 Phone : TEXT : 1. Data Structures and Algorithm Analysis in C++ by Weiss 2. Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein 3. Data Structures and Algorithms in C++ by Goodrich, Tamassia and Mount GRADING : EXAMS First and Second ( approx. 25%,25%) NO MAKE-UPs PROGRAMMING There are approximately 3-4 programming ASSIGNMENTS assignments or written assignments or quiz ( approx. 50%) * All programs are due before the class BEGINS on the day they are due * 15% penalty per day for late submission. EMPHASIS : To learn how to organize a large amount of data so that computer programs can access, modify or add data efficiently. We also learn algorithm design and analysis. Topics covered are basic data structures, algorithm analysis (worst-case, average-case), trees, hashing, heaps, sorting and disjoint sets. We will also cover basic algorithm design techniques such as greedy and divide and conquer. Time permits, we will also cover some advanced data structures. All subject to time constraints!!! SYLLABUS : (tentative) September - Algorithm analysis, quick review of lists, stacks and queues. Intro. to trees. October - Trees continued. AVL trees, Splay trees and B-Trees. (see Weiss Book) November - Sorting, Disjoint Set, Basic Algorithm Design Techniques - Revisit Recursion and Recurrence Relations. December - Basic well known algorithms, Amortized Analysis, Advanced Data Structures. PREPARATION: The system used for this course is a PC or a Mac. IMPORTANT : STUDENTS ARE RESPONSIBLE FOR LEARNING AND USING VARIOUS/ALL FEATURES OF C++. Instructor assumes that students are very comfortable in C++ programming: especially pointers, recursion and object oriented programming. Many programming assignments will be given during the semester. Exact deadline will be specified in the assignment sheet. For late submission, you will lose 15% of the grade for each day after the deadline. Collaboration is NOT allowed. Cheating of any form will NOT be tolerated. Any form of cheating, copying or collaboration will be reported to the honor council of GU. However, students are allowed to discuss content of the assignment, general methodology, and mundane questions such as syntax etc. Students are not allowed to share codes or write code/solution for others. Each programming assignment should be well documented. It must be thoroughly checked for correctness by running it on your test data. In the case of a written assignment, I suggest that you type your answer and submit a printout. I use the following rule: "If I can't read and understand your answer then it must be wrong". Students are responsible for all instructions, exam announcements and assignments given during REGULAR CLASS hours. Makeup exams will NOT be given. If you have trouble in taking the exam you must tell the instructor well in advance - not a week before the exam. Depending on the progress of the class, surprise quizzes may be given during regular class hours. No Make-ups. Feel free to ask questions in the class or during regular office hours of the instructor/TA. If you can not meet during regular office hours then set an appointment.