Aviral Shrivastava: Teaching: CSE 310
CSE 310: Data Structures and Algorithms
Catalog Description
Advanced data structures and algorithms, including stacks, queues,
trees (B, B+, AVL), and graphs. Searching for graphs, hashing, external sorting.
Pre-requisites
Computer Systems Engineering BSE, Computer Science BS, Computational
Math Sciences BS or Biomedical Informatics BS student; CSE 205 with C
or better; MAT 243 with C or better (CMS students may substitute MAT
300) or CSE Graduate students.
Course Abstract
Data Structures and Algorithms is a fundamental course to CSE majors.
Students will learn important techniques to store data and to process
data efficiently. Data structures and algorithms cannot be separated.
On one hand, good data structures help in the design of efficient
algorithms. On the other hand, good data structures are discovered
during the design of efficient algorithms. This course will cover
three main concept areas i) Complexity analysis of algorithms, ii)
Recursive Algorithms, and iii) Sorting and graph algorithms.
This course requires a lot of work. Depending on different knowledge
levels the students may have, all students may not be required to
spend the same amount of time on this course.
Every student is encouraged to preview before the class and review
immediately after the class.
Students are encouraged to ask questions in class, and to fully use
the office hours of the instructor and the TAs.
Students may also ask questions via email to the instructor and/or the
TAs.
There will be closed book tests and many heavyweight homeworks.
Homeworks may involve theoretical contents as well as programming
contents.
The instructor will also assign suggested readings/exercises after
each lecture.
Textbook
Cormen, T. H., Leiserson, C. E., and Rivest, R. L., C. Stein,
Introduction to Algorithms, 2nd edition, McGraw Hills and MIT Press.
ISBN-10: 0262032937 ISBN-13: 978-0262032933.
Prerequisites
CSE205 (programming in C or C++), MAT243 (theorem proving)
Grading
- 6 Homeworks (5% each): Total 30%
Will be given on Monday, and to be submitted next Monday in class.
Can be programming assignments. Preferably use C/C++.
- 2 Midterm (20% each): Total 40%
Closed books/notes/internet 2 1/2 hour in-class exam
- 1 Final (30%): Total 30%
Comprehensive Exam
Course Learning Outcomes
Students who complete this course can:
- define data structures (types) such as heaps, balanced trees, hash tables.
- explain how to use a specific data structure in modeling a given problem (e.g. I can explain how to model a dictionary using balanced trees).
- identify, construct and clearly define a data structure that is useful for modeling a given problem.
- state some fundamental algorithms such as merge sort, topological sort, Prim's and Kruskal's algorithm, and algorithmic techniques such as dynamic programming and greedy algorithms.
- use a specific algorithmic technique in solving a given problem (e.g. I can write a dynamic program that solves a shortest-path problem).
- design an algorithm to solve a given problem.
- define the notions of worst-case/best-case/average-case running times of algorithms.
- analyze and compare different asymptotic running times of
algorithms.
- analyze a given algorithm and determine its asymptotic running time.
- combine fundamental data structures and algorithmic techniques in building a complete algorithmic solution to a given problem.
- create several algorithmic solutions to a given problem and choose the best one among them according to given requirements on time and space complexity.
Major Topics and Time Covered
- Asymptotic Notation (1.5 hrs)
- Recursion, recurrence relations (3 hrs)
- Worst-case Analysis (3 hrs)
- Sorting (4.5 hrs)
- Median, Selection Problems: More on Divide-and-Conquer Algorithms (2.5 hrs)
- Hash Tables (2.5 hrs)
- Binary Search Trees, Red-Black Trees (4.5 hrs)
- Longest Common Subsequence: Introduction to Dynamic Programming (2.5 hrs)
- Graph Algorithms: Depth-first and breadth-first search, min. spanning trees, shortest path (9 hours)
- Disjoint Sets (union-find): Introduction to Amortized Analysis;
- String Matching (time permitting)
Grade Appealing
Your grades will be posted at the class website, available to you.
Whenever the grade for a particular work is available, we will post
an announcement.
You will have one week to challenge the grade in writing.
If you do not contact either the instructor or the TAs within a
week, there would be no change to your grade for that particular work.
This applies to all of your graded work.
It is your responsibility to keep the graded hardcopy of your work,
except the last test.
Policy on Tests
All homework assignments are due before the lecture on its due date.
No late assignment will be accepted.
Final is pre-scheduled by the University and will not be changed.
The dates of midterms will be announced in class one week before
the test. In general, there will be no makeup test.
Brief Summary of the University Policies on Cheating
Any incidence of cheating in this class will be severely dealt with.
This applies to homework assignments and tests.
The minimum penalty for cheating will be that the student will not
obtain any credit for that particular assignment
(This means that if in a test and/or assignment a student is found to have
cheated, he/she will obtain zero in that test and/or assignment).
Students are encouraged to discuss with others the materials covered in class.
However students should not discuss problems in assignments/tests.
One tends to get very suspicious if two identically wrong results show up in
the homework assignment and/or tests.
Last Updated: Aviral Shrivastava, 05/2010