Chris Pollett >
Old Classes >

   ( Print View )

Grades: |Sec6|Sec8|

Course Info: Homework Assignments: Practice Exams:

Fall 2001 CS 146 Sec. 6 & 8 Home Page/Syllabus

Data Structures and Algorithms

Instructor: Chris Pollett
Office: MH 214
Phone Number: (408) 924-5145
Office Hours: MW 12-2pm F 1-2pm

Class Meets:
     Sec. 6 MW 4:00-5:15pm in MH 422 
     Sec. 8 MW 7:00-8:15pm in MH 423 


To take this class you must have taken CS 46B, Math 31 and Math 42 with a grade of C- or better. You should be competent in programming, testing, and debugging Java applications. Also, you should know to implement simple data structures such as (linked lists, trees, hash-tables, etc.)

To verify that you meet the prerequisite the coding part of the first assignment will serve as a prerequisite quiz. If you haven't added yet, you must complete the prequisite quiz before you can add.

Texts and Links

Required Texts: Data Structures & Algorithm Analysis in JAVA, by Mark Allen Weiss
Online References
& Other Links:
Sun's Java site .
The Java 2 Platform Class Library .


This class will describe in detail various techniques used in designing algorithms and determining how efficiently they run. We begin by discussing some of the mathematical ideas needed to reason about algorithms, as well as talk about recursion and exception handling in Java. We then review some simple ADTs such as lists, stacks, queues, and binary trees. More advanced trees which ``self-balance'' such as AVL and B-trees will then be considered. We then will focus on hashing and extendible hashing. After this, priority queues based on differing types of heaps will be investigated. Various sorting techniques such as quicksort and external sorting techniques will be described and analyzed. Next the Set ADT and directed and undirected graph algorithms as well as a little on P versus NP will be surveyed. We will conclude by examining different algorithm design strategies such as greedy, divide and conquer, and dynamic programming techniques.

Below is a tentative time table for when we'll do things this quarter:

Week 1: Aug. 27, 29 Read Weiss Ch. 1.
Week 2: Sept. 3 (no class), 5 Read Weiss Ch. 2.
Week 3: Sept. 10, 12(HW1 due) The 14th is drop day. Read Weiss Ch. 3.
Week 4: Sept. 17, 19 Read Weiss 4.1-4.4.
Week 5: Sept. 24, 26 Finish Weiss Ch.4.
Week 6: Oct. 1 (HW2 due), 3 Read Weiss 5
Week 7: Oct. 8, 10 Read Weiss Ch 6.1-6.3.
Week 8: Oct. 15, 17 (HW3 due) Finish Weiss Ch.6.
Week 9: Oct. 22, 24 (Midterm) Review for the midterm.
Week 10: Oct. 29, 31 Read Weiss 7.1-7.5.
Week 11: Nov. 5 (HW4 due), 7 Finish Weiss Ch. 7.
Week 12: Nov. 12, 14 Read Weiss Ch. 8.
Week 13: Nov. 19 (HW5 due), 21 Read Weiss 9.1-9.3
Week 14: Nov. 26 , 28 Finish Weiss Ch.9.
Week 15: Dec. 3 (HW6 due), 5 Read Weiss Ch 10.1 - 10.3
Week 16: Dec. 10 Review for final.
Final is in class Thursday, Dec. 13 2:45 - 5:00pm for Sec. 6 and Monday Dec. 17 7:45-10:00pm for Sec.8

Grade Breakdown / Grading Policy

Homeworks       40% 
Midterm         25%
Final           35%

When I assign grades the high score has an opportunity to receive an A+. I do curve grades and my curving will be in line with previous times this class has been taught.

Homework Info

General Info

Links to the current list of assignments can be found on the left hand frame of the class homepage. After an assignment has been returned a links to its solution will be placed off the assignment page. Each homework will consist of a reading part and a programming part. Material from the reading part of an assignment may appear on midterms and finals. Late homeworks will not be accepted; however, your low homework score will be dropped.

Submitting Programming Assignments

To keep things simple the files you submit for a homework assignment will follow the naming convention cs146sec+number hw+number+file+number+.extension. For example: for the first file in HW1 for section 6. To turn in your homework you simply e-mail me the file as an attachment to the address:

Make sure the title is in the format:
cs146sec+number hw+number lastname last_four_digits_of_student_id.
For example, if I were to submit hw1 in section 6 I would have as title:
cs146sec6 hw1 pollett 1234
Notice this is all lower case.


If you believe an error was made in the grading of your program or exam, you may request in person a regrade from me, Professor Pollett, during my office hours. I do not accept e-mail requests for regrades. A request for a regrade must be made no more than a week after the homework is returned.

Required Formatting

Since some of the grading process will be automated, it is important that your program follow the specifications in the assignment exactly. In particular, make sure submitted filenames are correct, you use the correct title in the mail message, and data items in your program are inputted and outputted in the proper sequence and format.

Your code should conform to the Departmental Java Coding Guidelines.


As shown above in the grade breakdown there will be both a midterm and final in this course. The midterm will be during class time on Oct. 24. The final will be Thursday, Dec. 13 2:45 - 5:00pm for Sec. 6 and Monday, Dec. 17 7:45-10:00pm for Sec.8 in this classroom. Both of these are closed book, closed notes. You will be allowed only the test and your pen or pencil on your desk during these exams. Beeper or cell-phone interruptions will result in immediate excusal from the test. The final will cover material from the whole quarter although there will be an emphasis on material after the midterm. No make up midterms will be given. The final exam may be scaled to replace the midterm if the midterm was missed under provably legitimate circumstances. These exams will test whether or not you have mastered the material both presented in class or assigned as homework during the quarter. My exams usually consist of a series of essay style questions. I try to avoid making tricky problems. The week before each exam I will give out a list of problems representative of the level of difficulty of problems the student will be expected to answer on the exam. Any disputes concerning grades on exams should be directed to me, Professor Pollett.

Academic Honesty

You are both allowed and encouraged to discuss general algorithms and approaches to programming problems with your classmates. But these discussions must remain at a high level and not involve actual code being exchanged. In particular, the code you submit as a solution to an assignment must be your own. Outright plagiarism or cheating on tests will result in appropriate academic disciplinary action being taken. Information on the university policy governing academic dishonesty can be found at