COMPSCI 342 Home Page

COMPSCI 342 -Data Structures and Algorithms

Spring 2009
Tue. Thu. 2:40pm - 4:30pm
MEC 106

Catalog Description
Prerequisites by topic
Objectives
Textbook
List of sections covered from the text
Programming Examples
Grading and Examination Dates
Homework
Class Mailing List
Programming Assignments
Handouts
Relevant Web Links
Office hours.

Catalog Description

COMPSCI 342 DATA STRUCTURES AND ALGORITHMS (4-0-4)(F/S). Basic data structures (continued from COMPSCI 225), introduction to design and analysis of algorithms, fundamental algorithms for sequences, sets, graphs and combinatorial problems, introduction to complexity of problems. Examples are drawn from various areas of computer science. PREREQ: COMPSCI 225 and MATH 187 and MATH 170 or PERM/INST.

Prerequisites by topic

Computation of summations and probability (basic exposure).
Recursion.
Sorting algorithms.
Some basic data structures (stacks, queues, lists).
Familiarity with Java.

Objectives

By the end of this course:

Each student will be able to choose the most efficient algorithms to solve well-known problems. The students will be able to do running time analysis to choose the most efficient algorithm.

Each student will be able to choose appropriate data structures to implement algorithms.

Each student will be able to design recursive solutions to solve problems by the divide-and-conquer technique, and will be able to evaluate the solution's running time through recurrence equations.

Each student will be able to design solutions to solve optimization problems using dynamic programming or greedy approach.

Each student will have gained experience working in a team environment.

Each student will have gained further experience with an Integrated Development Environment, continuing from COMPSCI 225. This includes debugging techniques as well as testing techniques.

Textbook

Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.

List of Topics

Foundations

Chapter 1. Sections 1.1, 1.2.
Chapter 2. Sections 2.1, 2.2, 2.3.
Chapter 3. Sections 3.1, 3.2.
Chapter 4. Sections 4.1, 4.2, 4.3.

Sorting and Order Statistics

Chapter 8. Sections 8.2, 8.3, 8.4.
Chapter 6. Section 6.1, 6.2, 6.3, 6.4, and 6.5.
Chapter 7. Review.
Chapter 9. Sections 9.1, 9.2 (except the average-case analysis).
Chapter 8. Section 8.1.

Data Structures

Chapter 10. Sections 10.3, and 10.4.
Chapter 11. Sections 11.1, 11.2, 11.3.1, 11.3.2, and 11.4 (except the analysis on pages 241-244).
Chapter 12. Review Sections 12.1, 12.2, and 12.3.
Chapter 13. Sections 13.1, 13.2, 13.3 and 13.4.
Chapter 18. Section 18.1, 18.2, 18.3.
Chapter 21. Section 21.1, 21.2, and 21.3

Graph Algorithms

Chapter 22. Section 22.1, 22.2, 22.3, 22.4.
Chapter 23. Section 23.1, 23.2.
Chapter 24. Section 24.1, 24.2, 24.3.

Dynamic Programming and Greedy Algorithms

Chapter 15. Knapsack problem (from notes), Section 15.2, 15.3, 15.4.
Chapter 16. Section 16.1, 16.2, 16.3.
Chapter 17. Section 17.4.

Miscellaneous Topics

Chapter 32. Section 32.1, 32.2, 32.3.
Chapter 34. One lecture on NP-completeness.

Grading

Homework and Programming Assignments: 500 points (50%).
First Examination (18th March) : 150 points (15%).
Second Examination: 150 points (15%).
Final Examination (11th May, 3:30pm-5:30pm): 200 points (20%).

Class Mailing List

You can join the class mailing list by sending email to: majordomo@cs.boisestate.edu with the following line in the message:

    subscribe cs342

To send email to mailing list, send email to cs342@cs.boisestate.edu or simply to cs342 on onyx

If you ever want to remove yourself from this mailing list, you can send mail to majordomo@cs.boisestate.edu with the following
command in the body of your email message:

    unsubscribe cs342

or from another account, besides the machine from which you joined:

    unsubscribe cs342  <complete email address from where you joined>

If you ever need to get in contact with the owner of the list, (if you have trouble unsubscribing, or have questions about the list itself) send email to owner-cs342@cs.boisestate.edu

Homework

All homeworks are due in class.

Solutions (requires a password)

Homework 1 (30 points). Due date 2/4/2009.
Homework 2 (15 points). Due date 2/11/2009.
Homework 3 (36 points). Due date 2/25/2009.
Homework 4 (30 points). Due date 3/16/2009.
Homework 5 (20 points). Due date 4/15/2009.

Programming Assignments

All programming assignments are available in PDF formats.

All assignments are due by 11pm on the due date. You may submit assignments up to 48 hours late for a 10% penalty without asking for permission.

IMPORTANT Instructions on setting up your directories, submitting your programs etc.

Program 1 (Object Cache). 60 points. Due date 2/19/2009.
Program 2 (Radixsort). 60 points. Due date 3/11/2009.
Program 3 (Bioinformatics using B-Trees). Due date 4/20/09 (10% off late deadline now 4/24/2009).
Reprise 5/18/2009 by noon.
Program 4 (Graphs and Social Networks). Due date 5/8/2009. (10% off late deadline now 5/13/2009).

Handouts

Java Generics Tutorial
Exam 1 review and practice problems
Lyrics of the song ``Hole in the Bucket''.
Handout on the Maximum subvector problem.
Handout on the Disjoint Sets problem.
Knapsack problem.
Sample in-class exam. (PDF)
Sample take home exam. (PDF)
Sample in-class exam (PDF)
Sample in-class final exam (PDF)
Sample take-home part of the final exam (PDF)
Programming Style Tips. (pdf )
Subversion Lecture notes.

Relevant Web Links

Useful page on algorithms with examples from various application areas: http://www.cbtplanet.com/articles-tutorials/the-development-and-use-of-computer-algorithms.htm (Thanks to Sara Davis for sending this link)
Local Linux guide (html, postscript, pdf)
2-3-4 Tree Animation
Brief primer on DNA structure.
(borrowed from http://projects.edtech.sandi.net/miramesa/DNAproject/structure.html)

Last update: Fri Apr 17 11:12:44 MDT 2009
Send comments to amit@cs.boisestate.edu