Home |
Publications |
Teaching |
Service |
Lab |

ASU 101 |
CSE 230 |
CSE 310 |
CSE 325 |
CSE 420 |
CSE
591 PEC |
CSE
591 ARC |
Multi-core Programming |

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.

- 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

- 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.

- 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)

**Last Updated:** Aviral Shrivastava, 05/2010