Department of Computer Science University of San FranciscoComputer Science 245-01Data Structures and AlgorithmsSpring 2005Professor: Peter PachecoOffice: Harney 540Phone: 422-6630Email: [email protected] Hours: MW 5:30–7:00 and by appointmentTA: Anna TikhonovaEmail: [email protected]: A C or better in Computer Science 112, Introduction to Computer Science II, andMathematics 322, Discrete Mathematics. Knowledge of the Java programming language.Text: Clifford A. Shaffer, A Practical Introduction to Data Structures and Algorithm Analysis,Java Edition, Prentice Hall, 1998.Class Website: http://cs.usfca.edu/peter/cs245Class Mailing List: http://cs.usfca.edu/mailman/listinfo/cs245. To subscribe, go to thiswebsite and type in your full preferred email address.Coursework and Grades: I will base your final grade on eight homework assignments, fourprogramming assignments, two midterms, and a final exam, weighted as follows.Homework 1.5% each 12%Program 1 5%Programs 2–3 8% each 16%Program 4 12%Midterms 15% each 30%Final Exam 25%Total 100%I will assign grades on a straight scale. Roughly, 90-100% is an A, 80-89% is a B, 65-79% is a C,55-64% is a D, and 0-54% is an F.Homework: Homework assignments may involve coding and/or written work. Due datesare listed in the following course outline. Electronic copies of your code should be copied toyour submit directory by 3 pm on the due date. Hardcopies of your c ode and your writtenwork should be turned in at the beginning of class.There will be 10 homework assignments. Only your best 8 scores will be counted in thecalculation of your final average. Late assignments will not be accepted.1Programs: Unless otherwise specified, programs should be written in Java. Electroniccopies should be submitted by 3:00 pm on the dates indicated in the following course outline.Hardcopy should be turned in to m e by 6 pm of the due date. Late programs that aresubmitted within 24 hours of the due date will lose 50% credit. Programs submitted morethan 24 hours late will receive no credit.Guidelines for grading will b e included with the assignments. Your programs will be testedon USF CS department machines. So if you develop your program on another system, besure that it works on a CS department machine before you submit it.Midterms: The midterms will b e given in class on Wednesday, March 9, and Wednesday,April 27. They are closed book, closed notes.Final Exam: The final exam will be given on Wednesday, May 18, at 8 am in Harney 235.The final exam is also closed book, closed notes.Class meetings: Typical class meetings will be divided into two segments with a five or ten minutebreak in between segments.Attendance: There is no attendance requirement. However, if you miss a class you will still beresponsible for all the material covered, and I expect to cover material that is not covered in thetext.Academic Honesty: It is fine for you to discuss homework and programs with your classmates.Any other collaboration is unacceptable. In particular, copying another person’s work is unaccept-able. Students who violate these rules will receive an F in the course. Repeat violators may besubject to more severe penalties.Computer Access: You may use any of the Computer Science Department computers in Harney235, 530, 535, and 536. You do not need to own a computer for this class.Learning Outcomes: In this course students will learn1. How to implement a variety of important abstract data types,2. The costs and benefits associated with these implementations, and3. How to assess the needs of an application so that appropriate implementations are chosen.2Tentative Course OutlineWeek Material1/24–1/28 Preliminaries. Data Structures and Algorithms.1/31–2/4 Review of algorithm analysis, lists,stacks and queues.Homework 1 due, Monday, 1/312/7–2/11 Trees, binary trees, binary search trees.Program 1 due, Wednesday, 2/9.2/14–2/18 Heaps and priority queues.Homework 2 due, Monday, 2/14.2/21–2/25 General trees.Homework 3 due, Wednesday, 2/23.2/28–3/4 Graph implementations and traversals.Program 2 due, Wednesday, 3/2.3/7–3/11 Shortest path algorithms.Homework 4 due, Monday, 3/7.Midterm 1, Wednesday, 3/9.3/14–3/18 Minimum-cost spanning trees.Homework 5 due, Monday, 3/14.3/28–4/1 Θ(n2) sorting algorithms.Homework 6 due, Wednesday, 3/30.4/4–4/8 Shellsort, quicksort, and heapsort.Program 3 due, Wednesday, 4/6.4/11–4/15 File processing.Homework 7 due, Monday, 4/11.4/18–4/22 External sorting.Homework 8 due, Monday, 4/18.4/25–4/29 Searching and hashing.Homework 9 due, Monday, 4/25.Midterm 2, Wednesday, 4/27.5/2–5/6 B-trees.Program 4 due, Wednesday, 5/4.5/9–5/13 Algorithm performance and cache.Homework 10 due, Monday,