Course Information: CS535 Fall 2023
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Course Information: CS535
FALL 2023
General Information
1. Books:
. (primary Text) Introduction to Algorithms: cormen, Leicerson, Rivest and stein (cLRs) , MIT press
. Algorithm Design and Analysis: Dexter kozen, springer-verlag
. Algorithm Design: kleinberg and Tardos, Addison-wesley.
. Algorithms by Dasgupta, papadimtriou and vazirani.
. combinatorial optimization: papadimitriou and steiglitz, Dover.
Additional Notes will be provided.
2. pRE-REQUIsITE: cs43O
students are expected to know elementary algorithms and data structures for searching and sorting, heaps Introductory applications of greedy, divide and conquer and dynamic programming techniques as well as Graph algorithms.
syllabus
The topics below are subject to change.
part 1: Design techniques and data structures advances :
1. Motivation for Algorithm Design- Minimum spanning Tree
2. Advanced schemes for selection
Binomial Heaps
Fibonacci heaps and applications in Minimum spanning Trees
3. Divide and conquer: advanced applications.
4. Greedy Method and Matroids
5. Dynamic programming- applications in shortest paths
6. Linear programming and Duality-applications in shortest paths.
7. Randomized algorithms and Data structures
part 2: speciic problems and techniques
1. Graph Algorithms Review (Bi-connectivity,strong-connectivity, planarity*)
2. Flows in Networks, Matching.
3. string Matching
4. Fast Fourier Transforms.
part 3: complexity and intractability
1. Lower Bounds*
2. Np-complete problems
3. Approximation Algorithms*
* represents advanced topics to be covered if time permits.
course Requirements
(subject to change in the irst week)
FoT SectionS otheT than the Section foT PhD StudentS:
Home-works： 4o%.
Exams ( Midterms (3o%) + Final(3o%))： The exams may include a take-home component. policies for the exams will be detailed along with the exam.
FoT PhD Section：
Home-works： 25%； project 1o%. Research a Topic and write report.
Exams (Midterms (3o%) + Final(35%))： The exams, except the inals, include a substantial take-home component. The inal exam will be 3 hours. policies for the exams will be detailed along with the exam.
Honesty pledge
while discussions are allowed all submitted work should be independent work. Any commonality will be considered as plagiarism. Sign a pledge, to be made available on the blackboard, stating that all home work, including take-home exams, will be your own and that you will cite any resources used (except the textbook and any class notes). This pledge must be turned in with the First assignment. violating the pledge typically results in stringent penalties.
Office Hours
professor kapoor, [email protected] Rm. SB 228, 4.oo-5.oo p.m. Mw or per appointment.
TA,s：yi zhang([email protected]), Li zhang ([email protected] ) , Harsh patel ([email protected])： Room oo4 SB.
O伍ce Hours： M,w (5-6 pm), F(2-4pm).
2023-09-09