CS25100: Data Structures and Algorithms, Spring 2012

Section 1: TTh 1:30-2:45 pm, LWSN B155, Prof. Sonia Fahmy

Section 2: TTh 10:30-11:45 am, LWSN B155, Prof. Xavier Tricoche

Schedule • Assignments

Instructors

Sonia Fahmy
Email: fahmy[at]cs.purdue.edu
Tuesdays, Thursdays 1:30-2:45 pm
Office: LWSN 2142H
Phone: (765) 494 6183
Office hours: Tuesdays, Thursdays 3:15-4:10 pm;
Wednesdays 11 am-12 noon, or by appointment
 Xavier Tricoche
Email: xmt[at]cs.purdue.edu
Tuesdays, Thursdays 10:30-11:45 am
Office: LWSN 3154P
Phone: (765) 496 9416
Office hours: Tuesdays, Thursdays 12 noon-1 pm;
Wednesdays 11 am-12 noon, or by appointment

Teaching assistants

Purnima Kapoor
Email: cs251-ta@cs.purdue.edu
Office: LWSN B116J
Office hours: M 1:30-2:30 PM
PSO: M 3:30-5:20 PM
 Yanshan Lu
Email: cs251-ta@cs.purdue.edu
Office: LWSN B116E
Office hours: Th 4:30-5:30 PM
PSO: M 11:30 AM-1:20 PM
Rahul Nanda
Email: cs251-ta@cs.purdue.edu
Office: LWSN B116E
Office hours: Th 3:30-4:30 PM
PSOs: W 3:30-5:20 PM, F 9:30-11:20 AM
 Ruby Tahboub
Email: cs251-ta@cs.purdue.edu
Office: LWSN B116B
Office hours: T 5:30-6:30 PM
PSOs: F 11:30-1:20, 3:30-5:20 PM

All PSOs are held in LWSN B146, except for the Friday 3:30 afternoon PSO, which will be held in LWSN B158.

Description

This course provides an introduction to the theoretical and practical aspects of data structures and algorithms. Topics will include: fundamental data structures (e.g., arrays, stacks, queues, trees, hash tables, graphs), fundamental algorithms (e.g., sorting, pattern matching, topological sorting, shortest path, minimum spanning tree), and their implementations (e.g., asymptotic and average running time analysis, pointer-based implementation of trees, and adjacency matrix implementations of graphs).

Prerequisites

CS24000: Programming in C.

Text

R. Sedgewick and K. Wayne (2010). Algorithms. Addison-Wesley, 4th edition. The web site for the book that includes code snippets can be found here.

Assignments and exams

There will be two written homework assignments.

There will be six programming assignments. Programming assignments should be written in Java or C++, unless otherwise noted. Assignments should be submitted on lore using "turnin." Details will be provided in the assignments.

In general, questions about the details of assignments should be directed to the Blackboard discussion group for general questions, or to the TAs/instructors (via the joint email list cs251-ta@cs.purdue.edu) for questions specific to your assignment, though you should feel free to email the instructor directly.

There will be several unannounced in-class quizzes as well as a midterm exam and a comprehensive final exam. Exams and quizzes will be closed book and closed notes.

Grading

Grades will be posted on Blackboard. If you think a grading error was made on an assignment or test, or if you do not receive a homework assignment or exam back, you must talk to the TA or the instructor within a week of when it was returned.

Late policy

Assignments are to be electronically submitted by the due date listed. Each person will be allowed four days of extensions which can be applied to any combination of assignments during the semester without penalty. After that a late penalty of 20% per day will be assigned. Use of a partial day will be counted as a full day. Use of extension days (including number) must be stated explicitly in the subject line of an email to the TAs, otherwise late penalties will apply. Extensions cannot be used after the final day of classes (i.e., April 28th). Extension days cannot be rearranged after they are applied to a submission. Use them wisely! Assignments will NOT BE accepted if they are more than five days late (regardless of whether extension days will be applied to that particular assignment or not). Additional extensions will be granted only due to serious and documented medical or family emergencies.

Academic honesty

Please read the departmental academic integrity policy. This will be followed unless we provide written documentation of exceptions. However, we encourage you to interact amongst yourselves: you may discuss and obtain help with basic concepts covered in lectures or the textbook, homework specification (but not solution), and program syntax issues (but not program design). However, unless otherwise noted, work turned in should reflect your own efforts and knowledge. Sharing or copying solutions is unacceptable and could result in failure. Do not copy code and then make changes (either from the Web or from other students). You are also expected to take reasonable precautions to prevent others from using your work. Be aware that we will use a software tool called MOSS (http://theory.stanford.edu/~aiken/moss/) to check for copying among submitted assignments. Additionally, the instructors and TAs will be inspecting all submitted material to ensure honesty. Any case of academic dishonesty will be dealt with by a severe grade penalty in the overall class grade and referral to the office of the Dean of Students.

Discussion group

Questions/comments should be posted on the discussion forum on Blackboard.
Make sure that you check the discussion group and your Purdue e-mail (we will use a course email list for important announcements) *frequently* (at least once or twice per day). Please do NOT post answers to the assignments on the discussion group, though posting general clarifications is fine. Complaints about the assignments or the class should NOT be posted to the group-- instead, they should be e-mailed to the joint TA/instructor email list cs251-ta@cs.purdue.edu

Additional course policies

Please read the general course policies here.

Counseling

If you are experiencing personal problems or stress, Purdue provides counseling services through the Purdue CAPS Center. See https://www.purdue.edu/CAPS/ for more details.

Course topics

Introduction and review
Proof methods and mathematics concepts.

Program analysis
Running time analysis of algorithms and their implementations, including asymptotic and average time analysis.

One-dimensional data structures
Bags, stacks, queues. Abstract data types and their implementation.

Trees
Tree data structures, including properties, implementation, and traversal.

Heaps
Heap data structures, including properties, implementation, and construction.

Sorting algorithms
Comparison-based sorting (e.g., merge sort) and non-comparison based (e.g., bucket sort).

Search trees
Binary search tree data structures, including properties, implementation, and construction.

Hash tables
Data structures, including properties and implementation, as well as performance characteristics.

Pattern matching and text processing
Strings, Boyer-Moore algorithm, tries, Huffman's algorithm.

Graphs
Graph data structures, including properties, implementation, and search.

Directed graphs
Graph algorithms, including connected components, transitive closure, and topological sorting.

Weighted graphs
Shortest path and minimum spanning tree algorithms.

Additional selected topics
As time permits.