ECS 60

Course Syllabus

Spring 2012

Instructor: Michael Neff, Assistant Professor neff [at] cs [dot] ucdavis [dot] edu 3031 Kemper Hall Office Hours: Tues. 3:30-4:30, Thurs. 11:00-11:50

Teaching Assistant: Alfredo Gimenez alfredo.gimenez [at] gmail [dot] com Office hours will be in the instructional labs in the CSIF (53 Kemper). Office Hours: Tues., Thurs. 2:00-4:00

Web page: http://www.cs.ucdavis.edu/~neff/ teaching/ecs60s12/index.html

This course will use SmartSite discussion forums for class discussion.  There are two separate forums, one for discussion of class material and one for discussion of assignments.  There are separate topics set up for each assignment. Please post your questions to the appropriate section.  Both the TA and instructor will monitor the forums and reply, generally within 24 hours.  The discussion forums are a great way to ensure that all class participants have the same information and clarify any misunderstandings that arise during the course.

E-mail to Prof. Neff should only be regarding personal matters (e.g. an illness) and should have “[ECS 60]” in the subject line.  All course and assignment questions should be posted to the discussion forum.

Required Materials:  Weiss, Mark Allen, Data Structures and Algorithm Analysis in C++, 3^rd ed., Berkeley, CA: Addison Wesley, 2006.

Prerequisites:  ECS 20 and ECS 40 or equivalents with grade of C- or better.

Course objectives:

1. Students will be able to apply algorithm analysis to the operations on data structures and interpret the results.
2. Students will be able to understand and evaluate the operations and possible implementations of the following abstract data types: lists, stacks, queues, binary trees, AVL trees, splay trees, B-trees, hash tables, and heaps.
3. Students will understand the operation and characteristics of the following sorting algorithms: insertion sort, shellsort, heapsort, mergesort, quicksort, bucketsort, and external sorts.
4. Students will understand the operation and application of graph algorithms including depth first search, breadth first search, shortest path and minimum spanning tree.
5. Students will be able choose (and justify) appropriate data structures and algorithms for complex programming tasks.

Course Grading

Programs	50% (10% per assignment)
Midterm exam	20%
Final exam	30%
Class effort/participation	up to 5% bonus

Letter grades will be approximately: A = 90+% ; B = 80-89%; C = 70-79%; D = 60-69%; F <60%

Work Input/Output

• Programs: Collaboration is an important part of computer science and your fellow students are an important resource in your learning.  You are actively encouraged to discuss the course material, help each other with debugging, etc.  However, each student/group must write their own code.  Programs that do not compile will receive no credit.  Certain assignments may be submitted to the MOSS program at UC Berkeley for plagiarism analysis. Students that hand in suspicious programs may be reported to Student Judicial Affairs.

This course will feature both group and individual programming assignments.  Each assignment will be clearly marked.  For group assignments:

· Students should work together in groups of two people to write the programs. Each group must write their own code.  The names of both group members must appear on the first line of each file. Program source code will be submitted using the handin facility of UNIX by midnight on the date due. Each group will submit all of its programs to the handin directory of exactly one of its members.

For individual assignments:

· Students may engage in general discussions about the problem, but each student must write their own code.  The name of the student must appear on the first line of each file.  Program source code will be submitted using the handin facility of UNIX by midnight on the date due.  Some work may be submitted to the homework box, as directed.

• Silent Running:  For each assignment in the course we will use something called silent running.  This means that the TA and instructor will not answer any questions received within 26 hours of the due date of an assignment (i.e. after 9:59pm the day before).   There are two reasons for this: 1) to encourage you to work on the assignments early and 2) to ensure that all students have the same information a day before the assignment is due.  You are free to continue to answer each others’ questions on the newsgroup, but we will not read it during this period.
• All work: Late work will NOT be accepted without a doctor's excuse.  All work will be returned in lecture.  All work not picked up in class will be available in my office during office hours.

Lectures

TR 4:40-6:00pm in 217 Art.

Discussions

F 2:10-3:00pm in 217 Art.

Exams

Exams are cumulative, closed book, closed notes. 

Tentative Schedule

Dates	Subjects	Reading
4/3	Intro, math review, induction, complexity.	Chapter 1,2
4/5	Complexity (cont’d), ADTs, lists, skip lists.	Chapter 2, 3.1, 3.2, 10.4.2, 12.3
4/10	Stacks and queues; general trees	Chapter 3.3, 3.6, 3.7, 4.1
4/12	Trees cont’d:  Binary trees, search trees, tree traversals, AVL trees	Chapter 4.2, 4.3, 4.4,4.6
4/17	Trees cont'd: Splay trees, with amortized analysis, B-trees.	Chapter 4.5, 4.7, 11.5
4/19	Hashing: idea, hash functions	Chapter 5.1-5.2
4/24	Hashing cont'd: separate chaining, open addressing, rehashing, extendible hashing	Chapter 5.3, 5.4, 5.5, 5.6
4/26	Hashing wrap-up; Priority Queues: binary heap, heap applications.	Chapter 6.1-6.4
5/1	d-heaps, leftist heaps, skew heaps with amortized analysis.	Chapter 6.5-6.7, 11.3
5/3	Binomial queues with amortized analysis, and lazy merging.	Chapter 6.8, 11.2, 11.4.2
5/8	Disjoint Set: intro and basic data structures, smart union, path compression, analysis	Chapter 8.1-8.6
5/10	Disjoint Set cont’d.; Review
5/15	Midterm	None
5/17	Graph Algorithms: Definitions, topological sort, shortest path algorithms	Chapter 9.1-9.3
5/22	Graph Algorithms cont’d: Network flow, minimum spanning tree.	Chapter 9.4-9.5
5/24	Graph Algorithms cont'd: DFS and catch-up.	Chapter 9.6
5/29	Sorting: insertion sort, lower bound, shellsort, heapsort	Chapter 7.1-7.5
5/31	Sorting: mergesort, quicksort	Chapter 7.5-7.7
6/5	Sorting: indirect sorting, lowerbound, bucket sort, radix sort, external sorting	Chapter 7.8-7.11
6/7	Review