View the sample final here.

The tree diagrams are in this pdf.

solutions for the sample final here

solutions for problem set 5 here

University of Denver Home Page DU Department of Computer Science Home Page   Home Page for Catherine Durso  

Algorithms and Data Structures, fall 2012
Course Information and Syllabus

Assignments

Instructor:

Catherine Durso
(email cdurso"AT"cs"DOT"du"DOT"edu)
Office: JGH 106 303 871 3598
Office Hours: Tuesday 2:00-4:00pm, Thursday 1:00-3:00pm
and by appointment

TA:

Brian Passeullo
(email passuell"AT"cs"DOT"du"DOT"edu)
Office: JGH 327
Office Hours: Monday 2:00-4:00pm, Friday 1:00-3:00pm

About This Course

This course presents some fundamental data structures, including lists, stacks, queues, hashes, and binary trees. Students will master a number of algorithms including Mergesort and Quicksort. We will study techniques for analyzing the running time and space requirements of these algorithms, and of other algorithms based on the data structures. The goals for the course are for the students to analyze running times of algorithms, and to design algorithms using appropriate data structures to solve non-trivial computing problems.

The material in this course should provide students tools to approach more sophisticated programming problems than previous courses have presented.

There will be approximately weekly assignments of pencil-and-paper exercises. The assignments will consist of basic exercises, not to be handed in, with solutions available, and a small number of exercises to be completed and handed in.

There will be a programming assignment in which students implement and test applications of techniques adressed in class. These assignments may be done in C, C++, or Java.

Course Meeting Times

The lecture for section 1 is held 10:00-11:50am MW in JGH 316.

  The midterm for this section is on Wednesday, October 17, at 10:00-11:50am

  The final for this section is on Monday, November 19, at 10:00-11:50am

The lecture for section 2 is held 10:00-11:50 TR in JGH 216.

  The final for this section is on Tuesday, November 20, at 10:00-11:50am

  The midterm for this section is on Thursday, October 18, at 10:00-11:50am

Text

Introduction to Algorithms, ed. 3, Cormen, Leiserson, Rivest, and Stein

Syllabus

We will cover sections 1, 3, and 2, in that order, at a depth dictated by time and interest. We will cover B-trees, chapter 18, and expressions trees.

Week 1:Chapter 1 and Chapter 2
Introduction, Chapter 2
Week 2:Chapter 2
Chapter 2, Chapter 3
Week 3:Chapter 3
In class exercise, Chapter 4
Week 4:Chapter 4, Thursday Problem session
sage advice, additions welcome
Week 5: More Chapter 4
Week 6:Chapter 5 Introduction, and Midterm
Chapter 5
Week 7:Chapter 10
Chapter 10
Week 8:Chapter 10, 11
Chapter 11
Week 9:Chapter 12, 13
Chapter 12,Chapter 13
Week 10:Chapter 18, 17
Chapter 18, diagrams for Chapter 18, Chapter 7

Grading

Grades in this course will be calculated as follows:
homework30% total
in-class exam 20%
programming assignment30%
final 20%

Collaboration and Academic Honesty

When you turn in work in this course, you are implicitly agreeing that you have followed the rules for collaboration set forth for that assignment. In general,

Instructions for Homework Assignments

You may certainly type your solutions, however, handwriting is acceptable as long as I find it to be readable, understandable and organized. Please turn in paper copies in class on the due date. Assignments will be posted here.

Note that solutions to some exercises and problems can be found on links from the online supplement to the text . You may consult these solutions.

Exercises appear in the text after most sections. They are labeled chapter.section-exercise. For example, the third exercise from the second section of chapter 5 is 5.2-3.

Problems are listed at the end of each chapter. They are labeled with the chapter and the problem number. For example, the sixth problem from chapter 3 is 3-6.

Assignments will typically include a few exercises for you to do as warmup, not to be turned in, and one or two problems to hand in.

Homework Assignments

Problem set 1, assigned day 2, week 1, due day 2, week 2
Do, but do not hand in:
Exercise 2.1-1,
Exercise 2.2-1, 2.2-2
To hand in:
problem 1 10 points

Problem set 2, assigned day 2, week 2 (Sept. 17-21), due day 2, week 3, (Sept. 24-28)
Do, but do not hand in:
Exercise 2.3-1, 2.3-5, 2-4
To hand in:
1. (5 points) Problem 2.3-4
2. (5 points) Problem 2.3-7

Problem set 3, assigned day 2, week 3, due Thursday, October 4, week 4
(You may hand it in during the joint problem session in JGH 216 10:00-noon on Thursday, or put it in my box by 5:00pm Thursday.)
Do, but do not hand in:
Exercise 3.1-1, 3.1-2, 3.2-3(from first principles)
To hand in:
1. (5 points) Problem 3-2
1. (5 points)Problem 3-4 a, c, d, h

Problem set 4, assigned day 2, week 4, due day 1, week 6, October 15 or 16
Do, but do not hand in:
Exercise 4.1-1, 4.1-5, 4.4-6, 4-2a
To hand in:
1. (5 points) Problem 4.4-4
1. (5 points) 4-1

Programming Problem 1, due Nov. 6
programming problem 1
Please note that the analysis is due Monday, November 5 for the MW class and Tuesday, November 6 for the TuTh class.
You may use the sample data points.dat. This is a text file. The output should be
-2.00 6
0.25 2
There is additional sample data in points.txt. This is a text file. You will have to change the extension to fit the assignment description. Using the convention that a vertical line has slope Infinity, and the x-intercept is reported instead of the y-intercept, the output should be
-3.0000000 6
0.3333333 -1
Infinity 2
Problem set 5, assigned day 2, week 7,October 24 or 25, due day 2, week 8, October 31 or November 1, respectively
Do, but do not hand in:
Exercise 5.2-2, 5.2-5, 10.1-1
To hand in:
1. (5 points) Problem 5.3-3 (hint: consider n=3 carefully)
2. (5 points) Problem 10.1-2
3. (5 points) Suppose you start with an array of size 1. You insert n elements using the following strategy: Whenever the array is full, you allocate an array of twice the size of the current array and write the current elements into the new array. If there are k elements in the array, this is k writes. Give a big-Theta bound on the total number of 'writes' required to insert n elements. (Hint: consider n=2^m.)
Problem set 6, assigned day 2, week 7, due day 2, week 8, Nov. 7 or 8
Do, but do not hand in:
Exercise 10.1-1, 10.1-3, 10.1-4,10.2-1, 10.2-2,10.3-1, 10.4-1,10.4-2,10.6-6
To hand in:
1. (5 points) 10-1 Please interpret x as a node, k as a value, SUCCESSOR and PREDECESSOR as the next larger and next smaller values, and use sentinel node implementation.
1. (5 points) 11.2-2

Programming Problem 2, due Nov. 17
programming problem 2
Please note that the description is due on the day of your final.

Problem set 7, assigned day 2, week 9, due day 2, week 10, Nov. 14 or 15
Complete the sample final. Solutions will be posted on Nov. 16, so late work won't be accepted.